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 { 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 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 { 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 专业知识分享