第十周枚举一.ppt

第十讲,枚举(一),ACM算法与程序设计,2/33,求高精度幂,1、链接地址 http:/acm.pku.edu.cn/JudgeOnline/ problem?id=1001 2、问题描述 对数值很大、精度很高的数进行高精度计算是一类十分常见的问题。比如，对国债进行计算就是属于这类问题。 现在要你解决的问题是：对一个实数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 后不要的 0 。如果输出是整数，不要输出小数点。,4/33,Description,输入样例 95.123 12 0.4321 20 5.1234 15 6.7592 9 98.999 10 1.0100 12 输出样例 548815620517731830194541.899025343415715973535967221869852721 .00000005148554641076956121994511276767154838481760200726351203835429763013462401 43992025569.928573701266488041146654993318703707511666295476720493953024 29448126.764121021618164430206909037173276672 90429072743629540498.107596019456651774561044010001 1.126825030131969720661201,5/33,解决本题的基本思路是把底数转化为整数，同时记住原数有几位小数(注意不能包括末尾多余的0)，在高精度乘法结束后再添加上小数点即可。 为便于计算，可定义一个结构体表示一个大整数，如下： typedef struct/记录数的长度，减少循环 int numberLEN; int len; digit; 在运算结束时，添加小数点要注意小数位与高精度乘法结果有3种可能的关系：(1)小数位数整数位。 注意小数位数也可能为0。,3、解题思路,6/33,4、参考程序,#include #define LEN 150 typedef 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; 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) /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 c.len) 小数位比结果数位多 printf(“.“); for(i = 0; i = 0; i-) printf(“%d“,c.numberi); printf(“n“); return 0; ,11/33,什么是枚举,枚举是基于已有的知识进行答案猜测的一种问题求解策略。通常是根据建立的数学模型中的一组变量及其条件，在条件允许的范围内对变量依次取值，判断所取的值是否满足数学模型中的条件，直到找到(全部)符合条件的值为止。 使用时注意以下三方面的问题： 建立简洁的数学模型。数学模型中变量的数量要尽量少，它们之间相互独立。 减小搜索的空间。利用已有的知识，缩小数学模型中各个变量的取值范围，避免不必要的计算。 采用合适的搜索顺序。对搜索空间的遍历顺序要与数学模型中的条件表达式一致。,12/33,生理周期,1、链接地址 http:/poj.grids.cn/problem?id=2977 2、问题描述 人生来就有三个生理周期，分别为体力、感情和智力周期，它们的周期长度为23 天、28 天和33 天。每一个周期中有一天是高峰。在高峰这天，人会在相应的方面表现出色。例如，智力周期的高峰，人会思维敏捷，精力容易高度集中。因为三个周期的周长不同，所以通常三个周期的高峰不会落在同一天。对于每个人，我们想知道何时三个高峰落在同一天。,13/33,问题描述,对于每个周期，我们会给出从当前年份的第一天开始，到出现高峰的天数（不一定是第一次高峰出现的时间）。你的任务是给定一个从当年第一天开始数的天数，输出从给定时间开始（不包括给定时间）下一次三个高峰落在同一天的时间（距给定时间的天数）。例如：给定时间为10，下次出现三个高峰同天的时间是12，则输出2（注意这里不是3）。,14/33,问题描述,输入格式 输入四个整数：p, e, i 和d。 p, e, i 分别表示体力、情感和智力高峰出现的时间（时间从当年的第一天开始计算）。d 是给定的时间，可能小于p, e, 或 i。 所有给定时间是非负的并且小于365, 所求的时间小于等于21252。 输出要求 从给定时间起，下一次三个高峰同天的时间（距离给定时间的天数）。,15/33,问题描述,输入样例 0 0 0 0 0 0 0 100 5 20 34 325 4 5 6 7 283 102 23 320 203 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 triple 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、解题思路,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:/poj.grids.cn/problem?id=2692 2、问题描述 赛利有12枚银币。其中有11枚真币和1枚假币。假币看起来和真币没有区别，但是重量不同。但赛利不知道假币比真币轻还是重。于是他向朋友借了一架天平。朋友希望赛利称三次就能找出假币并且确定假币是轻是重。 例如：如果赛利用天平称两枚硬币，发现天平平衡，说明两枚都是真的。如果赛利用一枚真币与另一枚银币比较，发现它比真币轻或重，说明它是假币。经过精心安排每次的称量，赛利保证在称三次后确定假币。,20/33,问题描述,输入格式 第一行有一个数字n，表示有n组测试用例。 对于每组测试用例：输入有三行，每行表示一次称量的结果。赛利事先将银币标号为A-L。每次称量的结果用三个以空格隔开的字符串表示：天平左边放置的硬币 天平右边放置的硬币 平衡状态。其中平衡状态用”up”, “down”, 或”even”表示, 分别为右端高、右端低和平衡。天平左右的硬币数总是相等的。 输出要求 输出哪一个标号的银币是假币，并说明它比真币轻还是重(heavy or light)。,21/33,问题描述,输入样例 1 ABCD 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种猜测中，只有唯一的猜测与三组称量数据都不矛盾。因此，如果猜测(x，w )满足下列条件，这个猜测就是要找的答案： 在称量结果为“even'' 的天平两边，没有出现x ； 如果w表示假币比真币轻，则在称量结果为“up'' 的天平右边一定出现x、在称量结果为“down'' 的天平左边一定出现x； 如果w表示假币比真币重，则在称量结果为“up'' 的天平左边一定出现x、在称量结果为“down'' 的天平右边一定出现x。,3、解题思路,23/33,具体实现时，要注意两点： (1) 选择合适的算法 对于每一枚硬币x 逐个试探： x 比真币轻的猜测是否成立？猜测成立则进行输出。 x 比真币重的猜测是否成立？猜测成立则进行输出。 (2) 选择合适的数据结构 以字符串数组存储称量的结果。每次称量时，天平左右最多有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 counterfeit 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(righti, 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 | strchr(lefti, x) != NULL) return false; break; case 'd': if(strchr(righti, x) = NULL) return false; break; return true; ,28/33,完美立方,1、链接地址 http:/poj.grids.cn/problem?id=2810 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的值，从小到大依次输出。当两个完美立方等式中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)，判断它们是否满足完美立方等式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 “, ,