第1讲简单计算题.ppt

《第1讲简单计算题.ppt》由会员分享，可在线阅读，更多相关《第1讲简单计算题.ppt（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一讲第一讲简单计算题简单计算题1鸡兔同笼鸡兔同笼v问题描述：问题描述：一个笼子里面关了鸡和兔子（鸡有一个笼子里面关了鸡和兔子（鸡有2 2只脚，兔子有只脚，兔子有4 4只只脚，没有例外）。已经知道了笼子里面脚的总数脚，没有例外）。已经知道了笼子里面脚的总数a a，问笼子里面至少有多少只动物，至多有多少只动物。问笼子里面至少有多少只动物，至多有多少只动物。2鸡兔同笼鸡兔同笼v输入数据：输入数据：第第1 1行是测试数据的组数行是测试数据的组数n n，后面跟，后面跟着着n n行输入。每组测试数据占行输入。每组测试数据占1 1行，包括一个正行，包括一个正整数整数a(aa(a32768)32768)。v

2、输出要求：输出要求：n n行，每行输出对应一个输入。输出行，每行输出对应一个输入。输出是两个正整数，第一个是最少的动物数，第二是两个正整数，第一个是最少的动物数，第二个是最多的动物数，两个正整数用空格分开。个是最多的动物数，两个正整数用空格分开。如果没有满足要求的情况出现，则输出如果没有满足要求的情况出现，则输出2 2个个0 0。v输入样例：输入样例：2 23 32020v输出样例：输出样例：0 00 05 105 103鸡兔同笼鸡兔同笼v解题思路：解题思路：这个问题可以描述成任给一个整数这个问题可以描述成任给一个整数N N，如果，如果N N是奇数，是奇数，输出输出0 00 0，否则如果，否则

3、如果N N是是4 4的倍数，输出的倍数，输出N/4 N/2N/4 N/2，如果，如果N N不是不是4 4的倍数，输出的倍数，输出N/4+1 N/2N/4+1 N/2。这是一个一般的计。这是一个一般的计算题，只要实现相应的判断和输出代码就可以了。题算题，只要实现相应的判断和输出代码就可以了。题目中说明了输入整数在一个比较小的范围内，所以只目中说明了输入整数在一个比较小的范围内，所以只需要考虑整数运算就可以了。需要考虑整数运算就可以了。45鸡兔同笼鸡兔同笼v实现中常见的问题：实现中常见的问题：因为对问题分析不清楚，给出了错误的计算公式；因为对问题分析不清楚，给出了错误的计算公式；不用数学方法，而试

4、图用枚举所有鸡和兔的个数来求不用数学方法，而试图用枚举所有鸡和兔的个数来求解此题，造成超时；解此题，造成超时；试图把所有输入先存储起来，再输出，开的数组太小，试图把所有输入先存储起来，再输出，开的数组太小，因数组越界产生运行错；因数组越界产生运行错；在每行输出末尾缺少换行符；在每行输出末尾缺少换行符；对输入输出语法不熟悉导致死循环或语法错。对输入输出语法不熟悉导致死循环或语法错。6棋盘上的距离棋盘上的距离v问题描述：问题描述：国际象棋国际象棋的棋盘是的棋盘是黑白相间黑白相间的的8*88*8的的方格，棋方格，棋子放在格子放在格子中间。子中间。7棋盘上的距离棋盘上的距离v王、后、车、象的走子规则如

5、下：王、后、车、象的走子规则如下：王：横、直、斜都可以走，但每步限走一格；王：横、直、斜都可以走，但每步限走一格；后：横、直、斜都可以走，每步格数不受限制；后：横、直、斜都可以走，每步格数不受限制；车：横、竖均可以走，不能斜走，格数不限；车：横、竖均可以走，不能斜走，格数不限；象：只能斜走，格数不限。象：只能斜走，格数不限。写一个程序，给定起始位置和目标位置，计算王、写一个程序，给定起始位置和目标位置，计算王、后、车、象从起始位置走到目标位置所需的最小步后、车、象从起始位置走到目标位置所需的最小步数。数。8棋盘上的距离棋盘上的距离v输入数据：输入数据：第第1 1行是测试数据的组数行是测试数据的

6、组数t(0=t=20)t(0=t=20)。以下每行是一组测试数据，每组包括棋盘上的两以下每行是一组测试数据，每组包括棋盘上的两个位置，第一个是起始位置，第二个是目标位置。个位置，第一个是起始位置，第二个是目标位置。位置用位置用“字母字母-数字数字”的形式表示，字母从的形式表示，字母从“a”a”到到“h”h”，数字从，数字从“1”1”到到“8”8”。v输出要求：输出要求：对输入的每组测试数据，输出王、后、对输入的每组测试数据，输出王、后、车、象所需的最小步数。如果无法到达，就输出车、象所需的最小步数。如果无法到达，就输出“InfInf”。v输入样例：输入样例：2 2a1 c3a1 c3f5 f8

7、f5 f8v输出样例：输出样例：2 1 2 12 1 2 13 1 1 3 1 1 InfInf9棋盘上的距离棋盘上的距离v解题思路：解题思路：题目的重点是要分析王、后、车、象的行走规则特题目的重点是要分析王、后、车、象的行走规则特点，从而推出它们从起点到终点的步数。点，从而推出它们从起点到终点的步数。我们假设起始位置与终止位置在水平方向上的距离我们假设起始位置与终止位置在水平方向上的距离为为x x，在竖直方向上的距离为，在竖直方向上的距离为y y。王：王：min(x,y)+abs(x-ymin(x,y)+abs(x-y)后：后：1 1（x=yx=y或者或者x=0 x=0或者或者y=0y=0）

8、或）或2 2（x xy y）车：车：1 1（x x=0=0或或y=0y=0）或）或2 2（x x和和y y都不等于都不等于0 0）10棋盘上的距离棋盘上的距离象：棋盘上的格点分为两类：象：棋盘上的格点分为两类：一类是格点的横纵坐标之差为奇数；一类是格点的横纵坐标之差为奇数；一类是格点的横纵坐标之差为偶数。一类是格点的横纵坐标之差为偶数。对于只能斜走的象，它每走一步，因为横纵坐标对于只能斜走的象，它每走一步，因为横纵坐标增加或减少的绝对值相等，所以横纵坐标之差的增加或减少的绝对值相等，所以横纵坐标之差的奇偶性无论如何行走都保持不变。因此，上述的奇偶性无论如何行走都保持不变。因此，上述的第一类点和

9、第二类点不能互相到达。第一类点和第二类点不能互相到达。如果判断出如果判断出起始点和终止点分别属于两类点，就可以得出它起始点和终止点分别属于两类点，就可以得出它们之间需要无数步的结论。们之间需要无数步的结论。如果它们属于同一类点，需要如果它们属于同一类点，需要1 1（x x的绝对值等于的绝对值等于y y的绝对值）或的绝对值）或2 2（x x的绝对值不等于的绝对值不等于y y的绝对值）。的绝对值）。111213校门外的树校门外的树v问题描述：问题描述：某校大门外长度为某校大门外长度为L L的马路上有一排树，每两颗相邻的马路上有一排树，每两颗相邻的树之间的间隔都是的树之间的间隔都是1 1米。我们可以

10、把马路看成一个米。我们可以把马路看成一个数轴，马路的一端在数轴数轴，马路的一端在数轴0 0的位置，另一端在的位置，另一端在L L的位置；的位置；数轴上的每个整数点，即数轴上的每个整数点，即0 0，1 1，2 2，L L，都种有一，都种有一棵树。棵树。由于马路上有一些区域要用来建地铁。这些区域用它由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点合的部分。现在要把这些区域中

11、的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。后，马路上还有多少棵树。14校门外的树校门外的树v输入数据：输入数据：第第1 1行有两个整数行有两个整数L L（1=L=100001=L=10000）和）和M M（1=M=1001=M=100），），L L代表马路的长度，代表马路的长度，M M代表区域代表区域的数目，的数目，L L和和M M之间用一个空格隔开。接下来的之间用一个空格隔开。接下来的M M行行每行包含两个不同的整数，用一个空格隔开，表每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止

12、点的坐标。示一个区域的起始点和终止点的坐标。v输出要求：输出要求：输出包括一行，这一行只包含一个整输出包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。数，表示马路上剩余的树的数目。v输入样例：输入样例：500 3500 3150 300150 300100 200100 200470 471470 471v输出样例：输出样例：29829815校门外的树校门外的树v解题思路：解题思路：这个问题可以概括为输入一个大的整数闭区间，及一这个问题可以概括为输入一个大的整数闭区间，及一些可能互相重叠的在该大区间内的小的整数闭区间。些可能互相重叠的在该大区间内的小的整数闭区间。在大的整数闭区间内去

13、除这些小的整数闭区间，问之在大的整数闭区间内去除这些小的整数闭区间，问之后剩下的可能不连续的整数区间内有多少个整数。后剩下的可能不连续的整数区间内有多少个整数。这个题目给出的范围是大的区间在这个题目给出的范围是大的区间在1-100001-10000以内，要以内，要去除的小的区间的个数是去除的小的区间的个数是100100个以内。因为规模较小，个以内。因为规模较小，所以可以考虑用空间换时间，用一个大数组来模拟这所以可以考虑用空间换时间，用一个大数组来模拟这些区间，数组中的每个数表示区间上的一个数。些区间，数组中的每个数表示区间上的一个数。例如，如果输入例如，如果输入L L的长度是的长度是50050

14、0，则据题意可知最初有，则据题意可知最初有501501棵树。我们就用一个棵树。我们就用一个501501个元素的数组来模拟这个元素的数组来模拟这501501棵树，数组的下标分别代表从棵树，数组的下标分别代表从1 1到到501501棵树，数组棵树，数组元素的值代表这棵树是否被移走。元素的值代表这棵树是否被移走。16校门外的树校门外的树v解题思路：解题思路：最初这些树没有被移走，所以所有数组元素的值都用最初这些树没有被移走，所以所有数组元素的值都用truetrue来表示。每当输入一个小区间，就将这个区间对来表示。每当输入一个小区间，就将这个区间对应的树全部移走，即将这个区间对应的数组元素下标应的树全

15、部移走，即将这个区间对应的数组元素下标指示的元素的值置成指示的元素的值置成falsefalse。如果有多个区间对应同。如果有多个区间对应同一个数组元素，会导致多次将某个数组元素置成一个数组元素，会导致多次将某个数组元素置成falsefalse。不过这并不影响结果的正确性。不过这并不影响结果的正确性。当所有小区间输入完成，我们可以数一下剩下的仍旧当所有小区间输入完成，我们可以数一下剩下的仍旧为为truetrue的元素的个数，就可以得到最后剩下的树的数的元素的个数，就可以得到最后剩下的树的数目。目。1718校门外的树校门外的树v思考：思考：语句语句1313最坏情况下要执行多少次？最好情况下要被执最坏情况下要执行多少次？最好情况下要被执行多少次？如果区间的起点和终点是随机分布的，那行多少次？如果区间的起点和终点是随机分布的，那么语句么语句1313平均要被执行多少次？（答案是平均要被执行多少次？（答案是L L和和M M的函数）的函数）如果马路长度如果马路长度L L的值极大，比如是的值极大，比如是4040亿，以至于无法亿，以至于无法开设这么大的开设这么大的treestrees数组，本题该如何解决？数组，本题该如何解决？19练习练习-装箱问题装箱问题20