<input id="0qass"><u id="0qass"></u></input>
  • <input id="0qass"><u id="0qass"></u></input>
  • <menu id="0qass"><u id="0qass"></u></menu>

    LeetCode-漢諾塔問題

    python 同時被 2 個專欄收錄
    5 篇文章 0 訂閱
    6 篇文章 0 訂閱

    鏈接:https://leetcode-cn.com/problems/hanota-lcci
    在經典漢諾塔問題中,有 3 根柱子及 N 個不同大小的穿孔圓盤,盤子可以滑入任意一根柱子。一開始,所有盤子自上而下按升序依次套在第一根柱子上(即每一個盤子只能放在更大的盤子上面)。移動圓盤時受到以下限制:
    (1) 每次只能移動一個盤子;
    (2) 盤子只能從柱子頂端滑出移到下一根柱子;
    (3) 盤子只能疊在比它大的盤子上。
    請編寫程序,用棧將所有盤子從第一根柱子移到最后一根柱子。
    解題思路:遞歸與分治
    n = 1 時,直接把盤子從 A 移到 C;
    n > 1 時,
    先把上面 n - 1 個盤子從 A 移到 B(子問題,遞歸);
    再將最大的盤子從 A 移到 C;
    再將 B 上 n - 1 個盤子從 B 移到 C(子問題,遞歸)。

    class Solution:
        def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:
            n = len(A)
            self.move(n, A, B, C)
        # 定義move 函數移動漢諾塔
        def move(self,n, A, B, C):
            if n == 1:
                C.append(A[-1])
                A.pop()
                return 
            else:
                self.move(n-1, A, C, B)  # 將A上面n-1個通過C移到B
                C.append(A[-1])          # 將A最后一個移到C
                A.pop()                  # 這時,A空了
                self.move(n-1,B, A, C)   # 將B上面n-1個通過空的A移到C
    
    • 0
      點贊
    • 0
      評論
    • 0
      收藏
    • 打賞
      打賞
    • 掃一掃,分享海報

    ??2022 CSDN 皮膚主題:大白 設計師:CSDN官方博客 返回首頁

    打賞作者

    小饅頭的yy

    你的鼓勵將是我創作的最大動力

    ¥2 ¥4 ¥6 ¥10 ¥20
    輸入1-500的整數
    余額支付 (余額:-- )
    掃碼支付
    掃碼支付:¥2
    獲取中
    掃碼支付

    您的余額不足,請更換掃碼支付或充值

    打賞作者

    實付
    使用余額支付
    點擊重新獲取
    掃碼支付
    錢包余額 0

    抵扣說明:

    1.余額是錢包充值的虛擬貨幣,按照1:1的比例進行支付金額的抵扣。
    2.余額無法直接購買下載,可以購買VIP、C幣套餐、付費專欄及課程。

    余額充值
    多乐彩