图3-4所示为4行5 列逆转矩阵。

1 14 13 12 11

2 15 20 19 10

3 16 17 18 9

4 5 6 7 8

图3-4 4行5列逆转矩阵

试应用递推设计构造并输出任意指定m行n列逆转矩阵。

解： 对输入的m,n，取c=min(m,n)，计算数字矩阵的圈数d=(c+1)/2。 设置i(1——d)循环，从外圈至内圈，分4边进行递推赋值。 程序设计：

// m×n数字逆转矩阵 #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圈赋值 { v++;

for(h=i;h<=m-i;h++) // 一圈的左列从上至下递增

{ s++; a[h][v]=s;}

for(v=i;v<=n-i;v++) // 一圈的下行从左至右递增 { s++; a[h][v]=s;}

for(h=m+1-i;h>i;h--) // 一圈的右列从下至上递增 { s++; a[h][v]=s;

if(s==m*n) {h=i;break;} }

for(v=n+1-i;v>i;v--) // 一圈的上行从右至左递增 { s++; a[h][v]=s;

if(s==m*n) {v=i;break;} }

}

printf(\行%d列旋转矩阵为:\\n\ for(i=1;i<=m;i++)

{ for(j=1;j<=n;j++) // 按m行n列输出矩阵 printf(\

printf(\ } }

3-7 猴子吃桃

有一猴子第1天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了1个。第2天早上又将剩下的桃子吃掉一半，又多吃了1个。以后每天早上都吃了前一天剩下的一半后又多吃1个。到第10天早上想再吃时，见只剩下1个桃子了。

求第1天共摘了多少个桃子。 (1) 求解要点

第1天的桃子数是第2天桃子数加1后的2倍，第2天的桃子数是第3天桃子数加1后的2倍，…，一般地，第k天的桃子数是第k+1天桃子数加1后的2倍。设第k天的桃子数是t(k)，则有递推关系

t(k)=2*(t(k+1)+1) (k=1,2,…,9) 初始条件：t(10)=1

逆推求出t(1)，即为所求的第一天所摘桃子数。 (2) 程序设计

// 猴子吃桃程序

#include void main()

{ int k; long t[1000];

t[10]=1; // 确定初始条件 for(k=9;k>=1;k--) // 逆推计算t(1) t[k]=2*(t[k+1]+1);

printf(\第 1 天摘桃%ld个。\\n\ for(k=1;k<=9;k++)

{ printf(\第 %d 天面临%4ld个桃，\

printf(\吃了%4ld+1=%4ld个，\ printf(\还剩%4ld个。\\n\ }

printf(\第10天早上还剩1个。\}

3-8 拓广猴子吃桃

有一猴子第1天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了m个。第2天早上又将剩下的桃子吃掉一半，又多吃了m个。以后每天早上都吃了前一天剩下的一半后又多吃m个。到第n天早上想再吃时，见只剩下d个桃子了。

求第1天共摘了多少个桃子(m,n,d由键盘输入)？ 解：递推关系

t(k)=2*(t(k+1)+m) (k=1,2,…,n-1) 初始条件：t(n)=d

逆推求出t(1)，即为所求的第一天所摘桃子数。 // 拓广猴子吃桃程序 #include void main()

{ int d,k,m,n; long t[1000];

printf(\请确定正整数m,n,d: \ scanf(\

t[n]=d; // 确定初始条件 for(k=n-1;k>=1;k--) // 逆推计算t(1) t[k]=2*(t[k+1]+m);

printf(\第 1 天摘桃%ld个。\\n\ for(k=1;k<=n-1;k++)

{ printf(\第 %d 天面临%4ld个桃，\

printf(\吃了%4ld+%d=%4ld个，\ printf(\还剩%4ld个。\\n\ }

printf(\第%d天早上还剩%d个。\}

3-9 据例3-1中求裴波那契数列的第40项与前40项之和的递推算法与迭代算法，写出完整的程序，并比较其运行结果。

(1) 应用递推求解

// 裴波那契数列递推程序 #include void main()

{ int k; long s,f[50]; f[1]=1;f[2]=1;

s=f[1]+f[2]; // 数组元素与和变量赋初值 for(k=3;k<=40;k++)

{ f[k]=f[k?1]+f[k?2]; // 实施递推 s+=f[k]; // 实施求和

}

printf(\数列第40项为: %ld \\n\ printf(\前40项之和为: %ld \\n\ }

(2) 应用迭代求解

// 裴波那契数列迭代程序 #include void main()

{ int k; long a,b,s;

a=1;b=1;s=a+b; // 迭代变量a,b,s赋初值 k=2;

while(k<=20) // 控制迭代次数

{ a=a+b; // 推出a是f数列的第2k-1项

b=a+b; // 推出b是f数列的第2k项 s=s+a+b; // 推出s是f数列的前2k项之和 k=k+1; }

printf(\数列的第40项为：%ld \\n\printf(\前40项之和为：%ld \\n\}

习题4

4-1 阶乘的递归求解

阶乘n!定义: n!=1(n=1)；n!=n*(n-1)! (n>1) 设计求n!的递归函数，调用该函数求

s?1?111 ????1!2!n!解： 定义n!的递归函数f(n),在求和的k(1——n)循环中实施求和

s+=(double)1/f(k); 程序设计：

#include long f(int n) { long g;

if(n==1) g=1; else g=n*f(n-1); return(g); }

void main() { int k,n; double s=1;

printf(\请输入n: \ for(k=1;k<=n;k++) s+=(double)1/f(k); printf(\ }

4-2 递归求解f数列 已知f数列定义：

f1?f2?1,fn?fn?1?fn?2(n?2)

建立f数列的递归函数，求f数列的第n项与前n项之和。

解：定义f数列的递归函数f(n),在求和的k(1——n)循环中实施求和 s+=f(k)。 程序设计：

#include

long f(int n) { long g;

if(n==1 || n==2) g=1; else g=f(n-1)+f(n-2); return(g); }

void main()

{ int k,n; long s=0;

printf(\请输入n: \ for(k=1;k<=n;k++) s+=f(k);

printf(\ printf(\ }

4-3 递归求解b数列 已知b数列定义：

b1?1,b2?2,bn?3bn?1?2bn?2(n?2) 建立b数列的递归函数，求b数列的第n项与前n项之和。 解：#include long b(int n) { long g;

if(n==1) g=1;

else if(n==2) g=2;

else g=3*b(n-1)-2*b(n-2);