WORD格式可编辑

for(j=1;j<=i-1;j++) if(b[i]==b[j])

{t=1;break;}

if(t==1) {i--;continue;} // 出现相同数时，返回重新产生 s+=b[i]; printf(\ } if(s%2==0)

{printf(\以上%d个整数总和为%d.\\n\

s1=s/2; } else

printf(\和%ld为奇数,无法平分!\\n\ a[1]=1;i=2;a[i]=2; m=0; while(1) {if(i==n)

{for(s=0,j=1;j<=n;j++)

s+=b[a[j]];

if(s==s1) // 满足均分条件时输出 {m++; printf(\ for(j=1;j<=n;j++)

printf(\

} }

else

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

while(a[i]==n+i) i--; // 调整或回溯 if(i>1) a[i]++; else break; }

if(m>0) printf(\共有以上%d种分法。\

else printf(\无法实现二堆均分. \}

5-3 指定低逐位整除数探求

试求出所有最高位为3的24位低逐位整除数（除个位数字为“0”外,其余各位数字均不得为“0”）。

// 最高位为3的n位右逐位整除 #include

专业知识分享

WORD格式可编辑

void main()

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

printf(\逐位整除n位，请确定n：\ scanf(\

printf(\所求%d位最高位为3的右逐位整除数：\\n\ for(j=1;j<=100;j++) a[j]=1; t=0;a[1]=0;i=1; while(a[1]<1)

{ if(t==0 && i

for(r=0,j=i;j>=1;j--) // 检测i时是否整除i { r=r*10+a[j]; r=r%i; } if(r!=0)

{ a[i]=a[i]+1;t=1; // 余数r!=0时a[i]增1,t=1 while(a[i]>9 && i>1)

{ a[i]=1;i--; // 回溯 a[i]=a[i]+1; }

}

else t=0; // 余数r=0时,t=0

if(t==0 && i==n) { if(a[n]==3)

{s++;printf(\

for(j=n;j>=1;j--) printf(\ printf(\

}

a[i]=a[i]+1; } }

if(s>0)

printf(\最高位为3的%d位右逐位整除数共%ld个.\ else

printf(\未找到n位右逐位整除数.\ }

5-4 枚举求解8项素数和环，与回溯结果进行比较。 (1) 设计要点

为简化输出，环序列简化为一般序列输出，为避免重复，约定首项为“1”。

环中的每一项为一个数字，相连的8项构成一个8位数。因而设置a循环在没有重复数

专业知识分享

WORD格式可编辑

字数字且以“1”开头的8位数812345678——18765432中枚举。注意到所有1——8没有重复数字的8位数的数字和为9的倍数，该数也为9的倍数，为此，枚举循环步长可取9，以精简枚举次数。

为操作与判断方便，设置3个数组：

f数组统计8位数a中各个数字的频数。如f[3]=2，即a中有2个数字“3”。 g数组表示8位数a中每位数的数字。如g[4]=6，即a的从高位开始第4位数为数字“6”。 b数组标记整数x是否为素数。如b[13]=1，标识“1”表示13为素数，标识“0”为非素数。

枚举实施：

1） 注意到8项中每相邻两项之和不超过15,对15以内的5个素数用b数组标注“1”,其余均为“0”。

2） 在8位数的a 循环中，对a实施8次求余分离出各个数字x，应用f[x]++统计数字x的频数，应用g[9-k]=x记录a的各位数字。

3） 设置k(1——8)判断循环：

若f[k]!=1 ，表明数字k出现重复或遗漏，返回。

若 b[g[k]+g[k+1]]!=1，表明相邻的第k项与第k+1项之和不是素数，返回。顺便说明，为判断方便，首项“1”先行赋值给g[9]，以与g[8]相邻，在k循环中一道进行判别。

4） 通过以上判断筛选的a，其各个数字即为所求的8项素数环的各项，打印输出。 (2) 枚举实现8项素数和环 // 8项素数和环枚举求解 #include #include void main()

{ int t,k,s,x,g[10],f[10],b[18];long a,y; for(k=1;k<=15;k++) b[k]=0; g[9]=1;s=0;

b[3]=b[5]=b[7]=b[11]=b[13]=1; // 5个奇素数标记 printf(\项素数和环：\\n\

for(a=12345678;a<=18765432;a+=9) // 步长为9枚举8位数 {t=0;y=a;

for(k=0;k<=9;k++) f[k]=0; for(k=1;k<=8;k++)

{x=y;f[x]++; // 分离a的8个数字,用f数组统计x的个数 g[9-k]=x; // 用g数组记录a的第k位数字

y=y/10;

}

for(k=1;k<=8;k++)

if(f[k]!=1 || b[g[k]+g[k+1]]!=1) t=1;

if(t==1) continue; // 有相同数字或相邻和非素，返回

专业知识分享

WORD格式可编辑

s++;

printf(\输出8项素数和环 for(k=2;k<=8;k++) printf(\ printf(\ } }

5-5 递归求解20项素数环 // 递归求解素数环问题 #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

专业知识分享