c语言--简单计算题PPT课件

.,1,第二章简单计算题,.,2,2.1例题：鸡兔同笼,问题描述一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。已经知道了笼子里面脚的总数a，问笼子里面至少有多少只动物，至多有多少只动物,.,3,输入数据第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a(a32768)。输出要求n行，每行输出对应一个输入。输出是两个正整数，第一个是最少的动物数，第二个是最多的动物数，两个正整数用空格分开。如果没有满足要求的情况出现，则输出2个0。,输入样例2320输出样例00510,输入输出,.,4,题目分析,（1）如果有奇数只脚，则输入不正确（2）若要动物数目最少，使动物尽量有4只脚（3）若要动物数目最多，使动物尽量有2只脚（4）题目中说明了输入整数在一个比较小的范围内，所以只需要考虑整数运算就可以了。,.,5,解题思路,这个问题可以描述成任给一个整数N，(1)如果N是奇数，输出00，(2)否则如果N不是4的倍数，输出N/4+1（只有一个是两只脚）N/2（全两只脚）(3)如果N是4的倍数，输出N/4（全4只脚）N/2（全两只脚）,.,6,流程,intmain()intnCases,i,nFeet;读入测试次数ncase；控制循环进行ncase次读入脚的只数nFeet;如果有奇数只脚，则输入不正确，否则如果nFeet不是4的倍数动物数目最少nFeet/4+1,最多nFeet/2;否则动物数目最少nFeet/4,最多nFeet/2;,.,7,#includeintmain()intnCases,i,nFeet;scanf(%d,例程,.,8,实现中常见的问题,这是一个数学计算题，出错有一下几种情况：1）因为对问题分析不清楚，给出了错误的计算公式；2）不用数学方法，而试图用枚举所有鸡和兔的个数来求解此题，造成超时；3）试图把所有输入先存储起来，再输出，开的数组太小，因数组越界产生运行错；4）在每行输出末尾缺少换行符；5）对输入输出语法不熟悉导致死循环或语法错。,.,9,2.2例题：棋盘上的距离,国际象棋的棋盘是黑白相间的8*8的方格，棋子放在格子中间。王、后、车、象的走子规则如下：王：横、直、斜都可以走，但每步限走一格。后：横、直、斜都可以走，每步格数不受限制。车：横、竖均可以走，不能斜走，格数不限。象：只能斜走，格数不限。写一个程序，给定起始位置和目标位置，计算王、后、车、象从起始位置走到目标位置所需的最少步数。,.,10,输入输出要求,输入数据第一行是测试数据的组数t（0（8，2）又例：（2，3）到（7，4）可达，需2步:（2，3）-(5,6)-（7，4）,规律：第一步的步长是(|x1-x2|+|y1-y2|)/2,.,17,参考程序,#include#includeintmain()intnCases,i;scanf(%d,对你有用的信息是:起止位置之间横坐标的差x，和纵坐标的差y,#include#includeintmain()intnCases,i;scanf(%d,.,18,if(x=0,/车的步数if(x=0|y=0)printf(1);elseprintf(2);/象的步数if(abs(x-y)%2!=0)printf(Infn);elseif(x=y)printf(1n);elseprintf(2n);,.,19,实现中常见的问题,这个问题需要一些简单的推理，出错有一下几种情况：1)因为对问题分析不清楚，给出了错误的计算公式；2)在每行输出末尾缺少换行符；3)将”Inf”错写成”inf”;4)漏判了起始位置和终止位置相同的情况。,.,20,2.3例题：校门外的树,某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，L，都种有一棵树。由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。,.,21,输入输出要求,输入数据输入的第一行有两个整数L（1=L=10000）和M（1=M=100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。输出要求输出包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。,输入样例5003150300100200470471输出样例298,.,22,解题思路,这个题目给出的范围是大的区间在110000以内，要去除的小的区间的个数是100个以内。用一个大数组来模拟这些区间，数组中的每个数表示区间上的一棵树。,输入样例103254689输出样例4,a,0,0,0,0,0,0,0,0,0,0,.,23,参考程序,#includeintmain()intL,i,j,n;/L为区间的长度，n为区间的个数booltrees10001;/用一个数组模拟树的存在情况。intbegin,end;/用begin,end存储区间的起止位置。intcount=0;/用count计数，数数剩余的树的数目。for(i=0;i10001;i+)/赋初值treesi=1;scanf(%d%d,.,24,for(i=0;in;i+)scanf(%d%d,.,25,实现中常见的问题,问题一：数组开的不够大，造成数组越界，有的人数组开成trees10000；问题二：数组trees没有初始化，想当然地认为它会被自动初始化为0；问题三：有些人用区间合并的办法先将要移走树的小区间合并，但是合并算法想得不清楚；问题四：循环的边界没有等号，少数了一棵树；问题五：有人数被移走的树的数目，然后用L去减它，但是忘记了加一(原来有L+1棵树。,.,26,2.4例题：填词,Alex喜欢填词游戏。填词游戏是一个非常简单的游戏。填词游戏包括一个N*M大小的矩形方格盘和P个单词。然后需要把每个方格中填上一个字母使得每个单词都能在方格盘上被找到。每个单词都能被找到要满足下面的条件：每个方格都不能同时属于超过一个的单词。一个长为k的单词一定要占据k个方格。单词在方格盘中出现的方向只能是竖直的或者水平的（可以由竖直转向水平，反之亦然）。你的任务是首先在方格盘上找到所有的单词，当然在棋盘上可能有些方格没有被单词占据。然后把这些没有用的方格找出来，把这些方格上的字母按照字典序组成一个“神秘单词”。,.,27,2.4例题：填词,比如在下图中寻找单词BEG和GEE。,正确,正确,错误，两个E不相邻,错误，同一个E不能用两次,.,28,输入输出格式,输入数据输入的第一行包括三个整数N，M和P(2=M,N=10,0=P=100)。接下来的N行，每行包括M个字符，来表示方格盘。接下来P行给出需要在方格盘中找到的单词。输入保证填词游戏至少有一组答案。输入中给出的字母都是大写字母。输出要求输出“神秘单词”，注意“神秘单词”中的字母要按照字典序给出。,输入样例332EBGGEEEGEBEGGEE输出样例EEG,.,29,解题思路,输入保证填词游戏至少有一组答案这说明我们不必寻找单词所在的位置，只要去掉这些单词所占用的字母就可以了。“神秘单词”中的字母要按照字典序给出说明我们只要知道“神秘单词”中的字母组成就可以了，在字母组成确定的情况下，按字典序输出的方式只有一种。分析到这里我们发现这其实是个很简单的问题。给出一个字母的集合，从中去掉一些在给出单词中出现过的字母，将剩下的字母按字典序输出！,.,30,解题思路,可以定义一个有26个元素的数组，分别记录在输入的矩形中每个字母出现的次数，当读入单词时，将数组中对应到单词中的字母的元素值减一。处理完所有的单词后，将数组中的非0的元素对应的字母依次输出，数组元素的值是几，就输出几次该字母。,输入332EBGGEEEGEBEGGEE,STR,0,2,1,输出EEG,.,31,参考程序,#includeintmain()intcharacters26;charstr200;intn,m,p;/输入的第一行，输入包括一个n*m的矩阵，和p个单词。inti,j;/循环变量for(i=0;i26;i+)/赋初值charactersi=0;scanf(%d%d%d,.,32,for(i=0;in;i+)/读入矩阵，只记录每个字母出现次数scanf(%s,str);for(j=0;strj!=0;j+)charactersstrj-A+;/读入p个单词，并将单词中出现的字母累计数组中去掉for(i=0;ip;i+)scanf(%s,str);for(j=0;strj!=0;j+)charactersstrj-A-;,.,33,/这一段输出所有出现次数大于0的字母。for(i=0;i26;i+)if(charactersi!=0)for(j=0;jcharactersi;j+)printf(%c,i+A);printf(n);,.,34,实现中常见的问题,问题一：对题目理解得不够透彻，尤其对“输入保证填词游戏至少有一组答案”这句话理解不够，想方设法找出单词的填法，结果不能很好解决问题；问题二：题目中没有说明p个单词的长度一定是M，所以读入单词时，数组开小了，造成错误；问题三：如果一个字符一个符地读入，没有略去每行末尾的换行符，也会出错。,.,35,课下练习,1054-105614141410108114211585-:100920142015202120332040208920932096209814122156216010301049,.,36,注意库函数的使用排序函数qsort()函数,排序是最常用的预处理技术。1009FatMouseTrade1412：A+B集合合并,.,37,qsort()函数,qsort包含在头文件中函数根据你给的比较条件进行快速排序排序之后的结果仍然放在原数组中使用qsort函数必须自己写一个比较函数。,.,38,qsort()函数使用,qsort()函数格式qsort(数组名，数组元素个数，每个元素的字节数，比较函数),.,39,一、对整型数组排序,Intmain()inta10=4,2,7,3,6,1,5;inti,n=7;qsort(a,n,sizeof(a0),cmp);for(i=0;i*(double*)b?1:-1;,.,42,四、对结构体数组一级排序,structstudentcharname10;intscore;stu100;,intcmp(constvoid*a,constvoid*b)structstudent*c,*d;c=(structstudent*)a;d=(structstudent*)b;returnd-scorec-score;/降序,按照成绩的值从大到小排序,调用：qsort(stu,100,sizeof(stu0),cmp),.,43,五、对结构体数组二级排序,structstudentcharname10;intscore;stu100;,intcmp(constvoid*a,constvoid*b)str