9-1

问题 计算Fibonacci数列前20个数值之和，其中Fibonacci数列有如下的迭代规律：

第一个元素：

第二个元素：

第三个元素：

……

第n个元素：

分析 根据Fibonacci数列的递推规律，必须已知第n-1项和第n-2项之后，才可以计算出第n项。可以同时计算第n－1项和第n项序列的值。所需数据与算法如下。

数据要求

问题中的常量：

无

问题的输入：

int f1=1 /*序列中第1项*/

int f2=1 /*序列中第2项*/

问题的输出：

unsigned long sum /*序列前20项之和*/

设计 初始算法

1． f1和f2初始化为1，并初始化sum的值为sum=0。

2． 计算第n-1项并求和，再计算第n项并求和。

3． 循环执行步骤2至求出前20项之和，输出sum。

算法细化

1． 初始化：

f1=1;

f2=1;

sum= f1+f2;

当n=1，n=2时f1=1，f2=1；因此前两项之和为sum=f1+f2。

2． 循环体的语句如下：

f1=f1+f2; /*计算第n-1项*/

sum+=f1;

f2=f2+f1; /*计算第n项*/

sum+=f2;

当n=3时f3=f1+f2。如果f3用f1表示，则f1=f1+f2；因此前三项之和为sum=sum+f1。

当n=4时f4=f3+f2。如果f3用f1表示，f4用f2表示，则f2=f2+f1。前四项之和为sum=sum+f2。

依次类推，可以求解出前ｎ项之和。

3． 由于循环次数已知，因此可以使用for语句。由于循环一次计算２项，因此循环9次可以计算18项数据的和，加上前两项之和，正好为前20项之和。循环条件为

for(i=1;i<10;i++)

{

……

}

流程图

实现 程序代码如下：

#include "stdio.h"

void main()

{

unsigned long f1,f2,sum; /*f1代表第n－2项，f2代表第n－1项，sum代表和*/

int i;

f1=1;f2=1; /*计算第一项，第二项*/

sum=f1+f2; /*计算第一项与第二项之和*/

for(i=1;i<10;i++) /*累加剩余的18项*/

{

f1=f1+f2; /*计算第n－1项*/

sum+=f1;

f2=f2+f1; /*计算第n项*/

sum+=f2;

}

printf("sum=%d",sum);

}

运行结果 sum=17710

测试 如果将数据的声明由数据类型unsigned long改为int，则程序仍然能得到正确的结果；如果再将循环条件改为i<20，即求序列前40项之和，则得到结果3127，显然该结果是一个错误的结果。该测试说明：要注意保存序列和变量的类型，一定要能够容纳最终结果，不要因为超出类型的表示范围而导致错误的结果。

9-2

问题 根据如下的公式计算PI，直到最后一项的绝对值小于

分析 解决此类问题可以进行如下的处理，假设PI=， =Y，则有Y*6=PI*PI，根据题目中公式则有。因此问题的转化为计算Y，求解出Y之后，就可以根据，求解PI。所需数据与算法如下。

数据要求

问题的输入：

unsigned long n; /*公式循环计算变量*/

double sum; /*公式求和变量*/

问题的输出：

double pi; /*根据公式计算出的值*/

设计 初始算法

1． 初始化n=1。

2． 计算序列第n项的值，如果该值大于等于，则执行下面循环：

sum+=；n加1；

3．结束循环，求解pi。

算法细化

1． 循环变量n的初值为1，循环条件，可以进一步转换为

。因此循环结构为：

for(n=1; n<1000; n++)

{

……

｝

2． 循环体为：

t=1.0/(n*n);

sum+=t;

3． 求解出sum之后，即可计算pi的值，在C程序中没有求根方的运算符，但是在其标准函数库中提供了数学函数sqrt函数，可以实现求根功能。

流程图

实现 程序代码如下：

#include "stdio.h"

#include "math.h"

void main()

{

unsigned long n;

double pi;

double sum=0;

double t;

for(n=1;n<1000;n++)

{

t=1.0/(n*n;

sum+=t;

}

pi=sqrt(6.0*sum);

printf("Pi=%f",pi);

}

运行结果 Pi=3.140637

测试 如果将循环条件改为n<2000，则结果为3.141115，更接近于。该测试说明该程序中循环变量取值范围越大，越能够接近正确结果。

9.3

问题 采用矩形法求定积分

分析 利用矩形法可以求定积分其原理如图（9-1）所示。求函数ｆ在（a,b）区间的定积分公式为：

图9-1 矩形法求定积分

所需数据与算法如下。

数据要求

问题的输入：

double a; /*积分区间下限*/

double b; /*积分区间上限*/

问题的输出：

double fx; /*积分结果*/

设计 初始算法

1． 初始化积分区间（a，b）。

2． 如果把积分区间划分为100个格，则h=fabs(a-b)/100；

3． 因为区间划分为100个格，因此循环过程如下：

for(i=0;i<100;i++)

{

fx=f (x+i*h+h/2);

… …

}

流程图

实现 程序代码如下：

#include "stdio.h"

#include "math.h"

double f (double x)

{

return sin(x);

}

double Jifen(double a,double b)

{

double h;

double fx;

double x;

int i;

double sum=0;

h=fabs(a-b)/100;

x=a;

for(i=0;i<100;i++)

{

fx=f (x+i*h+h/2);

sum=sum+fx;

}

return sum*h;

}

void main()

{

double a;

double b;

double fx;

a=0;

b=3.1415926;

fx=Jifen(a,b);

printf("Ji Fen Y=%f" ,fx);

}

运行结果 Ji Fen Y=2.000082

测试 如果将积分区间划分为1000个格，则循环条件改为i<1000，得到结果为2.00001。该测试说明积分区间划分越多，越能够接近正确结果。

9.4　

问题 从键盘读入一段文本，统计其中的英文字母、数字、空格和除此之外的其他字符个数。

分析 由于输入字符的个数不确定，需构建条件循环while((c=getchar())!=EOF)，其中EOF为符号常量，用于表示文本输入结束，在PC机上通过输入Ctrl+Z组合键来输入此字符。所需数据与算法如下。

数据要求

问题的输入：

char c; /*获取从键盘上输入的字符*/

问题的输出：

unsigned int nChar; /*文本中英文字母的个数*/

unsigned int nNum; /*文本中数字的个数*/

unsigned int nBlank; /*文本中空格的个数*/

unsigned int nOther; /*文本中其他字符的个数*/

设计 初始算法

1． 初始化变量nChar、nNum、nBlank、nOther为零

2． 从键盘输入文本，直到输入特殊的字符结束

3． 对文本中每一个字符，做循环判断并计数。

算法细化

1． unsigned int nChar=0,nNum=0,nBlank=0,nOther=0;

2． 循环统计从键盘输入的英文字母个数，算法如下：

while((c=getchar())!=EOF)

{

if((c>='a')&&(c<='z')||(c>='A')&&(c<='Z'))

nChar++;

……

｝

流程图

实现 程序代码如下：

#include "stdio.h"

void main()

{

unsigned int nChar=0,nNum=0,nBlank=0,nOther=0;

char c;

while((c=getchar())!=EOF)

{

if((c>='a')&&(c<='z')||(c>='A')&&(c<='Z'))

nChar++;

else

{

if((c>='0')&&(c<='9'))

nNum++;

else

{

if(c==' ')

nBlank++;

else

nOther++;

}

}

}

printf("Char=%d\tNum=%d\tBlank=%d\tOther=%d",nChar,nNum,nBlank,nOther);

}

运行结果

输入 #define PI 3.14^Z

输出 Char=8 Num=3 Blank=2 Other=2

9.14

问题 汉诺（Hanoi）塔问题：古代有一个梵塔，塔内有三个座A、B、C，A座上有64个盘子，盘子大小不等，大的在下，小的在上（如图）。有一个和尚想把这64个盘子从A座移到B座，但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘在上。在移动过程中可以利用B座，要求打印移动的步骤。

图9-5汉诺塔问题

分析 递归算法是计算机算法的重要内容，很多问题都可以使用递归方法解决。递归算法的特点是可以比较自然的反映解决问题的过程，并能够便于调试程序。对于某些问题（例如汉诺塔问题，树的遍历等问题），需要通过递归算法求解。所需数据与算法如下。

数据要求

问题的输入：

int n; /*盘子数*/

问题的输出：

char chSour; /*盘子所在源座*/

char chDest; /*盘子移动后的目标座*/

设计 初始算法

1． 输入盘子数n

2． 利用递归算法移动盘子

算法细化

这个问题在盘子比较多的情况下，很难直接写出移动步骤。我们可以先分析盘子比较少的情况。假定盘子从大向小依次为：盘子1，盘子2，...，盘子64。

如果只有一个盘子，则不需要利用B座，直接将盘子从A移动到C。

如果有2个盘子，可以先将盘子1上的盘子2移动到B；将盘子1移动到c；将盘子2移动到c。这说明了：可以借助B将2个盘子从A移动到C，当然，也可以借助C将2个盘子从A移动到B。

如果有3个盘子，那么根据2个盘子的结论，可以借助c将盘子1上的两个盘子从A移动到B；将盘子1从A移动到C，A变成空座；借助A座，将B上的两个盘子移动到C。这说明：可以借助一个空座，将3个盘子从一个座移动到另一个。

如果有4个盘子，那么首先借助空座C，将盘子1上的三个盘子从A移动到B；将盘子1移动到C，A变成空座；借助空座A，将B座上的三个盘子移动到C。

上述的思路可以一直扩展到64个盘子的情况：可以借助空座C将盘子1上的63个盘子从A移动到B；将盘子1移动到C，A变成空座；借助空座A，将B座上的63个盘子移动到C。

归纳成递归公式，可以写成：

其中，Hanoi函数的第一个参数表示盘子的数量，第二个参数表示源座，第三个参数表示借用的座，第四个参数代表目的座。比如Hanoi(n-1,A,C,B)表示借助C座把n-1个盘子从A座移动到B座。

Move函数的第一个参数表示源座，第二个参数代表目的座。Move函数的功能是将源座最上面的一个盘子移动到目的座上。

流程图

实现 程序代码如下：

void Move(char chSour, char chDest)

{

/*打印移动步骤*/

printf("\nMove the top plate of %c to %c",chSour, chDest);

}

Hanoi(int n, char chA, char chB, char chC)

{

/*检查当前的盘子数量是否为1*/

if(n==1) /*盘子数量为1，打印结果后，不再继续进行递归*/

Move(chA,chC);

else/*盘子数量大于1，继续进行递归过程*/

{

Hanoi(n-1,chA,chC,chB);

Move(chA,chC);

Hanoi(n-1,chB,chA,chC);

}

}

main()

{

int n;

/*输入盘子的数量*/

printf("\nPlease input number of the plates: ");

scanf("%d",&n);

printf("\nMoving %d plates from A to C:",n);

/*调用函数计算，并打印输出结果*/

Hanoi(n,'A','B','C');

}

运行结果

如果n为4，程序输出结果为：

Moving 4 plates from A to C:

Move the top plate of A to B

Move the top plate of A to C

Move the top plate of B to C

Move the top plate of A to B

Move the top plate of C to A

Move the top plate of C to B

Move the top plate of A to B

Move the top plate of A to C

Move the top plate of B to C

Move the top plate of B to A

Move the top plate of C to A

Move the top plate of B to C

Move the top plate of A to B

Move the top plate of A to C

Move the top plate of B to C

测试 当输入的盘子数过多时，如64，程序运行很慢。递归过程实现的程序结构清晰，程序简单，但执行速度慢。

计算Fibonacci数列前20个数值之和