מגדלי האנוי

מעביר רקורסיבית ערימת דיסקים בין יתדות בעזרת יתד עזר.

5 דיסקים

31 מהלכים בסך הכול

שלב 1 מתוך 64

מגדלי האנוי עם 5 דיסקים. העבר את כל הדיסקים מעמוד A לעמוד C תוך שימוש בעמוד B כעזר. מספר המהלכים המזערי הנדרש: 31.

מהלכים0 / 31

מצב העמודים

12345

ריק

▶אלגוריתם

Hanoi(n, from, to, via):
if n == 0: return
Hanoi(n−1, from, via, to)
move disk n: from → to
place disk n on peg to
Hanoi(n−1, via, to, from)
// complete

איך זה עובד

כדי להעביר n דיסקים מ־A ← C: העבר n−1 דיסקים מ־A ← B, העבר את דיסק n ל־C, ואז העבר n−1 דיסקים מ־B ← C. כך מתקבל T(n) = 2ⁿ − 1 מהלכים.

1 / 64מהירות