程序设计基础课件

1第九章

递归思想与相应算法2014.12.01

3200整理课件1第九章

递归思想与相应算法2014.12.01

320029.2

递归算法举例

——分书问题带回溯的递归程序的设计与实现(1)

整理课件29.2递归算法举例

——分书问题带回溯的递3

0 1 2 3 4ABCDE0011011001011010001001001人书任务描述：有编号分别为0，1，2，3，4的五本书，准备分给A,B,C,D,E五个人。希望你写一个程序，输出所有分书方案，让人人皆大欢喜。假定5个人对5本书的阅读兴趣如下表：整理课件3 0 1 2 3 4001101141、定义一个整型的二维数组，将表中的阅读喜好用初始化方法赋给这个二维数组。可定义intlike[5][5]={{0,

0,

1,

1,

0},

{1,

1,

0,

0,

1},

{0,

1,

1,

0,

1},

{0,

0,

0,

1,

0},

{0,

1,

0,

0,

1}

};解题思路：

1,i喜欢编号为j的书like[i][j]= 0,i不喜欢编号为j的书每个人阅读兴趣用一个二维数组描述：整理课件41、定义一个整型的二维数组，将表中的阅读喜好用初始化方法赋52、定义一个整型一维数组book[5]用来记录书是否已被选用。

用下标作为五本书的标号，已被分配的书对应的数组元素值为1，未被分配的书对应的数组元素值为0。初始时，所有数组元素皆置0。

intbook[5]={0,0,0,0,0};

若book[j]==1则表示第j本已分配给某个人了解题思路：整理课件52、定义一个整型一维数组book[5]用来记录书是否已被选63、画出思路图定义Try(i)——试着给第i人分书(i=0,1,…,4)i

表示人的编号j表示书的编号给第i个人分书，有5种分法，分别对应分配第j本书给第i个人，每种可能的分法均要尝试才算是完成了对第i个人分书尝试。所以要使用与结点！整理课件63、画出思路图i表示人的编号给第i个人分书，有5种分法，7爱好匹配且尚未分配整理课件7爱好匹配且尚未分配整理课件8说明：（1）试着给第i个人分书，先试分0号书，再分1号书，分2号书…，因此有一个与结点，让j表示书j=0,1,2,3,4。（2）LP为循环结构的循环体。（3）条件C是由两部分“与”起来的。“第i个人喜欢j书，且j书尚未被分走”。满足这个条件是第i人能够得到j书的条件。（4）如果不满足C条件，则什么也不做，这是直接可解结点。整理课件8说明：整理课件9（5）满足C条件，做三件事。

sh1第一件事：将j书分给i。 用一个数组take[i]=j，记住书j给了i，

同时记录j书已被选用，book[j]=1。整理课件9（5）满足C条件，做三件事。整理课件10sh2第二件事：查看i是否为4。如果不为4，表示尚未将所有5个人所要的书分完，这时应递归再试下一人，即Try(i+1)。

如果等于4，则应先使方案数加一，然后输出第n个方案下的每个人所得之书。整理课件10sh2第二件事：查看i是否为4。整理课件11sh3第三件事：回溯。 让第i人退回

j书，恢复j书尚未被选的标志，即book[j]=0。这是在已输出第n个方案之后，去寻找下一个分书方案所必需的。（6）在有了上述的与或图之后，我们很容易写出一个程序框图。先看被调用函数Try(i)的框图。整理课件11sh3第三件事：回溯。整理课件12sh3：回溯整理课件12sh3：回溯整理课件13//*******************************************//*程序：assign_book.cpp*//*作者：wuwh*//*编制时间：2002年10月28日*//*主要功能：分书问题*//*******************************************#include<iostream> //coutusingnamespacestd;inttake[5],n; //整型变量intlike[5][5]={{0,0,1,1,0},{1,1,0,0,1},{0,1,1,0,1},{0,0,0,1,0},{0,1,0,0,1}};//各人对书的喜好intbook[5]={0,0,0,0,0}; //整型变量,定义数组，初始化下面讨论主程序应该做的事情1、将分书方案号预置02、从第0号人（A）开始试分书，调用Try(0)整理课件13//*************************14voidTry(inti){

for(intj=0;j<=4;j++)

{//循环，j代表书号

if((like[i][j]>0)&&

(book[j]

==

0)){

//满足分书条件

tak

e[i]

=

j; //把j号书给i

book[j]

=

1; //记录j书已分SH1分书条件C整理课件14voidTry(inti)SH1分书条件C整理课件15

if(i

==

4){ //如果i==4,输出分书方案

n++;

//

输出分书方案

cout<<"第"<<n<<"个方案\n"; for(intk=0;k<=4;k++){

cout<<take[k]<<"号书分给";

cout<<char('A'+k)<<endl;

}

cout<<endl; } elseTry(i+1);//如i!=4,

继续给下一人分书

book[j]=0;

//回溯——“退还”编号为j的书

}//__if__ }//__for_j__}SH2SH3整理课件15 if(i==4){ //如果i==4,输16intmain() //主函数{ //主函数开始

n=0; //分书方案号预置0

//从第0个人（A）开始分书

Try(0); return0;} //主函数结束 整理课件16intmain() //主函数整理课件17小结这是一种试探型的算法，采用的是“向前走，碰壁回头”的策略。把这个策略与递归结合起来，就是称为“回溯法”的递归解题思路。

在“分书”示例的解题过程中，把已“分配”的书再“退回来”就是“回溯”。整理课件17小结整理课件189.2

递归算法举例

——八皇后问题带回溯的递归程序的设计与实现(2)

整理课件189.2递归算法举例

——八皇后问题带回19

12345678

12345678观看8皇后GUI演示整理课件1912320

在8×8的棋盘上，放置8个皇后（棋子），使两两之间互不攻击。所谓互不攻击是说任何两个皇后都要满足：（1）不在棋盘的同一行；（2）不在棋盘的同一列；（3）不在棋盘的同一对角线上。因为棋盘一共有8行，每行能有且只能有一个皇后，所以，至多能放8个皇后。这8个皇后“每个应该放在哪一列上”是解该题的任务。我们还是用试探的方法，即“向前走，碰壁回头”的策略。这就是“回溯法”的解题思路。整理课件20在8×8的棋盘上，放置8个皇后（棋子），使21定义函数Try(i)：将第i个皇后放到棋盘上。由于棋盘的对称性，我们假定是逐行放置皇后。下面讨论将第i行的皇后放在j列位置上之后（如果该位置是安全的话），棋盘各位置安全性的变化（对未来放置皇后过程有影响）。

在放第i行的皇后时，第i行上应还没有皇后，不会在行上遭到其它皇后的攻击。只考虑来自列和对角线的攻击。

用数组q来记录各行皇后的位置（列号），q[i]=j表示第i行皇后放到第j列。显然，放过第i个皇后之后，第j列就不安全了。若用数组C表示各列的安全性，则C[j]=false。

同时，通过(i,j)的对角线也不安全了。经过分析可以看出:

(1)对于从左上到右下的对角线，每个位置都有

i–j=常数的特点；

(2)对于从左下到右上的对角线，每个位置都有

i+j=常数的特点。整理课件21定义函数Try(i)：将第i个皇后放到棋盘上。整理课件22怎样理出解题的思路？

——如何降低难题的难度？先讨论四皇后问题目的是降低规模，降低难度

寻找解题规律之后再回到原题的解法注意：

因为是从第一行开始一行一行按顺序放皇后，所以可以不用判行是否安全，只判列和对角线是否安全整理课件22怎样理出解题的思路？

——如何降低难题的难度？先讨论四皇23

判列是否安全问题

可以使用数组，元素数目５定义bool

C[5];true第j列未放皇后

C[j]=

false第j列已放皇后

j=1,2,3,4

下面的难点是判对角线是否安全问题整理课件23判列是否安全问题整理课件24QQ

ATry(i)j=12...4第2行皇后放到第3列，导致第3行无法无法放置皇后整理课件24QQ25Q

ATry(i)j=12...4QQ第2行皇后放第4列，导致第3行仅一个位置安全，第4行无安全位置整理课件25Q26Q

ATry(i)j=12...4Q取走第3行的皇后整理课件26Q27Q

ATry(i)j=12...4取走第2行的皇后整理课件27Q28Q

ATry(i)j=12...4QQQ取走第1行皇后，重新放置到第2列。终于……成功了整理课件28Q29

123412341Q1Q

2Q

2Q

33Q

44123412341Q

1Q

2

Q2Q

3Q3

Q

4Q4Q

整理课件29123430重点研究怎样描述对角线整理课件30重点研究怎样描述对角线整理课件31Y2=X2+B2Y1=-X1+B1XYY1+X1=B1Y2－

X2=B2整理课件31Y2=X2+B2Y1=-X1+B1XYY32

j

2123431i+j42i536478从右上到左下的斜线数值范围是2~8整理课件32从右上到左33

ji-ji-j+5

1234-321-23i2-14305

416

27

38从左上到右下的斜线将数值范围调整到2~8，与“右上到左下斜线”计算结果范围保持一致。整理课件33从34定义boolR[9]R[k]k=2,3,…,8k=i+ji=1,2,…,4j=1,2,…,4

描述从右上至左下的对角线是否安全数据类型为布尔型

true--------安全

false--------不安全使用数组来描述对角线上是否安全整理课件34定义boolR[9]使用数组来描述对角线上35定义boolL[9]L[k]k=2,3,…,8k=i–j+5i=1,2,…,4j=1,2,…,4

描述从左上至右下的对角线是否安全数据类型为布尔型

true--------安全

false--------不安全整理课件35定义boolL[9]整理课件36利用这个特点，我们可以令

L[i-j+5]=false;

R[i+j]=false;来表示在(i,j)位置放皇后之后，通过该位置的两条对角线上不安全了。这样我们得出了在(i,j)位置放皇后的安全条件为

nq=C[j]&&L[i-j+5]&&R[i+j]

整理课件36利用这个特点，我们可以令整理课件37

ATry(i)

j=12..4

Lp有了上述铺垫，我们就可以设计算法了。首先想到的是使用递归思想。画出与或结点图。整理课件37有了上述铺垫，我们就可以设计算法了。首先想到的38

Lp

不安全安全什么也不做q[i]=j;c[j]=true;C[j]=false;R[i+j]=true;L[i-j+5]=false;i<4i==4L[i-j+5]=true;R[i+j]=false;Try(i+1);Num++;

输出方案

整理课件38Lp整理课件39参考程序

整理课件39整理课件intmain() //主函数{

定义变量：循环控制变量i 方案数Num,初始化为0

置所有列为安全的

置所有对角线为安全的

递归放置4个皇后，从第一个开始放

Try(1); return0;}40整理课件intmain() //主函数40整理课件voidTry(inti) //被调用函数{

定义变量

for(j=1;j<=4;j++){ //循环判放j列时是否安全，如安全做如下3件事

1记录位置(i,j)，

置列和对角线不安全。

2判断是否放完4个皇后

未放完则继续放下一个：Try(i+1);

已经放完4个皇后，方案数加1

输出方案号和具体位置

3修改安全标志，回溯，找新方案

}//for}41整理课件voidTry(inti) //被调用函数41整理课42//*******************************************//*程序：4Q.cpp*//*作者：wuwh*//*时间：2006年2月26日*//*功能：四皇后问题

*//*******************************************#include<iostream> //预编译命令usingnamespacestd;

constintNormalize=5; //定义常量，用来统一数组下标intNum=1; //整型变量，记录方案数intq[5]; //记录4个皇后所占用的列号boolC[5]; //C[1]~C[4]，布尔型变量，当前列是否安全boolL[9]; //L[2]~L[8]，布尔型变量，(i-j)对角线是否安全boolR[9]; //R[2]~R[8]，布尔型变量，(i+j)对角线是否安全整理课件42//*************************43voidTry(inti) //被调用函数{ intj; //循环变量，表示列号

intk; //临时变量

for(j=1;j<=4;j++) //循环

{

if((C[j]==true)&&

(R[i+j])==true)&&(L[i-j+Normalize]==true))//表示第i行，第j列是安全的整理课件43整理课件44{ q[i]=j;

//第一件事，占用位置(i,j)

C[j]=false;

//修改安全标志，包括所在列和两个对角线

L[i-j+Normalize]=false;

R[i+j]=false;

if(i<4) //第二件事，判断是否放完8个皇后

{ //未放完4个皇后

Try(i+1); //则继续放下一个

} else //已经放完4个皇后

{ Num++; //方案数加1 cout<<"方案"<<Num<<"：";//输出方案号

for(k=1;k<=4;k++) cout<<q[k]<<""; //输出具体方案

cout<<endl; //换行

}

C[j]=true; //第三件事，修改安全标志，回溯

L[i-j+Normalize]=true; R[i+j]=true;}整理课件44整理课件45

} //循环结束} //Try函数结束intmain() //主函数{ inti; //循环变量

Num=0; //方案数清零

for

(i=1;i<5;i++) //置所有列为安全

C[i]=true; for

(i=0;i<9;i++) //置所有对角线为安全

{

L[i]=true;

R[i]=true;

}

Try(1); //递归放置4个皇后，从第一个开始放

return0;}整理课件45 } //循环结束整理课件46放置8

个皇后与4个皇后相比，哪里有了变化？——哪些需要调整？哪里没有改变？——哪些继续沿用？整理课件46与4个皇后相比，整理课件古老的哲学命题——变与不变万变不离其宗以不变应万变斗转星移，物是人非——————————————

皇后数量从4增加为8

棋盘从4x4扩大为8x8——————————————

求解的策略（套路）相同

对角线数学关系仍然满足47整理课件古老的哲学命题——变与不变万变不离其宗47整理课件48

ij2+3

12345678

1234567

false82345678910111213141516整理课件48i49定义boolR[17]R[k]k=2,3,…,16k=i+ji=1,2,…,8j=1,2,…,8

描述从右上至左下的对角线是否安全数据类型为布尔型

true--------安全

false--------不安全整理课件49定义boolR[17]整理课件50

12345678-81-7i-j=-72-6i-j=-63-5i-j=-5

i4-4i-j=-45-3i-j=-36-2i-j=-27-1i-j=-180i-j=01i-j=12i-j=23i-j=34i-j=45i-j=56i-j=67i-j=78整理课件501234551j1234567812i-j+9=223i-j+9=334i-j+9=4

i45i-j+9=556i-j+9=667i-j+9=778i-j+9=889i-j+9=910i-j+9=1011i-j+9=1112i-j+9=1213i-j+9=1314i-j+9=1415i-j+9=1516i-j+9=16

整理课件51j1234552j12345678false12i-j+9=223i-j+9=334i-j+9=4

i45i-j+9=556i-j+9=667i-j+9=778i-j+9=889i-j+9=910i-j+9=1011i-j+9=1112i-j+9=1213i-j+9=1314i-j+9=1415i-j+9=15

2–7+9=416i-j+9=16

整理课件52j1234553

定义boolL[17]L[k]k=2,3,…,16k=i–j+9i=1,2,…,8j=1,2,…,8

描述从左上至右下的对角线是否安全数据类型为布尔型

true--------安全

false--------不安全整理课件53定义boolL[17]整理课件54利用这个特点，我们可以令

L[i-j+9]=false;

R[i+j]=false;来表示在(i,j)位置放皇后之后，通过该位置的两条对角线上不安全了。这样我们得出了在(i,j)位置放皇后的安全条件为

nq=C[j]&&L[i-j+9]&&R[i+j]

整理课件54利用这个特点，我们可以令整理课件55

L[i-j+9]=false;

R[i+j]=false;

?1.数组的下标不能为负值2.选9是为了使L数组和R数组的下标上下界取齐，均为2,3,…,16整理课件55L[i-j+9]=false;

56为了判断安全条件，在程序中要用到三个数组（1）C[j]为布尔型的，j=1,2,…,8，初始化时全部置为true；（2）L[k]为布尔型的，k=i-j+9,k=2,3,…,16,初始化时全部置为true；（3）R[m]为布尔型的,m=i+j,m=2,3,…,16，初始化时全部置为true；整理课件56为了判断安全条件，在程序中要用到三个数组整理课件573、从思路上，在放第i个皇后时（当然在第i行），选第j列，当nq为true时，就可将皇后放在(i,j)位置，这时做如下3件事（1）放皇后q[i]=j，同时让第j列和过(i,j)位置的两条对角线变为不安全。即让

C[j]=false;L[i-j+9]=false;R[i+j]=false;整理课件573、从思路上，在放第i个皇后时（当然在第i行），选58（2）之后查一下i是否为8，如果为8，则表明已经放完8个皇后，这时让方案数Num加1，输出该方案下8个皇后在棋盘上的位置。否则，未到8个，还要让皇后数i加1再试着放，这时还要递归调用Try(i+1)。（3）回溯，将先前放的皇后从棋盘上拿起来，看看还有没有可能换一处放置。这时要将被拿起来的皇后的所在位置的第j列，和两条对角线恢复为安全的。我们用与或图来描述8皇后问题的解题思路。整理课件58（2）之后查一下i是否为8，如果为8，则表明已经放59整理课件59整理课件60

ATry(i)j=12...8

Lp整理课件6061

Lp

不安全安全什么也不做q[i]=j;c[j]=true;C[j]=false;R[i+j]=true;L[i-j+9]=false;i<8i==8L[i-j+9]=true;R[i+j]=false;Try(i+1);Num++;输出整理课件6162八皇后问题的参考程序整理课件62八皇后问题的参考程序整理课件63//*******************************************//*程序：8Q.cpp*//*作者：wuwh*//*时间：2002年11月06日*//*功能：八皇后问题*//*******************************************#include<iostream> //预编译命令usingnamespacestd;

constintNormalize=9; //定义常量，用来统一数组下标intNum=0; //整型变量，记录方案数intq[9]; //记录8个皇后所占用的列号boolC[9]; //C[1]~C[8]，布尔型变量，当前列是否安全boolL[17]; //L[2]~L[16]，布尔型变量，(i-j)对角线是否安全boolR[17]; //R[2]~R[16]，布尔型变量，(i+j)对角线是否安全整理课件63//*************************64voidTry(inti) //被调用函数{ intj; //循环变量，表示列号

intk; //临时变量

for(j=1;j<=8;j++) //循环

{

if((C[j]==true)&&(R[i+j])==true)&&

(L[i-j+Normalize]==true))//表示第i行，第j列是安全的整理课件64整理课件65{ q[i]=j;

//第一件事，占用位置(i,j)

C[j]=false;

//修改安全标志，包括所在列和两个对角线

L[i-j+Normalize]=false;

R[i+j]=false;

if(i<8) //第二件事，判断是否放完8个皇后

{ //未放完8个皇后

Try(i+1); //则继续放下一个

} else //已经放完8个皇后

{ Num++; //方案数加1 cout<<"方案"<<Num<<"：";//输出方案号

for(k=1;k<=8;k++) cout<<q[k]<<""; //输出具体方案

cout<<endl; //换行

}

C[j]=true; //第三件事，修改安全标志，回溯

L[i-j+Normalize]=true; R[i+j]=true;}整理课件65整理课件66

} //循环结束} //Try函数结束intmain() //主函数{ inti; //循环变量

Num=0; //方案数清零

for

(i=0;i<9;i++) //置所有列为安全

C[i]=true; for

(i=0;i<17;i++) //置所有对角线为安全

{

L[i]=

true;

R[i]=true;

}

Try(1); //递归放置8个皇后，从第一个开始放

return0;}整理课件66 } //循环结束整理课件67共92组解，部分答案如下：方案1：15863724方案2：16837425方案3：17468253方案4：17582463方案5：24683175方案6：25713864方案7：25741863方案8：26174835方案9：26831475方案10：27368514整理课件67共92组解，部分答案如下：整理课件689.2

递

归

算

法

举

例

——青蛙过河整理课件689.2递归算法举例

——青蛙过河整理课件69问题描述（2000年全国青少年信息学奥林匹克试题）一条小溪尺寸不大，青蛙可以从左岸跳到右岸，在左岸有一石柱L，面积只容得下一只青蛙落脚，同样右岸也有一石柱R，面积也只容得下一只青蛙落脚。有一队青蛙从尺寸上一个比一个小。我们将青蛙从小到大，用1，2，…，n编号。规定初始时这队青蛙只能趴在左岸的石头L上，按编号一个落一个，小的落在大的上面。不允许大的在小的上面。整理课件69问题描述整理课件70在小溪中有S个石柱，有y片荷叶，规定溪中的柱子上允许一只青蛙落脚，如有多只同样要求按编号一个落一个，大的在下，小的在上，而且必须编号相邻。对于荷叶只允许一只青蛙落脚，不允许多只在其上。对于右岸的石柱R，与左岸的石柱L一样允许多个青蛙落脚，但须一个落一个，小的在上，大的在下，且编号相邻。当青蛙从左岸的L上跳走后就不允许再跳回来；同样，从左岸L上跳至右岸R，或从溪中荷叶或溪中石柱跳至右岸R上的青蛙也不允许再离开。问:在已知溪中有s根石柱和y片荷叶的情况下，最多能跳过多少只青蛙？整理课件70在小溪中有S个石柱，有y片荷叶，规定溪中的柱子上允许一只71在已知溪中有s根石柱和y片荷叶的情况下，最多能跳过多少只青蛙？（s,y）NumintJump(s,y);?参数： s:河中柱子数 y:河中荷叶数返回值：

最多跳过的数目整理课件71在已知溪中有s根石柱和y片荷叶的情况下，最多能跳过多少只72先从个别再到一般，要善于对多个因素作分解，孤立出一个一个因素来分析，化难为易。简化问题，探索规律有正确的策略才能产生正确的思路整理课件72先从个别再到一般，要善于对多个因素作分解，孤立出一个一个73先看简单情况，河中无柱子：s=0

，

Jump(0,y)

当

y=1时，Jump(0,1)=2；

第一步：1#跳到荷叶上；

第二步：2#从

L直接跳至

R上；

第三步：1#再从荷叶跳至

R上。

如下图：

1#

2#整理课件73先看简单情况，河中无柱子：s=0，整理课件74当

y=2时，

Jump(0,2)=3；

1#，2#，3#3只青蛙在

L处

第一步：1#从

L跳至叶

1上，

第二步：2#从

L跳至叶

2上，

第三步：3#从

L直接跳至

R上，

第四步：2#从叶

2跳至

R上，

第五步：1#从叶

1跳至

R上，采用归纳法：Jump(0,y)=y+1；一片荷叶只能落一只青蛙！整理课件74当y=2时，采用归纳法：一片荷叶只能落一只青蛙！75再看Jump(s,y)

先看一个最简单情况：

s=1，y=1。从图上看出需要

9步，跳过

4只青蛙。

1#青蛙从

L－>Y；

2#青蛙从

L－>S；

1#青蛙从

Y－>S；

3#青蛙从

L－>Y；

4#青蛙从

L－>R；

3#青蛙从

Y－>R；

1#青蛙从

S－>Y；

2#青蛙从

S－>R；

1#青蛙从

Y－>R；整理课件75再看Jump(s,y)

先看一个最简单情况：s76tLSYRL4L3L2L1S2S1R4R3R2R10

1

2

3

4

5

6

7

8

94

4

4

4

43

3

3

32

21

2

2

2

2

2

1

1

1

1

1

3

1

1

4

4

4

4

4

3

3

3

3

2

2

1表一整理课件76LSYRL4L3L2L1S2S1R4R3R2R10

1

77为了将过河过程描述得更清楚，我们给出了表1。表中L1L2L3L4表示左岸石柱上落在一起的青蛙的高度位置。L1在最上面，L4在最下面的位置。引入这个信息就可比较容易地看出对青蛙占位的约束条件。同理R1R2R3R4也是如此。对水中石柱S，也分成两个高度位置S1S2。对荷叶Y无须分层，因为它只允许一只青蛙落在其上。t=0为初始时刻，青蛙从小到大落在石柱L上。t=1为第一步：1#从L跳至荷叶Y上；L上只剩2#3#4#。t=2为第二步；2#从L跳至石柱S上，处在S2位置上，L上只剩3#和4#。t=3为第三步，1#从Y跳至S，将Y清空。整理课件77为了将过河过程描述得更清楚，我们给出了表1。表中L1L78这时你看，S上有1#、2#，L上有3#、4#，好象是原来在L上的4只青蛙，分成了上下两部分，上面的2只通过荷叶y转移到了S上。这一过程是一分为二的过程。即将L上的一队青蛙，分解为两个队，每队各２只，且将上面的２只转移到了S上。这时我们可以考虑形成两个系统，一个是L，Y，R系统，一个是S，Y，R系统。前者２只青蛙号大；后者２只青蛙号小。先跳号大的，再跳号小的。从第五步到第九步可以看出的确是这么做的。整理课件78这时你看，S上有1#、2#，L上有3#、4#，好象是原来792YRSL31整理课件792YRSL31整理课件80LYS,将

L上的一半青蛙转移到

S上LYR,将

L上的青蛙转移到

R上SYR,将

S上的青蛙转移到

R上对于LYR系统，相当于Jump(0,1)

对于SYR系统，相当于Jump(0,1)两个系统之和为2*Jump(0,1)，因此有：

Jump(1,1)=2*Jump(0,1)=2*2=4

整理课件80整理课件81

现在再看S=2，y=1Jump(2,1)

我们将河中的两个石柱称作S1和S2，荷叶叫y.

考虑先将L上的青蛙的一半借助于S2和y转移到S1上，当然是一半小号的青蛙在S1上，大的留在L上。整理课件81 整理课件82s=2,