习题3
3-1 递推求解b数列 已知b数列定义：
b1?1,b2?2,bn?3bn?1?bn?2(n?2)
递推求b数列的第20项与前20项之和。 解：
#include
{ 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
{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 {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 {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 {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列逆转矩阵