《第十周枚举一.ppt》由会员分享，可在线阅读，更多相关《第十周枚举一.ppt（33页珍藏版）》请在三一办公上搜索。
1、第十讲,枚举(一),ACM算法与程序设计,2/33,求高精度幂,1、链接地址 http:/problem?id=10012、问题描述 对数值很大、精度很高的数进行高精度计算是一类十分常见的问题。比如，对国债进行计算就是属于这类问题。现在要你解决的问题是：对一个实数R(0.0 R 99.999)，要求写程序精确计算 R 的 n 次方(Rn)，其中n 是整数并且 0 n=25。,3/33,问题描述,输入格式输入包括多组 R 和 n。R 的值占第 1 到第 6 列，n 的值占第 8 和第 9 列。输出要求对于每组输入，要求输出一行，该行包含精确的 R 的 n 次方。输出需要去掉前导的 0 后不要的
2、0。如果输出是整数，不要输出小数点。,4/33,Description,输入样例95.123 120.4321 205.1234 156.7592 998.999 101.0100 12输出样例548815620517731830194541.899025343415715973535967221869852721.0000000514855464107695612199451127676715483848176020072635120383542976301346240143992025569.9285737012664880411466549933187037075116662954767
3、2049395302429448126.76412102161816443020690903717327667290429072743629540498.1075960194566517745610440100011.126825030131969720661201,5/33,解决本题的基本思路是把底数转化为整数，同时记住原数有几位小数(注意不能包括末尾多余的0)，在高精度乘法结束后再添加上小数点即可。为便于计算，可定义一个结构体表示一个大整数，如下：typedef struct/记录数的长度，减少循环int numberLEN;int len;digit;在运算结束时，添加小数点要注意小数位
4、与高精度乘法结果有3种可能的关系：(1)小数位数整数位。注意小数位数也可能为0。,3、解题思路,6/33,4、参考程序,#include#define LEN 150typedef struct/记录数的长度，减少循环 int numberLEN;int len;digit;/a,b是乘数，c是积void multiply(digit*a,digit*b,digit*c)int i,j,t;c-len=a-len+b-len;/先乘，后进位 for(i=0;i len;i+)/清零 c-numberi=0;,7/33,4、参考程序,for(i=0;i len;i+)/逐位作乘法 for(j=0
5、;j len;j+)c-numberi+j+=a-numberj*b-numberi;for(i=0;i len-1;i+)/统一进位 if(c-numberi=10)c-numberi+1+=c-numberi/10;c-numberi%=10;/积的最大长度为两数长度之和，最小为之和减1 for(i=c-len;c-numberi=0;i-)c-len-;,8/33,4、参考程序,int main(void)char str7;/按字符串的方式读入第一个数R int i,n,m,s,t;digit a,b,c;while(scanf(%s%d,str,9/33,4、参考程序,if(n=1)
6、/1次方，直接输出 for(i=s;i t;i+)printf(%c,stri);if(stri=.)/注意若R是整数，则str为25.的形式 printf(n);else printf(%cn,stri);else multiply(,10/33,4、参考程序,if(m=0)/没有小数 for(i=c.len-1;i=0;i-)printf(%d,c.numberi);printf(n);else if(m*n=m*n;i-)printf(%d,c.numberi);printf(.);for(;i=0;i-)printf(%d,c.numberi);printf(n);else/(m*n
7、c.len)小数位比结果数位多 printf(.);for(i=0;i=0;i-)printf(%d,c.numberi);printf(n);return 0;,11/33,什么是枚举,枚举是基于已有的知识进行答案猜测的一种问题求解策略。通常是根据建立的数学模型中的一组变量及其条件，在条件允许的范围内对变量依次取值，判断所取的值是否满足数学模型中的条件，直到找到(全部)符合条件的值为止。使用时注意以下三方面的问题：建立简洁的数学模型。数学模型中变量的数量要尽量少，它们之间相互独立。减小搜索的空间。利用已有的知识，缩小数学模型中各个变量的取值范围，避免不必要的计算。采用合适的搜索顺序。对搜索空
8、间的遍历顺序要与数学模型中的条件表达式一致。,12/33,生理周期,1、链接地址 http:/2、问题描述人生来就有三个生理周期，分别为体力、感情和智力周期，它们的周期长度为23 天、28 天和33 天。每一个周期中有一天是高峰。在高峰这天，人会在相应的方面表现出色。例如，智力周期的高峰，人会思维敏捷，精力容易高度集中。因为三个周期的周长不同，所以通常三个周期的高峰不会落在同一天。对于每个人，我们想知道何时三个高峰落在同一天。,13/33,问题描述,对于每个周期，我们会给出从当前年份的第一天开始，到出现高峰的天数（不一定是第一次高峰出现的时间）。你的任务是给定一个从当年第一天开始数的天数，输出
9、从给定时间开始（不包括给定时间）下一次三个高峰落在同一天的时间（距给定时间的天数）。例如：给定时间为10，下次出现三个高峰同天的时间是12，则输出2（注意这里不是3）。,14/33,问题描述,输入格式输入四个整数：p,e,i 和d。p,e,i 分别表示体力、情感和智力高峰出现的时间（时间从当年的第一天开始计算）。d 是给定的时间，可能小于p,e,或 i。所有给定时间是非负的并且小于365,所求的时间小于等于21252。输出要求从给定时间起，下一次三个高峰同天的时间（距离给定时间的天数）。,15/33,问题描述,输入样例0 0 0 00 0 0 1005 20 34 3254 5 6 7283
10、102 23 320203 301 203 40-1-1-1-1,输出样例Case 1:the next triple peak occurs in 21252 days.Case 2:the next triple peak occurs in 21152 days.Case 3:the next triple peak occurs in 19575 days.Case 4:the next triple peak occurs in 16994 days.Case 5:the next triple peak occurs in 8910 days.Case 6:the next tri
11、ple peak occurs in 10789 days.,16/33,假设从当年的第一天开始数，第x 天时三个高峰同时出现。符合问题要求的x 必需大于d、小于等于21252，并满足下列三个条件：(1)(x-p)%23=0(2)(x-e)%28=0(3)(x-i)%33=0 在搜索空间d+1，21252中，对每个猜测的答案都进行三个条件的判断，开销很大，也没有必要。首先从搜索空间d+1，21252中找到符合条件(1)的全部时间，然后从这些时间中寻找符合条件(2)、(3)的时间，可以将对条件(2)、(3)的判定次数减少为原来的1/23。用同样的办法，可以继续减少对条件3)的判定次数。,3、解题
12、思路,17/33,对每一组数据，分别执行下列算法：读入p,e,i,d从d+1 循环到21252，找到第一个满足条件(1)的时间a、并跳出循环从a 循环到21252，找到第一个满足条件(2)的时间b、并跳出循环从b 循环到21252，找到第一个满足条件(3)的时间x、并跳出循环输出x-d,3、解题思路,18/33,4、参考程序,#include void main()int p,e,i,d,j,no=1;scanf(%d%d%d%d,19/33,称硬币,1、链接地址 http:/2、问题描述 赛利有12枚银币。其中有11枚真币和1枚假币。假币看起来和真币没有区别，但是重量不同。但赛利不知道假币比
13、真币轻还是重。于是他向朋友借了一架天平。朋友希望赛利称三次就能找出假币并且确定假币是轻是重。例如：如果赛利用天平称两枚硬币，发现天平平衡，说明两枚都是真的。如果赛利用一枚真币与另一枚银币比较，发现它比真币轻或重，说明它是假币。经过精心安排每次的称量，赛利保证在称三次后确定假币。,20/33,问题描述,输入格式第一行有一个数字n，表示有n组测试用例。对于每组测试用例：输入有三行，每行表示一次称量的结果。赛利事先将银币标号为A-L。每次称量的结果用三个以空格隔开的字符串表示：天平左边放置的硬币 天平右边放置的硬币 平衡状态。其中平衡状态用”up”,“down”,或”even”表示,分别为右端高、右
14、端低和平衡。天平左右的硬币数总是相等的。输出要求输出哪一个标号的银币是假币，并说明它比真币轻还是重(heavy or light)。,21/33,问题描述,输入样例1ABCD EFGH even ABCI EFJK up ABIJ EFGH even输出样例K is the counterfeit coin and it is light.,22/33,此题中赛利已经设计了正确的称量方案，保证从三组称量数据中能得到唯一的答案。答案可以用两个变量表示：x-假币的标号、w-假币是比真币轻还是比真币重。x共有12种猜测；w有2种猜测。根据赛利设计的称量方案，(x，w)的24种猜测中，只有唯一的猜测与
15、三组称量数据都不矛盾。因此，如果猜测(x，w)满足下列条件，这个猜测就是要找的答案：在称量结果为even 的天平两边，没有出现x；如果w表示假币比真币轻，则在称量结果为up 的天平右边一定出现x、在称量结果为down 的天平左边一定出现x；如果w表示假币比真币重，则在称量结果为up 的天平左边一定出现x、在称量结果为down 的天平右边一定出现x。,3、解题思路,23/33,具体实现时，要注意两点：(1)选择合适的算法对于每一枚硬币x 逐个试探：x 比真币轻的猜测是否成立？猜测成立则进行输出。x 比真币重的猜测是否成立？猜测成立则进行输出。(2)选择合适的数据结构以字符串数组存储称量的结果。每
16、次称量时，天平左右最多有6 枚硬币。因此，字符串的长度需要为7，最后一位存储字符串的结束符0，便于程序代码中使用字符串操作函数。char left37,right37,result37;,3、解题思路,24/33,4、参考程序,#include#include char left37,right37,result35;bool isHeavy(char x);bool isLight(char x);int main(void)int i,n;char c;scanf(%d,25/33,4、参考程序,for(c=A;c=L;c+)if(isLight(c)printf(%c is the co
17、unterfeit coin and it is light.n,c);break;if(isHeavy(c)printf(%c is the counterfeit coin and it is heavy.n,c);break;n-;return 0;,26/33,4、参考程序,bool isLight(char x)/判断硬币x 是否为轻的代码 int i;for(i=0;i 3;i+)/判断是否与三次称量结果矛盾 switch(resulti0)case u:if(strchr(righti,x)=NULL)return false;break;case e:if(strchr(rig
18、hti,x)!=NULL|strchr(lefti,x)!=NULL)return false;break;case d:if(strchr(lefti,x)=NULL)return false;break;return true;,27/33,4、参考程序,bool isHeavy(char x)/判断硬币x 是否为重的代码 int i;for(i=0;i 3;i+)/判断是否与三次称量结果矛盾 switch(resulti0)case u:if(strchr(lefti,x)=NULL)return false;break;case e:if(strchr(righti,x)!=NULL|
19、strchr(lefti,x)!=NULL)return false;break;case d:if(strchr(righti,x)=NULL)return false;break;return true;,28/33,完美立方,1、链接地址 http:/2、问题描述 a3=b3+c3+d3为完美立方等式。例如123=63+83+103。编写一个程序，对任给的正整数N(N100)，寻找所有的四元组(a,b,c,d)，使得a3=b3+c3+d3，其中a,b,c,d 大于1，小于等于N。,29/33,问题描述,输入格式正整数N(N100)输出要求每行输出一个完美立方，按照a的值，从小到大依次输出
20、。当两个完美立方等式中a的值相同，则依次按照b、c、d进行非降升序排列输出，即b值小的先输出、然后c值小的先输出、然后d值小的先输出。,30/33,问题描述,输入样例24输出样例Cube=6,Triple=(3,4,5)Cube=12,Triple=(6,8,10)Cube=18,Triple=(2,12,16)Cube=18,Triple=(9,12,15)Cube=19,Triple=(3,10,18)Cube=20,Triple=(7,14,17)Cube=24,Triple=(12,16,20),31/33,此题的思路非常简单：给定4 个整数的四元组(a、b、c、d)，判断它们是否满足
21、完美立方等式a3=b3+c3+d3。对全部的四元组进行排序，依次进行判断。如果一个四元组满足完美立方等式，则按照要求输出。先判断a值小的四元组；两个四元组的a 值相同，则先判断b值小的；两个四元组的a值和b值分别相同，则先判断c值小的。关键是解决两个方面的问题：,3、解题思路,32/33,(1)确定全部需要判断的四元组，并对它们进行排序。稍作分析不难发现，在这个序列中，任意一个四元组(a、b、c、d)：(a)a6，因为a 最小必须是5，才能使得b、c、d 分别是3 个大于1 的不同整数，但(5、2、3、4)不满足完美立方等式的要求；(b)如果(a、b、c、d)满足完美立方等式，则b、c、d 都要比a 小。(2)避免对一个整数的立方的重复计算。2,N中的每个整数i，在整个需要判断的四元组序列中都反复出现。每出现一次，就要计算一次它的立方。在开始完美立方等式的判断之前，先用一个数组保存2,N中的每个整数的立方值。在判断四元组(a、b、c、d)是否满足完美立方等式的要求时，直接使用存储在数组中的立方值。,3、解题思路,33/33,4、参考程序,#include#include int main(void)int i,n,a,b,c,d;long cube101;scanf(%d,
