算法与程序实践1（简单计算）

目 录

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：数字阶梯 ............................................................................................................................. 18 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，当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

输入样例： 3 3 3 10 50 24 20000

输出样例： No Yes Yes

参考程序1（zzg）： 循环版

#include int main() {

1

int fn2,fn1,fn,m,n,a,i,j; fn2=0; fn1=1; //freopen(\ //freopen(\ scanf(\ for(i=1;i<=m;i++) { scanf(\ if(n==1) { if(a<=fn1) printf(\ else printf(\ } else { for(j=2;j<=n;j++) { fn=fn2+fn1; fn2=fn1; fn1=fn; if(a<=fn) { printf(\ break; } } if(j>n) printf(\ } } return 1; }

递归版（zzg） #include int fib(int n) { if(n<2) return n==0?0:1;

2

else return fib(n-2)+fib(n-1); }

int main() { int m,n,a,i,j; scanf(\ for(i=1;i<=m;i++) { scanf(\ for(j=1;j<=n;j++) { if(a<=fib(j)) { printf(\ break; } } if(j>n) printf(\ } return 1; }

注意事项：

这题主要考察递归与非递归的用法，还有数值越界的情况。 1）测试数据可取一下 1 1和1 3试一下。 2）测试数据可以取一下 50 1000和1000 1000。程序中若考虑到值的越界就没问题或者考虑使用break也可以。

CS2：正整数解

求x2+y2=2000的正整数解，输出所有不同的解。

参考程序：

#include #include

int main() { int x,y,m; m=(int)sqrt(2000);

3

for(x=1;x<=m;x++) for(y=x;y<=m;y++) if(x*x+y*y==2000) printf(\ return 0; }

注意事项：

这题主要考察枚举的用法，还有求平方根（数学函数）的用法。

1） 要考虑x和y可调换，所以需要加上y>=x，这样就能保证不会出现重复的解

2） 考虑一下优化的问题for(y=x;y<=m;y++)可以优化为：for(y=m;y>=x;y--)，甚至还可以 int temp=(int)sqrt(2000-x*x) for(y=temp;y>=x;y--)

CS3：鸡兔同笼

（来源：poj.grids.cn 2750） 问题描述：

一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。已经知道了笼子里面脚的总数a，问笼子里面至少有多少只动物，至多有多少只动物。 输入：

第1 行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a (a < 32768) 。

输出：

n 行，每行输出对应一个输入。输出是两个正整数，第一个是 …… 此处隐藏：2609字，全部文档内容请下载后查看。喜欢就下载吧 ……