برج هانوی: چرا چند دیسک، حرکت‌ها رو زیاد می‌کنه؟

قانون حرکت، مسئله رو محدود می‌کنه

سه میله داریم، هر بار فقط دیسک بالایی یک میله رو برمی‌داریم و دیسک بزرگ‌تر هیچ‌وقت روی دیسک کوچک‌تر نمی‌ره. هدف اینه که کل برج از میلهٔ شروع به میلهٔ پایان برسه.

حل n دیسک به حل n−۱ دیسک وابسته‌ست

M(n) = 2*M(n-1) + 1

برای جابه‌جایی برج، اول n−۱ دیسک رو به میلهٔ کمکی می‌بریم، دیسک بزرگ رو جابه‌جا می‌کنیم و بعد n−۱ دیسک رو روی اون می‌ذاریم. همین الگو تعداد حرکت‌ها رو بازگشتی می‌سازه.

کمترین حرکت‌ها با فرمول نمایی

M(n) = 2^n - 1

وقتی از یک دیسک به دیسک بعدی می‌رسیم، باید کل برج قبلی رو دو بار جابه‌جا کنیم و یک بار هم بزرگ‌ترین دیسک رو حرکت بدیم. برای ده دیسک، نتیجه ۱۰۲۳ حرکته.