1.双幂序列
设x,y为非负整数,试计算集合
的元素由小到大排列的双幂序列第n项与前n项之和。
(1) 递推设计要点
集合由2的幂与3的幂组成,实际上是给出两个递推关系。
设置一维f数组,f[k]存储双幂序列的第k项。
显然,第1项也是最小项为f[1]=1(当x=y=0时)。
从第2项开始,为了实现从小到大排序,设置a,b两个变量,a为2的幂,b为3的幂,显然a≠b。
设置k循环(k=2,3,…,n,其中n为键盘输入整数),在k循环外赋初值:a=2;b=3;在k循环中通过比较选择赋值:
当a<b时,由赋值f[k]=a确定为序列的第k项;然后a=a2,即a按递推规律乘2,为后一轮比较作准备;
当a>b时,由赋值f[k]=b确定为序列的第k项;然后b=b3,即b按递推规律乘3,为后一轮比较作准备。
(2) 递推描述
a=2;b=3; // 为递推变量a,b赋初值 for(k=2;k<=n;k++) { if(a<b) { f[k]=a;a=a*2;} // 用a给f[k]赋值 else { f[k]=b;b=b*3;} // 用b给f[k]赋值 }
2.多幂序列
设x,y,z为非负整数,试计算集合
的元素由小到大排列的多幂序列第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且a<c时,由赋值f[k]=a确定为序列的第k项;然后a=a2,即a按递推规律乘2,为后一轮比较作准备;
当b<a且b<c时,由赋值f[k]=b确定为序列的第k项;然后b=b3,即b按递推规律乘3,为后一轮比较作准备。
当c<a且c<b时,由赋值f[k]=c确定为序列的第k项;然后c=c*5,即c按递推规律乘5,为后一轮比较作准备。
(2) 递推描述
a=2;b=3;c=5; // 为递推变量a,b,c赋初值 for(k=2;k<=n;k++) { if(a<b && a<c) { f[k]=a;a=a*2;} // 用a给f[k]赋值 else if(b<a && b<c) { f[k]=b;b=b*3;} // 用b给f[k]赋值 else { f[k]=c;c=c*5;} // 用c给f[k]赋值 }
3.双幂积序列的和
由集合
元素组成的复合幂序列,求复合幂序列的指数和x+y≤n(正整数n≤50从键盘输入)的各项之和
(1) 递推设计要点
当x+y=0时,s(1)=1;
当x+y=1时,s(1)=2+3;
当x+y=2时,s(2)=22+2×3+32=2s(1)+ 32
当x+y=3时,s(3)=23+22×3+2×32+33=2s(2)+ 33
一般地,当x+y=k时,s(k)=2s(k−1)+3k
即有递推关系:
s(k)=2s(k)+3k
其中3k可以通过变量迭代实现。这样可以省略数组,简化为一重循环实现复合幂序列求和。
(2) 递推描述
// 复合幂序列求和 #include <stdio.h> void main() {int k,n; long sum,t,s[100]; printf("请输入幂指数和至多为n:"); scanf("%d",&n); 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",n,sum); }
(3) 数据测试
请输入幂指数和至多为n:50
幂指数和至多为50的幂序列之和为:717652233