برج هانوی چیست؟ – بررسی مسئله برج هانوی Tower Of Hanoi در ۱۰ دقیقه

مقدمه مقاله برج هانوی چیست؟

در طول تاریخ، ریاضیات بسیاری از نیازها مانند اندازه‌گیری زمین، مطالعه نجوم، محاسبه مالیات و بسیاری از پیچیدگی‌های مسائل بشر را برآورده کرده است. اما از ریاضیات می‌توان برای سرگرمی نیز استفاده کرد. بسیاری از بازی‌ها، پازل‌ها و معماها که جنبه‌ی تقویت ذهن را دارند، حول مفاهیم ریاضی می‌چرخند. به بازی‌های ساده مانند تیک‌تاک، بازی‌های استراتژیک‌تر مانند شطرنج یا پازل‌های ریاضی مانند سودوکو فکر کنید. مردم قرن‌هاست که این بازی‌ها و پازل‌ها را انجام می‌دهند! این بازی‌ها سرگرم‌کننده و گاهی اوقات مفید هستند.

در همه این‌ها رد پایی از ریاضیات، این علم گسترده که در همه علوم به صورت چشمگیر رخنه کرده است، دیده می‌شود و زمانی برای همگان قابل درک‌تر می‌شود که با علم برنامه‌نویسی ترکیب شده و نتیجه در کسری از زمان در خروجی ظاهر گردد.

تاریخچه مسئله برج هانوی

برج هانوی (Tower Of Hanoi) که برج برهما یا برج لوکاس نیز نامیده می‌شود توسط یک ریاضیدان فرانسوی به نام ادوارد لوکاس در قرن نوزده ابداع شد. این بازی با افسانه‌ای از یک معبد هندو مرتبط است که در آن از پازل برای افزایش انضباط ذهنی کشیش‌های جوان استفاده می‌شد.

در این افسانه آمده است که به کشیشان جوان ۶۴ دیسک طلا داده می‌شد که به‌طور مرتب روی یکی از سه پایه‌ها چیده شده بودند. هر دیسک روی یک دیسک کمی بزرگ‌تر قرار داشت. هدف کاهنان این بود که دوباره پشته را روی یک پایه متفاوت با جابجایی دیسک‌ها، یکی پس از دیگری، به پایه دیگری انتقال دهند، قانون این کار بدین‌صورت بود که دیسک بزرگ‌تر هرگز روی دیسک کوچک‌تر قرار نمی‌گیرد. با استفاده از ریاضیات، می‌توانید محاسبه کنید که حتی اگر کشیش‌ها کارآمدترین راه‌ها را هم برای حل این مسئله پیدا می‌کردند و دیسک‌ها را با سرعت یک ثانیه جابجا می‌کردند، تقریباً ۵۸۵ میلیارد سال طول می‌کشید تا کار تمام شود. یعنی بیش از ۴۰ برابر سن کیهان!

ممکن است تعجب کنید که چگونه ریاضیات در انجام این بازی دخیل است. همان‌طور که بازی را با دیسک‌های بیشتر و بیشتر انجام می‌دهید، متوجه خواهید شد که شروع به جستجوی الگوها می‌کنید. اگر بخواهید توضیح دهید که چگونه معما را حل می‌کنید، ممکن است متوجه شوید که از یکی از مفاهیم ریاضی زیر استفاده می‌کنید:

• راه حل‌های تکراری، که در آن توالی یکسانی از دستورالعمل‌ها بارها و بارها تکرار می‌شود.
• راه حل‌های بازگشتی، که در آن از اطلاعات یک مرحله برای یافتن مرحله بعدی استفاده می‌کنید.
• الگوها و ترجمه آنها در فرمول‌های ریاضی.

برج هانوی چیست؟

در تعریف برج Hanoi می‌توان گفت: برج هانوی یک پازل ریاضی است که در آن سه میله و n حلقه‌داریم. این حلقه‌ها اندازه‌های مختلفی دارند و به صورت صعودی روی‌هم قرار می‌گیرند، یعنی حلقه کوچک‌تر روی حلقه بزرگ‌تر قرار می‌گیرد. انواع دیگری از پازل وجود دارد که در آن تعداد حلقه‌ها افزایش می‌یابد، اما تعداد برج‌ها ثابت می‌ماند. هدف از این بازی این است که کل حلقه‌ها را به میله دیگری با رعایت قوانین ساده زیر منتقل کنید:

1. فقط یک دیسک را می‌توان در یک زمان جابجا کرد.
2. هر حرکت شامل برداشتن دیسک بالایی از یکی از پشته‌ها و قرار دادن آن در بالای پشته دیگر است، یعنی یک دیسک تنها در صورتی می‌تواند جابجا شود که بالاترین دیسک روی یک پشته باشد.
3. هیچ دیسکی را نمی‌توان روی دیسک کوچک‌تر قرارداد

برای درک این مسئله مثالی از برج هانوی با دو حلقه می‌زنیم. فرض کنید میله ۱ = ‘A’، میله ۲ = ‘B’، میله ۳ = ‘C’ باشند.

• مرحله ۱: اولین دیسک را از “A” به “B” تغییر دهید.
• مرحله ۲: دیسک دو را از “A” به “C” تغییر دهید.
• مرحله ۳: دیسک یک را از “B” به “C” تغییر دهید.

پس می‌توان گفت الگوی کلی راه‌حل به صورت زیر است:

• دیسک‌های ‘n-۱‘ را از ‘A’ به ‘B’ تغییر دهید.
• آخرین دیسک را از A به C تغییر دهید.
• دیسک‌های ‘n-۱‘ را از ‘B’ به ‘C’ تغییر دهید.

در شکل زیر این مسئله با سه حلقه نشان داده شده است. همان‌طوریکه مشاهده می‌کنید در طی ۷ مرحله این پازل چیده شده است.

می‌توان نشان داد که برای یک برج از n دیسک، ۲ⁿ − ۱ انتقال دیسک جداگانه لازم است تا برج به طور کامل به میله دیگری منتقل شود. بنابراین برای ۸ دیسک، پازل به ۱ − ۲^۸  یا ۲۵۵ انتقال نیاز دارد. اگر “پایه” اصلی برجی با ۶۴ دیسک بود، تعداد انتقال‌ها  ۱− ۲^۶۴  یا ۱۸,۴۴۶,۷۴۴,۰۷۳,۷۰۹,۶۰۰,۰۰۰ خواهد بود. این دقیقاً همان عددی است که برای پر کردن یک تخته شطرنجی ۸ × ۸ با دانه‌های گندم، ۱ در مربع یک، ۲ در مربع دو، ۴ در بعدی، سپس ۸، ۱۶، ۳۲ و غیره لازم است.

برای انجام بازی دو دیسکی تنها با سه حرکت، دیسک کوچک را روی میله وسط، دیسک بزرگ‌تر را در سمت راست‌ترین میله قرار دهید و با قرار دادن دیسک کوچک‌تر روی دیسک بزرگ‌تر بازی را به پایان برسانید. یک راه برای انجام بازی سه دیسک این است که بالاترین پشته دو دیسکی را به میله میانی منتقل کنید. سپس بزرگ‌ترین دیسک را از سمت چپ به سمت راست‌ترین میله حرکت دهید (یک حرکت). بعد پشته دو دیسکی را که اکنون در میله وسطی بالای بزرگ‌ترین دیسک است حرکت دهید. باز هم یک تغییر جزئی از بازی دو دیسکی که با سه حرکت قابل انجام است. این حاصل ۳ + ۱ + ۳، یا هفت حرکت است.

این رویکرد مشابه، به بازی چهار دیسک کمک می‌کند. ابتدا بالاترین پشته سه دیسکی را با استفاده از هفت حرکت به میله وسط منتقل کنید. سپس بزرگ‌ترین دیسک را از سمت چپ به سمت راست‌ترین میله حرکت دهید (یک حرکت). حالا پشته سه دیسکی را که در میله وسط قرار دارد روی بزرگ‌ترین دیسک حرکت دهید (هفت حرکت). این دقیقاً ۷ + ۱ + ۷ یا ۱۵ حرکت را نشان می‌دهد. ریاضیدانان به این روش بازگشتی می‌گویند. برای حل پازل با دیسک‌های بیشتر، با یافتن راه‌حل برای تعداد کمتری دیسک شروع کنید. اگر تصمیم به ارائه درباره برج هانوی دارید و می‌خواهید ارائه‌ای مفید و بی نقص داشته باشید پیشنهاد می‌کنیم از فایل آماده درج شده در لینک زیر استفاده کنید.

• پاورپوینت برج هانوی — کلیک کنید.

راه‌های دیگری نیز برای انجام بازی وجود دارد. برای شروع بازی با حداقل تعداد حرکت، الگویی وجود دارد: کوچک‌ترین دیسک هنگام بازی با تعداد زوج دیسک به سمت راست‌ترین میله و هنگام بازی با تعداد فرد دیسک به میله وسط می‌رود. شاید شما نیز متوجه شده‌اید که در حین بازی، کوچک‌ترین دیسک را به طور متناوب حرکت می‌دهید. اگر دقت کنید، متوجه خواهید شد که همان مجموعه دستورالعمل‌ها را بارها و بارها تکرار می‌کنید تا زمانی که برج در طرف دیگر میله شما ظاهر شود. ریاضیدانان این را یک راه‌حل تکراری می‌نامند.

رابطه تکرار برای این پازل به صورت زیر خواهد بود:

حال می‌توان این رابطه را در یک تکرار به صورت جدول زیر حل کرد:

برج هانوی یک مسئله برنامه‌نویسی پویا است که در چالش‌های مختلف برنامه‌نویسی رقابتی استفاده می‌شود. در ادامه، مسئله برج هانوی با چند زبان برنامه‌نویسی پیاده‌سازی شده است:

پیاده سازی برج هانوی با ++C

// C++ recursive function to
// solve tower of hanoi puzzle
#include <bits/stdc++.h>
using namespace std;

void towerOfHanoi(int n, char from_rod,
					char to_rod, char aux_rod)
{
	if (n == 0)
	{
		return;
	}
	towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);
	cout << "Move disk " << n << " from rod " << from_rod <<
								" to rod " << to_rod << endl;
	towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);
}

// Driver code
int main()
{
	int n = 4; // Number of disks
	towerOfHanoi(n, 'A', 'C', 'B'); // A, B and C are names of rods
	return 0;
}

پیاده سازی برج هانوی با #C

مسئله برج هانوی در زبان #C به صورت زیر پیاده سازی می شود:

/*
 * C# Program to Demonstrate Tower Of Hanoi
 */
using System;
class TowerOfHanoi
{
    int m_numdiscs;
    public TowerOfHanoi()
    {
        numdiscs = 0;
    }
    public TowerOfHanoi(int newval)
    {
        numdiscs = newval;
    }
    public int numdiscs
    {
        get
        {
            return m_numdiscs;
        }
        set
        {
            if (value > 0)
                m_numdiscs = value;
        }
     }
     public void movetower(int n, int from, int to, int other)
     {
         if (n > 0)
         {
             movetower(n - 1, from, other, to);
             Console.WriteLine("Move disk {0} from tower {1} to tower {2}", 
                                n, from, to);
             movetower(n - 1, other, to, from);
         }
     }
}
class TowersOfHanoiApp
{
    public static int Main()
    {
        TowerOfHanoi T = new TowerOfHanoi();
        string cnumdiscs;
        Console.Write("Enter the number of discs: ");
        cnumdiscs = Console.ReadLine();
        T.numdiscs = Convert.ToInt32(cnumdiscs);
        T.movetower(T.numdiscs, 1, 3, 2);
        Console.ReadLine();
        return 0;
    }
}

ما تعداد دیسک‌ها را با استفاده از متغیر cnumdiscs می‌خوانیم. تابع ()movetower را با ارسال مقادیر متغیر numdiscs، ۱، ۳، ۲ به عنوان آرگومان تابع فراخوانی می کنیم. با استفاده از شرط if شرط را بررسی می‌کنیم، مقدار متغیر ‘n’ بزرگ‌تر از ۰ است. اگر شرط درست است، با حرکت دادن دیسک‌ها به صورت بازگشتی، دستور را اجرا می‌کنیم. شما عزیزان می‌توانید با اندکی هزینه سورس کد کامل برج هانوی بصورت کاملاً گرافیکی را از فروشگاه ما دانلود کنید. جهت دانلود به لینک زیر مراجعه کنید.

• سورس کد برج هانوی در سی شارپ Hanoi Tower به صورت گرافیکی — کلیک کنید.

پیاده سازی برج هانوی با Java

مسئله برج هانوی در زبان جاوا نیز به صورت زیر پیاده سازی می‌شود:

/*
 * Java Program to Solve Tower of Hanoi Problem using Stacks
 */
 
 import java.util.*;
 
 /* Class TowerOfHanoiUsingStacks */
 public class TowerOfHanoiUsingStacks
 {
     public static int N;
     /* Creating Stack array  */
     public static Stack<Integer>[] tower = new Stack[4]; 
 
     public static void main(String[] args)
     {
         Scanner scan = new Scanner(System.in);
         tower[1] = new Stack<Integer>();
         tower[2] = new Stack<Integer>();
         tower[3] = new Stack<Integer>();
         /* Accepting number of disks */         
         System.out.println("Enter number of disks");
         int num = scan.nextInt();
         N = num;
         toh(num);
     }
     /* Function to push disks into stack */
     public static void toh(int n)
     {
         for (int d = n; d > 0; d--)
             tower[1].push(d);
         display();
         move(n, 1, 2, 3);         
     }
     /* Recursive Function to move disks */
     public static void move(int n, int a, int b, int c)
     {
         if (n > 0)
         {
             move(n-1, a, c, b);     
             int d = tower[a].pop();                                             
             tower[c].push(d);
             display();                   
             move(n-1, b, a, c);     
         }         
     }
     /*  Function to display */
     public static void display()
     {
         System.out.println("  A  |  B  |  C");
         System.out.println("---------------");
         for(int i = N - 1; i >= 0; i--)
         {
             String d1 = " ", d2 = " ", d3 = " ";
             try
             {
                 d1 = String.valueOf(tower[1].get(i));
             }
             catch (Exception e){
             }    
             try
             {
                 d2 = String.valueOf(tower[2].get(i));
             }
             catch(Exception e){
             }
             try
             {
                 d3 = String.valueOf(tower[3].get(i));
             }
             catch (Exception e){
             }
             System.out.println("  "+d1+"  |  "+d2+"  |  "+d3);
         }
         System.out.println("\n");         
     }
 }

سخن پایانی مسئله برج هانوی

در پایان این مسئله که عنوان کرده بود: برج هانوی چیست؟ باید بگویم همان طوریکه ریاضیات راه حل بسیاری از مسائل پیچیده، از شرط‌بندی فوتبال گرفته تا بانکداری و پرتاپ موشک و هزاران مورد دیگر را دارد، برای این مسئله هم پاسخی در چنته دارد. ترکیب دو علم ریاضی و برنامه‌نویسی جواب بسیاری از مسائل پیچیده را در کمترین زمان می‌دهد در این معما هم با کمک گرفتن از الگوریتم‌های بهینه و پیاده‌سازی در زبان‌های برنامه‌نویسی مختلف پاسخ را نشان می‌دهد. امید است این پست نظر آنان که ذهن‌های پویا دارند و به حل معماهایی با اساس ریاضیات علاقه‌مند هستند را جلب کرده باشد، بی‌صبرانه و مشتاق، منتظر دریافت نظرات شما در این زمینه هستیم. موفق و پیروز باشید.

پاورپوینت الگوریتم و فلوچارت — آموزش رسم فلوچارت

پاورپوینت الگوریتم و فلوچارت — آموزش رسم فلوچارت

کلیک کنید