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

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 行，每行输出对应一个输入。输出是两个正整数，第一个是最少的动物数，第二个是最多的动物数，两个正整数用空格分开。如果没有满足要求的情况出现，则输出2个0。 输入样例：

2 3 20 输出样例：

0 0 5 10

参考程序：

#include

int main() {

int nCase,nFeet,i; scanf(\

4

}

for(i=1;i<=nCase;i++) {

scanf(\ if(nFeet%2 != 0) printf(\ else if(nFeet%4 != 0)

printf(\ else

printf(\}

return 0;

解题思路：

这个问题可以描述成任给一个整数N，如果N是奇数，输出0 0，否则如果N是4的倍数，输出N / 4，N / 2，如果N不是4的倍数，输出N/4+1，N/2 。这是一个一般的计算题，只要实现相应的判断和输出代码就可以了。题目中说明了输入整数在一个比较小的范围内，所以只需要考虑整数运算就可以了。

注意事项：

这里考察数学计算，出错有一下几种情况：

1） 因为对问题分析不清楚，给出了错误的计算公式；

2） 不用数学方法，而试图用枚举所有鸡和兔的个数来求解此题，造成超时； 3） 试图把所有输入先存储起来，再输出，开的数组太小，因数组越界产生运行错； 4） 在每行输出末尾缺少换行符；

5） 对输入输出语法不熟悉导致死循环或语法错。

CS4：棋盘上的距离

（来源：poj.grids.cn 1657）

问题描述：国际象棋的棋盘是黑白相间的8 * 8 的方格，棋子放在格子中间。如图1-1 所示：

5

图1-1 国际象棋棋盘

王、后、车、象的走子规则如下：

王：横、直、斜都可以走，但每步限走一格。 后：横、直、斜都可以走，每步格数不受限制。 车：横、竖均可以走，不能斜走，格数不限。 象：只能斜走，格数不限。

写一个程序，给定起始位置和目标位置，计算王、后、车、象从起始位置走到目标位置所需的最少步数。 输入：

第一行是测试数据的组数t（0 <= t <= 20 ）。以下每行是一组测试数据，每组包括棋盘上的两个位置，第一个是起始位置，第二个是目标位置。位置用\字母-数字\的形式表示，字母从“a”到“h”，数字从“1” 到“8” 。 输出要求：

对输入的每组测试数据，输出王、后、车、象所需的最少步数。如果无法到达，就输出“Inf”。 输入样例 2 a1 c3 f5 f8 输出样例 2 1 2 1 3 1 1 Inf

解题思路

这个问题是给定一个棋盘上的起始位置和终止位置，分别判断王、后、车、象从起始位置到达终止位置需要的步数。首先，王、后、车、象彼此独立，分别考虑就可以了。所以这个题目重点要分析王、后、车、象的行走规则特点，从而推出它们从起点到终点的步数。

6

我们假设起始位置与终止位置在水平方向上的距离是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）。

根据象行走得规则，它可以斜走，格数不限。棋盘上的格点可以分为两类，第一类是它的横坐标和纵坐标之差为奇数，第二类是横纵坐标之差为偶数。对于只能斜走的象，它每走一步，因为横纵坐标增加或减小的绝对值相等，所以横坐标和纵坐标之差的奇偶性无论如何行走都保持不变。因此，上述的第一类点和第二类点不能互相到达。如果判断出起始点和终止点分别属于两类点，就可以得出它们之间需要无数步的结论。如果它们属于同一类点，象从起始点走到终止点需要1（x 的绝对值等于y 的绝对值）或者2（x 的绝对值不等于y 的绝对值）。

CS5：校门外的树木

（来源：poj.grids.cn 2808）

问题描述：

某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，??，L，都种有一棵树。由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。 输入：

输入的第一行有两个整数L（1 <= L <= 10000 ）和 M（1 <=M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。 输出要求：

输出包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。

输入样例：

500 3 150 300 100 200 470 471

输出样例:

298

7