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

目 录 CS1：斐波那契数列 1 CS2：正整数解 3 CS3：鸡兔同笼 4 CS4：棋盘上的距离 5 CS5：校门外的树木 7 CS6：填词 8 CS7：装箱问题 9 CS8：求平均年龄 10 CS9：数字求和 11 CS10：两倍 11 CS11：肿瘤面积 12 CS12：肿瘤检测 12 CS13：垂直直方图 13 CS14：谁拿了最多的奖学金 14 CS15：简单密码 15 CS16：化验诊断 16 CS17：密码 17 CS18：数字阶梯 17 CS19：假票 18 CS20：纸牌（Deck） 19 《算法与程序实践》习 题 解 答1——简单计算 这一章的主要目的是通过编写一些简单的计算题，熟悉C/C++语言的基本语法。 基本思想：解决简单的计算问题的基本过程包括将一个用自然语言描述的实际问题抽象成一个计算问题，给出计算过程，继而编程实现计算过程，并将计算结果还原成对原来问题的解答。这里首要的是读懂问题，搞清输入和输出的数据的含义及给出的格式，并且通过输入输出样例验证自己的理解是否正确。 课堂练习：CS1、CS2、CS3 课堂讲解：CS4 课后练习：CS4、CS5、CS8、CS9、CS10 课堂上机：CS11、CS18、CS19 课后题：CS6、CS7、CS12、CS13、CS15 CS1：斐波那契数列 问题描述： 已知斐波那契数列第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，且均小 输出： 输出包含m行，每行对应一个输入，若a不大于Fib(n)，则输出Yes，否则输出No 输入样例： 3 3 3 10 50 24 20000 输出样例： No Yes Yes 参考程序1（zzg）： 循环版 #includestdio.h int main() { int fn2,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); else printf(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); } } return 1; } 递归版（zzg） #includestdio.h int fib(int n) { if(n2) return n==0?0:1; else return fib(n-2)+fib(n-1); } int main() { int m,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); } return 1; } 注意事项： 这题主要考察递归与非递归的用法，还有数值越界的情况。 1）测试数据可取一下 1 1和1 3试一下。 2）测试数据可以取一下 50 1000和1000 1000。程序中若考虑到值的越界就没问题或者考虑使用break也可以。 CS2：正整数解 求x2+y2=2000的正整数解，输出所有不同的解。 参考程序： #includestdio.h #includemath.h int main() { int x,y,m; m=(int)sqrt(2000); for(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); return 0;