内容发布更新时间 : 2025/7/24 1:22:39星期一 下面是文章的全部内容请认真阅读。
// 优化穷举设计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个数字在二重循环中逐个比较: