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

}

{

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

解题思路

这个问题可以概括为输入一个大的整数闭区间，及一些可能互相重叠的在该大区间内的小的整数闭区间。在大的整数闭区间内去除这些小的整数闭区间，问之后剩下的可能不连续的整数区间内有多少个整数。这个题目给出的范围是大的区间在1~10000以内，要去除的小的区间的个数是100个以内。因为规模较小，所以可以考虑用空间换时间，用一个大数组来模拟这些区间，数组中的每个数表示区间上的一个数。例如，如果输入L的长度是500，则据题意可知最初有501棵树。我们就用一个501个元素的数组来模拟这501棵树，数组的下标分别代表从1到501棵树，数组元素的值代表这棵树是否被一走。最初这些树都没有被移走，所以所有数组元素的值都用true来表示。每当输入一个小区间，就将这个区间对应的树全部移走，即将这个区间对应的数组元素下标指示的元素的值置成false。如果有多个区间对应同一个数组元素，会导致多次将某个数组元素置成false。不过这并不影响结果的正确性。当所有小区间输入完成，我们可以数一下剩下的仍旧为true的元素的个数，就可以得到最后剩下的树的数目。当然如果最开始输入的区间不是500，则我们使用的数组大小就不是500。因为题目给出的上限是10000，所以我们可以定义一个大小是10001个元素的数组，这样对所有输入都是够用的。

思考题：

如果马路长度L的值极大，比如是40亿，以至于无法开设这么大的trees数组，本题该如何解决？

CS6：填词

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

Alex 喜欢填词游戏。填词游戏是一个非常简单的游戏。填词游戏包括一个N *M 大小的矩形方格盘和P个单词。然后需要把每个方格中填上一个字母使得每个单词都能在方格盘上被找到。每个单词都能被找到要满足下面的条件：

每个方格都不能同时属于超过一个的单词。一个长为k的单词一定要占据k个方格。单词在方格盘中出现的方向只能是竖直的或者水平的（可以由竖直转向水平，反之亦然）。 你的任务是首先在方格盘上找到所有的单词，当然在棋盘上可能有些方格没有被单词占据。然后把这些没有用的方格找出来，把这些方格上的字母按照字典序组成一个“神秘单词”。

如果你还不了解规则，我们可以用一个例子来说明，比如在图1-2中寻找单词BEG和GEE。

E B G G E E E G E 正确

E B G G E E E G E 不正确，(2,2)中的字母E属于两个单词

E B G G E E E G E 不正确，(3,1)和(2,2)中的字母E不相邻

E B G G E E E G E 不正确，(2,2)中的字母E被用了两次

8

图1-2 填词游戏方格盘

输入：

输入的第一行包括三个整数N，M 和P (2 <= M, N <= 10, 0 <= P <=100) 。接下来的N 行，每行包括M个字符来表示方格盘。接下来P行给出需要在方格盘中找到的单词。

输入保证填词游戏至少有一组答案。输入中给出的字母都是大写字母。

输出要求

输出“神秘单词”，注意“神秘单词”中的字母要按照字典序给出。 输入样例

3 3 2 EBG GEE EGE BEG GEE 输出样例

EEG

解题思路

题目中给出的条件比较隐晦。输入中给出的字母都是大写字母——表明输出也只能是大写字母。输入保证填词游戏至少有一组答案——这说明我们不必寻找单词所在的位置，只要去掉这些单词所占用的字母就可以了。“神秘单词”中的字母要按照字典序给出——说明我们只要知道“神秘单词”中的字母组成就可以了，在字母组成确定的情况下，按字典序输出的方式只有一种。分析到这里我们发现这其实是个很简单的问题。给出一个字母的集合，从中去掉一些在给出单词中出现过的字母，将剩下的字母按字典序输出！

可以定义一个有26个元素的数组，分别记录在输入的矩形中，每个字母出现的次数，当读入单词时，将数组中对应到单词中的字母的元素值减一。处理完所有的单词后，将数组中的非0 的元素对应的字母依次输出，数组元素的值是几，就输出几次该字母。

CS7：装箱问题

（来源：poj.grids.cn 1017）

问题描述：

一个工厂制造的产品形状都是长方体，它们的高度都是h，长和宽都相等，一共有六个型号，他们的长宽分别为1*1, 2*2, 3*3, 4*4, 5*5, 6*6. 这些产品通常使用一个 6*6*h 的长方体包裹包装然后邮寄给客户。因为邮费很贵，所以工厂要想方设法的减小每个订单运送时的包裹数量。他们很需要有一个好的程序帮他们解决这个问题从而节省费用。现在这个程序由你来设计。 输入：

输入文件包括几行，每一行代表一个订单。每个订单里的一行包括六个整数，中间用

9

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库算法与程序实践1（简单计算）(2)在线全文阅读。