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 int a(int n) { int g;

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 void main()

{ 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 #include void main()

{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 m,n,a[20][20]={0}; void main()

{ 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 int p(int k) { int h,i,j; if(k<=m+n)

{ 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填入□□/□+□□/□=□□/□