第二章 简单计算问题.ppt

第二章 简单计算题,基本思想：解决简单计算问题的基本过程 包括将一个用自然语言描述的实际问题抽象成一个计算问题，给出计算过程，继而编程实现计算过程，并将计算结果还原成对原来问题的解答。这里首要的是读懂问题，搞清输入和输出数据的含义及给出的格式，并且通过输入输出样例验证自己的理解是否正确。,鸡兔同笼问题,笼子里关了鸡和兔子(鸡有2只脚，兔子有4只脚，没有例外)。已经知道笼子里面脚的总数a，问笼子里面至少有多少只动物，至多有多少只动物？输入数据第一行是测试数据的组数n，后面跟着n行输入。每组数据占一行，每行包含一个正整数a(a32768)输出要求输出n行，每行对应一个输入，包含两个正整数，第一个是最少的动物数，第二个是最多的动物数，两个正整数用一个空格分开。如果没有满足要求的答案，则输出两个0 解题思路 本问题可描述成任给一个整数N，如果N是奇数，输出0 0，否则如果N是4的倍 数，输出N/4 N/2，如果N不是4的倍数，输出N/4+1 N/2。这是一个一般的计算题，只要实现相应的判断和输出代码就可以了。输入整数在一个较小范围，只考虑整数运算。,鸡兔同笼问题,#include void main()int nCases,i,nFeet;scanf(%d,国际象棋的棋盘是黑白相间的8*8的方格，棋子在格子中间，走子规则如下：王：横、直、斜都可以走，但每步限走一格后：横、直、斜都可以走，每步格数不受限制车：横、竖均可以走，不能斜走，格数不受限制象：只能斜走，格数不限,棋盘上的距离,输入数据 测试数据的组数t。每行测试数据包括棋盘上起始位置和目标位置。位置用字母-数字形式表示，字母从a到h，数字从1到8。输出要求 对输入的每组测试数据，输出王、后、车、象所需的最少步数。无法到达输出 Inf 解题思路 王、后、车、象彼此独立，分别考虑，假设起始位置与终止位置在水平方向上的距离是x，它们在竖直方向上的距离是y 王需要的步数是 min(x,y)+abs(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的绝对值不相等）,棋盘上的距离,#include#include void main()int nCases,i;scanf(%d,棋盘上的距离,if(x=0,校门外的树,某校大门外长度为L的马路上有一排树，每两棵相邻的树之间间隔是1米。将马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，L，都种有一棵树。由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。任务：计算将这些树移走后，马路上还有多少树？,思路1：开一个有L+1个元素的数组，每个元素对应一棵树，初始化为1，表示各个位置上都有树;然后每读入一个区间，就将该区间对应数组元素变成0，表示该区间的树都被砍了;最后算一下还有几个1，就是还剩几棵树了。这种做法比较慢但直观思路2：将区间按起点排序，然后把所有区间遍历一遍，就把所有的树都砍了。不用开设L+1个元素的数组了，但是要开设数组将所有区间的起点，终点保存下来留做习题,校门外的树,#include void main()int L,i,j,n;bool trees10001;/*标准C中定义成int型*/for(i=0;i 10001;i+)treesi=true;scanf(%d%d,校门外的树,填词,Alex喜欢填词游戏。填词游戏包括一个N*M大小的矩形方格盘和P个单词。然后需要把每个方格中填上一个字母使得每个单词都能在方格盘上被找到。每个单词都能被找到要满足下面的条件每个方格都不能同时属于超过一个的单词。一个长为k的单词一定要占据k个方格。单词在方格盘中出现的方向只能是竖直的或者水平的。你的任务是首先在方格盘上找到所有的单词，当然在棋盘上可能有些方格没有被单词占据。然后所这些没有用的方格找出来，把这些方格上的字母按照字典顺序组成一个“神秘单词”,填 词,解题思路 给出条件比较隐晦。输入中给出的字母都是大写，表明输出也只能是大写字母。输入保证填词游戏至少有一组答案,这说明我们不必寻找单词所在位置，只要去掉这些单词所占用的字母就可以。“神秘单词”中的字母要按照字典序给出,这说明只要知道“神秘单词”中的字母组成就可以，因为在字母组成确定的情况下，按字典序输出的方式只有一种。经过分析发现本问题是给出一个字母的集合，从中去掉一些在给出单词中出现过的字母，将剩下的字母按字典序输出！可以定义一个有26个元素的数组，分别记录在输入的矩形中每个字母出现的次数，当读入单词时，将数组中对应到单词中的字母的元素值减一。处理完所有的单词后，将数组中的非0的元素对应的字母依次输出，数组元素的值是几，就输出几次该字母。,填 词,#include void main()int characters26;int n,m,p,i,j;for(i=0;i 26;i+)charactersi=0;scanf(%d%d%d,for(i=0;i p;i+)char str200;scanf(%s,str);for(j=0;strj!=0;j+)charactersstrj-A-;for(i=0;i 26;i+)if(charactersi!=0)for(j=0;jcharactersi;j+)printf(%c,i+A);printf(n);,装箱问题,一个工厂制造的产品形状都是长方体，它们的高度是h，长宽相等，一共有六个型号，他们的长宽分别为1*1，2*2，3*3，4*4，5*5，6*6。这些产品用一个6*6*h的长方体包裹包装然后邮寄给客户，编程计算每个订单运送时的最少包裹数量。输入数据 输入包括几行，每一行代表一个订单。每个订单包括六个整数，中间用空格隔开，分别为1*1 至6*6 这六种产品的数量。输入以 6 个0 组成的一行结尾。输出要求 除了最后一行6 个0 外，输入每一行对应着输出一行，每一行输出一个整数代表对应的订单所需的最小包裹数。,解题思想：先放大的，后放小的6*6的木块每个占用一个新箱子；5*5的木块每个占用一个新箱子，余下11个1*1的空格；4*4的木块每个占用一个新箱子，余下5个2*2的空格；3*3的木块每4个占用新一个箱子，不足4个也占一个新箱子，分情况余下不同数目的空格；2*2的木块先填空格，空格不足开新箱子，每9个2*2的木块占一个新箱子；1*1的木块先填空格，空格不足开新箱子，每36个占一个新箱子。,装箱问题,装箱问题,#include void main()int N,a,b,c,d,e,f,y,x;int u4=0,5,3,1;while(1)scanf(%d%d%d%d%d%d,实验题五,1平均年龄：班上有学生若干名，给出每名学生的年龄（整数），求班上所有学生的平均年龄，保留到小数点后两位。2数字求和：给定一个正整数a，以及另外的5个正整数，问题是这5个整数中，小于a的整数的和是多少？3两倍：给定2到15个不同的正整数，计算这些数里面有多少个数对满足条件一个数是另一个数的两倍。比如给定1 4 3 2 9 7 18 22，得到的答案是3，因为2是1的两倍，4是2的两倍，18是9的两倍。4.捕鱼：A、B、C、D、E五个人在某天夜里合伙去捕鱼，到第二天凌晨时疲惫不堪，于是各自找地方睡觉。日上三竿，A第一个醒来，将鱼分成5份，把多余的1条扔了，拿走自己的一份。B第二个醒来，也将鱼分成5份，把多余的1条扔了，拿走自己的一份。C、D、E依次醒来，按同样的方法拿鱼。编程求他们合伙至少捕了多少条鱼呢？5刀功：不错，有人放一张大的煎饼在板上，问他饼不离开板，切100刀最多能分成多少块？请编写程序帮王小二算一算，他能切出多少呢？,