《信息学竞赛简单计算专题》由会员分享，可在线阅读，更多相关《信息学竞赛简单计算专题（15页珍藏版）》请在金锄头文库上搜索。
1、信息学竞赛习 题 解 答1简单计算这一章的主要目的是通过编写一些简单的计算题，熟悉C/C+语言的基本语法。基本思想：解决简单的计算问题的基本过程包括将一个用自然语言描述的实际问题抽象成一个计算问题，给出计算过程，继而编程实现计算过程，并将计算结果还原成对原来问题的解答。这里首要的是读懂问题，搞清输入和输出的数据的含义及给出的格式，并且通过输入输出样例验证自己的理解是否正确。CS1：斐波那契数列（来源：自编）问题描述： 已知斐波那契数列第n项的计算公式如下。在计算时有两种算法：递归和非递归，请分别给出这两种算法。当n=0时，Fib(n)=0，当n=1时，Fib(n)=1，当n1时，Fib(n)=
2、 Fib(n-1)+ Fib(n-2)输入：第一行是测试数据的组数m，后面跟着m行输入。每行包括一个项数n和一个正整数a。（m，n，a均大于0，且均小于10000000）输出：输出包含m行，每行对应一个输入，若a不大于Fib(n)，则输出Yes，否则输出No输入样例：33 310 5024 20000输出样例：NoYesYes参考程序1（zzg）：循环版#includeint main()int fn2,fn1,fn,m,n,a,i,j;fn2=0;fn1=1;/freopen(in.txt,r,stdin);/freopen(out.txt,w,stdout); /c+/#include/i
3、fstream cin(in.txt);/ofstream cout(out.txt);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?0:1;elsereturn fib(n-2)+fib(n-1);int main()in
4、t 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：正整数解（来源：程序设计方法及在线实践指导（王衍等）例4.1，P145）求x2+y2=2000的正整数解，输出所有不同的解。参考程序：#include#include
5、int 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.1 P83）问题描述：一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。已经知道了笼子里面脚的总数a，问笼子里面至少有多少只动物，至多有多少只动物。输入：第1 行是测试数据的组数n，后面跟着n行
6、输入。每组测试数据占1行，包括一个正整数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
7、+1,nFeet/2);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） 试图把所有输入
8、先存储起来，再输出，开的数组太小，因数组越界产生运行错；4） 在每行输出末尾缺少换行符；5） 对输入输出语法不熟悉导致死循环或语法错。CS4：棋盘上的距离（来源： 1657，程序设计导引及在线实践（李文新）例2.2 P85）问题描述：国际象棋的棋盘是黑白相间的8 * 8的方格，棋子放在格子中间。如图1-1所示：图1-1 国际象棋棋盘王、后、车、象的走子规则如下：王：横、直、斜都可以走，但每步限走一格。后：横、直、斜都可以走，每步格数不受限制。车：横、竖均可以走，不能斜走，格数不限。象：只能斜走，格数不限。写一个程序，给定起始位置和目标位置，计算王、后、车、象从起始位置走到目标位置所需的最少步数
9、。输入：第一行是测试数据的组数t（0 = t = 20）。以下每行是一组测试数据，每组包括棋盘上的两个位置，第一个是起始位置，第二个是目标位置。位置用字母-数字的形式表示，字母从“a”到“h”，数字从“1”到“8”。输出要求：对输入的每组测试数据，输出王、后、车、象所需的最少步数。如果无法到达，就输出“Inf”。输入样例2a1 c3f5 f8输出样例 2 1 2 1 3 1 1 Inf解题思路这个问题是给定一个棋盘上的起始位置和终止位置，分别判断王、后、车、象从起始位置到达终止位置需要的步数。首先，王、后、车、象彼此独立，分别考虑就可以了。所以这个题目重点要分析王、后、车、象的行走规则特点，从
10、而推出它们从起点到终点的步数。我们假设起始位置与终止位置在水平方向上的距离是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）。根据象行走得规则，它可以斜走，格数不限。棋盘上的格点可以分为两类，第一类是它的横坐标和纵坐标
11、之差为奇数，第二类是横纵坐标之差为偶数。对于只能斜走的象，它每走一步，因为横纵坐标增加或减小的绝对值相等，所以横坐标和纵坐标之差的奇偶性无论如何行走都保持不变。因此，上述的第一类点和第二类点不能互相到达。如果判断出起始点和终止点分别属于两类点，就可以得出它们之间需要无数步的结论。如果它们属于同一类点，象从起始点走到终止点需要1（x的绝对值等于y的绝对值）或者2（x的绝对值不等于y的绝对值）。参考程序：#include#includeint main()int nCase,i;char begin3,end3; /用来存储开始和结束位置int x,y;/用来存储水平和垂直方向上起止位置间的间距s
12、canf(%d,&nCase);for(i=1;i=nCase;i+)scanf(%s%s,begin,end);x=abs(end0-begin0);y=abs(end1-begin1);if(x=0 & y=0) printf(0 0 0 0n); /起止位置相同，都不需要走else/王走的步数if(xy) printf(%d,x+abs(x-y);else printf(%d,y+abs(x-y);/后走的步数if(x=y | x=0 | y=0)printf( 1);elseprintf( 2);/车走的步数if(x=0 | y=0 ) printf( 1);else printf( 2);/象走的步数if(abs(x-y)%2!=0 ) printf( Infn);else if(x=y) printf( 1n);else printf( 2n);return 0;注意事项：这个问题需要一些简单的推理，出错有以下几种情况：1) 因为对问题分析不清楚，给出了错误的计算
