程序设计讲义之三程序设计讲义之三 枚举算法枚举算法1枚举法也称穷举法、穷举搜索法算法思想算法思想： 对所有可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从众找出那些符合要求的候选解作为问题的解。 算法特点：算法特点： 算法简单，但执行效率低。因此枚举法的关键在于提高编程效率。2例例1、求水仙花数、求水仙花数/ 程序1：对数循环#include void main() int i,a,b,c;for (i=100; i=999; i+)a=i/100;b=i/10%10;c=i%10;if (a*a*a+b*b*b+c*c*c=i)printf(%dn,i);3/ 程序2：对数的各位数字循环#include void main( ) int n,a,b,c;for (a=1; a=9;a+)for (b=0; b=9; b+)for (c=0; c=9; c+)n=a*100+b*10+c;if (n=a*a*a+b*b*b+c*c*c)printf(%dn,n); 4例例2、百鸡百钱问题、百鸡百钱问题设母鸡每只5元，公鸡每只3元，小鸡1元3只。现用100元买100只鸡，求出所有可能的解。算法分析：算法分析：设母鸡、公鸡、小鸡分别为x、y、z只，则应满足下面2个条件：x+y+z=1005x+3y+z/3=100 对于此类实际问题，还需考虑x,y,z的取值范围： 0= x =1000= y =1000= z =100 5/ 程序1：有问题的程序#include void main() int x,y,z;for (x=0; x=100;x+)for (y=0; y=100; y+) for (z=0; z=100; z+) if ( x+y+z=100 & 5*x+3*y+z/3=100 )printf(%d,%d,%dn,x,y,z); 思考：1、上面的程序能否输出所有可能的解？ 2、上面的程序是否输出了错误的解？ 3、上面的程序的时间复杂度？6/ 程序2：正确的程序#include void main() int x,y,z;for (x=0; x=100;x+)for (y=0; y=100; y+) for (z=0; z=100; z+) if ( z%3=0 & x+y+z=100 & 5*x+3*y+z/3=100 )printf(%d,%d,%dn,x,y,z); 问题：上面程序的执行速度太慢，如何解决？7/ 程序3：改进后的程序#include void main() int x,y,z;for (x=0; x=100;x+)for (y=0; y=100; y+)z=100-x-y;if (z%3=0 & 5*x+3*y+z/3=100)printf(%d,%d,%dn,x,y,z); 问题：上面程序的执行速度还可以加快，如何修改？8/ 程序4：对程序3改进后的程序#include void main() int x,y,z;for (x=0; x=20;x+)for (y=0; y=99; y+)z=100-x-y;if ( z%3=0 & 5*x+3*y+z/3=100)printf(%d,%d,%dn,x,y,z); 思考：思考：是否可以将对y的循环改成对z的循环？9/ 程序5：对程序3的另一种改进#include void main() int x,y,z;for (x=0; x=20;x+)for (z=0; z=99; z=z+3)y=100-x-z;if ( 5*x+3*y+z/3=100)printf(%d,%d,%dn,x,y,z); 思考：思考：上面程序的存在什么问题，为什么会出现问题？10例例3、两个乒乓球队进行比赛，各出3人。甲队为A、B、C三人，乙队为X、Y、Z三人。有人向队员打听比赛的名单，A说他不和X比， C说他不和X、Z比，编程找出三对比赛的名单。例例4、现有红、黄、黑、白色球各一个，放置在一个内编号1、2、3、4四个盒子中，每个盒子放置一球，它们的位置未知。小李、小张和小刘的猜测如下：小李认为黑球编号1，黄球编号2；小张认为黑球编号2，白球编号3；小刘认为红球编号2，白球编号4。结果表明他们各猜对了一半。根据他们的猜测确定四个色球在哪个盒子？ 11/例例3：两个乒乓球队比赛：两个乒乓球队比赛#include void main( ) char A,B,C;for (A=X; A=Z; A+)for (B=X; B=Z; B+) for (C=X; C=Z;C+)if ( A!=X & C!=X & C!=Z & A!=B & A!=C & B!=C )printf(A=%c,B=%c,C=%cn,A,B,C); 12例例4 4算法分析算法分析：关键是如何表示“每个人只说对了一个”，也就是说“一个表达式为真，另一个为假”方法方法1 1 相与为假，相或为真方法方法2 2 两个关系表达式的和为1方法方法2 2 两个关系表达式不相等13/程序：红、黄、黑、白色球程序：红、黄、黑、白色球#include void main( ) int a,b,c,d; for (a=1;a=4;a+) for (b=1; b=4; b+) for (c=1; c=4; c+) d=10-a-b-c; if ( (c=1)!=(b=2) & (c=2)!=(d=3) & (a=2)!=(d=4) & a!=b & a!=c & a!=d & b!=c & b!=d & c!=d ) printf(%d,%d,%d,%dn,a,b,c,d); 14例例5、两求边长不大于20的所有直角三角形。#include void main() int a,b,c;for (a=1; a20; a+)for (b=1; b20; b+)for (c=1; c=20; c+) if (a*a+b*b=c*c) printf(a=%d,b=%d,c=%dn,a,b,c);思考：1、上面程序是否输出了多余的解？ 2、如何减少上面程序种循环的次数？ 15/改进后的程序改进后的程序#include void main( ) int a,b,c;for (a=1; a20; a+)for (b=a; b20; b+)for (c=b; c=20; c+)if (a*a+b*b=c*c) printf(a=%d,b=%d,c=%dn,a,b,c);16练习题练习题1 在1500中，找出能同时满足用3除余2，用5除余3，用7除余2的所有整数 。练习题练习题2 如果一个数从左边读和右边读都是同一个数，就称为回文数，例如686就是一个回文数。编程求1000以内所有的既是回文数同时又是素数的自然数。 练习题练习题3 试找出6个小于160而成等差数列的素数。 17/练习题1：如何改进？#include void main() int n;for (n=1; n=500; n+)if (n%3=2 & n%5=3 &n%7=2) printf(%10d,n); 改进后改进后#include void main()int n;for (n=2; n=500; n+=7)if (n%3=2 & n%5=3 ) printf(%10d,n); 18#include int huiwen(int n) / 判断回文数判断回文数 int s=0,x=n;while ( x)s=s*10+x%10; x/=10; return s=n; int sushu(int n) / 判断素数判断素数int i;for (i=2; in; i+)if (n%i=0) return 0;return 1; void main( ) /主函数主函数 int n; for (n=2; n=1000; n+) if ( huiwen(n) & sushu(n) ) printf(%10d,n); /练习题练习题2：设计判断回文数和素数的函数：设计判断回文数和素数的函数19/练习题3：共4个函数（显示、素数、计算、主函数）#include void show(int a ) / 显示数组a int i;for (i=0; i6; i+)printf(%10d,ai);printf(n);int sushu(int n) /判断n是否是素数 int i;for (i=2; in; i+)if (n%i=0) return 0;return n; 20/ a1和a2为等差数列中的前2个数/根据a1和a2来计算等差数列中的后4个数/如果后4个数都是素数，则显示void jisuan(int a ,int a1,int a2) int i;a0=a1;a1=a2;for (i=2;i160 | !sushu(ai) ) break; if (i=6) show(a); 21/主函数void main() int a6,a1,a2,i,j;for (i=2; i160; i+)if ( a1=sushu(i) ) /第1个素数for (j=i+1;j160; j+)if (a2=sushu(j) ) /第2个素数jisuan(a,a1,a2); 22/练习题练习题3的另一种解法：的另一种解法：/设级数为：n，n-d，n-2d，n-3d，n-4d，n-5d。/若这个数全为素数，则为要求的解。/这里d、n均是要寻找的，d最大可为33。#include int sushu(int n) /判断n是否是素数int i;for (i=2; in; i+)if (n%i=0) return 0;return 1; 23#include void main( ) int n,d; for (d=1;d=6; n-) if ( n-5*d1 & sushu(n) & sushu(n-d) & sushu(n-2*d) & sushu(n-3*d)& sushu(n-4*d) & sushu(n-5*d) ) printf(%d,%d,%d,%d,%d,%dn, n,n-d,n-2*d,n-3*d,n-4*d,n-5*d);24练习题练习题4 已知一个正整数的个位数为7，将7移到该数的首位，其它数字顺序不变，则得到的新数恰好是原数的7倍，编程找出满足上述要求的最小自然数。练习题练习题5 在纯粹素数是这样定义的：一个素数，去掉最高位，剩下的数仍为素数，再去掉剩下的数的最高位，余下的数还是素数。这样下去一直到最后剩下的个位数也还是素数。求出所有小于3000的四位的纯粹素数。25/练习题练习题4：无解：无解#include int f(int n) int k,t=n;k=n%10; while ( t9 )k=k*10; t=t/10; return k+n/10; void main( ) int i=7;while ( f(i)!=7*i )i=i+10;printf(%d,%dn,i,f(i) );26/练习题5：共3个函数（素数、计算、主函数）#include int sushu(int n) /判断n是否是素数 for (int i=2; in; i+)if (n%i=0) return 0;return 1; int jisuan(int x) /判断x是否满足条件 int i,t=1000;for (i=1;i=3; i+)if ( !sushu(x) ) return 0; x=x%t; t=t/10;return 1;27/练习题5的主函数void main() int i;for (i=1001; i3000; i=i+2)if ( jisuan(i) )printf(%10d,i);28练习题练习题6 一个自然数，若它的素因数至少是两重的（相同的素因数至少个数为二个，如：36=2*2*3*3），则称该数为“漂亮数”。若相邻的两个自然数都是“漂亮数”，就称它们为“孪生漂亮数”，例如8和9就是一对“孪生漂亮数”。编程再找出一对“孪生漂亮数”。练习题练习题7 若某个自然数的所有小于自身的因数之和恰好等于其自身，则该自然数称为一个完全数。例如：6是一个完全数，6=1+2+3。编程找出三个最小的完全数。 29/练习题练习题6：漂亮数对漂亮数对#include int f(int n) /判断n是否是为“漂亮数” int i,bz1=0,bz2;for (i=2; n1 ;i+)bz2=0;while (n%i=0 )n=n/i; bz2+; bz1+; if ( bz2=1) return 0; if (bz10) return 1; else return 0;30/练习题6：主函数void main() int a=2,i=0;while (i2)if ( f(a) & f(a+1) )printf(%d,%dn,a,a+1); i+; a+;31/练习题练习题7：三个最小的完全数三个最小的完全数#include int f(int n) int i,s=0;for (i=1; in; i+)if ( n%i=0 ) s=s+i;return s; void main() int a=6,i=0;while (i3)if ( f(a)=a )printf(%dn,a); i+; a+;32例例6、求出方程 Xn+Yn = Sn+tn 的最小整数(使方程两边的数值最小)解。其中x，y，s，t，n 均为整数，当给出n之后，求出满足方程的最小整数解，且xt，xs。例如n=2时，满足方程的最小整数解为：52+52= 12+72=50 算法分析：算法分析：由于不能确定x、y、s、t的取值范围，也不能对x和y 设计下面这样的循环（x不可能自增）：for (x=1; ; x+) for (y=1; ; y+) 所以，对方程两边的数值和进行循环。 33#include int f(int x,int n) int s=1,i;for (i=1; i=n; i+)s=s*x;return s; void main() int n,x,y,t,s,m;scanf(%d,&n); 34for (m=1; ;m+) for (x=1;f(x,n)m; x+) for (y=1 ; f(y,n)m; y+) if ( f(x,n)+f(y,n)=m) for (t=2; f(t,n)m; t+) for (s=2; f(s,n)m; s+)if ( f(t,n)+f(s,n)=m & x!=t & x!=s & y!=t) printf(%d,%d,%d,%dn,x,y,t,s);goto abc; abc: ;35练习题练习题8运动会连续开了n天，一共发了m枚奖章，第一天发枚并剩下(m-1)枚的1/7，第二天发枚并剩下的1/7，以后每天按此规律发奖章，在最后一天即第n天发了剩下的n枚奖章。问运动会开了多少天？一共发了几枚奖章？练习题练习题9 五个学生A、B、C、D、E参加某一项比赛。甲、乙两人在猜测比赛的结果。甲猜的名次顺序为A、B、C、D、E，结果没有猜中任何一个学生的名次，也没有猜中任何一对相邻名次（所谓一对相邻名次，是指其中一对选手在名次上邻接。例如与，或者与等）。乙猜的名次顺序为D、A、E、C、B，结果猜中了两个学生的名次，并猜对了两对学生名次是相邻的。问比赛结果如何？36/练习题练习题8 ：运动会奖章：运动会奖章#includevoid main( )int x=0,m,n,bz;do x+; m=7*x+1; n=1; bz=1; while ( mn & bz) m=m-n; if (m % 7=0) m=m/7*6; else bz=0; n+; while ( ! bz ) ;printf(n=%d,m=%dn,n,7*x+1);37练习题练习题9 算法分析：算法分析：设五名选手A、B、C、D、E 分别用变量a、b、c、d、e来表示。通过对关系表达式相加的结果来表示猜测比赛的结果。#includevoid main()int a,b,c,d,e,b1,b2,b3,b4,b5,x1,x2,x3,x4;for (a=1;a=5;a+)for (b=1; b=5; b+)for (c=1; c=5; c+)for (d=1; d0 ) printf(a=%d,b=%d,c=%d,a,b,c); printf(d=%d,e=%dn, d,e); 39例例7 7：0-10-1背包问题背包问题 有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。例如：设限制重量为7，现有4件物品，它们的重量和价值见下表，问如何物品的价值之和最大？物品0123重量5321价值443140 0-1背包问题有很多解法：递归算法（见程序设计培训讲义4）、动态规划算法（程序设计培训讲义9） ，下面是枚举法的解题过程：枚举算法（判断所有可能的解）枚举算法（判断所有可能的解）每种物品都有2种选择：选与不选。设选择物品用1表示，不选择用0表示；则所有可能的解空间为：从100000 到 111 111，每个可能的解有n位。计算出每个可能的解的价值，即可得出最大值。下面程序中的数组bN用来循环所有的解，aN用来表示已求出的最大值的解空间(选择与不选择)，m表示已求出的最大值。41#include# include #define N100float wN,vN,max_w,max_v=0;/ 存放每种物品的重量、价值、限制重量与最大价值int n,aN,bN;/存放物品种数、每种物品选择标记（1:选 0:不选）int pow(int k) /计算所有可能的解的个数2nint i,s=1;for (i=1; i=k; i+) s=s*2;return s; 42void input( ) int i;printf(输入物品种数n);scanf(%d,&n);printf(输入各物品的重量和价值n);for (i=0;in;i+)scanf(%f%f,&wi,&vi);printf(输入限制重量n); scanf(%f,&max_w);43void f( ) /计算解对应的价值int i;float weight=0,value=0;for (i=0; in; i+)if ( bi=1 ) weight+=wi;value+=vi; if ( weightmax_v )max_v=value; /保存最大解的价值for (i=0; in; i+ ) /保存最大解的物品号ai=bi;44void max( )int i,j,t;for (i=0; i=0; j-) /计算对应物品 bj=t%2; t=t/2; f( ); void main( )input( );max();for (int i=0;in;i+)if (ai) printf(%4d,i+1);printf(n最大价值为%.2fn,max_v);45例例8：卡车更新问题：卡车更新问题 某人购置了一辆新卡车, 从事个体运输业务. 给定以下各有关数据（数据为实型, 单位为万元 ）: rt, t=1,2,.,k, 表示已使用过 t 年的卡车, 再工作一年所得的运费, 它 随 t 的增加而减少, k (k20) 年后卡车已无使用价值。 ut, t=1,.,k, 表示已使用过 t 年的卡车, 再工作一年所需的维修费, 它 随 t 的增加而增加。 ct, t=1,2,.,k, 表示已使用过 t 年的旧卡车, 卖掉旧车, 买进新车, 所 需的净费用, 它随 t 的增加而增加。 设某卡车已使用过 t 年, 如果继续使用, 则第 t+1 年回收额为 Rt-Ut, 如果卖掉旧车,买进新车, 则 第 t+1 年回收额为 R0-U0-Ct 46该运输户从某年初购车日起,计划工作 N (N=20) 年, N 年后不论车的状态如 何,不再工作. 为使这 N 年的总回收额最大, 应在哪些年更新旧车? 假定在这 N 年内, 运输户每年只用一辆车, 而且以上各种费用均不改变。 输入: 用文件输入已知数据, 格式为: 第 1 行: N (运输户工作年限) 第 2 行: k (卡车最大使用年限, k20 ) 第 3 行: R0 R1 . Rk 第 4 行: U0 U1 . Uk 第 5 行: C0 C1 . Ck 输出: 用文本文件按以下格式输出结果: 第 1 行: W ( N 年总回收额 ) 第 2-N+1 行: 每行输出 3 个数据: 年序号 是否更新 当年回收额47例: 设给定以下数据: N=4, k=5, i: 0 1 2 3 4 5 Ri: 8 7 6 5 4 2 Ui: 0.5 1 2 3 4 5 Ci: 0 2 3 5 8 10 则正确的输出应该是 24.5 1 0 7.5 2 1 5.5 3 1 5.5 4 0 6.0 48示例输入文件内容：4 58 7 6 5 4 20.5 1 2 3 4 50 2 3 5 8 10 卡车更新问题有很多解法：动态规划算法（见程序设计培训讲义9），下面是枚举法的解题过程：49方法：枚举算法（判断所有可能的解）方法：枚举算法（判断所有可能的解）运输户每年都有2种选择：换新车与不换。设换车用1表示，不换车用0表示；则所有可能的解空间为：从100000 到 111 111，每个可能的解有n位。计算出每个可能的解的价值，即可得出最大值。下面程序中的数组bN用来循环所有的解，aN用来表示已求出的最大值的解空间(换新车与不换)，gN表示已求出的最大值的解空对应的价值,m表示已求出的最大值。说明：第1年一定是用新车。50#include #define N 20float rN,uN,cN,dN,eN,fNN,m=0,gN;int aN,bN=0;int k,n;void output( )int i;printf(nn%fn,m);for (i=1; i=n; i+) printf(%dt%dt%8.1fn,i,ai-1,gi-1); int pow(int k) int i,s=1;for (i=1; i=k; i+) s=s*2;return s; 51void input()int i; char str80;FILE *fp;printf(input :);scanf(%s,str); fp=fopen(str,r);fscanf(fp,%d,&n);fscanf(fp,%d,&k);for (i=0; i=k; i+)fscanf(fp,%f,&ri);for (i=0; i=k; i+)fscanf(fp,%f,&ui);for (i=0; i=k; i+)fscanf(fp,%f,&ci);fclose(fp);52void disp ( ) int i;printf(%dn,n);printf(%dn,k);for (i=0; i=k; i+) printf(%8.1f,ri);printf(n);for (i=0; i=k; i+) printf(%8.1f,ui);printf(n);for (i=0; i=k; i+) printf(%8.1f,ci);printf(n);53void max( )int i,t=1;float m2;m2=d0; g0=d0;for (i=1; im )m=m2;for (i=0; in; i+ )ai=bi;54void main()int i,j,t;input();disp();for (i=0; i=k; i+)di=ri-ui;ei=d0-ci; for (i=0; i=k; i+) fn+1i=0;for (i=1; i=n+1; i+) fik+1=0;for (i=0; ipow(n-1); i+)t=i;for (j=1; jn-1; j+) bj=t%2; t=t/2; max(); output(); 55例例5 5：组合问题：组合问题 找出从自然数1、2、n中任取r个数的所有组合。例如n=5，r=3的所有组合为：（1）5、4、3 （2）5、4、2（3）5、4、1 （4）5、3、2（5）5、3、1 （6）5、2、1 （7）4、3、2 （8）4、3、1（9）4、2、1 （10）3、2、1 枚举法程序见（程序设计讲义枚举法程序见（程序设计讲义4 4）56例例6 6：棋盘问题。：棋盘问题。在44的棋盘上放置8个棋,要求每一行,每一列上只能放置2个。找出所有可能的解并输出解的个数。 (回溯算法见程序设计培训讲义8)枚举思想枚举思想1 1：用二维数组a44存放所有可能的解（1表示放，0表示不放）。依次对数组每一行循环，如果第i行满足条件（2个1），再进入下一行。如果所有行（共4行）都满足条件，说明已生成二维数组a44 ；再判断二维数组a44 所有列（共4列）是否满足条件，如果满足，则输出。57#include int a44=0,sum=0;int f(int x,int i) /将x转换成二进制存入数组的第i行int j,s=0;for (j=3; j=0; j-)aij=x%2; s=s+x%2; x=x/2; if (s=2) return 1; else return 0; void output( ) /输出解for (int i=0; i4; i+)printf(n);for (int j=0; j4; j+)printf(%2d,aij);printf(n);58void pd( ) /判断二维数组a44的每一列是否满足条件int i,j,s;for (j=0;j4; j+)s=0;for (i=0; i4; i+) s=s+aij;if ( s!=2) break;if (s=2) sum+;output( ); 59void main( )int m,n,k,t;for ( m=0; m16; m+) /第0行if ( f(m,0) )for (n=0; n16; n+) /第1行if ( f(n,1) )for ( k=0; k16; k+) /第2行if ( f(k,2) )for ( t=0; t16; t+) /第3行if ( f(t,3) ) pd( );printf(n共有%d个解n,sum);60枚举思想枚举思想2 2：用二维数组a44存放所有可能的解（1表示放，0表示不放）。二维数组a44的所有可能的解有65536种，将m从0循环到65535，并将m转换成二进制存入二维数组a44中。 依次对数组每行每列判断，如果都满足条件（2个1），则输出之。/枚举思想枚举思想2 2源程序：源程序：#include int a44=0,sum=0;61void create(int x) / 将x转换成二进制存入二维数组a44中int i,j;for (i=3; i=0; i-)for (j=3; j=0; j-)aij=x%2; x=x/2; void output( )for (int i=0; i4; i+)printf(n);for (int j=0; j4; j+)printf(%2d,aij);printf(n);62void pd( ) /判断每行每列是否满足条件并输出int i,j,s,bz=1;for (i=0;i4 & bz; i+) /第i行s=0;for (j=0; j4; j+) s=s+aij;if ( s!=2) bz=0;for (j=0;j4 & bz; j+) /第j 列s=0;for (i=0; i4; i+) s=s+aij;if ( s!=2) bz=0;if ( bz ) sum+;output( ); 63#include void main( )long m;for ( m=0; m65535; m+)create(m); /生成二维数组pd( ); /判断并输出printf(n共有%d个解n,sum);试比较上面二种枚举算法的效率？试比较上面二种枚举算法的效率？64思考题思考题1 1：三角形数：三角形数ABCDEF这六个变量排成下图所示的三角形，这六个变量分别取1至6这六个自然数中的一个，且均不相同。求使三角形三条边上的变量之和相等的全部解。ABDFCE16244565思考题思考题2 2：邮票问题：邮票问题邮局发行一套票面有四种不同面值的邮票，若限每封信所贴的邮票张数不能超过三枚。请确定这四种邮票的面值，可以贴出连续数1，2，3，r 值来，找出这四种面值数，使得 r 值为最大。例如，面值为1，4，6，8的四种面值，在一封信上不超过三枚可以贴出如下的连续数: 1, 1+1=2, 1+1+1=3, 4, 1+4=5, 6, 1+6=7, 8, 1+8=9, 1+1+8=10, 1+4+6=11, 4+8=12 ,1+4+8=13, 4+4+6=14, 1+6+8=15, 8+8=16 , 1+8+8=17, 4+6+8=18 , 4+8+8=20。虽然可以贴出20，但因为19这个数无法贴出所以 r=18。通用的递推算法见国际大学生程序设计竞赛辅导教程P11066