算法与程序实践1(简单计算)

目录CS1：斐波那契数列.........................................................................................................................1CS2：正整数解.................................................................................................................................3CS3：鸡兔同笼.................................................................................................................................4CS4：棋盘上的距离.........................................................................................................................5CS5：校门外的树木.........................................................................................................................7CS6：填词.........................................................................................................................................8CS7：装箱问题.................................................................................................................................9CS8：求平均年龄...........................................................................................................................10CS9：数字求和...............................................................................................................................11CS10：两倍.....................................................................................................................................11CS11：肿瘤面积.............................................................................................................................12CS12：肿瘤检测.............................................................................................................................12CS13：垂直直方图.........................................................................................................................13CS14：谁拿了最多的奖学金.........................................................................................................14CS15：简单密码.............................................................................................................................15CS16：化验诊断.............................................................................................................................16CS17：密码.....................................................................................................................................17CS18：数字阶梯.............................................................................................................................18CS19：假票.....................................................................................................................................18CS20：纸牌（Deck）.....................................................................................................................191《算法与程序实践》习题解答1——简单计算这一章的主要目的是通过编写一些简单的计算题，熟悉C/C++语言的基本语法。基本思想：解决简单的计算问题的基本过程包括将一个用自然语言描述的实际问题抽象成一个计算问题，给出计算过程，继而编程实现计算过程，并将计算结果还原成对原来问题的解答。这里首要的是读懂问题，搞清输入和输出的数据的含义及给出的格式，并且通过输入输出样例验证自己的理解是否正确。课堂练习：CS1、CS2、CS3课堂讲解：CS4课后练习：CS4、CS5、CS8、CS9、CS10课堂上机：CS11、CS18、CS19课后题：CS6、CS7、CS12、CS13、CS15CS1：斐波那契数列问题描述：已知斐波那契数列第n项的计算公式如下。在计算时有两种算法：递归和非递归，请分别给出这两种算法。当n=0时，Fib(n)=0，当n=1时，Fib(n)=1，当n1时，Fib(n)=Fib(n-1)+Fib(n-2)输入：第一行是测试数据的组数m，后面跟着m行输入。每行包括一个项数n和一个正整数a。（m，n，a均大于0，且均小于10000000）输出：输出包含m行，每行对应一个输入，若a不大于Fib(n)，则输出Yes，否则输出No输入样例：33310502420000输出样例：NoYesYes参考程序1（zzg）：循环版#includestdio.hintmain(){2intfn2,fn1,fn,m,n,a,i,j;fn2=0;fn1=1;//freopen(in.txt,r,stdin);//freopen(out.txt,w,stdout);scanf(%d,&m);for(i=1;i=m;i++){scanf(%d%d,&n,&a);if(n==1){if(a=fn1)printf(Yes\n);elseprintf(No\n);}else{for(j=2;j=n;j++){fn=fn2+fn1;fn2=fn1;fn1=fn;if(a=fn){printf(Yes\n);break;}}if(jn)printf(No\n);}}return1;}递归版（zzg）#includestdio.hintfib(intn){if(n2)returnn==0?0:1;3elsereturnfib(n-2)+fib(n-1);}intmain(){intm,n,a,i,j;scanf(%d,&m);for(i=1;i=m;i++){scanf(%d%d,&n,&a);for(j=1;j=n;j++){if(a=fib(j)){printf(Yes\n);break;}}if(jn)printf(No\n);}return1;}注意事项：这题主要考察递归与非递归的用法，还有数值越界的情况。1）测试数据可取一下11和13试一下。2）测试数据可以取一下501000和10001000。程序中若考虑到值的越界就没问题或者考虑使用break也可以。CS2：正整数解求x2+y2=2000的正整数解，输出所有不同的解。参考程序：#includestdio.h#includemath.hintmain(){intx,y,m;m=(int)sqrt(2000);4for(x=1;x=m;x++)for(y=x;y=m;y++)if(x*x+y*y==2000)printf(%d*%d+%d*%d=2000\n,x,x,y,y);return0;}注意事项：这题主要考察枚举的用法，还有求平方根（数学函数）的用法。1）要考虑x和y可调换，所以需要加上y=x，这样就能保证不会出现重复的解2）考虑一下优化的问题for(y=x;y=m;y++)可以优化为：for(y=m;y=x;y--)，甚至还可以inttemp=(int)sqrt(2000-x*x)for(y=temp;y=x;y--)CS3：鸡兔同笼（来源：poj.grids.cn2750）问题描述：一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。已经知道了笼子里面脚的总数a，问笼子里面至少有多少只动物，至多有多少只动物。输入：第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a(a32768)。输出：n行，每行输出对应一个输入。输出是两个正整数，第一个是最少的动物数，第二个是最多的动物数，两个正整数用空格分开。如果没有满足要求的情况出现，则输出2个0。输入样例：2320输出样例：00510参考程序：#includestdio.hintmain(){intnCase,nFeet,i;scanf(%d,&nCase);5for(i=1;i=nCase;i++){scanf(%d,&nFeet);if(nFeet%2!=0)printf(00\n);elseif(nFeet%4!=0)printf(%d%d\n,nFeet/4+1,nFeet/2);elseprintf(%d%d\n,nFeet/4,nFeet/2);}return0;}解题思路：这个问题可以描述成任给一个整数N，如果N是奇数，输出00，否则如果N是4的倍数，输出N/4，N/2，如果N不是4的倍数，输出N/4+1，N/2。这是一个一般的计算题，只要实现相应的判断和输出代码就可以了。题目中说明了输入整数在一个比较小的范围内，所以只需要考虑整数运算就可以了。注意事项：这里考察数学计算，出错有一下几种情况：1