《计算机常用算法与程序设计案例教程》习题解答

习题3

3-1 递推求解b数列 已知b数列定义：

b1?1,b2?2,bn?3bn?1?bn?2(n?2)

递推求b数列的第20项与前20项之和。 解：

#include void main()

{ int k,n; long b[3000],s; printf(\请输入n: \ scanf(\ b[1]=1;b[2]=2;s=3; for(k=3;k<=n;k++)

{ b[k]=3*b[k-1]-b[k-2];

s+=b[k]; }

printf(\ printf(\ }

3-2 双关系递推数列 集合M定义如下： 1）1?M

2）x?M?2x?1?M,3x?1?M

3）再无别的数属于M

试求集合M元素从小到大排列的第2011个元素与前2011 个元素之和。 解：（1）设计要点

设n个数在数组m中，2x+1与3x+1均作为一个队列，从两队列中选一排头（数值较小者）送入数组m中。所谓“排头”就是队列中尚未选入m的最小的数（下标）。这里用p2表示2x+1这一列的排头的下标，用p3表示3x+1这一列的排头的下标。

if(2*m(p2)<3*m(p3))

{ m(i)=2*m(p2)+1;p2++;} if(2*m(p2)>3*m(p3))

{ m(i)=3*m(p3)+1;p3++;}

特别注意：两队列若出现相等时，给m数组赋值后，两排头都要增1。

if(2*m(p2)==3*m(p3)) { m(i)=2*m(p2)+1;

p2++; p3++; // 为避免重复项，P2，p3均须增1

} （2） 程序设计 // 双关系递推 #include void main()

{int n,p2,p3,i;long s,m[3000]; m[1]=1;s=1;

p2=1;p3=1; // 排头p2,p3赋初值 printf(\请输入n: \ scanf(\ for(i=2;i<=n;i++) if(2*m[p2]<3*m[p3])

{ m[i]=2*m[p2]+1; s+=m[i];

p2++; }

else

{ m[i]=3*m[p3]+1; s+=m[i];

if(2*m[p2]==3*m[p3]) p2++; // 为避免重复项，P2须增1 p3++;

}

printf(\ printf(\ }

3-3 多幂序列

设x,y,z为非负整数，试计算集合

M?{2x,3y,5z|x?0,y?0,z?0}

的元素由小到大排列的多幂序列第n项与前n项之和。 （1）递推算法设计

集合由2的幂、3的幂与5的幂组成，实际上给出的是3个递推关系。 显然，第1项也是最小项为1（当x=y=z=0时）。 从第2项开始，为了实现从小到大排列，设置3个变量a,b,c，a为2的幂，b为3的幂，c为5的幂，显然a,b,c互不相等。

设置k循环（k=2,3,…,n，其中n为键盘输入整数），在k循环外赋初值：a=2;b=3;c=5;s=1;

在k循环中通过比较赋值：

当a

当b

当c

递推过程描述：

a=2;b=3;c=5; // 为递推变量a,b,c赋初值 for(k=2;k<=n;k++) { if(a

{ f[k]=a;a=a*2;} // 用a给f[k]赋值

else if(b

{ f[k]=b;b=b*3;} // 用b给f[k]赋值 else

{ f[k]=c;c=c*5;} // 用c给f[k]赋值

}

在这一算法中，变量a,b,c是变化的，分别代表2的幂、3的幂与5的幂。 上述递推算法的时间复杂度与空间复杂度均为O(n)。 （2）多幂序列程序实现

// 多幂序列求解 #include void main()

{int k,m,t,p2,p3,p5; double a,b,c,s,f[100];

printf(\求数列的第m项与前m项和,请输入m: \ scanf(\

f[1]=1;p2=0;p3=0;p5=0; a=2;b=3;c=5;s=1; for(k=2;k<=m;k++) { if(a

{ f[k]=a;a=a*2; // 用2的幂给f[k]赋值 t=2;p2++; // t=2表示2的幂，p2为指数 }

else if(b

{ f[k]=b;b=b*3; // 用3的幂给f[k]赋值 t=3;p3++; // t=3表示3的幂，p3为指数 } else

{ f[k]=c;c=c*5; // 用5的幂给f[k]赋值 t=3;p5++; // t=5表示5的幂，p5为指数 }

s+=f[k]; }

printf(\数列的第%d项为: %.0f \

if(t==2) // 对输出项进行标注 printf(\ else if(t==3)

printf(\ else

printf(\

printf(\数列的前%d项之和为：%.0f \\n\}

3-4 双幂积序列的和

由集合M?{2x3y|x?0,y?0}元素组成的复合幂序列，求复合幂序列的指数和x+y≤n（正整数n从键盘输入）的各项之和

s?x?y?0?23xny,x?0,y?0

（1）设计要点

归纳求和递推关系: 当x+y=0时，s(1)=1； 当x+y=1时，s(1)=2+3；

222

当x+y=2时，s(2)=2+2×3+3=2*s(1)+ 3

32233

当x+y=3时，s(3)=2+2×3+2×3+3=2*s(2)+ 3

k

一般地，当x+y=k时，s(k)=2*s(k?1)+3 即有递推关系：

s(k)=2*s(k)+3k

k

其中3可以通过变量迭代实现。这样可以省略数组，简化为一重循环实现复合幂序列求和。

（2）程序实现

// 复合幂序列求和 #include void main()

{int k,n; long sum,t,s[100];

printf(\请输入幂指数和至多为n:\ scanf(\ t=1;s[0]=1; sum=1;

for(k=1;k<=n;k++)

{t=t*3; // 迭代得t=3^k s[k]=2*s[k-1]+t; // 实施递推

sum=sum+s[k]; }

printf(\幂指数和至多为%d的幂序列之和为:%ld\\n\}

3-5 粒子裂变

核反应堆中有α和β两种粒子，每秒钟内一个α粒子可以裂变为3个β粒子，而一个β粒子可以裂变为1个α粒子和2个β粒子。若在t=0时刻的反应堆中只有一个α粒子，求在t秒时反应堆裂变产生的α粒子和β粒子数。

1. 算法设计

设在t秒时α粒子数为f(t)，β粒子数为g(t)，依题可知：

g(t)=3f(t-1)+2g(t-1) （1） f(t)=g(t-1) （2） g(0)=0,f(0)=1

由（2）得f(t-1)=g(t-2) （3） 将式（3）代入（1）得

g(t)=2g(t-1)+3g(t-2) (t≥2) （4） g(0)=0,g(1)=3 （5） 以递推关系（4）与初始条件（5）完成递推。 2．粒子裂变C程序设计 // 粒子裂变

#include void main()

{int t,k;long g[100]; printf(\ scanf(\

g[0]=0; g[1]=3; // 确定初始条件 for(k=2;k<=t;k++)

g[k]=2*g[k-1]+3*g[k-2]; // 完成递推 printf(\秒时反应堆中β粒子数为:%ld \\n\ printf(\秒时反应堆中α粒子数为:%ld \\n\}

3-6 m行n列逆转矩阵