第八章 枚举.ppt

第八章 枚 举 8.1 基本思想 8.2 简单枚举的例子：生理周期 8.3 数学模型中包括多个变量的例子：称硬币 8.4 有哪些信誉好的足球投注网站空间中解不唯一的例子：完美立方 8.5 遍历有哪些信誉好的足球投注网站空间的例子：熄灯问题 8.6 优化判断条件的例子：讨厌的青蛙 求小于N的最大素数 #include stdio.h int isprime(int n) { int j; for (j=2;jn;j++) if (n%j==0) return 0; return 1; } void main( ) { int n,N,i; scanf(%d,N); n=2; for (i=3;iN;i=i+2) if (isprime(i)) n=i; printf(小于%d的最大素数是%d\n,N,n); } 例：百钱买百鸡问题：有一个人有一百块钱，打算买一百只鸡。到市场一看，大鸡三块钱一只，小鸡一块钱三只，不大不小的鸡两块钱一只。 以三种鸡的个数为枚举对象（分别设为x,y,z）,以三种鸡的总数（x+y+z）和买鸡用去钱的总数(x*3+y*2+z)为判定条件，穷举各种鸡的个数。 for x=1 to 100 for y=1 to 100 for z=1 to 100 if (x+y+z=100) (x*3+y*2+z/3=100)(z%3=0) printf(“x=%d,y=%d,z=%d”,x,y,z); 上面条件进行优化，三种鸡的和固定100，枚举x和y，第三种鸡根据约束条件求z=100-x-y，这样就缩小枚举范围 x的取值范围可以改为1~33，y的取值范围可以改为1~49 for x=1 to 33 for y=1 to 49 { z=100-x-y; if (x*3+y*2+z/3=100)(z%3=0) printf(“x=%d,y=%d,z=%d”,x,y,z); } 水仙花数 #include stdio.h void main( ) {int a,b,c,x; for (a=1;a=9;a++) for (b=0;b=9;b++) for (c=0;c=9;c++) { x=a*100+10*b+c; if (a*a*a +b*b*b +c*c*c == x) printf(%d ,x); } } 生理周期 问题描述 人有体力、感情和智力三个生理周期，其长度为23、28和33天。每一个周期中有一天是高峰，如人处于智力高峰期，会思维敏捷。对于每个人，想知道三个高峰何时在同一天。 对于每个周期，给出从当前年份第一天到出现高峰的天数（不一定是第一次高峰出现的时间）。输出从给定时间开始（不包括给定时间）下一次三个高峰落在同一天的时间（距给定时间的天数）。 输入数据 p,e,i表示体力、情感和智力高峰出现的时间，d是给定时间，可能小于p,e或i。所有给定时间是非负的并且小于365,所求的时间小于等于21252＝28*23*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)的判定次数。 1)读入p, e, i, d 2)从d+1到21252，找到第一个满足条件1)的时间a、并跳出循环 3)从a到21252(a每次增加23)，找到满足条件2)的时间b结束循环 4)从b到21252(b每次增加23*28)，找满足条件3)的时间x结束循环 5)输出x-d 生理周期 #include stdio.h void main( ) {int p,e,i,d,j,no=1; scanf(%d%d%d%d, p, e, i, d); while (p!=-1 e!=-1 i!=-1 d!=-1) { for(j=d+1; j21252; j++) if ((j-p)%23 == 0) break; for( ; j21252; j=j+23) if ((j-e)%28