穷举法 基本思想是首先根据问题的部分条件预估答案的范.ppt

* 穷举法 基本思想是首先根据问题的部分条件预估答案的范围，然后在此范围内对所有可能的情况进行逐一验证，直到全部情况通过了验证为止。若某个情况使验证符合题目的全部条件，则该情况为本题的一个答案；若全部情况验证结果均不符合题目的全部条件，则说明该题无答案。 特点 算法简单，容易理解，但运算量大。通常可以解决“有几种组合”、“是否存在”、求解不定方程等类型的问题。用循环结构实现。 首页 上页 下页 节 末页 结束 循环变量初值 循环条件 循环体 循环变量的增量 进入循环之前执行，只做一次 多次判断 重复执行的语句 多次执行，控制循环结束 while ( ) do –while ( ); for (……） if---goto 适合用在循环次数已知的场合 首页 上页 下页 节 末页 结束 for ( i=999 ; i = 100 ; i-- ) for(i=1;i=9;i++) for(j=1;j=9;j++) {……} i=1时 j=1 j=2 . . j=9 i=2时 . . 要素 语句 嵌套 题1 每只公鸡5个钱，每只母鸡3个钱，每3只小鸡1个钱，用100个钱，买100只鸡，问公鸡、母鸡和小鸡各买几只？ 定义变量 x , y, z , 表示公鸡、母鸡和小鸡的只数 for( x=1; x=100 ;x++) for( y=1; y=100 ; y++) for( z=1;z=100;z++) if( 5*x+ 3*y+ z/3==100 x+y+z==100) 程序运算100万次 首页 上页 下页 节 末页 结束 买100只鸡 100元钱 x 最多为20，y 最多为34，当 x, y 已确定时， z的值为100-x-y，不必对z进行循环。 main( ) { int x,y,z; for (x=1;x20;x++) for(y=1;y=34-x;y++) { z=100-x-y; if ( 5*x+3*y+z/3==100 ) printf(“%d,%d,%d\n”,x,y,z); } } 3 20 77 4 18 78 7 13 80 8 11 81 11 6 83 12 4 84 所求的z不能被3整除如何解决? if ( (5*x+3*y+z/3==100) z%3== 0) printf(“%d,%d,%d\n”,x , y , z); 首页 上页 下页 节 末页 结束 特点 算法简单，容易理解，但运算量大。 首页 上页 下页 节 末页 结束 题4.33 编写程序求出 555555 的约数中最大的三位数是多少 1 理解约数：n% k==0 则 k是n 的约数 2 最大数：从大到小循环，找到一个约数就退出循环 main( ) { int a; for ( a= 999 ; a=100 ; a - -) \*正确地表示三位数的范围 *\ if ( 555555%a==0) \* 如果555555能被a整除 *\ break; \* 结束循环 *\ printf(“%d”,a); } 题4.49 一辆卡车违反交通规则，撞人逃跑了。现场三人目击，记下了车号特征：前两位数字相同，后两位数字相同，四位数恰好是一个整数的平方。求该车号。 1 将车号假定为aabb，是个四位数，a,b的变化范围是1--9 2 四位数的范围是1000---9999，某整数的平方是四位数 3 预估整数的范围：32的平方是1024，94的平方是8836 main( ) { int n,a,b ； for (n=32;n=94;n++) \* n*n是个四位数 *\ for(a=1;a=9;a++) \ * a 的范围 *\ for(b=1;b=9;b++) \* b 的范围 *\ if(n*n == a*1000+a*100+b*10+b) printf(“%d%d%d%d”,a,a,b,b)