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