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

در این بخش سورس کد برج هانوی در سی شارپ قرار داده شده است. برج هانوی (Tower of Hanoi) یکی از مسائل تاریخی مشهور است که در مباحث طراحی الگوریتم به آن پرداخته می‌شود.

نمونه‌ای از برج هانوی

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

میله اولیه ۶۴ قرص داشت، که بر روی هم به‌طور نزولی بر اساس اندازه‌شان چیده شده‌ بودند.همانند شکل زیر سه میله داریم. یکی از میله‌ها میله مبدأ (A)، دیگری میله کمکی (B) و دیگری میله مقصد (C) است. هدف انتقال تمام دیسک‌ها از میله مبدأ به میله مقصد با رعایت شرایط زیر است:

• در هر زمان فقط یک دیسک را می‌توان جابجا نمود.
• نباید در هیچ زمانی دیسکی بر روی دیسک با اندازه کوچکتر قرار بگیرد.

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

هدف ارائه الگوریتمی است که کمترین توالی حرکت‌ها را برای انتقال دیسک‌ها به ما بدهد. مثلاً اگر n=۲ باشد، توالی حرکت به صورت زیر است:

دیسک ۱ را به میله B منتقل می‌کنیم.
دیسک ۲ را به میله C منتقل می‌کنیم.
دیسک ۱ را به میله C منتقل می‌کنیم.

توجه داشته باشید که بر اساس قانون اول نمی‌توان به غیر از بالاترین دیسک هر میله، به دیسک دیگری از آن دسترسی پیدا کرد.

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

n – ۱ دیسک بالایی را با شرایط ذکر شده و به کمک میله C به میله B منتقل می‌کنیم. بزرگترین دیسک را از میله مبدأ به میله مقصد حرکت می‌دهیم. n – ۱ دیسک را که هم اکنون در میله B هستند با شرایط داده شده به میله مقصد انتقال می‌دهیم. می‌بینیم که توانستیم عملیات جابجا کردن n دیسک را به دو عملیات مشابه ولی با اندازه کمتر و یک عملیات ساده تقسیم کنیم. واضح است که جابجا کردن n – ۱ دیسک راحتتر از جابجا نمودن n دیسک است.

تحلیل پیچیدگی زمانی مسئله‌ی برج هانوی

در حالت کلی می‌خواهیم بدانیم اگر تعداد دیسک‌ها n باشد، کمترین تعداد حرکت برای جابجا نمودن دیسک‌ها چقدر است؟

فرض کنید (T(n تعداد حرکت‌های لازم جهت انتقال n دیسک به مقصد باشد. بر اساس توضیحات فوق، تعداد (T(n−۱ حرکت برای انتقال n−۱ دیسک به میله‌ی کمکی، یک حرکت برای انتقال بزرگترین دیسک به میله‌ی مقصد و مجددا (T(n−۱ حرکت برای انتقال n−۱ دیسک موجود در میله‌ی کمکی به میله‌ی مقصد نیاز است. پس:

T(n)=2T(n−۱)+۱

با حل این رابطه‌ی بازگشتی به روش‌های ریاضی، به نتیجه‌ی زیر می‌رسیم:

T(n)=2n−۱

مرتبه‌ی اجرایی این الگوریتم (O(2n است که چندان مرتبه‌ی مطلوبی به نظر نمی‌رسد. اما همانگونه که بحث شد، این روش حداقل تعداد حرکت‌های ممکن را می‌دهد؛ و هرگز نمی‌توان روش دیگری با مرتبه‌ی پایین‌تر برای حل آن یافت.

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

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

کلاس MoveCalculator : این کلاس با هدف تنها کار بر روی راه حل ایجاد شده است. حل مسئله بصورت بازگشتی است.

public static class MoveCalculator
{         
    private static void Calculate(int n, int fromPole, int toPole)
    {
        if (n == -1)
        {
            return; // We are done
        }
        int intermediatePole = GetIntermediatePole(fromPole, toPole);
        
        Calculate(n - 1, fromPole, intermediatePole);
        moves.Add(new Move(fromPole, toPole));
        Calculate(n - 1, intermediatePole, toPole);
    }    
    ... 
}

کلاس GameState : کلاس بالا لیستی از حرکت‌ها را باز می‌کند و GameState آنها را می‌سازد.

public static class GameState
    {
        public static List<Pole> Poles = new List<Pole>();
        public static List<Bitmap> ImageList = new List<Bitmap>();
        public static int MoveCount { get; set; }
        public static int NumberOfDisks { get; set; }
        
        // Start the game
        static GameState()
        {
            LoadImagesFromFile();
            RestartGame(3);
        }
 
        public static int Move(Move move)
        {
         if (move.AffectCount())
            {
                MoveCount++;
            }
            
            if (move.IsValid())
            {
                Disk disk = move.FromPole.getTopDisk();
                Poles[move.FromPole.Number].RemoveDisk();
                Poles[move.ToPole.Number].AddDisk(disk);
                return MoveCount;
            }
 
            else //Invalid move
            {
                return -1;
            }  
        }
 
        public static bool IsSolved()
        {
            return (Poles[Properties.Settings.Default.EndPole].Disks.Count == NumberOfDisks);
        } 
}

کلاس Move: این کلاس برای تعریف حرکت دیسک‌ها ایجاد شده است.

public class Move 
{
    public Pole FromPole { get; set; }
    public Pole ToPole { get; set; }
    
    public bool AffectCount()
    {
        //If the poles don't change the move should not be counted
        if (ToPole.Equals(FromPole))
        {
            return false;
        }
        return IsValid();
    }            

    public bool IsValid()
    {
        //Allow a move where the pole dont change
        if (ToPole.Equals(FromPole))
        {
            return true;
        }
        return ToPole.AllowDisk(FromPole.getTopDisk());
    }    
    ...
}

فرم GameForm: فرم اصلی برنامه می‌باشد که توابع و کلاس‌ها در آن ایجاد می‌شود.

نمایش خروجی محصول

درباره سورس کد برج هانوی در سی شارپ

سورس کد برج هانوی بصورت در سی شارپ دارای دو قسمت حل به روش دستی و حل خود کار با استفاده از روش بازگشتی بصورت گرافیکی می‌باشد. این سورس کد به زبان سی شارپ #C در Microsoft Visual Studio 2013 نوشته شده است. این سورس کد توسط کارشناسان پی استور تست و اجرا شده است و مورد تایید پی استور می‌باشد و دارای نشان ضمانت پی استور می‌باشد. برای دانلود سورس کد برج هانوی در سی شارپ Hanoi Tower به صورت گرافیگی، اثر  را خریداری کنید. به محض خرید لینک دانلود در دسترس خواهد بود.