Untitled
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...