内容发布更新时间 : 2024/5/19 2:21:24星期一 下面是文章的全部内容请认真阅读。

这样处理，能较快的找出所有解，既无重复，也没有遗漏。

3. 三阶素数幻方程序设计

// 指定区间内素数构造三阶素数幻方 #include #include void main()

{int c,d,j,k,n,t,t1,t2,w,x,y,z,m=0; int a[3000];

printf(\请确定区间下限c,上限d: \ scanf(\ if(c%2==0) c=c+1;

for(k=c;k<=d;k++) a[k]=0; for(k=c;k<=d;k+=2)

{for(t=0,j=3;j<=sqrt(k);j+=2) if(k%j==0) {t=1;break;}

if(t==0) a[k]=1; // [c,d]中的奇数k为素数，标注1 } for(k=c;k

{n=k; // 探索合适的 n,x,y for(y=2;y<=d-n-1;y+=2)

for(x=y+2;x<=d-n;x+=2) { z=x-y;w=x+y;

if(x==2*y || n-wd)

continue; // 控制幻方的素数范围 t1=a[n-w]*a[n+w]*a[n-z]*a[n+z]; t2=a[n-x]*a[n+x]*a[n-y]*a[n+y];

if(t1*t2==0) continue; // 控制其余8个均为素数

m++;

printf(\统计并输出三阶素数幻方 printf(\ printf(\ printf(\ } }

printf(\共 %d 个素数方阵.\\n\ }

4. 程序运行示例

21

请确定区间下限c,上限d: 300,600 NO 1: 401 563 419 479 461 443 503 359 521 共 1 个素数方阵.

2.7.2 指定幻和的三阶素数方阵

1. 案例提出

试寻求9个素数，构造一个3阶素数幻方，使得该素数方阵中3行、3列与两对角线上的3个素数之和均等于给定的整数s。

2. 设计要点

按前例构造9数组成的方阵。

对于键盘输入的整数s, 如果存在幻和为s的素数幻方，则s应为中间素数的3倍。 设n=s/3，若通过试商知n不是素数，显然不存在幻和为s的素数幻，显示“此时无解！”后结束。

若n=s/3是一个素数，确定素数幻方中素数取值的上限d=s-8，并在[3,d]范围内确定x,y,w,z,并检测8个数n-x，n+w，n-y，n+z，n-z，n+y，n-w，n+x是否同时为素数。若同时为素数，即可按以上规定作输出，并用m统计解的个数。

3. 程序实现

// 指定幻和的三阶素数幻方 #include #include void main()

{int c,d,j,k,n,t,t1,t2,s,w,x,y,z,m; int a[3000];

printf(\请确定素数幻方的幻和s: \

scanf(\ n=s/3;m=0;

c=3;d=s-8; // 确定幻和为s时素数的最大最小区间 for(k=c;k<=d;k++) a[k]=0; for(k=c;k<=d;k+=2) {for(t=0,j=3;j<=sqrt(k);j+=2) if(k%j==0)

{t=1;break;} if(t==0) a[k]=1; // [c,d]中的奇数k为素数，标注1 }

if(a[n]==0)

22

{ printf(\幻和为%d时无解! \\n\for(y=2;y<=d-n-1;y+=2)

for(x=y+2;x<=d-n;x+=2) { z=x-y;w=x+y;

if(x==2*y || n-wd) continue; // 控制幻方的素数范围

t1=a[n-w]*a[n+w]*a[n-z]*a[n+z]; t2=a[n-x]*a[n+x]*a[n-y]*a[n+y];

if(t1*t2==0) continue; // 控制其余8个均为素数 m++; printf(\统计并输出三阶素数幻方 printf(\ printf(\

printf(\}

printf(\共 %d 个素数方阵.\\n\ }

4. 程序运行示例

请确定素数幻方的幻和s: 789 NO 1:

173 359 257 347 263 179 269 167 353 NO 2:

137 419 233 359 263 167 293 107 389 共 2 个素数方阵.

2.8 穷举设计的改进与优化

应用穷举设计求解比较简单，不存在太多难点，但也不能太随意。

实际上，穷举结构的设置，穷举参数的选取，都有很多值得我们观注与思考的地方，自然也存在很多改进与优化的空间。

23

2.8.1 整币兑零

1. 案例提出

计算把一张1元整币兑换成1分、2分、5分、1角、2角和5角共6种零币的不同兑换种数。

进一步计算把一张2元整币与一张5元整币兑换成上述6种零币的不同兑换种数。 2. 穷举设计求解 设整币的面值为n个单位，面值为1、2、5、10、20、50单位零币的个数分别为p1, p2, p3, p4, p5, p6。显然需解一次不定方程

p1+2*p2+5*p3+10*p4+20*p5+50*p6=n (p1, p2, p3, p4, p5, p6为非负整数) 对这6个变量实施穷举，确定穷举范围为0≤p1≤n, 0≤p2≤n/2, 0≤p3≤n/5, 0≤p4≤n/10, 0≤p5≤n/20, 0≤p6≤n/50。

在以上穷举的6重循环中，若满足条件 p1+2*p2+5*p3+10*p4+20*p5+50*p6=n

则为一种兑零方法，输出结果并通过变量m增1统计不同的兑换种数。 3. 穷举求解C程序设计 // 整币兑零穷举设计1 #include void main()

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

printf(\

printf(\分 2分 5分 1角 2角 5角 \\n\ for(p1=0;p1<=n;p1++) for(p2=0;p2<=n/2;p2++) for(p3=0;p3<=n/5;p3++)

for(p4=0;p4<=n/10;p4++) for(p5=0;p5<=n/20;p5++) for(p6=0;p6<=n/50;p6++)

if(p1+2*p2+5*p3+10*p4+20*p5+50*p6==n) // 根据条件检验 {m++;

printf(\ printf(\ }

printf(\}

运行程序，输入100，即得1元整币兑换成1分、2分、5分、1角、2角、5角共6?种零币的不同兑换方法及种数为：

24

1分 2分 5分 1角 2角 5角 0 0 0 0 0 2 0 0 0 0 5 0 0 0 0 1 2 1 ??

100(1,2,5,10,20,50)=4562

共有4562个解，即有4562种不同的兑换种数。 4. 精简穷举循环设计

在上述程序的6重循环中，我们可精简p1循环，在循环内应用 p1=n-(2*p2+5*p3+10*p4+20*p5+50*p6) 给p1赋值。如果p1为非负数，对应一种兑换法。

// 精简循环设计2 #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++) // 已精简了p1循环 for(p3=0;p3<=n/5;p3++) for(p4=0;p4<=n/10;p4++) for(p5=0;p5<=n/20;p5++) for(p6=0;p6<=n/50;p6++)

{p1=n-(2*p2+5*p3+10*p4+20*p5+50*p6); // p1为一分币的个数 if(p1>=0) {m++;

printf(\ printf(\ } }

printf(\}

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

200(1,2,5,10,20,50)=69118

精简穷举循环设计使穷举循环次数缩减为以上设计的1/n。 5. 穷举设计的进一步优化 以上程序的循环次数已经大大精简了。进一步的分析，我们看到在程序的循环设置中，p3循环从0～n/5可改进为0～(n-2*p2)/5，因为在n中p2已占去了2*p2。依此类推，对p4, p5, p6的循环可作类似的循环参量优化。

25