程序设计培训讲义3：枚举算法.ppt

//练习题7：三个最小的完全数 #include stdio.h 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(%d\n,a); i++; } a++; } } 例6、求出方程 Xn　+　Yn = Sn　+　tn 的最小整数(使方程两边的数值最小)解。其中x，y，s，t，n 均为整数，当给出n之后，求出满足方程的最小整数解，且x≠t，x≠s。例如n=2时，满足方程的最小整数解为： 5^2+5^2= 1^2+7^2=50 算法分析： 由于不能确定x、y、s、t的取值范围，也不能对x和y 设计下面这样的循环（x不可能自增）： for (x=1; ; x++) { for (y=1; ; y++) …… } 所以，对方程两边的数值和进行循环。 #include stdio.h 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); for (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,%d\n,x,y,t,s); goto abc; } } } abc: ; } 练习题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，结果猜中了两个学生的名次，并猜对了两对学生名次是相邻的。问比赛结果如何？ //练习题8 ：运动会奖章 #include stdio.h void 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=%d\n,n,7*x+1); } 练习题9 算法分析： 设五名选手A、B、C、D、E 分别用变量a、b、c、d、e来表示。 通过对关系表达式相加的结果来表示猜测比赛的结果。 #include stdio.h void 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; d=5; d++) { e=15-a-b-c-d; b1= (a==1) + (b==2) + (c==3) + (d==4) + (e==5); x1=b-a; x2=c-b; x3=d-c; x4=e-d; b2=(x1==1) + (x2==1) + (x3==1) + (x4==1); b3=(d==1) + (a==2) + (e==3) + (c==4) + (b==5); x1=a-d; x2=e-a; x3=c-e; x4=b-c; b4=(x1==1) + (x2==1) + (x3==1) + (x4==1);