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

#include void main()

{int g,i,k,u,t,a[10]; long m1,m2,m3; i=1;a[1]=1; while (1) {g=1;

for(k=i-1;k>=1;k--)

if(a[i]==a[k]) {g=0;break;} // 两数相同,标记g=0 if(i==9 && g==1 && a[1]1 && a[7]>1) {m1=a[2]*10+a[3];

m2=a[5]*10+a[6]; m3=a[8]*10+a[9];

for(t=0,u=2;u<=9;u++)

{if(a[1]%u==0 && m1%u==0) t=1; if(a[4]%u==0 && m2%u==0) t=1; if(a[7]%u==0 && m3%u==0) t=1; }

if(t==0 && m1*a[4]*a[7]+m2*a[1]*a[7]==m3*a[1]*a[4]) // 判断等式 {printf(\

printf(\} }

if(i<9 && g==1)

{i++;a[i]=1;continue;} // 不到9个数,往后继续 while(a[i]==9 && i>1) i--; // 往前回溯 if(a[i]==9 && i==1) break;

else a[i]++; // 至第1个数为9结束 } }

5-2 两组均分

参加拔禾比赛的12个同学的体重如下：

48，43，57，64，50，52，18，34，39，56，16，61

为使比赛公平，要求参赛的两组每组6个人，且每组同学的体重之和相等。 请设计算法解决这 “两组均分”问题。 （1） 求解要点

一般地，对已知的2n(n从键盘输入)个整数，确定这些数能否分成2个组，每组n个数，

且每组数据的和相等。

我们可采用回溯法逐步实施调整。

对于已有的存储在b数组的2n个数,求出总和s与其和的一半s1(若这2n个数的和s为奇数,显然无法分组)。把这2n个数分成二个组,每组n个数。为方便调整,?设置数组a存储b数组的下标值，即a(i):1─2n。

考察b(1)所在的组,只要另从b(2)─b(2n)中选取n-1个数。即定下a(1)=1,?其余的a(i)(i=2,…,n)在2─2n中取不重复的数。因组合与顺序无关,不妨设 2 ≤ a(2)

从a(2)取2开始,以后a(i)从a(i-1)+1开始递增1取值,直至n+i为止。这样可避免重复。

当a(n)已取值,计算s=b(1)+b(a(2))+…+b(a(n)),对和s进行判别: 若s=s1,满足要求,实现平分。

若s≠s1,则a(n)继续增1再试。如果a(n)已增至2n,则回溯前一个a(n-1)增1再试。如果a(n-1)已增至2n-1,继续回溯。直至a(2)增至n+2时,结束。 二堆均分问题并不总有解。有解时,找到并输出所有解。没有解时,显示相关提示信息“无法实现平分”。

（2） 两组均分程序设计

// 两组均分程序设计 #define N 50

#include #include #include void main()

{int n,m,a[N],b[2*N],i,j,t; long s1,s=0;

printf(\把2n个整数分为和相等的两个组,每组n个数.\\n\ t=time(0)00;srand(t); // 随机数发生器初始化 printf(\

for(s=0,i=1;i<=2*n;i++) // 产生2n个不同的随机整数 {t=0;b[i]=rand()%(5*n)+10; 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 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循环在没有重复数字数字且以“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; // 有相同数字或相邻和非素，返回 s++;

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

5-5 递归求解20项素数环