内容发布更新时间 : 2024/12/23 22:06:20星期一 下面是文章的全部内容请认真阅读。
#include
{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 {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 { 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 { 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项素数环