MyException - 我的异常网
当前位置:我的异常网» 数据结构与算法 » 算法-递推计策

算法-递推计策

www.MyException.Cn  网友分享于:2015-02-03  浏览:0次
算法--递推策略

 本文地址:http://www.cnblogs.com/archimedes/p/4265019.html,转载请注明源地址。

递推法是一种重要的数学方法,在数学的各个领域中都有广泛的运用,也是计算机用于数值计算的一个重要算法。这种算法特点是:一个问题的求解需一系列的计算,在已知条件和所求问题之间总存在着某种相互联系的关系,在计算时,如果可以找到前后过程之间的数量关系(即递推式),那么,从问题出发逐步推到已知条件,此种方法叫逆推。无论顺推还是逆推,其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简单运算,充分发挥出计算机擅长于重复处理的特点。

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

引例:Fibonacci数列 

Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”(又称“Fibonacci问题”)。

问题:

一个数列的第0项为0,第1项为1,以后每一项都是前两项的和,这个数列就是著名的裴波那契数列,求裴波那契数列的第N项。 

算法:

 f[0]:=0; f[1]:=1;

 for i:=2 to n do f[i]:=f[i–1]+f[i–2];

总结:

从这个问题可以看出,在计算裴波那契数列的每一项目时,都可以由前两项推出。这样,相邻两项之间的变化有一定的规律性,我们可以将这种规律归纳成如下简捷的递推关系式:Fn=g(Fn-1),这就在数的序列中,建立起后项和前项之间的关系。然后从初始条件(或是最终结果)入手,按递推关系式递推,直至求出最终结果(或初始值)。很多问题就是这样逐步求解的。

对一个试题,我们要是能找到后一项与前一项的关系并清楚其起始条件(或最终结果),问题就可以递推了,接下来便是让计算机一步步了。让高速的计算机从事这种重复运算,真正起到“物尽其用”的效果。

递推概念

给定一个数的序列H0,H1,…,Hn,…若存在整数n0,使当n>n0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hi(0<i<n)联系起来,这样的式子就叫做递推关系。
  • 如何建立递推关系

  • 递推关系有何性质

  • 如何求解递推关系

解决递推问题的一般步骤

  • 建立递推关系式

  • 确定边界条件

  • 递推求解

递推的两种形式

顺推法和倒推法

递推的应用分类

  • 一般递推问题

  • 组合计数类问题

  • 一类博弈问题的求解

  • 动态规划问题的递推关系

(一)递推的应用(一般递推问题)

例题2:输出杨辉三角的前N行(HDOJ2032

Problem Description
还记得中学时候学过的杨辉三角吗?具体的定义这里不再描述,你可以参考以下的图形:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
Input
输入数据包含多个测试实例,每个测试实例的输入只包含一个正整数n(1<=n<=30),表示将要输出的杨辉三角的层数。
 
Output
对应于每一个输入,请输出相应层数的杨辉三角,每一层的整数之间用一个空格隔开,每一个杨辉三角后面加一个空行。
 
Sample Input
2 3
Sample Output
1
1 1
 
1
1 1
1 2 1
 
代码如下:
#include <iostream>
using namespace std;
int a[31][31];
int main( )
{
    int i,j,n;
    a[0][0]=a[1][0]=a[1][1]=1;
    for(i=2; i<31; i++) {
        for(j=0; j<=i; j++) {
            if(j==0 || i==j) {
                a[i][j]=1;
            } else {
                a[i][j]=a[i-1][j-1]+a[i-1][j];
            }
        }
    }
    while(cin>>n) {
        for(i=0; i<n; i++) {
            for(j=0; j<=i; j++) {
                if(j!=0) cout<<" ";
                cout<<a[i][j];
            }
            cout<<endl;
        }
        cout<<endl;
    } 
    return 0;
}
例题3 : Hanoi塔问题 .

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

(1)一次只能移一个圆盘;

(2)圆盘只能在三个柱上存放;

(3)在移动过程中,不允许大盘压小盘。

问将这n个盘子从a柱移动到c柱上,总计需要移动多少个盘次?

 
分析

当n=1时:A->C

当n=2时:A->B,A->C,B->C

当n=3时:

 

设f(n)为n 个盘子从1柱移到3柱所需移动的最少盘次。

当n=1时,f(1)=1。

当n=2时,f(2)=3。

以此类推,当1柱上有n(n>2)个盘子时,我们可以利用下列步骤:

第一步:先借助3柱把1柱上面的n-1个盘子移动到2柱上,所需的移动次数为f(n-1)。

第二步:然后再把1柱最下面的一个盘子移动到3柱上,只需要1 次盘子。

第三步:再借助1柱把2柱上的n-1个盘子移动到3上,所需的移动次数为f(n-1)。

由以上3步得出总共移动盘子的次数为:f(n-1)+1+ f(n-1)。

所以:f(n)=2f(n-1)+1

         hn=2hn-1+1 =2n-1    边界条件:h1=1

(二)递推的应用(组合计数)

例题4:数的计数

【问题描述】我们要求找出具有下列性质数的个数(包含输入的自然数n),先输入一个自然数n(n≤1000),然后对此自然数按照如下方法进行处理:
1.不作任何处理;
2.在它的左边加上一个自然数,但该自然数不能超过原数的一半;
3.加上数后,继续按此规则进行处理,直到不能再而 自然数为止;

 方法1:用递推

用h[n]表示自然数n所能扩展的数据个数,则:h[1]=1,h[2]=2,h[3]=2,h[4]=4,h[5]=4,h[6]=6,h[7]=6,h[8]=10,h[9]=10。分析上数据,可得递推公式:h[i]=1+h[1]+h[2]+…+h[i/2]。时间复杂度O(n2)。 

方法2:是对方法1的改进。我们定义数组s

     s(x)=h(1)+h(2)+…+h(x),

     h(x)=s(x)-s(x-1)

    此算法的时间复杂度可降到O(n)。

方法3:还是用递推

只要做仔细分析,其实我们还可以得到以下的递推公式:

(1)当i为奇数时,h(i)=h(i-1);

(2) 当i为偶数时,h(i)=h(i-1)+h(i/2);

【例题6】传球游戏

【问题描述】上体育课的时候,小蛮的老师经常带着同学们一起做游戏。这次,老师带着同学们一起做传球游戏。
  游戏规则是这样的:n(3<=n<=30)个同学站成一个圆圈,其中的一个同学手里拿着一个球,当老师吹哨子时开始传球,每个同学可以把球传给自己左右的两个同学中的一个(左右任意),当老师再吹哨子时,传球停止,此时,拿着球没传出去的那个同学就是败者,要给大家表演一个节目。
  聪明的小蛮提出一个有趣的问题:有多少种不同的传球方法可以使得从小蛮手里开始传的球,传了m(3<=m<=30)次后,又回到小蛮手里。两种传球被视作不同的方法,当且仅当这两种方法中,接到球的同学按照顺序组成的序列是不同的。比如3个同学1号、2号、3号,并假设小蛮为1号,球传了3次回到小蛮手里的方式有1->2->3->1和1->3->2->1,共两种。 

分析:

设f[i][k]表示经过k次传到编号为i的人手中的方案数,传到i号同学的球只能来自于i的左边一个同学和右边一个同学,这两个同学的编号分别是i-1和i+1,所以可以得到以下的递推公式:

f[i][k]=f[i-1][k-1]+f[i+1][k-1]

f[1][k]=f[n][k-1]+f[2][k-1],   当i=1时

f[n][k]=f[n-1][k-1]+f[1][k-1],   当i=1时

边界条件:f[1][0]=1;结果在f[1][m]中。

核心代码:

cin>>n>>m;
memset(f,0,sizeof(f));
f[1][0]=1;
for(k=1;k<=m;k++)
{   
    f[1][k]=f[2][k-1]+f[n][k-1];
    for(i=2;i<=n-1;i++)f[i][k]=f[i-1][k-1]+f[i+1][k-1];
    f[n][k]=f[n-1][k-1]+f[1][k-1];
}
cout<<f[1][m]<<endl;

(三)递推的应用(组合计数)

Catalan数

定义:Cn=n+2条边的多边形,能被分割成三角形的方案数,例如5边型的分割方案有:

 

如图,有一个正n+2边形。任取一边,从这边的端点开始,依次顺时针给顶点编号为:0,1,2,3,….,n,n+1(所取的边端点编号为:0,n+1)。这样,除线段所在顶点外,还有n个顶点:1,2,3,…,n。我们以该线段为三角形的一条边,另一个顶点为i(1<=i<=n)。 

我们设题意要求的三角形剖分方案数为H(n),即除线段顶点(编号0与n+1)外,还有n个顶点时的三角形剖分方案为H(n)。则以顶点0,i为指定线段(上面还有1,2,…,i-1,共i-1个顶点)的剖分数位H(i-1);以顶点n+1,i为指定线段的剖分数为H(n-i)。根据乘法原理,以0,i,n+1为一剖分三角形的剖分数应为:H(i-1)*H(n-i),i=1,2,…,n,所得的剖分各不相同,根据加法原理则有:
这与Catalan数C(n)的表达式是一致的。故本题答案为H(n)=C(n)。

具体实现时,若直接用上述公式计算,对数字的精度要求较高。可将其化为递推式:

再进行递推计算,并且注意类型的定义要用long long长整型。

(四)递推的应用(博弈问题)

例题:走直线棋问题。

有如下所示的一个编号为1到n的方格:

现由计算机和人进行人机对奕,从1到n,每次可以走k个方格,其中k为集s={a1,a2, a3,....am}中的元素(m<=4),规定谁最先走到第n格为胜,试设计一个人机对奕方案,摸拟整个游戏过程的情况并力求计算机尽量不败。

分析:

题设条件:若谁先走到第N格谁将获胜,例如,假设S={1,2},从第N格往前倒推,则走到第N-1格或第N-2格的一方必败,而走到第N-3格者必定获胜,因此在N,S确定后,棋格中每个方格的胜、负或和态(双方都不能到达第N格)都是可以事先确定的。将目标格置为必胜态,由后往前倒推每一格的胜负状态,规定在自己所处的当前格后,若对方无论走到哪儿都必定失败,则当前格为胜态,若走后有任一格为胜格,则当前格为输态,否则为和态。

设1表示必胜态,-1表示必败态,0表示和态或表示无法到达的棋格。

例如,设N=10,S={1,2},则可确定其每个棋格的状态如下所示:

而N=10,S={2,3}时,其每格的状态将会如下所示:

有了棋格的状态图后,程序应能判断让谁先走,计算机选择必胜策略或双方和(双方均不能到达目标格)的策略下棋,就能保证计算机尽可能不败。

(五)递推的应用(动态规划中的递推)

例题:方格取数

在一个n×m的方格中,m为奇数,放置有n×m个数 ,如图,方格中间的下方有一人,此人可按照五个方向前进但不能越出方格,见右下图。人每走过一个方格必须取此方格中的数。要求找到一条从底到顶的路径,使其数相加之和为最大。输出和的最大值。

分析:

我们用坐标(x,y)唯一确定一个点,其中(m,n)表示图的右上角,而人的出发点是,受人前进方向的限制,能直接到达点(x,y)的点只有(x+2,y-1),(x+1,y-1),(x,y-1),(x-1,y-1),(x-2,y-1)。到点(x,y)的路径中和最大的路径必然要从(m/2,0)到(x+2,y-1),(x+1,y-1),(x,y-1),(x-1,y-1),(x-2,y-1)的几条路径中产生,既然要求最优方案,当然要挑一条和最大的路径,关系式如下:

Fx,y= Max{Fx+2,y-1 ,Fx+1,y-1,Fx,y-1,Fx-1,y-1,Fx-2,y-1}+Numx,y

其中Numx,y 表示(x,y) 点上的数字。

边界条件为:

动态规划与递推的关系

上题实质上是采用动态规划来求解,那么与递推动态规划之间到底是什么关系呢?

我们不妨画个图(如下图)。而通常人们理解的递推关系就是一般递推关系,故认为动态规划与递推关系是两个各自独立的个体。

 

1、一般递推边界条件很明显,动态规划边界条件比较隐蔽,容易被忽视

2、一般递推数学性较强,动态规划数学性相对较弱

3、一般递推一般不划分阶段,动态规划一般有较为明显的阶段

 

PS:更多递推练习,可以看看《递推求解专题练习

文章评论

5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
代码女神横空出世
代码女神横空出世
程序员应该关注的一些事儿
程序员应该关注的一些事儿
程序员必看的十大电影
程序员必看的十大电影
编程语言是女人
编程语言是女人
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
程序员的鄙视链
程序员的鄙视链
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
如何成为一名黑客
如何成为一名黑客
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
中美印日四国程序员比较
中美印日四国程序员比较
Java程序员必看电影
Java程序员必看电影
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
每天工作4小时的程序员
每天工作4小时的程序员
总结2014中国互联网十大段子
总结2014中国互联网十大段子
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
鲜为人知的编程真相
鲜为人知的编程真相
漫画:程序员的工作
漫画:程序员的工作
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
老程序员的下场
老程序员的下场
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
程序员和编码员之间的区别
程序员和编码员之间的区别
我的丈夫是个程序员
我的丈夫是个程序员
旅行,写作,编程
旅行,写作,编程
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
程序员都该阅读的书
程序员都该阅读的书
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
我是如何打败拖延症的
我是如何打败拖延症的
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
 程序员的样子
程序员的样子
一个程序员的时间管理
一个程序员的时间管理
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
为什么程序员都是夜猫子
为什么程序员都是夜猫子
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有