10.txt

CC++语言程序百例精解 非常经典的C

94.兎子产子

 

从前有一对长寿兎子，它们每一个月生一对兎子，新生的小兎子两个月就长大了，在第二个月的月底开始生它们的下一代小兎子，这样一代一代生下去，求解兎子增长数量的数列。

*问题分析与算法设计
问题可以抽象成下列数学公式：
Un=Un-1+Un-2
其中：
n是项数(n>=3)。它就是著名的菲波那奇数列，该数列的前几为：1，1，2，3，5，8，13，21…
菲波那奇数列在程序中可以用多种方法进行处理。按照其通项递推公式利用最基本的循环控制就可以实现题目的要求。

*程序说明与注释
#include<stdio.h>
int 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 generation is as felow:
1 1 2 3 5 8 13 21 34 55
89 144 233 377 610 987 1597 2584 4181 6765

 

95.将阿拉伯数字转换为罗马数字

将大于0小于1000的阿拉伯数字转换为罗马数字。阿拉伯数字与罗马数字的对应关系如下：
1 2 3 4 5 ……
I II III IV V ……

*问题分析与算法设计
题目中给出了阿拉伯数字与罗马数字的对应关系，题中的数字转换实际上就是查表翻译。即将整数的百、十、个位依次从整数中分解出来，查找表中相应的行后输出对应的字符。
*程序与程序设计
#include<stdio.h>
int 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("%s",a[2-m][t]); /*通过对照表翻译输出*/
}
printf("\n");
}

*运行结果
1. Please enter number:863
863=DCCCLXIII
2. Please enter number: 256
256=CCLVI
3. Please enter number:355
355=CCCLV
4. Please enter number:522
522=DXXII
5. Please enter number:15
15=XV

*思考题
输入正整数N，产生对应的英文数字符串并输出，例如：
1 ONE 2 TWO 3 THREE
10 TEN 11 ELEVEN
135 ONE HUNDRED THIRTY FIVE

 

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:记录同名次元素的下标*/
int 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) /*分数小于当前最小值*/
{
smallest=a[j]; /*则重新设置当覵最小值*/
k=0; /*重新设置同名次人数*/
l[++k]=j; /*重新记录同名次元素下标*/
}
else if(a[j]==smallest) /*若与当前最低分相同*/
l[++k]=j; /*记录同名次的元素下标*/
for(j=1;j<=k;j++) /*对同名次的元素进行名次处理*/
m[l[j>=num;
num++; /*名次加1*/
i=0; /*控制重新开始，找下一个没排名次的元素*/
}
printf("Player-No score Rank\n");
for(j=1;j<=NUM;j++) /*控制输出*/
printf(" %3d %4d %4d\n",j,a[j],m[j]);
}

*运行结果
Player-No Score Rank
1 5 3
2 3 1
3 4 2
5 7 5
5 3 1
3 5 3
7 6 4

*思考题
若将原题中的“名次连续编号，不用考虑同名次的选手人数”，改为”根据同名次的选手人数对选手的名次进行编号“，那么应该怎样修改程序。

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]; /*记录分解出的数值的数组*/
int 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]=total-sum;flag=1;} /*则计算第一个元素的并置标记*/
else{
sum+=i[k–];
i[k]=i[k+1]; /*置第k位的值后k-1*/
continue; /*继续向前处理其它元素*/
}
else if(sum+i[k]>total||k!=1) /*若和已超过total或不是第一个元素*/
{ sum-=i[++k]; flag=0;} /*k向后回退一个元素*/
else flag=1; /*sum+i[k]=total&&k=1 则设置flag标记*/
if(flag)
{
printf("[%d]:",++count);
for(flag=1;flag<=n;++flag)
printf("%d",i[flag]);
printf("\n");
}
if(++k>n) /*k向后回退一个元素后判断是否已退出最后一个元素*/
break;
sum-=i[k];
i[k]++; /*试验下一个分解*/
}
}

*运行结果
Please enter requried terms(<=10):4
their sum:8
There are following possible series:
[1]: 5111
[2]: 4211
[3]: 3311
[4]: 3221
[5]: 2222

 

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];
int 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++) /*判断是否有多个皇后在同一对角线*/