算法基础二Python递归算法解析

递归算法八大常用算法：枚举递归二分算法分治算法动态规划深度优先搜索广度优先搜索贪心算法人理解迭代，神理解递归递归：指在函数的定义中使用函数自身的方法。”递归“表达了两个意思：”递“＋”归“，基本思想是把规模大的问题转化为规模小的相似的子问题来解决。在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况。另外这个解决问题的函数必须有明显的结束条件，这样就不会产生无限递归的情况了递归应用三步法：1).明确递归终止条件例如：当N=0时，递归终止2).给出递归终止时的处理办法例如：ifn=0:return13).提取重复的逻辑，递归的一般式，缩小问题规模例如：returnn*f（n-1）例1：应用三步法解决实际问题：阶乘问题1).明确递归终止条件当N=0时，递归终止2).给出递归终止时的处理办法ifn=0:return13).提取重复的逻辑，缩小问题规模重复的逻辑是：returnn*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).给出递归终止时的处理办法ifn==1orn==2:return13).提取重复的逻辑，缩小问题规模*重复的逻辑是：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的逆波兰表示法为+23。逆波兰表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序，例如(2+3)*4的逆波兰表示法为*+234。本题求解逆波兰表达式的值，其中运算符包括+-*/四个。输入输入为一行，其中运算符和运算数之间都用空格分隔，运算数是浮点数输出输出为一行，表达式的值。递归习题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。样例输入173样例输出8。递归习题6：算24输入输入数据包括多行，每行给出一组测试数据，包括4个小于10个正整数。最后一组测试数据中包括4个0，表示输入的结束，这组数据不用处理。输出对于每一组测试数据，输出一行，如果可以得到24，输出“YES”；否则，输出“NO”。样例输入555111420000样例输出YESNO谢谢观看!八皇后问题国际象棋的皇后能吃掉横向纵向和斜向的棋子，非常厉害，比中国象棋里的车厉害多了。一个皇后放到棋盘中央，就一小半的格子不能放了其他皇后了。按什么思路去求解呢？我们假定存在一组数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==queenpos[i]:returnFalse#如果同列返回冲突，falseelifabs(len(queenpos)-i)==abs(pos-queenpos[i]):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(token[0])defcal1(leftnum,rightnum,i):#leftnum和rightnum是浮点型，i是字符型的运算符ifi=='+':returnleftnum+rightnumifi=='-':returnleftnum-rightnumifi=='*':returnleftnum*rightnumifi=='/':returnleftnum/rightnumprint(calc1('31.04