[递推]双幂序列、多幂序列、双幂积序列的和

简介: [递推]双幂序列、多幂序列、双幂积序列的和

1.双幂序列


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

20200320154124764.png


的元素由小到大排列的双幂序列第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为非负整数,试计算集合


20200320154219944.png

的元素由小到大排列的多幂序列第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.双幂积序列的和


由集合

20200320154300763.png

元素组成的复合幂序列,求复合幂序列的指数和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

目录
打赏
0
0
0
0
271
分享
相关文章
【动态规划】【矩阵】C++算法329矩阵中的最长递增路径
【动态规划】【矩阵】C++算法329矩阵中的最长递增路径
【算法训练-动态规划 三】【双序列DP问题】最长重复子数组、最长公共子串、最长公共子序列、编辑距离
【算法训练-动态规划 三】【双序列DP问题】最长重复子数组、最长公共子串、最长公共子序列、编辑距离
144 0
剑指offer 64. 和为S的连续正数序列
剑指offer 64. 和为S的连续正数序列
74 0
02:奇数单增序列
02:奇数单增序列
6994 0
【算法】最后一个单词的长度,颠倒二进制位,排列序列等三道算法题目
最后一个单词的长度,颠倒二进制位,排列序列等三道算法题目
73 0
数组连续最大序列问题----【滑动窗口、动态规划求解】
数组连续最大序列问题----【滑动窗口、动态规划求解】
171 0

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等