360网站建设价位,网上注册公司官网入口,东莞常平招聘网最新招聘信息,潍坊公司注册网站递归 递归初始递归#xff1a;数列求和递归的应用#xff1a;任意进制转换递归深度限制递归可视化#xff1a;分形树递归可视化#xff1a;谢尔宾斯基Sierpinski三角形递归的应用#xff1a;汉诺塔递归的应用#xff1a;探索迷宫 分治策略和递归优化问题兑换最少个数硬币… 递归 递归初始递归数列求和递归的应用任意进制转换递归深度限制递归可视化分形树递归可视化谢尔宾斯基Sierpinski三角形递归的应用汉诺塔递归的应用探索迷宫 分治策略和递归优化问题兑换最少个数硬币问题 贪心策略 递归
递归是一种解决问题的方法其精髓在于将问题分解为规模更小的相同问题持续分解直到问题规模小到可以用飞常简单直接的方式来解决。 递归的问题分解方式非常独特其算法方面的明显特征就是在算法流程中调用自身。 递归为我们提供了一种对复杂问题的优雅解决方案。
函数自己调用自己形如
int f(int x){xxxxxxxxxxxxxxxreturn f(x-1);
}初始递归数列求和
问题给定一个列表返回所有数的和 列表中数的个数不定需要一个循环和一个累加变量来迭代求和
既不能用for也不能用while对不确定长度的列表求和
def listsum(numList):theSum0for i in numList:theSumtheSumireturn theSumprint(listsum([1,3,5,7,9]))求和实际上由一次次的加法实现而加法恰有2个操作数
将问题规模较大的列表求和分解为规模较小而且固定的2个数求和
数列求和问题首先具备了基本结束条件当
递归的应用任意进制转换
整数转换为任意进制 十进制有10个不同符号convString“0123456789” 比10小的整数转换成十进制直接查表convString[n] 比10大的整数拆成一系列比10小的整数逐个查表如769拆成7、6、9 递归三定律里基本结束条件为小于10的整数拆解整数的过程就是向“基本结束条件”演进的过程 用整数除和求余数两个计算将整数一步步拆开 除以“进制基base”//base 对“进制基”求余数%base 问题分解为余数总小于“进制基base”是基本结束条件可直接进行查表转换 整数商成为“更小规模”问题通过递归调用自身解决
def toStr(n,base):convertString0123456789ABCDEFif nbase:return convertString[n]else:return toStr(n//base,base)convertString[n%base]print(toStr(1453,16))当一个函数被调用的时候系统会把调用时的现场数据压入到系统调用栈 每次调用压入栈的现场数据称为栈帧 当函数返回时要从调用栈的栈顶取得返回地址恢复现场弹出栈帧按地址返回
递归深度限制
RecursionError 检查是否忘记设置基本结束条件导致无限递归。 或者向基本结束条件演进太慢导致递归层数太多调用栈溢出
def tell_story():在Python内置的sys模块可以获取和调整最大递归深度
递归可视化分形树
Python的海龟作图系统tuetle moudle
import turtle
tturtle.Turtle()
# 作图开始
for i in range(4):t螺旋
import turtletturtle.Turtle()def drawSpiral(t,lineLen):if lineLen分形一个粗糙或零碎的几何形状可以分成数个部分且每一部分都至少近似地是整体缩小后的形状即具有自相似的性质
递归可视化谢尔宾斯基Sierpinski三角形
面积趋于0周长趋于∞ 谢尔宾斯基三角形是由三个尺寸减半的谢尔宾斯基三角形按照品字形拼叠而成 我们无法真正做出谢尔宾斯基三角形只能做出degree有限的近似图形 在degree有限的情况下degreen的三角形由3个degreen-1的三角形按品字形拼叠而成边长均为degreen的三角形的一半规模减小 当degree0则就是一个等边三角形这是递归结束的基本条件
import turtle
def sierpinski(degree,points):colormap[blue,red,green,white,yellow]递归的应用汉诺塔
规则 一次只能移动一个 大盘子不能叠在小盘子上
假设有5个盘子串在1#柱上需要移到3#柱上
把上面的一摞4个盘子移到2#柱上把剩下的最大号盘子移到3#柱上把2#柱上的4个盘子移到3#柱上 如果能有办法把最上面的4个盘子移到2#柱那么问题就好解决了。接下来的问题就是把4个盘子从1#移到2#此时问题规模已经减小
把上面的一摞3个盘子移到3#柱上把剩下的最大号盘子移到2#柱上把3#柱上的3个盘子移到2#柱上
移动3个盘子可以分解为上面2个和下面的最大号盘子 移动2个盘子可以分解为上面的盘子和下面的盘子
思路一定有三个柱子两个柱子是无法完成的 将盘子从开始柱经由中间柱移到目标柱
将上层N-1个盘子的塔从开始柱借助目标柱移到中间柱将最大的第N个盘子从开始柱移到目标柱将放置在中间柱的N-1个盘子借助开始柱移到目标柱
基本结束条件最小规模问题1个盘子的移动问题
def moveTower(height,fromPole,withPole,toPole):if height1:moveTower(height-1,fromPole,toPole,withPole)moveDisk(height,fromPole,toPole)moveTower(height-1,withPole,fromPole,toPole)def moveTower(height,fromPole,withPole,toPole):if height1:moveTower(height-1,fromPole,toPole,withPole)moveDisk(height,fromPole,toPole)moveTower(height-1,withPole,fromPole,toPole)def moveDisk(disk,fromPole,toPole):print(fMoving disk[{disk}] from {fromPole} to {toPole})moveTower(3,#1,#2,#3)递归的应用探索迷宫
将海归放在迷宫中间找到出口
将整个迷宫的空间矩形分为行列整齐的方格区分出墙壁和通道。每个方格具有行列位置并赋予“墙壁”、“通道”的属性考虑用矩阵方式来实现迷宫数据结构。采用“数据项为字符列表的列表”这两种列表的方式来保存方格内容。采用不同字符分别代表“墙壁”、“通道 ”、“海归投放点S”从一个文本文件读入迷宫数据
class Maze:def __init__(self,mazeFileName):rowsInMaze0columnsInMaze0self.mazelist[]mazeFileopen(mazeFileName,r)rowsInMaze0for line in mazeFile:rowList[]col0for ch in line[:-1]:rowList append(ch)if chS:self.startRowrowsInMazeself.startColcolcolcol1rowsInMazerowsInMaze1self.mazelist.append(rowList)columnsInMazelen(rowList)探索迷宫的递归算法思路如下
将海龟
所以需要有个机制记录海龟走过的路径 沿途洒“面包屑”
递归调用的基本结束条件
def carpet(N,C):def check(n,x,y):if n1:return Truen2n//3if n2xn2*2 and n2yn2*2:return Falsereturn check(n2,x%n2,y%n2)for y in range(N):for x in range(N):if check(N,x,y):print(C,end)else:print( *len(C),end)print()
#test
carpet(27,[])分治策略和递归
将问题分为若干更小规模的部分 通过解决每一个小规模部分问题并将结果汇总得到原问题的解 递归三定律 基本结束条件解决最小规模问题 缩小规模向基本结束条件演进 调用自身来解决已缩小规模的相同问题 ❖体现了分治策略 问题解决依赖于若干缩小了规模的问题 汇总得到原问题的解 ❖应用相当广泛 排序、查找、遍历、求值等等
优化问题
计算机科学中许多算法都是为了找到某些 问题的最优解 例如两个点之间的最短路径 能最好匹配一系列点的直线 或者满足一定条件的最小集合
兑换最少个数硬币问题
假设你为一家自动售货机厂家编程序自动售货 机要每次找给顾客最少数量硬币 假设某次顾客投进$1纸币买了ȼ37的东西要 找ȼ63那么最少数量就是2个quarterȼ25 、1个dimeȼ10和3个pennyȼ1一共6个
贪心策略
一般我们这么做 从最大面值的硬币开始用尽量多的数量 有余额的再到下一最大面值的硬币还用尽量 多的数量一直到pennyȼ1为止 因为我们每次都试图解决问题的尽量大的一部分 对应到兑换硬币问题就是每次以最多数量的最 大面值硬币来迅速减少找零面值 ❖“贪心策略”解决找零兑换问题在美元 或其他货币的硬币体系下表现尚好
❖动态规划算法采用了一种更有条理的方式 来得到问题的解 ❖找零兑换的动态规划算法从最简单的“1 分钱找零”的最优解开始逐步递加上去 直到我们需要的找零钱数 ❖在找零递加的过程中设法保持每一分钱 的递加都是最优解一直加到求解找零钱 数自然得到最优解
