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

习题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列逆转矩阵