算法基础二Python递归算法解析ppt课件.pptx
递归,算法,人理解迭代，神理解递归,递归：指在函数的定义中使用函数自身的方法。”递归“ 表达了两个意思：”递“”归“，基本思想是把规模大的问题转化为规模小的相似的子问题来解决。在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况。另外这个解决问题的函数必须有明显的结束条件，这样就不会产生无限递归的情况了,递归应用三步法：1). 明确递归终止条件 例如：当N=0时，递归终止2). 给出递归终止时的处理办法例如： if n=0 :return 13). 提取重复的逻辑，递归的一般式，缩小问题规模例如：return n*f（n-1）,例1：应用三步法解决实际问题：阶乘问题1). 明确递归终止条件 当N=0时，递归终止2). 给出递归终止时的处理办法 if n=0 :return 13). 提取重复的逻辑，缩小问题规模重复的逻辑是：return n*f（n-1）,defjiecheng(n):ifn=0:return1else:returnn*jiecheng(n-1)zzshu=int(input(输入待求的阶乘的正整数)print(zzshu,的阶乘是,jiecheng(zzshu),例2：应用三步法解决实际问题：斐波那契数列1). 明确递归终止条件 当N=1,或n=2时，递归终止2). 给出递归终止时的处理办法 if n=1 or n=2:return 13). 提取重复的逻辑，缩小问题规模*重复的逻辑是： f（n）=f(n-1)+f（n-2）,deffbnqsl(n):ifn=1orn=2:return1else:returnfbnqsl(n-1)+fbnqsl(n-2)zzshu=int(input(输入待求的斐波那切数列的个数为)print(zzshu,个斐波那切数列的是)foriinrange(1,zzshu+1):print(fbnqsl(i),例3：应用三步法解决实际问题：稍微复杂一点的例题：汉诺塔问题,法国数学家爱德华卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。,画图是分析问题的一个好习惯,1、先假设除最下面的盘子之外，我们已经成功地将上面的63个盘子移到了b柱，此时只要将最下面的盘子由a移动到c即可。如图：,分解问题,2、当最大的盘子由a移到c后，b上是余下的63个盘子，a为空。因此现在的目标就变成了将这63个盘子由b移到c。这个问题和原来的问题完全一样，只是由a柱换为了b柱，规模由64变为了63。因此可以采用相同的方法，先将上面的62个盘子由b移到a，再将最下面的盘子移到c,3、要以B为辅助将A上64个盘子转移到C上将c柱子作为辅助，把a上的63个圆盘移动到b上将a上最后一个圆盘移动到c这样问题转移成，接下来要以a为辅助，将B上所有63盘子转移到C上。,defmove(n,a,b,c):#将A柱上N个盘子以B柱为辅助移动到C柱上ifn=1:print(a,-,c)#如果只有1个盘子，直接将A柱上的盘子移动到c柱上else:move(n-1,a,c,b)#将N-1个盘子从A柱上以c柱为辅助移动到b柱上,这时a柱上只有当前最大一个盘子move(1,a,b,c)#将a柱上剩下的这个最大的盘子从A柱上以b柱为辅助（实际用不上B柱）移动到c柱上,这时a柱为空move(n-1,b,a,c)#将B柱上剩下的N-1个盘子以A柱为辅助，移动到C柱上move(4,A,B,C),递归习题1：八皇后问题：八重循环？体会递归之美！十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。递归习题2：波兰表达式 波兰表达式是一种把运算符前置的算术表达式，例如普通的表达式2 + 3的逆波兰表示法为+ 2 3。逆波兰表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序，例如(2 + 3) * 4的逆波兰表示法为* + 2 3 4。本题求解逆波兰表达式的值，其中运算符包括+ - * /四个。 输入 输入为一行，其中运算符和运算数之间都用空格分隔，运算数是浮点数 输出 输出为一行，表达式的值。递归习题3：表达式计算 输入为四则运算表达式，仅由整数、+、*、/ 、(、) 组成，没有空格，要求求其值。假设运算符结果都是整数。/结果也是整数 递归习题4：爬楼梯 树老师爬楼梯，他可以每次走1级或者2级，输入楼梯的级数，求不同的走法数 例如：楼梯一共有3级，他可以每次都走一级，或者第一次走一级，第二次走两级，也可以第一次走两级，第二次走一级，一共3种方法。 输入 输入包含若干行，每行包含一个正整数N，代表楼梯级数，1 = N = 30输出不同的走法数，每一行输入对应一行 。,递归习题5：放苹果 把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？5，1，1和1，5，1 是同一种分法。 输入 第一行是测试数据的数目t（0 = t = 20）。以下每行均包含二个整数M和N，以空格分开。1=M，N=10。 输出 对输入的每组数据M和N，用一行输出相应的K。 样例输入 1 7 3 样例输出 8 。递归习题6：算24输入 输入数据包括多行，每行给出一组测试数据，包括4个小于10个正整数。最后一组测试数据中包括4个0，表示输入的结束，这组数据不用处理。 输出 对于每一组测试数据，输出一行，如果可以得到24，输出“YES”；否则，输出“NO”。 样例输入 5 5 5 1 1 1 4 2 0 0 0 0 样例输出 YES NO,谢谢,观看!,八皇后问题,国际象棋的皇后能吃掉横向纵向和斜向的棋子，非常厉害，比中国象棋里的车厉害多了。一个皇后放到棋盘中央，就一小半的格子不能放了其他皇后了。按什么思路去求解呢？我们假定存在一组数a=a0,a1,a2,a3,a4,a5,a6,a7每个数字都是大于等于0小于8的正整数，表示某一行皇后所处的位置。这样的一组数如果满足了八皇后题面的要求，我们称之为八皇后问题的一个解。1、64选8，从64个格子里选8个，要计算44.26亿种可能2、考虑每一行每一列只能放置一个棋子，8！，是40320种可能，这样好算多了，但是如果这样要写8重循环，如果是20行呢，写20重循环？,递归习题1：八皇后问题： 共有92种布局,回溯法解题思想：回溯法解题思想有通用解题思路之称。 从递归的思想来看，我们在从第一行开始给每一行的皇后确定一个位置。每来到新的一行时，对本行的所有可能位置（皇后放在这个位置和前面所有已放置的皇后无冲突）分别进行递归地深入；若某一行可能的位置数为0，则表明这是一条死路，返回上一层递归寻找其他办法；若来到的这一行是第九行（不存在第九行，只不过是说明前八行都已经正确配置，已经得到一个解决方案），这说明得到解决方案。 可以看到，寻找一行内皇后应该摆放的位置这是个递归过程，并且在进入递归时，应该要告诉这个过程的东西包括两个： 1. 之前皇后放置的状态， 2. 现在是第几行。所以，递归主体函数可以设计为 8queen(queenset, row)，其中queenset表示的是当前棋盘的状态（比如一个数组，0表示该行未放置，非零表示该行放置皇后的位置）。另外还可以有一个check(queenset,row，pos)，pos可以是一个第row行放置queen的位置，check函数用来返回以当前的棋盘状态，如果在第row行pos位置再放置一个皇后是否会有冲突。,某一行的某一个位置是不是一个与已有皇后位置不冲突的位置，可以看成三个检测问题：1、检测是不是同一行：因为一行只放一个皇后，这个问题不用检测了2、检测是不是同一列：第a行第b列已经有了一个皇后，要检查第row行，第pos列是否冲突，就是b=pos3、检测是不是同一斜线|（a-row）|=|b-pos|如果以上三条，实际是是两条，如果满足，就返回错误，如果不满足程序继续；如果该位置与所有已有皇后都不冲突，则该位置是一个暂时可用的位置，可以进入下一行去判断,#习题一：这是求解8皇后问题的程序#这个程序将用递归的思路来求解8皇后问题，设置存放8皇后解的为一个名为queenpos的列表【queenpos0，queenpos1，queenpos2，。】defcheckqueen(pos,queenpos):#检查第len(queenpos)行，因为序号从0开始，就是当前行，pos位置（从0开始）的皇后是否与之前的皇后相冲突foriinrange(len(queenpos):#逐个皇后检查ifpos=queenposi:returnFalse#如果同列返回冲突，falseelifabs(len(queenpos)-i)=abs(pos-queenposi):returnFalse#如果同斜线返回冲突，FALSEreturnTrue#和之前的全部皇后都不冲突，返回真defqueen8(row=8,queenpos=():foriinrange(row):#在第一行一个一个尝试ifcheckqueen(i,queenpos):#如果当前位置可用，就看是不是最后一行，如果是就记录位置返回iflen(queenpos)=(row-1):yield(i,)else:#如果不是最后一行就看下一行直至递归调用到最后一行能不能找到解，如果能找到解，就一路递归返回，记录位置#如果找不到就什么都不干，在同一行找下一个位置forjiedainqueen8(row,queenpos+(i,):yield(i,)+jieda#如果能找到解，就一路递归返回，保存一个解h=queen8()forjinh:print(j)print(8皇后问题一共有,len(list(queen8(),种解法),习题2.1 逆波兰表达式求值网上很多习题甚至教材都将逆波兰表达式和波兰表达式搞混了。教材里的所谓递归求解逆波兰表达式，实质是求解波兰表达式。逆波兰表达式，简单直接求解就可以了，不用去写递归。左边的图里演示，用了两个函数，一个函数用于计算一个单步计算。另一个函数用于一个个弹出逆波兰表达式中的元素，如果是运算符，那么之前两个元素一定是数字，三个元素进行计算，结果压进堆栈如果是数字，直接压进堆栈全部元素弹出，最后剩下的就是结果。,#逆波兰表达式是后缀表达式#先写一个函数，计算两个被运算数的值和一个操作符的操作结果，cal1(leftnum,rightnum,op)#其中rightnum先从堆栈里弹出#开始读入算式，如果是运算数就入堆栈，如果是操作符就弹出两个运算数。defcalc1(expr):token=foriinexpr.split():ifiin+,-,*,/:rightnum,leftnum=float(token.pop(),float(token.pop()print(leftnum,i,rightnum)token.append(str(cal1(leftnum,rightnum,i)else:token.append(i)returnfloat(token0)defcal1(leftnum,rightnum,i):#leftnum和rightnum是浮点型，i是字符型的运算符ifi=+:returnleftnum+rightnumifi=-:returnleftnum-rightnumifi=*:returnleftnum*rightnumifi=/:returnleftnum/rightnumprint(calc1(31.0434.0+434.0*),递归习题2.2：波兰表达式,波兰表达式是一种把运算符前置的算术表达式，例如普通的表达式2 + 3的波兰表示法为+ 2 3。波兰表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序，例如(2 + 3) * 4的逆波兰表示法为* + 2 3 4。本题求解逆波兰表达式的值，其中运算符包括+ - * /四个。 输入 ：输入为一行，其中运算符和运算数之间都用空格分隔，运算数是浮点数 输出 ：输出为一行，表达式的值。,很多书籍、资料包括郭老师的讲课中都将这个表达式称为逆波兰表达式，我自己也为这个事困惑了一个多星期，在这里还是将逆波兰表达式和波兰表达式的例程都提供出来，供读者参考。,#PolishNotation这是波兰表达式的程序#输入为一行，其中运算符和运算数之间都用空格分隔，运算数是浮点数。#样例输入：*+11.012.0+24.035.0#1)一个数是一个波兰表达式，值为该数#2)运算符波兰表达式波兰表达式是波兰表达式，值为两个逆波兰表达式的值运算的结果#一个小工具：Pythonsplit()通过指定分隔符对字符串进行切片，如果参数num有指定值，则分隔num+1个子字符串，默认分割符为全部空字符#自左至右弹出元素，如果是运算符，就继续弹出左运算数和右运算数，左运算数是一个波兰表达式，右运算数也是一个波兰表达式#对于左右运算数分别调用函数自身求值，直到只剩一个数，则返回递归。defPolishNotation(expr):elem=elem=expr.pop()ifelemnotin+,-,*,/:returnfloat(elem)else:ifelem=+:returnPolishNotation(expr)+PolishNotation(expr)ifelem=-:returnPolishNotation(expr)-PolishNotation(expr)ifelem=*:returnPolishNotation(expr)*PolishNotation(expr)ifelem=/:returnPolishNotation(expr)/PolishNotation(expr)exprstr=*+11.012.0+24.035.0expr=exprstr.split()expr.reverse()print(PolishNotation(expr),#这是一个递归求解四则运算的例程，对只包含加减乘除括号和数字的四则运算，中缀运算符，进行求解#用递归算法的思路来编写程序表达式由项组成，一个单独的项可以是一个表达式，一个项加减另一个项也可以是一个表达式，由是可以调用项的定义循环定义无数次项由因子组成，一个单独的因子可以是一个项，一个因子乘除另一个因子也是一个项，由是可以调用因子的定义循环定义无穷因子可以是由一对括号和其内的表达式组成（这里间接构造了递归调用的一般形式），因子也可以由一个数直接组成（这里间接构造了递归的终止条件）一般递归是A调用A，这个程序是A调用B，B调用C，C调用A的间接递归def表达式(expr):结果=项(expr)#取出第一个项，表达式至少有一个项还有项=Truewhile还有项:iflen(expr)0andexpr-1in+,-:#一开始写这个程序没有加上列表是否为空的检测，总是出现下标越界操作=expr.pop()if操作=+:结果=结果+项(expr)else:结果=结果-项(expr)else:还有项=Falsereturn结果,#这是递归求解四则运算的第二部分，接上一页PPTdef项(expr):项结果=因子(expr)#取出该项的第一个因子，项至少有一个因子，也可以由多个因子乘除构成。还有因子=Truewhile还有因子:iflen(expr)0andexpr-1in*,/:#一开始写这个程序没有加上列表是否为空的检测，总是出现下标越界操作=expr.pop()if操作=*:项结果=项结果*因子(expr)else:项结果=项结果/因子(expr)else:还有因子=Falsereturn项结果def因子(expr):因子结果=0ifexpr-1notin+,-,*,/,(,):#如果是数字因子结果就等于数字因子结果=float(expr.pop()elifexpr-1=(:#如果是括号就说明后面是一个表达式expr.pop()#先把左括号去掉因子结果=表达式(expr)expr.pop()#再去掉右括号return因子结果expr1=3-4+5*6/2*(2*3+2)+1.0expr2=expr1.split()expr2.reverse()print(expr2)print(表达式(expr2),#树老师上台阶，一步上一台阶，或者一步上两台阶，对于给定N个台阶有多少种走法。#假定有N个台阶有F(N)种走法。#走第一步时，可能走一步，也可能走两步；F(n)=F(n-1)+F(n-2),由此得到递归的一般式#f(2)=2,f(1)=1；由此得到递归的终止条件def树老师走路(n):ifn=1:return1elifn=2:return2else:return树老师走路(n-1)+树老师走路(n-2)print(树老师走路(10),递归习题4：爬楼梯 树老师爬楼梯，他可以每次走1级或者2级，输入楼梯的级数，求不同的走法数 例如：楼梯一共有3级，他可以每次都走一级，或者第一次走一级，第二次走两级，也可以第一次走两级，第二次走一级，一共3种方法。,这是递归求解放苹果问题的例程：把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1是同一种分法。输入：第一行是测试数据的数目t（0=t=20）。以下每行均包含二个整数M和N，以空格分开。1=M，N=10。输出：对输入的每组数据M和N，用一行输出相应的K思路：设定m个苹果放进n个盘子里一共有f(m,n)种方法1、如果m小于n,则f(m,n)=f(m,m);m小于n时，总有n-m个盘子是空的，可以先把n-m个盘子拿走，不影响结果2、如果m大于n,则分为两类问题有盘子为空的算法+没有盘子为空的算法2.1、有盘子为空的算法则至少有一个盘子为空，把这一个盘子拿走就演变成求f(m,n-1)的总数2.2、没有盘子为空时，则至少每个盘子都有一个苹果，从每个盘子里都拿走一个拼过，就演变成求f(m-n,n)的总数如此构成递归的一般式3、递归的终止式：只剩下0个苹果或1个盘子的时候，返回0deff(m,n):ifmn:returnf(m,m)else:ifm=0:return1elifn=1:return1else:returnf(m,n-1)+f(m-n,n)print(f(20,10),这是递归求解4个数字算24点的例程一般的看，n个数算24点，至少要做第一步，将任意两个数进行加减乘除的运算，将运算结果再放回去，这时候只有N-1个数了，再求n-1个数是不是能算24，构成递归一般条件递归终止条件：n=1的时候，是不是等于24，如果是就可以注意浮点数不能用=0来判断它是不是0defsuan24(a):iflen(a)=1:#如果只有一个元素，就和24比较是否等于24ifabs(a0-24)0.000001:returnTrueelse:returnFalseelse:foriinrange(len(a)-1):forjinrange(i+1,len(a):#任意两个元素组合进行加减乘除b=forkina:b.append(k)print(b)ai=b.pop(i)#弹出第i个元素aj=b.pop(j-1)#弹出第j个元素b.append(ai+aj)#将两元素相加结果再加入进列表ifsuan24(b):returnTrueb.pop()#将两元素相加结果弹出列表，下类似,#这是递归求解4个数算24点例程的第二部分，接上一页PPT。本页继续增加两种相减、相乘和两种相除的情形。最后调用函数给出结果。ifabs(ai-aj)0.000001:b.append(ai-aj)ifsuan24(b):returnTrueb.pop()b.append(aj-ai)ifsuan24(b):returnTrueb.pop()b.append(ai*aj)ifsuan24(b):returnTrueb.pop()ifai0.000001:b.append(aj/ai)ifsuan24(b):returnTrueb.pop()ifaj0.000001:b.append(ai/aj)ifsuan24(b):returnTrueb.pop()a=1,5,1,3ifsuan24(a):print(Yes)else:print(no),
