Wikipedia

Wieże Hanoi: Różnice pomiędzy wersjami

Przeglądaj historię interaktywnie
[wersja nieprzejrzana][wersja przejrzana]
← poprzednia edycjanastępna edycja →
Usunięta treść Dodana treść
WizualnieWikikod
nazwy słupków
Linia 1:
[[Plik:Tower of Hanoi.jpeg|thumb|300px|od lewej: wieża A, bufor, wieża B]]
[[Plik:Tower of Hanoi 4.gif|right|frame|Rozwiązanie łamigłówki dla czterech krążków]]
'''Wieże [[Hanoi]]''' – problem polegający na odbudowaniu, z zachowaniem kształtu, wieży z krążków o różnych średnicach (popularna dziecięca zabawka), przy czym podczas przekładania wolno się posługiwać buforem, reprezentowanym w tym przypadku przez dodatkowy słupek, jednak przy ogólnym założeniu, że nie można kłaść krążka o większej [[średnica|średnicy]] na mniejszy ani przekładać kilku krążków jednocześnie. Jest to przykład zadania, którego [[złożoność obliczeniowa]] wzrasta niezwykle szybko w miarę zwiększania parametru wejściowego, tj. liczby elementów wieży.
Linia 7 ⟶ 6:
 
== Algorytm ==
[[Plik:Tower of Hanoi.jpeg|thumb|300px|Od lewej: słupek A z całą wieżą, pusty słupek B pełniący rolę bufora i pusty słupek docelowy C]]
Wieże Hanoi można łatwo rozwiązać za pomocą prostego algorytmu [[Rekursja|rekurencyjnego]] lub iteracyjnego.
* nazywamyOznaczmy kolejne słupki: literami A, B, i C.
* niechNiech ''n'' będzie liczbą krążków, które chcemy przenieść ze słupka A na słupek BC posługując się słupkiem CB jako buforem.
 
=== Rozwiązanie rekurencyjne ===
Algorytm rekurencyjny składa się z następujących kroków:
# przenieś (rekurencyjnie) przenieś ''n''-1 krążków ze słupka A na słupek CB posługując się słupkiem BC,
# przenieś jeden krążek ze słupka A na słupek BC,
# przenieś (rekurencyjnie) przenieś ''n''-1 krążków ze słupka CB na słupek BC posługując się słupkiem A
 
Przykładowe implementacje ▼
 
▲Przykładowe implementacje
* w [[Python]]ie:
<source lang="python">
def hanoi(n, A, CB, BC):
"""słupki A, B, C są listami"""
if n > 0:
hanoi(n-1, A, BC, CB) # rekurencyjnie przekładamy n-1 krążków z A na B
C.insert(0, A.pop(0)) # przekładamy jeden krążek z A na C
hanoi(n-1, B, CA, AC) # rekurencyjnie przekładamy n-1 krążków z C na A
</source>
* w [[C++]]:
Linia 33 ⟶ 32:
using namespace std;
 
void hanoi(int n, char aA, char cB, char bC) {
// przekłada n krążków z a na cA korzystając z bB na C
if (n > 0) {
hanoi(n-1, aA, bC, cB);
cout << aA << " -> " << cC << endl;
hanoi(n-1, bB, cA, aC);
}
}
Linia 47 ⟶ 46:
}
</source>
algorytmAlgorytm rozwiązywania wież Hanoi jest klasycznym przykładem algorytmu rekurencyjnego w nauczaniu [[informatyka|informatyki]].
 
=== Rozwiązanie iteracyjne ===
Źródło: „https://pl.wikipedia.org/wiki/Wieże_Hanoi”