内容发布更新时间 : 2024/11/8 18:48:41星期一 下面是文章的全部内容请认真阅读。

// 递归求解素数环问题 #include #include

int n,a[2000],b[1000];long s=0; void main() { int t,j,k; int p(int k);

printf(\前n个正整数组成素数环，请输入整数n: \ scanf(\

for(k=1;k<=2*n;k++) b[k]=0; for(k=3;k<=2*n;k+=2)

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

{t=1;break;} if(t==0) b[k]=1; // 奇数k为素数的标记 }

a[1]=1;k=2; p(k);

printf(\前%d个正整数组成素数环，以上是其中3个。\\n\}

// 素数环递归函数p(k) #include int p(int k) { int i,j,u; if(k<=n)

{ for(i=2;i<=n;i++)

{ a[k]=i; // 探索第k个数赋值i for(u=0,j=1;j<=k-1;j++) if(a[k]==a[j] || b[a[k]+a[k-1]]==0) // 若出现重复数字

u=1; // 若第k数不可置i,则u=1

if(u==0) // 若第k数可置i,则检测是否到n个数

{ if(k==n && b[a[n]+a[1]]==1 && s<3) // 若已到n个数时打印出一个解 { s++;

printf(\ for (j=2;j<=n;j++) printf(\ printf(\ } else

p(k+1); // 若没到m个数,则探索下一个数 p(k+1) } } }

return s; }

5-6 枚举探索6珠所能覆盖的最大和s。 // 数码串珠探索 #include void main()

{int d,i,j,s,t,u,v,a[20],b[300]; for(s=31;s>=28;s--)

{printf(\： \\n\统计s时解的个数 a[0]=0;a[1]=1;a[6]=s;

for(a[2]=a[1]+1;a[2]<=s-4;a[2]++) for(a[3]=a[2]+1;a[3]<=s-3;a[3]++) for(a[4]=a[3]+1;a[4]<=s-2;a[4]++) for(a[5]=a[4]+1;a[5]<=s-1;a[5]++) {for(i=7;i<=11;i++)

a[i]=s+a[i-6];

for(t=0,i=0;i<=5;i++) for(j=i+1;j<=i+5;j++)

{t++;b[t]=a[j]-a[i];} // 除s外，产生30个部分和 u=0;

for(d=1;d<=s-1;d++) for(i=1;i<=30;i++)

if(b[i]==d) // b有[1,s-1]中的一个数，u增1

{u+=1;i=30;}

if(u==s-1) // u=s-1时为完全环覆盖 {v++;

printf(\

for(i=1;i<=5;i++)

printf(\if(v%2==0)

printf(\}

}

if(v>0) return;

} }

5-7 枚举探索4阶德布鲁金环，并与德布鲁金环的回溯程序运行结果进行比较。 求解由16个0或1组成的环序列，形成的由每相连4个数字组成的16个二进制数恰好在环中都出现一次。

(1) 枚举设计要点 约定序列由0000开头，第5个数字与第16个数字显然都为1(否则会出现00000)。余下10个数字应用枚举探求。

设置一维a数组，由约定0000开头，即a(0)～a(3)均为0；a(4)=1,a(15)=1。其余10个数字a(5)～a(14)通过枚举探求。因为是环序列，a(16)～a(18)即为开头的0。

分析10个数字0、1组成的二进制数，高位最多2个0（否则出现0001或0000重复），即循环的初值可定为n1=2。同时，高位不会超过4个1（否则出现11111超界），即循环的终值可定为n2=2+2+2+2。

对区间[n1,n2]中的每一个整数n(为不影响循环，赋值给b)，通过除以2取余转化为10个二进制数码。用变量i统计该二进制数中1的个数，若i≠6返回，确保16个数字中有8个1时转入下面的检验：计算m1,m2并通过比较，检验a(0)～a(18)中每4个相连数字组成的二进制数若有相同，显然不能满足题意要求，标记t=1退出。若所有由4个相连数字组成的16个二进制数没有相同的，满足德布鲁金环序列条件，作打印输出。 （2）4阶德布鲁金环序列枚举实现 #include void main()

{ int b,m,m1,m2,n,n1,n2,i,j,k,t,a[20]; m=0; n1=128;

n2=512+256+128+64; // 确定枚举范围 for(n=n1;n

{for(k=0;k<=18;k++) a[k]=0; a[4]=1;a[15]=1; b=n;

for(i=0,k=14;k>=5;k--) // 正整数n(即b)转化为二进制数 {a[k]=b%2; b=b/2; i+=a[k]; }

if(i!=6) continue; // 确保8个1转入以下检验 for(t=0,k=0;k<=14;k++)

for(j=k+1;j<=15;j++) // 计算并检验16个二进制数是否相同

9

8

7

67

{m1=a[k]*8+a[k+1]*4+a[k+2]*2+a[k+3]; m2=a[j]*8+a[j+1]*4+a[j+2]*2+a[j+3];

if(m1==m2) {t=1;break;} }

if(t==0) // 若16个二进制数没有相同，输出结果 {m=m+1;

printf(\ for(j=0;j<=15;j++) // 依次输出16个二进制数 printf(\ if(m%2==0) printf(\ } } }

5-8 回溯实现组合C(n,m)

对指定的正整数m,n(约定1＜m≤n), 回溯实现从n个不同元素中取m个（约定1＜m＜n）的组合C(n,m)。

（1）回溯算法设计

注意到组合与组成元素的顺序无关，约定组合中的组成元素按递增排序。 设置一维数组a，a(i)(i=1,2,…,m)在1～n中取值。

首先从a(1)=1开始取值。以后各项从前一项增1取值：a[i]=a[i-1]+1。

若a(i)=n+i-m，则返回前一个数组元素a(i-1)。直到i=0，已无法返回，?意味着已全部试毕，求解结束。

问题的解空间是由数字1～n组成的m位整数组，其约束条件是没有相同数字。 按以上所描述的回溯的参量：m,n(m≤n) 元素初值：a[1]=1，数组元素初值取1。 取值点：a[i]=a[i-1]+1，以保持升序。

回溯点：a[i]=n+i-m，各数组元素取值至n+i-m后回溯。 （2）回溯实现C(n,m)的C程序实现 // 实现组合C(n,m) #include void main()

{int i,j,n,m,a[100]; long s=0;

printf(\ printf(\ i=1;a[i]=1; while(1)

{if(i==m) {s++;

for(j=1;j<=m;j++)

printf(\// 输出一个排列 printf(\

if(s==0) printf(\ }

if(i

{i++;a[i]=a[i-1]+1;continue;}

while(a[i]==n+i-m) i--; // 回溯到前一个元素 if(i>0) a[i]++; else break; }

printf(\总数为:%ld \\n\输出C(n,m)的值 }

5-9 回溯实现复杂排列

应用回溯法探索从n个不同元素中取m（约定1＜m≤n）个元素与另外n-m个相同元素组成的复杂排列。

（1）算法设计要点

引入变量k来控制0的个数，当k＜n-m时，a[i]=0，元素需从0开始取值；否则，0的个数已达n-m个，a[i]=1，即从1开始取值。这样处理，使0的个数不超过n-m，减少一些无效操作，提高了回溯效率。

按以上所描述的回溯的参量：n,m(m≤n) 元素初值：a[1]=0，数组元素取初值0。

取值点：当k＜n-m时，a[i]=0，需从0开始取值；否则，a[i]=1，即从1开始取值。 回溯点：a[i]=n，各元素取值至n时回溯。

约束条件1：a[k]!=0 && a[i]=a[k] || a[i]*a[k]＞0 && fabs(a[i]-a[k])=i-k, (其中i＞k)，排除同一列或同对角线上出现2个皇后。

约束条件2：i=n && h=n-m && b[1-n][1-n]=1, 当取值达n个，其中n-m个零，且棋盘全控时输出一个解。

（2）复杂排列回溯优化设计 #include #define N 30 void main()

{int i,j,h,k,n,m,t,a[N]; long s=0;

printf(\ printf(\