return(g); }
void main()
{ int k,n; long s=0;
printf(\请输入n: \ for(k=1;k<=n;k++) s+=b(k);
printf(\ printf(\ }
4-4 递归求解双递推摆动数列 已知递推数列：a(1)=1,a(2i)=a(i)+1,a(2i+1)=a(i)+a(i+1)，（i为正整数），试建立递归，求该数列的第n项与前n项的和。
// 摆动数列 #include
if(n==1) g=1;
else if(n%2==0) g=a(n/2)+1; else g=a((n-1)/2)+a((n+1)/2); return(g); }
void main()
{ int k,n; long s=0;
printf(\请输入n: \ for(k=1;k<=n;k++) s+=a(k);
printf(\ printf(\ }
4-5 应用递归设计输出杨辉三角。 // 杨辉三角递归设计 void c(int a[],int n) {int i; if(n==0) a[1]=1; else if(n==1)
{a[1]=1;a[2]=1;}
else
{c(a,n-1); a[n+1]=1;
for(i=n;i>=2;i--) a[i]=a[i]+a[i-1]; a[1]=1; } }
#include
{ int i,j,k,n,a[100];
printf(\请输入杨辉三角的行数：\scanf(\for(j=0;j<=n;j++) {c(a,j);
for(k=1;k<=30-2*j;k++) printf(\ for(i=1;i<=j;i++)
printf(\ printf(\
} }
4-6 试把m×n顺转矩阵的递归设计转变为递推设计。
解： 对输入的m,n，取c=min(m,n)，计算数字矩阵的圈数d=(c+1)/2。 设置i(1——d)循环，从外圈至内圈，分4边进行递推赋值。 程序设计：
// m×n数字旋转矩阵 #include
{int i,j,c,d,h,v,m,n,s,a[30][30];
printf(\行n列矩阵,请确定m,n: \ c=n;
if(m for(i=1;i<=d;i++) // 从外至内第d圈赋值 {h++; for(v=i;v<=n-i;v++) {s++;a[h][v]=s;} // d圈的首行从左至右赋值 for(h=i;h<=m-i;h++) {s++;a[h][v]=s;} // d圈的尾列从上至下赋值 for(v=n+1-i;v>=i+1;v--) { s++;a[h][v]=s; // d圈的尾行从右至左赋值 if(s==m*n) {i=d;break;} } // 赋值完成即行退出 for(h=m+1-i;h>=i+1;h--) { s++;a[h][v]=s; // d圈的首列从下至上赋值 if(s==m*n) {i=d;break;} } } printf(\行%d列旋转矩阵为:\\n\ for(i=1;i<=m;i++) { for(j=1;j<=n;j++) // 按m行n列输出矩阵 printf(\ printf(\ } } 4-7 试应用递归设计构造并输出任意指定逆转m×n矩阵。 解：在递归函数中，每圈4边按左列左列从上至下递增、下行从左至右递增、右列从下至上递增、上行从右至左递增给元素赋值。 程序设计： // m×n逆转矩阵递归设计 #include { int h,v,b,s,d; printf(\数阵为m行n列，请确定m,n：\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的排列 #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不得填在各分数的分母，且式中各分数的分子分母没有大于1的公因数，使下面的分数等式成立 □□ □□ □□ ── + ─── = ── □ □ □ 这一填数分数等式共有多少个解?? 解: 在桥本分数式回溯程序中修改 // 倒桥本分数式回溯实现 // 把1,2,...,9填入□□/□+□□/□=□□/□