WORD格式可编辑
{ 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;
专业知识分享
WORD格式可编辑
在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为指数 专业知识分享 WORD格式可编辑 } 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?23,x?0,y?0 xyn (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)+3 k k 其中3可以通过变量迭代实现。这样可以省略数组,简化为一重循环实现复合幂序列求和。 (2)程序实现 // 复合幂序列求和 专业知识分享 WORD格式可编辑 #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++) 专业知识分享