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

《算法与程序实践1(简单计算)》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实用文案目录CS1：斐波那契数列1CS2：正整数解3CS3：鸡兔同笼4CS4：棋盘上的距离5CS5：校门外的树木7CS6：填词8CS7：装箱问题9CS8：求平均年龄10CS9：数字求和11CS10：两倍11CS11：肿瘤面积12CS12：肿瘤检测12CS13：垂直直方图13CS14：谁拿了最多的奖学金14CS15：简单密码15CS16：化验诊断16CS17：密码17CS18：数字阶梯17CS19：假票18CS20：纸牌（Deck）19标准文档实用文案《算法与程序实践》习题解答1——简单计算这一章的主要目的是通过编写一些简单的计算题，

2、熟悉C/C++语言的基本语法。基本思想：解决简单的计算问题的基本过程包括将一个用自然语言描述的实际问题抽象成一个计算问题，给出计算过程，继而编程实现计算过程，并将计算结果还原成对原来问题的解答。这里首要的是读懂问题，搞清输入和输出的数据的含义及给出的格式，并且通过输入输出样例验证自己的理解是否正确。课堂练习：CS1、CS2、CS3课堂讲解：CS4（CS5）A类（满分80）课堂练习：CS8、CS9、CS10B类（满分100）课堂上机：CS11、CS20CS1：斐波那契数列问题描述：已知斐波那契数列第n项的计算公式如下。在计算时有两种算

3、法：递归和非递归，请分别给出这两种算法。当n=0时，Fib(n)=0，当n=1时，Fib(n)=1，当n>1时，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）：循环版#includeintmain(){intfn2

4、,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");elseprintf("No");}else{for(j=2;j<=n;j++){fn=fn2+fn1;fn2=fn1;fn1=fn;if(a<=fn){pr

5、intf("Yes");break;}}if(j>n)printf("No");}}return1;}递归版（zzg）#includeintfib(intn){if(n<2)returnn==0?0:1;else标准文档实用文案returnfib(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("Y

6、es");break;}}if(j>n)printf("No");}return1;}注意事项：这题主要考察递归与非递归的用法，还有数值越界的情况。1）测试数据可取一下11和13试一下。2）测试数据可以取一下501000和10001000。程序中若考虑到值的越界就没问题或者考虑使用break也可以。CS2：正整数解求x2+y2=2000的正整数解，输出所有不同的解。参考程序：#include#includeintmain(){intx,y,m;m=(int)sqrt(2000);for(x=

7、1;x<=m;x++)标准文档实用文案for(y=x;y<=m;y++)if(xx+yy==2000)printf("%d%d+%d%d=2000",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-xx)for(y=temp;y>=x;y--)C

8、S3：鸡兔同笼（来源：poj.grids.cn2750）问题描述：一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。已经知道了笼子里面脚的总数a，问笼子里面至少有多少只动物，至多有多少只动物。输入：第1行是测试数据的组数