内容发布更新时间 : 2025/7/8 9:11:51星期一 下面是文章的全部内容请认真阅读。
WORD格式可编辑
scanf(\s=m;
if(m>n) s=n; b=1;d=1;
void t(int b,int s,int d); // 递归函数说明
t(b,s,d); // 调用递归函数 printf(\×%d逆转矩阵: \\n\ for(h=1;h<=m;h++) {for(v=1;v<=n;v++)
printf(\ printf(\ } return; }
void t(int b,int s,int d) // 定义递归函数 { int j,h=b,v=b;
if(s<=0) return; // 递归出口
for(j=1;j<=m+1-2*b;j++) // 一圈的左列从上至下递增 { a[h][v]=d;h++;d++;}
for(j=1;j<=n+1-2*b;j++) // 一圈的下行从左至右递增 { a[h][v]=d;v++;d++;}
for(j=1;j<=m+1-2*b;j++) // 一圈的右列从下至上递增 { a[h][v]=d;h--;d++; if(d>m*n) return; }
for(j=1;j<=n+1-2*b;j++) // 一圈的上行从右至左递增 { a[h][v]=d;v--;d++;
if(d>m*n) return; // 另一递归出口 }
t(b+1,s-2,d); // 调用内一圈递归函数 }
4-8 应用递归设计实现n个相同元素与另m个相同元素的所有排列。 解： 设置递归函数p(k)，1≤k≤m+n，元素a[k]取值为0或1。
当k=m+n时，作变量h统计“0”的个数。若h=m则打印输出一排列，并用s统计排列个数。然后回溯返回，继续。
当k
// n个1与另m个0的排列
专业知识分享
WORD格式可编辑
#include
int m,n,r,a[30]; long s=0; void main() { int p(int k);
printf(\ printf(\个1与%d个0的排列:\\n\
p(1); // 从第1个数开始 printf(\输出排列的个数 }
// 排列递归函数 #include
{ for(i=0;i<=1;i++)
{ a[k]=i; // 探索第k个数赋值i
if(k==m+n) // 若已到m+n个数则检测0的个数h { for(h=0,j=1;j<=n+m;j++) if(a[j]==0) h++;
if(h==m) // 若0的个数为m个,输出一排列 { s++; printf(\ for(j=1;j<=n+m;j++) printf(\ if(s==0) printf(\ } } else p(k+1); // 若没到n+m个数,则调用p(k+1)探索下一个数 } }
return s; }
习题5
5-1 倒桥本分数式
把1,2,...,9?这9个数字填入下式的9个方格中，数字不得重复,且要求1不得填在各
专业知识分享
WORD格式可编辑
分数的分母，且式中各分数的分子分母没有大于1的公因数，使下面的分数等式成立
□□ □□ □□ ── + ─── = ── □ □ □
这一填数分数等式共有多少个解??
解: 在桥本分数式回溯程序中修改
// 倒桥本分数式回溯实现
// 把1,2,...,9填入□□/□+□□/□=□□/□ #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]
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结束 } }
专业知识分享
WORD格式可编辑
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;
专业知识分享