内容发布更新时间 : 2024/5/22 18:39:33星期一 下面是文章的全部内容请认真阅读。

// 优化穷举设计3 #include

void main()

{int p1,p2,p3,p4,p5,p6,n; long m=0; printf(\

printf(\分 2分 5分 1角 2角 5角 \\n\

for(p2=0;p2<=n/2;p2++)

for(p3=0;p3<=(n-2*p2)/5;p3++) // 缩减p3,p4,p5,p6循环范围 for(p4=0;p4<=(n-2*p2-5*p3)/10;p4++)

for(p5=0;p5<=(n-2*p2-5*p3-10*p4)/20;p5++) for(p6=0;p6<=(n-2*p2-5*p3-10*p4-20*p5)/50;p6++) {p1=n-(2*p2+5*p3+10*p4+20*p5+50*p6); if(p1>=0) {m++;

printf(\ printf(\ }

}

printf(\}

运行程序，输入n=500，即得5元整币兑换成1分、2分、5分、1角、2角、5角共6?种零币的不同兑换种数为

500(1,2,5,10,20,50)=3937256 6. 以上3个穷举设计比较

以上3个穷举求解程序体现了程序的改进与优化过程，因循环设置的差异与循环参量的不同，直接影响程序求解的速度。

由以上穷举设计1到精简循环改进设计2，到进一步优化设计3，循环次数逐步精简，程序运行时间逐步缩减。测试3个穷举算法中条件判断语句执行次数如表2.1所示。

表2.1

n取值 整币兑零穷举设计1 精简循环设计2 优化穷举设计3 3个穷举算法中条件判断语句执行次数比较

100 21 417 858 212 058 4 562 200 961 353 855 4 782 855 69 118 500 1.8e+11 369 769 686 3 937 256 由表2.1所列举的数据可见，求解同一个问题的穷举设计，精简循环的求解时间缩减为原穷举设计的数百分之一，而优化算法的求解时间缩减为精简循环设计的数百分之一。由此可见，算法的改进与优化对于提高求解效率的作用。

26

由于穷举计算所需的时间随n增加而迅速增加，以致当n比较大或所兑零币种数增多时求解变得无望，改进算法才能快速解决整币兑零种数问题。

2.8.2 完美综合式

1. 案例提出

把数字1,2,...,9这9个数字填入以下含加减乘除与乘方的综合运算式中的9个□中,?使得该式成立

□^□+□□÷□□-□□×□=0

要求数字1,2,...,9这9个数字在各式中都出现一次且只出现一次，且约定数字“1”不出现在乘、乘方的一位数中（即排除各式中的各个1位数为1这一平凡情形）。

2. 设计要点

式中含有加减乘除与乘方5种运算，求解难度更大些。

设式右的6个整数从左至右分别为 a,b,z,c,d,e,其中z,c,d为2位整数，a,b,e为大于1的一位整数。因式中有乘方，6个变量设置为double型。

设置a,b,c,d,e,z循环，对每一组a,b,c,d,e,z，进行以下检测: （1）若z不是c的倍数, 即fmod(z,c)!=0，则返回继续； （2）若等式不成立，即pow(a,b)+z/c!=d*e, 则返回继续； （3）式中9个数字是否存在相同数字。

对6个整数共9个数字进行分离，分别赋值给数组f[1]——f[9]。连同附加的f[0]=0，共10个数字在二重循环中逐个比较：

若存在相同数字，t=1，不作输出。

若不存在相同，即式中9 个数字为1——9不重复，保持标记t=0, 则输出所得的完美综合运算式。

设置n统计解的个数。 3. 程序实现

// 含乘方的完美综合运算式

#include #include void main()

{double a,b,c,d,e,z; int j,k,t,n,f[11];

printf(\□^□+□□/□□-□□*□=0 \\n\ n=0;

for(a=2;a<=9;a++)

for(b=2;b<=9;b++) for(c=12;c<=98;c++)

for(d=12;d<=98;d++) // 对a,b,c,d,e 实施穷举

27

for(e=2;e<=9;e++) for(z=12;z<=98;z++)

{if(fmod(z,c)!=0) continue;

if(pow(a,b)+z/c!=d*e) continue; t=0;

f[0]=0;f[1]=a;f[2]=b;f[3]=e; // 9个数字赋给f数组 f[4]=fmod(c,10);f[5]=floor(c/10); f[6]=fmod(d,10);f[7]=floor(d/10); f[8]=fmod(z,10);f[9]=floor(z/10); for(k=0;k<=8;k++)

for(j=k+1;j<=9;j++) if(f[k]==f[j])

{t=1; break;} // 检验数字是否有重复 if(t==0)

{ n++; // 输出一个解，用n统计个数

printf(\printf(\ } } }

4. 程序运行结果

□^□+□□/□□-□□*□=0

1: 3^5+87/29-41*6=0 2: 7^3+28/14-69*5=0 3: 7^3+82/41-69*5=0

5. 完美综合运算式优化 (1) 优化设计要点

所有量设置在整数范围内取值，其中a^b用a自乘b次即可。 即要求的综合运算式为

a^b+z/c-d*e=0

设置a,b,c,d,e循环，对每一组a,b,c,d,e，计算z=(d*e-a^b)*c。同样是穷举，这样处理，可省略z循环，同时省略z是否能被c整除，省略等式是否成立的检测。

计算z后，只要检测z是否为二位数即可。若计算所得z非二位数，则返回。 然后分别对6个整数进行数字分离，设置f数组对6个整数分离的共9个数字进行统计，f(x)即为数字x(1—9)的个数。

若某一f(x)不为1，不满足数字1,2,...,9这九个数字都出现一次且只出现一次，标记t=1.

若所有f(x)全为1，满足数字1,2,...,9这九个数字都出现一次且只出现一次，保持标记t=0, 则输出所得的完美综合运算式。

28

(2) 优化程序设计

// 完美综合运算式优化

#include #include void main()

{int a,b,c,d,e,k,t,n,x,y,z,m[7],f[10]; printf(\□^□+□□/□□-□□*□=0 \\n\ n=0;

for(a=2;a<=9;a++) for(b=2;b<=9;b++)

for(c=12;c<=98;c++)

for(d=12;d<=98;d++) // 对a,b,c,d,e 实施穷举 for(e=2;e<=9;e++)

{ for(t=1,k=1;k<=b;k++) t=t*a;

z=(d*e-t)*c;

if(z<10 || z>98) continue;

m[1]=a;m[2]=b;m[3]=c;m[4]=d;m[5]=e;m[6]=z;

for(x=0;x<=9;x++) f[x]=0; for(k=1;k<=6;k++) { y=m[k]; while(y>0)

{ x=y;f[x]=f[x]+1;

y=y/10; // 分离数字f数组统计 }

}

for(t=0,x=1;x<=9;x++)

if(f[x]!=1) {t=1;break;} // 检验数字1-9各出现一次 if(t==0) // 输出一个解，用n统计个数 { n++;

printf(\printf(\

} } }

优化程序还是得到以上三个解，但可读性好，且运行要快得多。

2.8.3 和积三角形

1. 案例提出

29

把和为正整数s（s≥36）的8个互不相等的正整数填入8数字三角形(如图1所示)中，若三角形三边上的数字之和相等(s1)且三边上的数字之积也相等(s2)，该三角形称为和积三角形。

图1 8数字三角形

1) 存在和积三角形,s至少为多大? 写出此时的和积三角形。

2) s=89时存在多少个不同的和积三角形? 分别写出此时的和积三角形。

2. 求解要点

把和为s的8个正整数存储于b数组b(1)，?，b(8)，分布如图2所示。为避免重复，不妨约定三角形中数字“下小上大、左小右大”，即 b(1)

b(4) b(3) b(5) b(2) b(6) b(1) b(8) b(7)

图2 b数组分布示意图

可以根据约定对b(1)、b(7)的值进行循环探索，设置:

b(1)的取值范围为1—(s-21)/2；（因除b(1),b(4)外其他6个数之和至少为21） b(7)的取值范围为b(1)+1—(s-28)；（因其他7个数之和至少为28） b(4)的取值范围为1—(s-28)；（因其他7个数之和至少为28） 同时据b(2)

b(8)=s-(b(1)+b(2)+b(3)+b(4)+b(5)+b(6)+b(7)) 对所取的8个整数，进行以下4道检测： 1） 若b(8)<=0，则返回；

2） 若这8个数出现相同数，则返回；

30