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

} if(j>n)
printf("No\n"); } } return 1; }
递归版（zzg） #include<stdio.h> int fib(int n) {
4
if(n<2) return n==0?0:1;
else return fib(n-2)+fib(n-1);
}
int main() {
输出： 输出包含 m 行，每行对应一个输入，若 a 不大于 Fib(n)，则输出 Yes，否则输出 No
输入样例： 3 33 10 50 24 20000
输出样例： Noபைடு நூலகம்Yes Yes
参考程序 1（zzg）： 循环版 #include<stdio.h> int main() {
2
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++)
3
{ fn=fn2+fn1; fn2=fn1; fn1=fn; if(a<=fn) { printf("Yes\n"); break; }
} return 1; }
注意事项： 这题主要考察递归与非递归的用法，还有数值越界的情况。 1）测试数据可取一下 1 1 和 1 3 试一下。 2）测试数据可以取一下 50 1000 和 1000 1000。程序中若考虑到 值的越界就没问题或者考虑使用 break 也可以。
CS2：正整数解
求 x2+y2=2000 的正整数解，输出所有不同的解。
CS1：斐波那契数列
问题描述： 已知斐波那契数列第 n 项的计算公式如下。在计算时有两种算法： 递归和非递归，请分别给出这两种算法。 当 n=0 时 ， Fib(n)=0， 当 n=1 时 ， Fib(n)=1， 当 n>1 时 ， Fib(n)= Fib(n-1)+ Fib(n-2)
输入： 1
第一行是测试数据的组数 m，后面跟着 m 行输入。每行包括一个 项数 n 和一个正整数 a。（m，n，a 均大于 0，且均小于 10000000）
printf("0 0\n"); else if(nFeet%4 != 0)
printf("%d %d\n",nFeet/4+1,nFeet/2); else
printf("%d %d\n",nFeet/4,nFeet/2); } return 0; }
解题思路： 这个问题可以描述成任给一个整数 N，如果 N 是奇数，输出 0 0， 否则如果 N 是 4 的倍数，输出 N / 4，N / 2，如果 N 不是 4 的倍数，输 出 N/4+1，N/2 。这是一个一般的计算题，只要实现相应的判断和输
目录
《算法与程序实践》习 题 解 答 1——简单计算 这一章的主要目的是通过编写一些简单的计算题，熟悉 C/C++语 言的基本语法。 基本思想：解决简单的计算问题的基本过程包括将一个用自然语 言描述的实际问题抽象成一个计算问题，给出计算过程，继而编程实 现计算过程，并将计算结果还原成对原来问题的解答。这里首要的是 读懂问题，搞清输入和输出的数据的含义及给出的格式，并且通过输 入输出样例验证自己的理解是否正确。 课堂练习：CS1、CS2、CS3 课堂讲解：CS4（CS5） A 类（满分 80）课堂练习：CS8、CS9、CS10 B 类（满分 100）课堂上机：CS11、CS20
输入： 第1 行是测试数据的组数n，后面跟着n行输入。每组测试数据占 1行，包括一个正整数a (a < 32768) 。
输出： n 行，每行输出对应一个输入。输出是两个正整数，第一个是最 少的动物数，第二个是最多的动物数，两个正整数用空格分开。如果 没有满足要求的情况出现，则输出2个0。 输入样例：
int temp=(int)sqrt(2000-x*x) for(y=temp;y>=x;y--)
CS3：鸡兔同笼
（来源： 2750） 问题描述：
7
一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例 外）。已经知道了笼子里面脚的总数a，问笼子里面至少有多少只动物， 至多有多少只动物。
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; } }
5
if(j>n) printf("No\n");
return 0; }
注意事项： 这题主要考察枚举的用法，还有求平方根（数学函数）的用法。
1） 要考虑 x 和 y 可调换，所以需要加上 y>=x，这样就能保证 不会出现重复的解
2） 考 虑 一 下 优 化 的 问 题 for(y=x;y<=m;y++)可 以 优 化 为 ： for(y=m;y>=x;y--)，甚至还可以
参考程序： #include<stdio.h> #include<math.h>
int main() {
int x,y,m; 6
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);
2 3 20 输出样例： 00 5 10
参考程序： #include<stdio.h>
8
int main() {
int nCase,nFeet,i; scanf("%d",&nCase); for(i=1;i<=nCase;i++) {
scanf("%d",&nFeet); if(nFeet%2 != 0)