《算法与程序实践1(简单计算)》由会员分享，可在线阅读，更多相关《算法与程序实践1(简单计算)（22页珍藏版）》请在金锄头文库上搜索。
1、目 录CS1：斐波那契数列1CS2：正整数解3CS3：鸡兔同笼4CS4：棋盘上的距离5CS5：校门外的树木7CS6：填词8CS7：装箱问题9CS8：求平均年龄10CS9：数字求和11CS10：两倍11CS11：肿瘤面积12CS12：肿瘤检测12CS13：垂直直方图13CS14：谁拿了最多的奖学金14CS15：简单密码15CS16：化验诊断16CS17：密码17CS18：数字阶梯17CS19：假票18CS20：纸牌（Deck）19电视墙也就是电视背景装饰墙，是居室装饰特别是大户型居室的重点之一，在装修中占据相当重要的地位，电视墙通常是为了弥补客厅中电视机背景墙面的空旷，同时起到修饰客厅的作用。因
2、为电视墙是家人目光注视最多的地方，长年累月地看也会让人厌烦，所以其装修就尤为讲究算法与程序实践习 题 解 答1简单计算这一章的主要目的是通过编写一些简单的计算题，熟悉C/C+语言的基本语法。基本思想：解决简单的计算问题的基本过程包括将一个用自然语言描述的实际问题抽象成一个计算问题，给出计算过程，继而编程实现计算过程，并将计算结果还原成对原来问题的解答。这里首要的是读懂问题，搞清输入和输出的数据的含义及给出的格式，并且通过输入输出样例验证自己的理解是否正确。课堂练习：CS1、CS2、CS3课堂讲解：CS4（CS5）A类（满分80）课堂练习：CS8、CS9、CS10B类（满分100）课堂上机：CS
3、11、CS20CS1：斐波那契数列问题描述： 已知斐波那契数列第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输入样例：33 310 5024 20000输出样例：NoYesYes参考程序1（zzg）：循环版#includeint main()
4、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(Yesn);elseprintf(Non);elsefor(j=2;j=n;j+)fn=fn2+fn1;fn2=fn1;fn1=fn;if(an)printf(Non);return 1;递归版（zzg）#includeint fib(int n)if(n2)return n=0?
5、0:1;elsereturn 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(an)printf(Non);return 1;注意事项：这题主要考察递归与非递归的用法，还有数值越界的情况。1）测试数据可取一下 1 1和1 3试一下。2）测试数据可以取一下 50 1000和1000 1000。程序中若考虑到值的越界就没问题或者考虑使用break也可以。CS2：正整数解求x2+y2=2000的正整数解，输出所有不同的解。参考程序：#i
6、nclude#includeint main()int x,y,m;m=(int)sqrt(2000);for(x=1;x=m;x+)for(y=x;y=x，这样就能保证不会出现重复的解2） 考虑一下优化的问题for(y=x;y=x;y-)，甚至还可以int temp=(int)sqrt(2000-x*x) for(y=temp;y=x;y-)CS3：鸡兔同笼（来源： 2750）问题描述：一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。已经知道了笼子里面脚的总数a，问笼子里面至少有多少只动物，至多有多少只动物。输入：第1 行是测试数据的组数n，后面跟着n行输入。每组测试数据占1
7、行，包括一个正整数a (a 32768) 。输出：n 行，每行输出对应一个输入。输出是两个正整数，第一个是最少的动物数，第二个是最多的动物数，两个正整数用空格分开。如果没有满足要求的情况出现，则输出2个0。输入样例：2320输出样例：0 05 10参考程序：#includeint main()int nCase,nFeet,i;scanf(%d,&nCase);for(i=1;i=nCase;i+)scanf(%d,&nFeet);if(nFeet%2 != 0) printf(0 0n);else if(nFeet%4 != 0)printf(%d %dn,nFeet/4+1,nFeet/2
8、);elseprintf(%d %dn,nFeet/4,nFeet/2);return 0;解题思路：这个问题可以描述成任给一个整数N，如果N是奇数，输出0 0，否则如果N是4的倍数，输出N / 4，N / 2，如果N不是4的倍数，输出N/4+1，N/2 。这是一个一般的计算题，只要实现相应的判断和输出代码就可以了。题目中说明了输入整数在一个比较小的范围内，所以只需要考虑整数运算就可以了。注意事项：这里考察数学计算，出错有一下几种情况：1） 因为对问题分析不清楚，给出了错误的计算公式；2） 不用数学方法，而试图用枚举所有鸡和兔的个数来求解此题，造成超时；3） 试图把所有输入先存储起来，再输出，
9、开的数组太小，因数组越界产生运行错；4） 在每行输出末尾缺少换行符；5） 对输入输出语法不熟悉导致死循环或语法错。CS4：棋盘上的距离（来源： 1657）问题描述：国际象棋的棋盘是黑白相间的8 * 8 的方格，棋子放在格子中间。如图1-1 所示：图1-1 国际象棋棋盘王、后、车、象的走子规则如下：王：横、直、斜都可以走，但每步限走一格。后：横、直、斜都可以走，每步格数不受限制。车：横、竖均可以走，不能斜走，格数不限。象：只能斜走，格数不限。写一个程序，给定起始位置和目标位置，计算王、后、车、象从起始位置走到目标位置所需的最少步数。输入：第一行是测试数据的组数t（0 = t = 20 ）。以下每
10、行是一组测试数据，每组包括棋盘上的两个位置，第一个是起始位置，第二个是目标位置。位置用字母-数字的形式表示，字母从“a”到“h”，数字从“1” 到“8” 。输出要求：对输入的每组测试数据，输出王、后、车、象所需的最少步数。如果无法到达，就输出“Inf”。输入样例2a1 c3f5 f8输出样例 2 1 2 1 3 1 1 Inf解题思路这个问题是给定一个棋盘上的起始位置和终止位置，分别判断王、后、车、象从起始位置到达终止位置需要的步数。首先，王、后、车、象彼此独立，分别考虑就可以了。所以这个题目重点要分析王、后、车、象的行走规则特点，从而推出它们从起点到终点的步数。我们假设起始位置与终止位置在水
11、平方向上的距离是x，它们在竖直方向上的距离是y。根据王的行走规则，它可以横、直、斜走，每步限走一格，所以需要的步数是min(x,y)+abs(x-y) ，即x，y 中较小的一个加上x 与y 之差的绝对值。根据后行走的规则，她可以横、直、斜走，每步格数不受限制，所以需要的步数是1（x 等于y 或者 x 等于0 或者 y 等于0）或者2(x不等于y)。根据车行走的规则，它可以横、竖走，不能斜走，格数不限，需要步数为1 （x 或者y 等于0）或者2（x 和y 都不等于0）。根据象行走得规则，它可以斜走，格数不限。棋盘上的格点可以分为两类，第一类是它的横坐标和纵坐标之差为奇数，第二类是横纵坐标之差为偶
12、数。对于只能斜走的象，它每走一步，因为横纵坐标增加或减小的绝对值相等，所以横坐标和纵坐标之差的奇偶性无论如何行走都保持不变。因此，上述的第一类点和第二类点不能互相到达。如果判断出起始点和终止点分别属于两类点，就可以得出它们之间需要无数步的结论。如果它们属于同一类点，象从起始点走到终止点需要1（x 的绝对值等于y 的绝对值）或者2（x 的绝对值不等于y 的绝对值）。CS5：校门外的树木（来源： 2808）问题描述：某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，L，都种
13、有一棵树。由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。输入：输入的第一行有两个整数L（1 = L = 10000）和 M（1 =M = 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。 输出要求：输出包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。输入样例：500 3
