《计算机常用算法与程序设计案例教程》习题解答

// 递归求解素数环问题 #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(\

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4