首页 > 其他分享 >汉诺塔和递归

汉诺塔和递归

时间:2024-08-30 08:54:10浏览次数:10  
标签:柱子 sub 递归 State 汉诺塔 盘子 id

目录


需求背景、限制条件、化简

汉诺塔就是一个由柱子和盘子组成的玩具,它有一些玩法上的限制,主要是规定了盘子移动有限制。
想理解到递归本质,汉诺塔是个不错的载体。
怎么体会?
在盘子移动的过程中。

# 盘子的数量:
#   通常,我们假设有 n 个盘子。盘子在初始时按从大到小的顺序叠放在一个柱子上(源柱子)。
#   这里采用数字表示盘子,数字大小表示盘子大小。

# 柱子数量:
#   总共有三个柱子:源柱子(起始柱子)、目标柱子(最终柱子) 和辅助柱子(中间柱子)。
#   这里用a,b,c list模拟三个柱子
#   规定list只能从末尾取出

# 移动规则:
#   每次只能移动一个盘子。
#   任何时刻盘子只能放在一个柱子上。
#   大的盘子不能放在小的盘子上。

# 目标:
#   将所有的盘子从源柱子移动到目标柱子,且遵守上述规则。

总结:

  1. 了解了问题和目标;
  2. 将现实问题抽出,化简,采用符号化方式去表达;

模拟盘子的移动步骤

先正常演示一次移动:

n = 1
a = [1]
b = []
c = []

a = []
b = []
c = [1]

n = 2
a = [2,1]
b = []
c = []

(1)
a = [2]
b = [1]
c = []

(2)
a = []
b = [1]
c = [2]

(3)
a = []
b = []
c = [2,1]

**

n = 3
a = [3,2,1]
b = []
c = [1]

(1)
a = [3,2]
b = []
c = [1]

(2)
a = [3]
b = [2]
c = [1]

(3)
a = [3]
b = [2,1]
c = []

(4)
a = []
b = [2,1]
c = [3]

(5)
a = [1]
b = [2]
c = [3]

(6)
a = [1]
b = []
c = [3,2]

(7)
a = []
b = []
c = [3,2,1]


上面正向的思考,n约大,步骤越多,越来越乱, 抓不住重点。
必须得以反向思维思考:

n = 3
a = [3]
b = [2,1]
c = []

a = []
b = [2,1]
c = [3]

**

n = 4
a = [4]
b = [3,2,1]
c = []

a = []
b = [3,2,1]
c = [4]

**
n = 5
a = [5]
b = [4,3,2,1]
c = []

a = []
b = [4,3,2,1]
c = [5]
......

简单的抓到一些固定特征:

  • 不管n是几,都是a到c.

  • 如果n>1,就把n-1的盘子都放到辅助柱子,n 直接去 c。(这个也是划分出来的一个子问题)

递归实现Code

def hanoi(n: int, a: list, b: list, c: list):
    print("sub State:", a, b, c)
    if n == 1:
        # 基准情况
        c.append(a.pop())
        print("State 1:", a, b, c)
    else:
        # 递归情况
        hanoi(n - 1, a, c, b)

        c.append(a.pop())
        print("State 2:", a, b, c)

        hanoi(n - 1, b, a, c)


a = [3, 2, 1]
b = []
c = []

print("Initial state:", a, b, c)
hanoi(len(a), a, b, c)
print("Final state:", a, b, c)

核心:
在递归调用中,柱子的角色(源、目标、辅助)不断交换。这种角色交换保证了每一步都能正确地完成盘子的移动。

out:

Initial state: [3, 2, 1] [] []
sub State: [3, 2, 1] [] []
sub State: [3, 2, 1] [] []
sub State: [3, 2, 1] [] []
State 1: [3, 2] [] [1]
State 2: [3] [1] [2]
sub State: [1] [3] [2]
State 1: [] [3] [2, 1]
State 2: [] [2, 1] [3]
sub State: [2, 1] [] [3]
sub State: [2, 1] [3] []
State 1: [2] [3] [1]
State 2: [] [1] [3, 2]
sub State: [1] [] [3, 2]
State 1: [] [] [3, 2, 1]
Final state: [] [] [3, 2, 1]

分析

采用可视化方式观察:
https://pythontutor.com/

看完的的一些体会:

  • 函数会嵌套函数, 多个嵌套函数之间一起组成一个整体的函数;
    image

  • 递归通过传递下去的变量,在 之间的改变,能达到一个很炸裂的效果;

  • 递归的层下沉,一般使用一个int变量控制。

练习 1

你有一个保存员工信息的数据结构,它包含了员工唯一的 id ,重要度和直系下属的 id 。

给定一个员工数组 employees,其中:

  • employees[i].id 是第 i 个员工的 ID。
  • employees[i].importance 是第 i 个员工的重要度。
  • employees[i].subordinates 是第 i 名员工的直接下属的 ID 列表。

给定一个整数 id 表示一个员工的 ID,返回这个员工和他所有下属的重要度的 总和。

image

# Definition for Employee.
class Employee:
    def __init__(self, id: int, importance: int, subordinates: List[int]):
        self.id = id
        self.importance = importance
        self.subordinates = subordinates

标签:柱子,sub,递归,State,汉诺塔,盘子,id
From: https://www.cnblogs.com/mysticbinary/p/18382105

相关文章

  • 以Top-Down思维去解决问题——递归
    目录递归的基础递归的底层实现(不是重点)递归的应用场景编程中两种解决问题的思维自下而上(Bottom-Up)自上而下(Top-Down)自上而下的思考过程——求和案例台阶问题案例易位构词生成案例递归和for循环(迭代法)很像,都是通过循环去完成一件事。但采用Top-Down思维去设计的递归结构,又会......
  • Luogu P4425 转盘 题解 [ 黑 ] [ 线段树 ] [ 贪心 ] [ 递归 ]
    转盘:蒟蒻的第一道黑,这题是贪心和线段树递归合并的综合题。贪心破环成链的trick自然不用多说。首先观察题目,很容易发现一个性质:只走一圈的方案一定最优。这个很容易证,因为再绕一圈回来标记前面的和等前面的标记完之后继续走是等价的,并且再绕一圈甚至可能更劣。于是,我们只用走......
  • day13: 第六章 二叉树part01 |二叉树的前序遍历,后序遍历,中序遍历,(递归。层序(广度)跟
    二叉树递归三部曲:1.确定递归函数的参数和返回值。2.确定终止条件3.确定单层递归的逻辑144.二叉树的前序遍历:中左右,递归:classSolution{publicList<Integer>preorderTraversal(TreeNoderoot){List<Integer>res=newArrayList<Integer>();p......
  • 从零开始学习C++之递归
    递归注:此算法与函数有关,如不了解请移步。在wikipedia中,递归的解释是这样的:在C++中,递归就是指在函数中调用函数本身;递归的作用类似于分治,将一个大问题分解为很多小问题进行求解。但是递归的时间复杂度极高,因为要解决很多小问题,所以时间复杂度高达\(O(2^n)\)。使用递......
  • 全网最易懂的解题——C语言“打印一个数的每一位(递归)”
    很简单吧递归我们做了很多题,逆序打印数字和逆序打印数组我们也做过代码就直接附上了voidmy_print(intnum){ if(num<10)//说明只有一位数字 { printf("%d",num); } else { my_print(num/10); printf("%d",num%10); }}//打印数字的每一位intmain(......
  • 全网最易懂的解题——C语言“求斐波那契数(递归)”
    那先来知道什么是斐波那契数列吧前两个数相加等于第三个数,如果其中数字都满足此条件,那么这就是斐波那契数列 现在我们要求第n个斐波那契数,代码框架先搭出来吧,找斐波那契数的函数就命名为Fib吧//求斐波那契数intmain(){ intn=0; printf("请输入你想知道第几个斐波......
  • Python——生成器、递归、内省、高阶和偏函数
    Python的生成器(Generators)是一种特殊的迭代器,它使用类似于函数的语法定义,但是使用yield语句一次返回一个值(可以多次返回),而不是使用return语句。生成器函数允许你声明一个像迭代器那样的对象,但是你可以使用更简洁的语法来创建它们。为什么要使用生成器?内存效率高:生成器按需产......
  • 代码训练营 Day13 | 递归遍历 | 层序遍历
    144. 二叉树的前序遍历递归思路:确定递归函数的参数和返回值确定递归函数的终止条件确定单层递归的逻辑前序遍历顺序:中左右#Definitionforabinarytreenode.#classTreeNode(object):#def__init__(self,val=0,left=None,right=None):#......
  • 方法,命令行传参,方法的可变参数与递归
    方法c中的函数例如 System.out.println() //System是一个类,out是System下的一个(PrintStream类的实例)对象(变量),println是一个方法方法最好保持原子性:一个方法只实现一个功能方法的定义修饰符:可选返回值类型方法名参数类型形参:方法内用的实参:调用方法的语句中的参数......
  • C语言:函数递归
    目录一、递归1.1递归的思想1.2递归的限制二、递归举例2.1举例1:求n的阶乘 画图推演2.2举例2:顺序打印一个整数的每一位画图推演​编辑  三、递归和迭代一、递归   递归是学习C语言函数绕不开的⼀个话题,那什么是递归呢?递归其实是⼀种解决问题的方法,在C语......