Untitled

 avatar
unknown
plain_text
2 years ago
4.0 kB
5
Indexable
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Zadanie3
{
    class Program
    {
        static void RuchKrazkow(char from, char to, int krazek)
        {
            Console.WriteLine("Ruch krazka " + krazek + " from " + from + " to " + to);
        }

        static void RuchPomiedzyDwomaPretami(ref Stack<int> src, ref Stack<int> dest, char s, char d)
        {
            int srcTopKrazek, destTopKrazek;

            if (src.Count == 0) // sprawdzenie, czy stos jest pusty czy nie
                srcTopKrazek = int.MinValue;
            else
                srcTopKrazek = src.Pop();

            if (dest.Count == 0)
                destTopKrazek = int.MinValue;
            else
                destTopKrazek = dest.Pop();

            // gdy srcTopKrazek jest pusty
            if (srcTopKrazek == int.MinValue)
            {
                src.Push(destTopKrazek);
                RuchKrazkow(d, s, destTopKrazek);
            }
            // gdy destTopKrazek jest pusty
            else if (destTopKrazek == int.MinValue)
            {
                dest.Push(srcTopKrazek);
                RuchKrazkow(s, d, srcTopKrazek);
            }
            // gdy srcTopKrazek jest wieksze od destTopKrazek
            else if (srcTopKrazek > destTopKrazek)
            {
                src.Push(srcTopKrazek);
                src.Push(destTopKrazek);
                RuchKrazkow(d, s, destTopKrazek);
            }
            // gdy destTopKrazek jest wiekszy od srcTopKrazek
            else
            {
                dest.Push(destTopKrazek);
                dest.Push(srcTopKrazek);
                RuchKrazkow(s, d, srcTopKrazek);
            }
        }

        static void WiezaHanoi(int n) //n - liczba krazkow
        {
            // stosy
            //src - slupek startowy, aux - pomocniczy, dest - docelowy
            Stack<int> src = new Stack<int>(n);
            Stack<int> aux = new Stack<int>(n);
            Stack<int> dest = new Stack<int>(n);

            char s = 'S', d = 'D', a = 'A'; // PRĘTY - startowy (source), docelowy (destination), pomocniczy(auxiliary)

            // 1. Obliczenie calkowitej liczby ruchow potrzebnych do ulozenia wiezy
            // liczba ruchow = (2^n)-1
            int liczba_ruchow = (int)(Math.Pow(2, n) - 1);
            Console.WriteLine("Liczba ruchow: " + liczba_ruchow);

            // 2. Jesli liczba dyskow jest parzysta => zamienic pręt pomocniczy(a) i docelowy
            if(n % 2 == 0)
            {
                char temp = d;
                d = a; 
                a = temp;
            }

            // (i % 3 == 0) legal movement between ‘A’ and ‘D’
            // (i % 3 == 1) legal movement between ‘S’ and ‘D’ 
            // (i % 3 == 2) legal movement between ‘S’ and ‘A’

            // uzupelnianie stosu startowego
            for(int i = n; i >= 1; i--)
            {
                src.Push(i);
            }

            for(int i = 1; i <= liczba_ruchow; i++)
            {
                if(i % 3 == 0)
                {
                    RuchPomiedzyDwomaPretami(ref aux, ref dest, a, d);
                } else if(i % 3 == 1)
                {
                    RuchPomiedzyDwomaPretami(ref src, ref dest, s, d);
                } else if(i % 3 == 2)
                {
                    RuchPomiedzyDwomaPretami(ref src, ref aux, s, a);
                }
            }




        }

        static void Main(string[] args)
        { /* Wykorzystując strukturę stos napisz metodę rozwiązującą problem wież
             Hanoi bez rekurencji. */
            //    Console.WriteLine("Podaj liczbę krążków: ");
            //    int n = Convert.ToInt32(Console.ReadLine());
            int n = 3;
            WiezaHanoi(n);
            Console.ReadKey();
        }
    }
}
Editor is loading...