برج‌های هانوی
n دیسک را از میله‌ی A به C می‌برد، هر بار یک دیسک و هیچ‌وقت دیسک بزرگ روی کوچک؛ دقیقاً 2ⁿ − 1 حرکت.
برای بردن k دیسک از میله‌ی مبدأ به مقصد:
- زمان:
O(2ⁿ) - حافظه:
O(n) - گریمالدی، فصل ۱۰
- جانسون‌باو، فصل ۴
سه دیسک: ۷ حرکت.
def hanoi(n):pegs = {"A": list(range(n, 0, -1)), "B": [], "C": []}moves = []solve(n, "A", "C", "B", pegs, moves)return movesdef solve(k, src, dst, via, pegs, moves):if k == 0:returnsolve(k - 1, src, via, dst, pegs, moves)disk = pegs[src].pop()pegs[dst].append(disk)moves.append((disk, src, dst))solve(k - 1, via, dst, src, pegs, moves)
شروع اجرا
pegs—
جدول هنوز خالی است.
درخت فراخوانی‌های بازگشتی
نارنجی پر = فراخوانی در حال اجرا · حاشیه‌ی نارنجی = هنوز روی پشته · خاکستری = تمام شده
متغیرهای محلی
n3
نارنجی = در همین گام عوض شد
Call stack
- hanoi()خط 1
گام ۱ از ۷۸
توضیح
ایده
برای بردن k دیسک از میله‌ی مبدأ به مقصد:
k − 1دیسک بالایی را (بازگشتی) به میله‌ی کمکی ببر؛- بزرگ‌ترین دیسک را به مقصد ببر؛
- آن
k − 1دیسک را (بازگشتی) از میله‌ی کمکی روی آن بگذار.
چند حرکت؟
T(k) = 2·T(k−1) + 1 و T(0) = 0، پس T(n) = 2ⁿ − 1. ثابت می‌شود کمتر از این ممکن نیست: بزرگ‌ترین دیسک باید دست‌کم یک بار حرکت کند و قبلش همه‌ی بقیه باید کنار رفته باشند.
در trace به چه چیزی نگاه کنی
- کارت
pegsوضعیت سه میله است (پایین به بالا) و جدول همه‌ی حرکت‌ها تا اینجا. - درخت فراخوانی‌ها درخت دودویی کاملی به عمق
nاست. - دیسک ۱ یک حرکت در میان حرکت می‌کند.