【数据结构与算法】递推

来源:《信息学奥赛一本通》

所谓递推,是指从已知的初始条件出发,依据某种递推关系,逐次推出所要求的各中间结果及最后结果。其中初始条件或是问题本身已经给定,或是通过对问题的分析与化简后确定。

  • 从已知条件出发逐步推到问题结果,此种方法叫顺推。
  • 从问题出发逐步推到已知条件,此种方法叫逆推。

无论顺推还是逆推,其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简单运算,充分发挥出计算机擅长于重复处理的特点。

递推法是一种重要的数学方法,在数学的各个领域中都有广泛的运用,也是计算机用于数值计算的一个重要算法。

递推算法的首要问题是得到相邻的数据项间的关系(即递推关系)。递推算法避开了求通项公式的麻烦,把一个复杂的问题的求解,分解成了连续的若干步简单运算。一般说来,可以将递推算法看成是一种特殊的迭代算法。

可用递推算法求解的题目一般有以下两个特点:
1、问题可以划分成多个状态;
2、除初始状态外,其它各个状态都可以用固定的递推关系式来表示。
在我们实际解题中,题目不会直接给出递推关系式,而是需要通过分析各种状态,找出递推关系式。

引入——斐波那契数列

满足 F 1 = F 2 = 1 , F n = F n − 1 + F n − 2 F_1=F_2=1,F_n=F_{n-1}+F_{n-2} F1=F2=1,Fn=Fn1+Fn2的数列称为斐波那契数列(Fibonacci):1,1,2,3,5,8,13,21,34…

求此数列的第n项(n>=3)

【算法分析】
f 1 = 1 ( n = 1 ) ; f 2 = 1 ( n = 2 ) ; f n = f n − 1 + f n − 2 ( n > = 3 ) f_1=1(n=1); f_2=1(n=2); f_n=f_{n-1}+f_{n-2}(n>=3) f1=1(n=1);f2=1(n=2);fn=fn1+fn2(n>=3)
【参考程序】

#include<iostream>
using namespace std;
int main(){
	int f0=1,f1=1,f2;
	int n;
	cin>>n;
	for(int i=3;i<=n;i++){
		f2=f0+f1;
		f0=f1;
		f1=f2;
	}
	cout<<f2<<endl;
	return 0;
}

例1.上楼梯

楼梯有n个台阶,上楼可以一步上一阶,也可以一步上两阶。一共有多少种上楼的方法?

这是一道计数问题。在没有思路时,不妨试着找规律。n=5时,一共有8种方法:

5=1+1+1+1+1
5=1+2+1+1
5=1+1+2+1
5=1+1+1+2
5=1+2+2
5=2+1+1+1
5=2+2+1
5=2+1+2

其中,有5种方法第一步走了1阶,3种方法第一步走了2阶。我们据此进行分析与推断。

【算法分析】

假设f(n)为n个台阶的走法总数,把n个台阶的走法分成两类:
第一类:第一步走1阶,剩下还有n-1阶要走,有f(n-1)种方法。
第二类:第一步走2阶,剩下还有n-2阶要走,有f(n-2)种方法。
这样,就得到了递推式:f(n)=f(n-1)+f(n-2),不要忘记边界情况:f(1)=1,f(2)=2
把f(n)的前几项列出:1,2,3,5,8...你发现了什么?

例2.兔子繁殖

把雌雄各一的一对新兔子放入养殖场中。每只雌兔在出生两个月以后,每月产雌雄各一的一对新兔子。试问第n个月后养殖场中共有多少对兔子。

还是先找找规律。

第1个月:一对新兔子r1。用小写字母表示新兔子。
第2个月:还是一对新兔子,不过已经长大,具备生育能力了,用大写字母R1表示。
第3个月:R1生了一对新兔子r2,一共2对。
第4个月:R1又生一对新兔子r3,一共3对。另外,r2长大了,变成R2
第5个月:R1和R2各生一对,记为r4和r5,共5对。此外,r3长成R3。
第6个月:R1、R2和R3各生一对,记为r6~r8,共8对。此外,r4和r5长大。
......

把这些数排列起来:1,1,2,3,5,8,……,事实上,可以直接推导出来递推关系:f(n)=f(n-1)+f(n-2)
第n个月的兔子由两部分组成,一部分是上个月就有的老兔子f(n-1),一部分是这个月出生的新兔子f(n-2)(第n个月时具有生育能力的兔子数就等于第n-2个月兔子总数)。
根据加法原理,f(n)=f(n-1)+f(n-2)

例3.骨牌问题

有2 × n的一个长方形方格,用一个1 × 2的骨牌铺满方格。
编写一个程序,试对给出的任意一个n(n>0), 输出铺法总数。

n=2

骨牌1

n=3

骨牌2

【算法分析】

(1)面对上述问题,如果思考方法不恰当,要想获得问题的解答是相当困难的。可以用递推方法归纳出问题解的一般规律。
(2)当n=1时,只能是一种铺法,铺法总数有示为x1=1。
(3)当n=2时:骨牌可以两个并列竖排,也可以并列横排,再无其他方法,如图所示,因此,铺法总数表示为x2=2;
(4)当n=3时:骨牌可以全部竖排,也可以认为在方格中已经有一个竖排骨牌,则需要在方格中排列两个横排骨牌(无重复方法),若已经在方格中排列两个横排骨牌,则必须在方格中排列一个竖排骨牌。如图,再无其他排列方法,因此铺法总数表示为x3=3。
由此可以看出,当n=3时的排列骨牌的方法数是n=1和n=2排列方法数的和。
(5)推出一般规律:对一般的n,要求x(n)可以这样来考虑,若第一个骨牌是竖排列放置,剩下有n-1个骨牌需要排列,这时排列方法数为x(n-1);若第一个骨牌是横排列,整个方格至少有2个骨牌是横排列(1*2骨牌),因此剩下n-2个骨牌需要排列,这是骨牌排列方法数为x(n-2)。从第一骨牌排列方法考虑,只有这两种可能,所以有:
x(n)=x(n-1)+x(n-2) (n>2)
x1=1
x2=2

x(n)=x(n-1)+x(n-2)就是问题求解的通项公式

【参考程序】

#include<iostream>
using namespace std;
int main(){
	int n,i,a[101];
	cin>>n;//输入骨牌数 
	a[1]=1;a[2]=2;
	for(i=3;i<=n;i++){
		a[i]=a[i-1]+a[i-2];
	}
	cout<<a[i-1]<<endl;
	return 0;
}

例4.数塔问题

如下所示为一个数字三角形。请编一个程序计算从顶到底的某处的一条路径,使该路径所经过的数字总和最大。只要求输出总和。

数塔问题

1、 一步可沿左斜线向下或右斜线向下走;
2、 三角形行数小于等于100;
3、 三角形中的数字为0,1,…,99;

测试数据通过键盘逐行输入,如上例数据应以如下所示格式输入:

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

【算法分析】

  此题解法有多种,从递推的思想出发,设想,当从顶层沿某条路径走到第i层向第i+1层前进时,我们的选择一定是沿其下两条可行路径中最大数字的方向前进,为此,我们可以采用倒推的手法,设a[i][j]存放从i,j 出发到达n层的最大值,则a[i][j]=max{a[i][j]+a[i+1][j],a[i][j]+a[i+1][j+1]},a[1][1] 即为所求的数字总和的最大值。

【参考程序】

#include<iostream>
using namespace std;
int main(){
  int n,i,j,a[101][101];
  cin>>n;
  for (i=1;i<=n;i++)
   for (j=1;j<=i;j++)
     cin>>a[i][j];                             //输入数字三角形的值
  for (i=n-1;i>=1;i--)
   for (j=1;j<=i;j++)
     {
       if (a[i+1][j]>=a[i+1][j+1])  a[i][j]+=a[i+1][j];     //路径选择
       else  a[i][j]+=a[i+1][j+1];
     } 
   cout<<a[1][1]<<endl; 
}

例5.位数问题

【问题描述】
在所有的N位数中,有多少个数中有偶数个数字3?由于结果可能很大,你只需要输出这个答案对12345取余的值。
【输入格式】
读入一个数N
【输出格式】
输出有多少个数中有偶数个数字3。
【输入样例】
2
【输出样例】
73
【数据规模】
1<=N<=1000
【样例说明】
在所有的2位数字,包含0个3的数有72个,包含2个3的数有1个,共73个

【算法分析】

方法一:排列组合(但需要运用动态规划)。
可以列出公式,在n个格子中放x个3(其中x为偶数,包括0).。
c(n,x)*9 ^ (n-x) - c(n-1,x)*9 ^ (n-x-1) 含义为在n个格子中取x个3,且不考虑第一位的特殊情况为c(n,x)*9^(n-x)。
而第一位为0的情况,为c(n-1,x)*9^(n-x-1),两者减下,就为答案。
方法二:递推
考虑这种题目,一般来说都是从第i-1位推导第i位,且当前位是取偶数还是取奇数的。
恍然大悟.可以用f[i][0]表示前i位取偶数个3有几种情况,f[i][1]表示前i位取奇数个3有几种情况。
则状态转移方程可以表示为:
   f[i][0]=f[i-1][0]*9+f[i-1][1];f[i][1]=f[i-1][0]+f[i-1][1]*9;
边界条件:f[1][1]=1;f[1][0]=9;

【参考程序】

#include<iostream>
using namespace std;
int main()
{
  int f[1001][2],n,i,x;
  cin>>n;
  f[1][1]=1;f[1][0]=9;                        
  for(i=2;i<=n;i++) 
   {   
      x=f[1][0];
      if(i==n)x--;
      f[i][0]=(f[i-1][0]*x+f[i-1][1])%12345;
      f[i][1]=(f[i-1][1]*x+f[i-1][0])%12345;   
   }
   cout<<f[n][0]; 
   return 0;
}

五种典型的递推关系

Ⅰ.Fibonacci数列

在所有的递推关系中,Fibonacci数列应该是最为大家所熟悉的。在最基础的程序设计语言Logo语言中,就有很多这类的题目。而在较为复杂的Basic、Pascal、C语言中,Fibonacci数列类的题目因为解法相对容易一些,逐渐退出了竞赛的舞台。可是这不等于说Fibonacci数列没有研究价值,恰恰相反,一些此类的题目还是能给我们一定的启发的。

Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”(又称“Fibonacci问题”)。
  问题的提出:有雌雄一对兔子,假定过两个月便可繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子?
  解:设满x个月共有兔子F(x)对,其中当月新生的兔子数目为N(x)对。第x-1个月留下的兔子数目设为F(x-1)对。则:
 F(x)=N(x)+F(x-1)
 N(x)=F(x-2) (即第x-2个月的所有兔子到第x个月都有繁殖能力了)
∴ F(x)=F(x-1)+F(x-2) 边界条件:F0=0,F1=1
 由上面的递推关系可依次得到
    F2=F1+F0=1,F3=F2+F1=2,F4=F3+F2=3,F5=F4+F3=5,……。

Fabonacci数列常出现在比较简单的组合计数问题中,例如以前的竞赛中出现的“骨牌覆盖”问题。在优选法中,Fibonacci数列的用处也得到了较好的体现。

Ⅱ.Hanoi塔问题

问题的提出:Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时,这n个圆盘由大到小依次套在a柱上,如图所示。
要求把a柱上n个圆盘按下述规则移到c柱上:

汉诺塔

(1)一次只能移一个圆盘;
(2)圆盘只能在三个柱上存放;
(3)在移动过程中,不允许大盘压小盘。
问将这n个盘子从a柱移动到c柱上,总计需要移动多少个盘次?

解:设hn为n个盘子从a柱移到c柱所需移动的盘次。显然,当n=1时,只需把a 柱上的盘子直接移动到c柱就可以了,故h1=1。当n=2时,先将a柱上面的小盘子移动到b柱上去;然后将大盘子从a柱移到c 柱;最后,将b柱上的小盘子移到c柱上,共记3个盘次,故h2=3。以此类推,当a柱上有n(n>=2)个盘子时,总是先借助c柱把上面的n-1个盘子移动到b柱上,然后把a柱最下面的盘子移动到c柱上;再借助a柱把b柱上的n-1个盘子移动到c柱上;总共移动h(n-1)+1+h(n-1)个盘次。
   ∴h(n)=2h(n-1)+1 边界条件:h1=1

Ⅲ.平面分割问题

问题的提出:设有n条封闭曲线画在平面上,而任何两条封闭曲线恰好相交于两点,且任何三条封闭曲线不相交于同一点,问这些封闭曲线把平面分割成的区域个数。

平面分割

从这些式子中可以看出a(n)-a(n-1)=2(n-1)。当然,上面的式子只是我们通过观察4幅图后得出的结论,它的正确性尚不能保证。下面不妨让我们来试着证明一下。当平面上已有n-1条曲线将平面分割成a(n-1)个区域后,第n-1条曲线每与曲线相交一次,就会增加一个区域,因为平面上已有了n-1条封闭曲线,且第n条曲线与已有的每一条闭曲线恰好相交于两点,且不会与任两条曲线交于同一点,故平面上一共增加2(n-1)个区域,加上已有的a(n-1)个区域,一共有a(n-1)+2(n-1)个区域。所以本题的递推关系是a(n)=a(n-1)+2(n-1),边界条件是a1=1

平面分割问题是竞赛中经常触及到的一类问题,由于其灵活多变,常常会感到棘手。

Ⅳ.Catalan数

Catalan数首先是由Euler在精确计算对凸n边形的不同的对角三角形剖分的个数问题时得到的,它经常出现在组合计数问题中。
   问题的提出:在一个凸n边形中,通过不相交于n边形内部的对角线,把n边形拆分成若干三角形,不同的拆分数目用h(n)表示,h(n)即为Catalan数。例如五边形有如下五种拆分方案(图3-14),故h5=5。求对于一个任意的凸n边形相应的h(n)。

卡特兰数1

卡特兰数2

Catalan数是比较复杂的递推关系,尤其在竞赛的时候,选手很难在较短的时间里建立起正确的递推关系。当然,Catalan数类的问题也可以用搜索的方法来完成,但是,搜索的方法与利用递推关系的方法比较起来,不仅效率低,编程复杂度也陡然提高。

【数据结构与算法】栈中的“栈与卡特兰数”有相关资料及习题

Ⅴ.第二类Stirling数

在五类典型的递推关系中,第二类Stirling是最不为大家所熟悉的。也正因为如此,我们有必要先解释一下什么是第二类Strling数。
【定义】n个有区别的球放到m个相同的盒子中,要求无一空盒,其不同的方案数用S(n,m)表示,称为第二类Stirling数。
下面就让我们根据定义来推导带两个参数的递推关系——第二类Stirling数。

解:设有n个不同的球,分别用b1,b2,……bn表示。从中取出一个球bn,bn的放法有以下两种:
   ①bn独自占一个盒子;那么剩下的球只能放在m-1个盒子中,方案数为S(n-1,m-1);
   ②bn与别的球共占一个盒子;那么可以事先将b1,b2,……bn-1这n-1个球放入m个盒子中,然后再将球bn可以放入其中一个盒子中,方案数为mS(n-1,m)。
综合以上两种情况,可以得出第二类Stirling数定理:
S(n,m)=mS(n-1,m)+S(n-1,m-1) (n>1,m>=1)
边界条件可以由定义2推导出:
S(n,0)=0;S(n,1)=1;S(n,n)=1;S(n,k)=0(k>n)。
注:原文中S有下标2,这里为了表示方便删去了。

第二类Stirling数在竞赛中较少出现,但在竞赛中也有一些题目与其类似,甚至更为复杂。读者不妨自己来试着建立其中的递推关系。

递家族除了递推,还有大名鼎鼎的递归

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/546681.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

jenkins(docker)安装及应用

jenkins Jenkins是一个开源的、提供友好操作界面的持续集成(CI)工具&#xff0c;起源于Hudson&#xff08;Hudson是商用的&#xff09;&#xff0c;主要用于持续、自动的构建/测试软件项目、监控外部任务的运行&#xff08;这个比较抽象&#xff0c;暂且写上&#xff0c;不做解…

论坛直击|发展新质生产力,高校怎么做?

新质生产力浪潮涌动 三大议题聚焦高校人才培养 今年全国两会的政府工作报告将“大力推进现代化产业体系建设&#xff0c;加快发展新质生产力”列在2024年政府工作任务首位&#xff0c;发展新质生产力的先导是培养拔尖创新人才&#xff0c;高等教育改革必须以立德树人为根本任…

幽灵漏洞进阶版来了

近日&#xff0c;网络安全研究人员披露了针对英特尔系统上 Linux 内核的首个原生 Spectre v2 漏洞&#xff0c;该漏洞是2018 年曝出的严重处理器「幽灵」&#xff08;Spectre&#xff09;漏洞 v2 衍生版本&#xff0c;利用该漏洞可以从内存中读取敏感数据&#xff0c;主要影响英…

Java怎么获取今天最早的时间

今天在实现项目里的一个功能的时候&#xff0c;需要获取今天最早的时间&#xff0c;比如今天是2024-4-15&#xff0c;则今天的开始时间为2024-4-14日24点之后&#xff08;2024-4-15零点&#xff09;的那个时间点。 这篇文章就分享一下博主获取这个时间的方法&#xff1a; 很简…

Python数据可视化库—Bokeh与Altair指南【第161篇—数据可视化】

&#x1f47d;发现宝藏 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。【点击进入巨牛的人工智能学习网站】。 在数据科学和数据分析领域&#xff0c;数据可视化是一种强大的工具&#xff0c;可以帮助我们…

代码随想录刷题day53|最长公共子序列不相交的线最大子序和

文章目录 day53学习内容一、最长公共子序列1.1、动态规划五部曲1.1.1、 确定dp数组&#xff08;dp table&#xff09;以及下标的含义1.1.2、确定递推公式1.1.3、 dp数组如何初始化1.1.4、确定遍历顺序1.1.5、输出结果 1.2、代码 二、不相交的线2.1、动态规划五部曲2.1.1、 确定…

【Git】Git的安装与常用命令

Git的安装与常用命令 一、Git的安装 &#xff08;一&#xff09;下载 官网下载&#xff1a;https://git-scm.com/downloads 镜像网站&#xff1a;https://registry.npmmirror.com/binary.html?pathgit-for-windows/ &#xff08;二&#xff09;安装 双击安装&#xff0c…

智能客服系统如何高效分配会话的实用指南

面对现在快节奏的商业市场&#xff0c;能否快速地把握住商机成为了企业制胜的关键&#xff0c;所以很多企业都想要一个可以快速响应客户需求的工具来帮助他们实现更高效的转化。如果能够有一个可以智能识别并自动将客户分配给合适客服的系统&#xff0c;来保证每个客户都能享受…

抖音扫码登录

抖音扫码登录&#xff0c;ck可以点赞关注上传视频 主要涉及参数: bd_ticket_guard_client_data bd_ticket_guard_server_data bd_ticket_guard_ree_public_key bd_ticket_crypt_cookie x–secadk–csrf–token req_sign abogus ts_sign ticket {"is_digg":…

从工程师到医疗高管,复旦MBA助我实现职场飞跃 | 校友故事

2月12日&#xff0c;英国《金融时报》&#xff08;FT&#xff09;发布2024年全球MBA项目百强榜单&#xff0c;复旦大学MBA项目位列全球第27位&#xff0c;并在多个分指标上位居全球前列。其中“职业服务”和“ESG与零排放教学”蝉联亚洲第1、“薪酬增长率”全球第2、“职业成长…

“智能医疗新纪元:机器学习在医疗健康领域的创新应用“

个人名片&#xff1a; &#x1f43c;作者简介&#xff1a;一名大三在校生&#xff0c;喜欢AI编程&#x1f38b; &#x1f43b;‍❄️个人主页&#x1f947;&#xff1a;落798. &#x1f43c;个人WeChat&#xff1a;hmmwx53 &#x1f54a;️系列专栏&#xff1a;&#x1f5bc;️…

[docker] 核心知识 - 容器/镜像的管理和操作

[docker] 核心知识 - 容器/镜像的管理和操作 想要查看完整的指令&#xff0c;可以通过 docker --help 列举所有的指令&#xff0c;这里会提到一些比较常用的核心指令 查看容器的状态 这个应该是最常用的指令&#xff0c;语法为 docker ps&#xff0c; ps 为 process status …

java:多线程解决生产者消费者问题

生产者消费者问题 生产者消费者问题&#xff0c;也称有限缓冲问题&#xff0c;是一个多线程同步问题的经典案例。该问题描述了共享固定大小缓冲区的两种线程——即所谓的“生产者”和“消费者”——在实际运行时会发生的问题。生产者的主要作用是生成一定量的数据放到缓冲区中…

【Qt 学习笔记】Qt常用控件 | 按钮类控件Radio Button的使用及说明

博客主页&#xff1a;Duck Bro 博客主页系列专栏&#xff1a;Qt 专栏关注博主&#xff0c;后期持续更新系列文章如果有错误感谢请大家批评指出&#xff0c;及时修改感谢大家点赞&#x1f44d;收藏⭐评论✍ Qt常用控件 | 按钮类控件Radio Button的使用及说明 文章编号&#xff…

【机器学习】机器学习创建算法第6篇:线性回归,学习目标【附代码文档】

机器学习&#xff08;算法篇&#xff09;完整教程&#xff08;附代码资料&#xff09;主要内容讲述&#xff1a;机器学习算法课程定位、目标&#xff0c;K-近邻算法定位,目标,学习目标,1 什么是K-近邻算法,1 Scikit-learn工具介绍,2 K-近邻算法API。K-近邻算法&#xff0c;1.4 …

云服务器降价,阿里腾讯华为京东云优惠价格表整理

现在租一个服务器多少一个月&#xff1f;优惠价格低至3.8元1个月&#xff0c;租用一个月云服务器收费价格表&#xff1a;阿里云和腾讯云2核2G3M服务器优惠价格61元一年&#xff0c;折合一个月5元&#xff0c;京东云轻量云主机5.8元一个月&#xff0c;华为云服务器优惠价格3.8元…

如何落地一个FaaS平台?

简介&#xff1a; 函数即服务&#xff08;FaaS&#xff09;作为云计算 2.0 时代重要的发展方向&#xff0c;能够从工程效率、可靠性、性能、成本等方面给开发者带来巨大的价值&#xff0c;尤其是能够极大地提升研发效率。因此&#xff0c;拥抱FaaS成为开发者关心的重要技术领域…

【Java】maven的生命周期和概念图

maven的生命周期&#xff1a; 在maven中存在三套"生命周期"&#xff0c;每一套生命周期,相互独立,互不影响的,但是中同一套生命周期里,执行后面的命令会自动先执行前面的命令 CleanLifeCycle&#xff1a;清理的生命周期 clean defaultLifeCycle&#xff1a;默认的…

YashanDB亮相数据技术嘉年华精彩不断

4月12-13日&#xff0c;由墨天轮数据社区和中国数据库联盟&#xff08;ACDU&#xff09;主办的第十三届数据技术嘉年华 &#xff08;DTC 2024&#xff09;在北京召开。崖山数据库系统YashanDB受邀亮相&#xff0c;多维度展示了YashanDB的独特技术、创新成果与行业应用。 数据库…

大话设计模式之享元模式

享元模式是一种结构型设计模式&#xff0c;旨在有效地支持大量细粒度的对象共享&#xff0c;从而减少内存消耗和提高性能。 在享元模式中&#xff0c;对象分为两种&#xff1a;内部状态&#xff08;Intrinsic State&#xff09;和外部状态&#xff08;Extrinsic State&#xf…