博文
100. 数字移动(2005-09-10 15:16:00)
摘要：100. 数字移动
在图中的九个点上,空出中间的点,其余的点上任意填入数字1到8;1的位置固定不动,然后移动其余的数字,使1到8顺时针从小到大排列.移动的规律是:只能将数字沿线移向空白的点.
请编程显示数字移动过程。
*题目分析与算法设计
分析题目中的条件,要求利用中间的空白格将数字顺时针方向排列,且排列过程中只能借空白的点来移动数字.问题的实质就是将矩阵外面的8个格看成一个环,8个数字在环内进行排序,同于受题目要求的限制"只能将数字沿线移向空白的点",所以要利用中间的空格进行排序,这样要求的排序算法与众不同.
观察中间的点,它是唯一一个与其它8个点有连线的点,即它是中心点.中心点的活动的空间最大,它可以向8个方向移动,充分利用中心点这个特性是算法设计成功与否的关键.
在找到1所在的位置后,其余各个数字的正确位置就是固定的.我们可以按照下列算法从数字2开始,一个一个地来调整各个数字的位置.
*确定数字i应处的位置;
*从数字i应处的位置开始,向后查找数字i现在的位置;
*若数字i现在位置不正确,则将数字i从现在的位置(沿连线)移向中间的空格,而将原有位置空出;依次将现有空格前的所有元素向后移动;直到将i应处的位置空出,把它移入再次空出中间的格.
从数字2开始使用以上过程,就可以完成全部数字的移动排序.
编程时要将矩阵的外边八个格看成一个环,且环的首元素是不定的,如果算法设计得不好,程序中就要花很多精力来处理环中元素的前后顺序问题.将题目中的3X3矩阵用一个一维数组表示,中间的元素(第四号)刚好为空格,设计另一个指针数组,专门记录指针外八个格构成环时的连接关系.指针数组的每个元素依次记录环中数字在原来数组中对应的元素下标.这样通过指针数组将原来矩阵中复杂的环型关系表示成了简单的线性关系,从而大大地简化了程序设计.
*程序与程序注释
#include<stdio.h>
int a[]={0,1,2,5,8,7,6,3}; /*指针数组.依次存入矩阵中构成环的元素下标*/
int b[9]; /*表示3X3矩阵,b[4]为空格*/
int c[9]; /*确定1所在的位置后,......
99.超长正整数的加法(2005-09-10 15:16:00)
摘要：99.超长正整数的加法
请设计一个算法来完成两个超长正整数的加法。
*问题分析与算法设计
首先要设计一种数据结构来表示一个超长的正整数，然后才能够设计算法。
首先我们采用一个带有表头结点的环形链来表示一个非负的超大整数，如果从低位开始为每 个数字编号，则第一位到第四位、第五位到第八位...的每四位组成的数字，依次放在链表的第一个、第二个、...结点中，不足4位的最高位存放在链表的最后一个结点中，表头结点的值规定为-1。例如：
大整数“587890987654321”可用如下的带表头结点head的链表表示：
按照此数据结构，可以从两个表头结点开始，顺序依次对应相加，求出所需要的进位后代入下面的运算。具体的实现算法请见程序中的注释。
*程序与程序注释
#include<stdio.h>
#include<stdlib.h>
#define HUNTHOU 10000
typedef struct node{ int data;
struct node *next;
}NODE; /*定义链表结构*/
NODE *insert_after(NODE *u,int num); /*在u结点后插入一个新的NODE，其值为num*/
NODE *addint(NODE *p,NODE *q); /*完成加法操作返回指向*p+*q结果的指针*/
void printint(NODE *s);
NODE *inputint(void);
void main()
{
NODE *s1,*s2,*s;
NODE *inputint(), *addint(), *insert_after();
printf("Enter S1= ");
s1=inputint(); /*输入被加数*/
printf("Enter S2= ");
s2=inputint(); /*输入加数*/
printf(" S1="); printint(s1)......
98. 八皇后问题(2005-09-10 15:16:00)
摘要：98. 八皇后问题
在一个8×8国际象棋盘上，有8个皇后，每个皇后占一格；要求皇后间不会出现相互“攻击”的现象，即不能有两个皇后处在同一行、同一列或同一对角线上。问共有多少种不同的方法。
*问题分析与算法设计
这是一个古老的具有代表性的问题，用计算机求解时的算法也很多，这里仅介绍一种。
采用一维数组来进行处理。数组的下标i表示棋盘上的第i列，a[i]的值表示皇后在第i列所放的位置。如：a[1]=5，表示在棋盘的第一例的第五行放一个皇后。
程序中首先假定a[1]=1，表示第一个皇后放在棋盘的第一列的第一行的位置上，然后试探第二列中皇后可能的位置，找到合适的位置后，再处理后续的各列，这样通过各列的反复试探，可以最终找出皇后的全部摆放方法。
程序采用回溯法，算法的细节参看程序。
*程序与程序注释
#include<stdio.h>
#define NUM 8 /*定义数组的大小*/
int a[NUM+1];
void main()
{
int i,k,flag,not_finish=1,count=0;
i=1; /*正在处理的元素下标，表示前i-1个元素已符合要求，正在处理第i个元素*/
a[1]=1; /*为数组的第一个元素赋初值*/
printf("The possible configuration of 8 queens are:\n");
while(not_finish) /*not_finish=1:处理尚未结束*/
{
while(not_finish&&i<=NUM) /*处理尚未结束且还没处理到第NUM个元素*/
{
for(flag=1,k=1;flag&&k<i;k++) /*判断是否有多个皇后在同一行*/
if(a[k]==a[i])flag=0;
for(k=1;flag&&k<i;k++) /*判断是否有多个皇后在同一对角线*/
if((a[i]==a[k]-(k-i))||(a[i]==a[k]+(k-i))) flag=0;
if(!flag......
97.满足特异条件的数列(2005-09-10 15:16:00)
摘要：97.满足特异条件的数列
输入m和n(20>=m>=n>0)求出满足以下方程的正整数数列 i1,i2,...,in，使得：i1+i1+...+in=m，且i1>=i2...>=in。例如：
当n=4, m=8时，将得到如下5 个数列：
5 1 1 1 4 2 1 1 3 3 1 1 3 2 2 1 2 2 2 2
*问题分析与算法设计
可将原题抽象为：将M分解为N个整数，且N个整数的和为M，i1>=i2>=...>=in。分解整数的方法很低多，由于题目中有"i1>=i2>=.....>=in，提示我们可先确定最右边in元素的值为1，然后按照条件使前一个元素的值一定大于等于当前元素的值，不断地向前推就可以解决问题。下面的程序允许用户选定M和N，输出满足条件的所有数列。
*程序与程序注释
#include<stdio.h>
#define NUM 10 /*允许分解的最大元素数量*/
int i[NUM]; /*记录分解出的数值的数组*/
void main()
{
int sum,n,total,k,flag,count=0;
printf("Please enter requried terms(<=10):");
scanf("%d",&n);
printf(" their sum:");
scanf("%d",&total);
sum=0; /*当前从后向前k个元素的和*/
k=n; /*从后向前正在处理的元素下标*/
i[n]=1; /*将最后一个元素的值置为1作为初始值*/
printf("There are following possible series:\n");
while(1)
{
if(sum+i[k]<total) /*若后k位的和小于指定的total*/
if(k<=1) /*若正要处理的是第一个元素*/
{i[1]=tota......
96.选美比赛(2005-09-10 15:16:00)
摘要：96.选美比赛
在选美大奖赛的半决胜赛现场，有一批选手参加比赛，比赛的规则是最后得分越高，名次越低。当半决决赛结束时，要在现场按照选手的出场顺序宣布最后得分和最后名次，获得相同分数的选手具有相同的名次，名次连续编号，不用考虑同名次的选手人数。例如：
选手序号： 1，2，3，4，5，6，7
选手得分： 5，3，4，7，3，5，6
则输出名次为： 3，1，2，5，1，3，4
请编程帮助大奖赛组委会完成半决赛的评分和排名工作。
*问题分析与算法设计
问题用程序设计语言加以表达的话，即为：将数组A中的整数从小到大进行连续编号，要求不改变数组中元素的顺序，且相同的整数要具有相同的编号。
普通的排序方法均要改变数组元素原来的顺序，显然不能满足要求。为此，引入一个专门存放名次的数组，再采用通常的算法：在尚未排出名次的元素中找出最小值，并对具有相同值的元素进行处理，重复这一过程，直到全部元素排好为止。
*程序与程序注释
#include<stdio.h>
#define NUM 7 /*定义要处理的人数*/
int a[NUM+1]={0,5,3,4,7,3,5,6}; /*为简单直接定义选手的分数*/
int m[NUM+1],l[NUM+1]; /*m:已编名次的标记数组 l:记录同名次元素的下标*/
void main()
{
int i,smallest,num,k,j;
num=1; /*名次*/
for(i=1;i<=NUM;i++) /*控制扫描整个数组，每次处理一个名次*/
if(m[i]==0) /*若尚未进行名次处理(即找到第一个尚未处理的元素)*/
{
smallest=a[i]; /*取第一个未处理的元素作为当前的最小值*/
k=1; /*数组l的下标，同名次的人数*/
l[k]=i; /*记录分值为smallest的同名次元素的下标*/
for(j=i+1;j<=NUM;j++) /*从下一个元素开始对余下的元素进行处理*/
if(m[j]==0) /*若为尚未进行处理的元素*/
if(a[j]<smallest) /*分......
95.将阿拉伯数字转换为罗马数字(2005-09-10 15:16:00)
摘要：95.将阿拉伯数字转换为罗马数字
将大于0小于1000的阿拉伯数字转换为罗马数字。阿拉伯数字与罗马数字的对应关系如下：
1 2 3 4 5 ……
I II III IV V ……
*问题分析与算法设计
题目中给出了阿拉伯数字与罗马数字的对应关系，题中的数字转换实际上就是查表翻译。即将整数的百、十、个位依次从整数中分解出来，查找表中相应的行后输出对应的字符。
*程序与程序设计
#include<stdio.h>
void main()
{
static char *a[][10]={"","I","II","III","IV","V","VI","VII","VIII","IX"
"","X","XX","XXX","XL","L","LX","LXX","LXXX","XCC",
"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"
}; /*建立对照表*/
int n,t,i,m;
printf("Please enter number:");
scanf("%d",&n); /*输入整数*/
printf("%d=",n);
for(m=0,i=1000;m<3;m++,i/=10)
{
t=(n%i)/(i/10); /*从高位向低位依次取各位的数字*/
printf(&quo......
94.兎子产子(2005-09-10 15:15:00)
摘要：94.兎子产子
从前有一对长寿兎子，它们每一个月生一对兎子，新生的小兎子两个月就长大了，在第二个月的月底开始生它们的下一代小兎子，这样一代一代生下去，求解兎子增长数量的数列。
*问题分析与算法设计
问题可以抽象成下列数学公式：
Un=Un-1+Un-2
其中：
n是项数(n>=3)。它就是著名的菲波那奇数列，该数列的前几为：1，1，2，3，5，8，13，21...
菲波那奇数列在程序中可以用多种方法进行处理。按照其通项递推公式利用最基本的循环控制就可以实现题目的要求。
*程序与程序注释
#include<stdio.h>
void main()
{
int n,i,un1,un2,un;
for(n=2;n<3;)
{
printf("Please enter required number of generation:");
scanf("%d",&n);
if(n<3) printf("\n Enter error!\n"); /*控制输入正确的N值*/
}
un=un2=1;
printf("The repid increase of rabbits in first %d generation is as felow:\n",n);
printf("l\tl\t");
for(i=3;i<=n;i++)
{
un1=un2;
un2=un;
un=un1+un2; /*利用通项公式求解N项的值*/
printf(i%10?"%d\t":"%d\n",un);
}
printf("\n");
}
*运行结果
Please enter required number of generation: 20
The repid increase of rabbits in first 20 gene......
93.汉诺塔(2005-09-10 15:15:00)
摘要：93.汉诺塔
约19世纪末，在欧州的商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到右边的杆上，条件是一次只能移动一个盘，且不允许大盘放在小盘的上面。
*问题分析与算法设计
这是一个著名的问题，几乎所有的教材上都有这个问题。由于条件是一次只能移动一个盘，且不允许大盘放在小盘上面，所以64个盘的移动次数是：
18，446，744，073，709，551，615
这是一个天文数字，若每一微秒可能计算(并不输出)一次移动，那么也需要几乎一百万年。我们仅能找出问题的解决方法并解决较小N值时的汉诺塔，但很难用计算机解决64层的汉诺塔。
分析问题，找出移动盘子的正确算法。
首先考虑a杆下面的盘子而非杆上最上面的盘子，于是任务变成了：
*将上面的63个盘子移到b杆上；
*将a杆上剩下的盘子移到c杆上；
*将b杆上的全部盘子移到c杆上。
将这个过程继续下去，就是要先完成移动63个盘子、62个盘子、61个盘子....的工作。
为了更清楚地描述算法，可以定义一个函数movedisc(n,a,b,c)。该函数的功能是：将N个盘子从A杆上借助C杆移动到B杆上。这样移动N个盘子的工作就可以按照以下过程进行：
1) movedisc(n-1,a,c,b);
2) 将一个盘子从a移动到b上；
3) movedisc(n-1,c,b,a)；
重复以上过程，直到将全部的盘子移动到位时为止。
*程序与程序注释
#include<stdio.h>
void movedisc(unsigned n,char fromneedle,char toneedle,char usingneedle);
int i=0;
void main()
{
unsigned n;
printf("please enter the number of disc:");
scanf("%d",&n); /*输入N值*/
printf("\tneedle:\ta\t b......
92.人机猜数游戏(2)(2005-09-10 15:15:00)
摘要：92.人机猜数游戏(2)
将以上游戏双方倒一下，请人想一个四位的整数，计算机来猜，人给计算机提示信息，最终看计算机用几次猜出一个人“想”的数。请编程实现。
*问题分析与算法设计
解决这类问题时，计算机的思考过程不可能象人一样具完备的推理能力，关键在于要将推理和判断的过程变成一种机械的过程，找出相应的规则，否则计算机难以完成推理工作。
基于对问题的分析和理解，将问题进行简化，求解分为两个步聚来完成：首先确定四位数字的组成，然后再确定四位数字的排列顺序。可以列出如下规则：
1)分别显示四个1，四个2，......，四个0，确定四位数字的组成。
2)依次产生四位数字的全部排列(依次两两交换全部数字的位置)。
3)根据人输入的正确数字及正确位置的数目，进行分别处理：
(注意此时不出现输入的情况，因为在四个数字已经确定的情况下，若有3个位置正确，则第四个数字的位置必然也是正确的)
若输入4：游戏结束。
判断本次输入与上次输入的差值
若差为2：说明前一次输入的一定为0，本次输入的为2，本次交换的两个数字的位置是正确的，只要交换另外两个没有交换过的数字即可结束游戏。
若差为-2：说明前一次输入的一定为2，本次的一定为0。说明刚交换过的两个数字的位置是错误的，只要将交换的两个数字位置还原，并交换另外两个没有交换过的数字即可结束游戏。
否则：若本次输入的正确位置数<=上次的正确位置数
则恢复上次四位数字的排列，控制转3)
否则：将本次输入的正确位置数作为“上次输入的正确位置数”，控制转3)。
*程序与程序注释
#include<stdio.h>
#include<stdlib.h>
void bhdy(int s,int b);
void prt();
int a[4],flag,count;
void main()
{
int b1,b2,i,j,k=0,p,c;
printf("Game guess your number in mind is # # # #.\n");
for(i=1;i<10&&k&......
91.人机猜数游戏(2005-09-10 15:19:00)
摘要：91.人机猜数游戏
由计算机“想”一个四位数，请人猜这个四位数是多少。人输入四位数字后，计算机首先判断这四位数字中有几位是猜对了，并且在对的数字中又有几位位置也是对的，将结果显示出来，给人以提示，请人再猜，直到人猜出计算机所想的四位数是多少为止。
例如：计算机“想”了一个“1234”请人猜，可能的提示如下：
人猜的整数 计算机判断有几个数字正确 有几个位置正确
1122 2 1
3344 2 1
3312 3 0
4123 4 0
1243 4 2
1234 4 4
游戏结束
请编程实现该游戏。游戏结束时，显示人猜一个数用了几次。
*问题分析与算法设计
问题本身清楚明了。判断相同位置上的数字是否相同不需要特殊的算法。只要截取相同位置上的数字进行比较即可。但在判断几位数字正确时，则应当注意：计算机所想的是“1123”，而人所猜的是“1576”，则正确的数字只有1位。
程序中截取计算机所想的数的每位数字与人所猜的数字按位比较。若有两位数字相同，则要记信所猜中数字的位置，使该位数字只能与一位对应的数字“相同”。当截取下一位数字进行比较时，就不应再与上述位置上的数字进行比较，以避免所猜的数中的一位与对应数中多位数字“相同”的错误情况。
*程序与程序注释
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
void main()
{
int stime,a,z,t,i,c,m,g,s,j,k,l[4]; /*j:数字正确的位数 k:位置正确的位数*/
long ltime;
ltime=time(NULL); /*l:数字相同时，人所猜中数字的正确位置*/
stime=(unsigned int)ltime/2;
srand(stime);
z=random(9999); /*计算机想一个随机数*/
printf("I have a number with 4 digits in mind,please guess.\n");
for(c=1;;......