《算法设计与分析基础》（Python语言描述） 课件 第3章基本算法设计方法(2).pptx

3.1穷举法;3.4.1递归法概述;原问题可以转化为一个或多个子问题来求解，而这些子问题的求解方法与原问题完全相同，只是在数量规模上不同。

递归调用的次数必须是有限的。

必须有结束递归的条件来终止递归。;2.递归模型;3.提取求解问题的递归模型;4.递归算法框架;【例3-4】假设二叉树采用二叉链存储，设计一个算法判断两棵二叉树t1和t2是否相同，所谓相同是指它们的形态相同并且对应结点值相同。;解;1 defsame(r1,r2): #递归算法：判断r1和r2是否相同

2 ifr1==Noneandr2==None:

3 returnTrue

4 elifr1==Noneorr2==None:

5 returnFalse

6 ifr1.val!=r2.val:

7 returnFalse

8 leftans=same(r1.left,r2.left) #递归调用1

9 rightans=same(r1.right,r2.right) #递归调用2

10 returnleftansandrightans;3.4.2冒泡排序;;;;;;;给定正整数n（n≥1），给出求1～n的全排序的递归模型和递归算法。

例如，n=3时，全排列是{{1，2，3}，{1，3，2}，{3，1，2}，{2，1，3}，{2，3，1}，{3，2，1}}。;;;;;3.4.4实战—字符串解码（LeetCode394★★）;问题描述：给定一个经过编码的有效字符串s，设计一个算法返回s解码后的字符串。编码规则是用“k[encoded_string]”表示方括号内的encoded_string?（仅包含小写字母）正好重复k（k?保证为正整数）次。

例如，s=3[a]2[bc]，答案为aaabcbc，若s=abc3[cd]xyz，答案为abccdcdcdxyz。

要求设计如下方法：

def?decodeString(self,s:str)-str;;;;;;;;;;;;;;;;;