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