Joan: /* Torres de Hanoi */

2017-06-06T15:33:17Z

Torres de Hanoi

Pàgina nova

=Introducció=
Es tracta de mostrar els dissenys típics que s'estudien en algorismes, i exemples clàssics i il.lustratius.
*https://es.wikipedia.org/wiki/Algoritmo
*https://es.wikipedia.org/wiki/Dise%C3%B1o_de_algoritmos
*https://es.wikipedia.org/wiki/Categor%C3%ADa:Algoritmos
=Classificació=
A grans trets, 3 tipus:
<pre>
-divide y vencerás (torres de hanoi)
-Vuelta atrás (cerca exhaustiva) (backtracking)
-voraç (greedy algorythm)
-ramificació i poda
-temps...
-algoritmo dijkstra, prim, kruskal, floyd
</pre>
=Divide y vencerás=
==Torres de Hanoi==
*https://ca.wikipedia.org/wiki/Torres_de_Hanoi
<pre>
// g++ -o torres_hanoi torres_hanoi.cpp

#include <iostream>

using namespace std;

void hanoi(int n, char origen, char desti, char aux) {
if(n != 0) {
hanoi(n-1,origen,aux,desti);
cout << origen << " => " << desti << endl;
hanoi(n-1,aux, desti, origen);
}
}

int main() {
int n;
cout << "Introdueix el nombre de discs: ";
cin >> n;
cout << "Els moviments que s'han de fer:\n";
hanoi(n,'A','C','B'); // transfereix n discos de A a C utilitzant B
}
</pre>
<pre>
$ g++ -o torres_hanoi torres_hanoi.cpp
</pre>

Millorant la sortida per pantalla per tal de què quedi clara la recursivitat:
<pre>
// g++ -o torres_hanoi torres_hanoi.cpp

#include <iostream>

using namespace std;
int num;

void hanoi(int n, char origen, char desti, char aux) {
if(n != 0) {
for (int i=0; i < num-n; i++) {
cout << "\t";
}
cout << "hanoi(" << n-1 << ", " << origen << ", " << desti << ", " << aux << ")" << endl;
hanoi(n-1,origen,aux,desti);
cout << origen << " => " << desti << endl;
hanoi(n-1,aux, desti, origen);
}
}

int main() {
cout << "Introdueix el nombre de discs: ";
cin >> num;
cout << "Els moviments que s'han de fer:\n";
hanoi(num,'A','C','B'); // transfereix n discos de A a C utilitzant B
}
</pre>
I el resultat per 3 i 4 discs:
<pre>
Introdueix el nombre de discs: 3
Els moviments que s'han de fer:
hanoi(2, A, C, B)
hanoi(1, A, B, C)
hanoi(0, A, C, B)
A => C
hanoi(0, A, C, B)
A => B
hanoi(1, A, B, C)
hanoi(0, C, B, A)
C => B
hanoi(0, C, B, A)
A => C
hanoi(2, A, C, B)
hanoi(1, B, C, A)
hanoi(0, B, A, C)
B => A
hanoi(0, B, A, C)
B => C
hanoi(1, B, C, A)
hanoi(0, A, C, B)
A => C
hanoi(0, A, C, B)

Introdueix el nombre de discs: 4
Els moviments que s'han de fer:
hanoi(3, A, C, B)
hanoi(2, A, B, C)
hanoi(1, A, C, B)
hanoi(0, A, B, C)
A => B
hanoi(0, A, B, C)
A => C
hanoi(1, A, C, B)
hanoi(0, B, C, A)
B => C
hanoi(0, B, C, A)
A => B
hanoi(2, A, B, C)
hanoi(1, C, B, A)
hanoi(0, C, A, B)
C => A
hanoi(0, C, A, B)
C => B
hanoi(1, C, B, A)
hanoi(0, A, B, C)
A => B
hanoi(0, A, B, C)
A => C
hanoi(3, A, C, B)
hanoi(2, B, C, A)
hanoi(1, B, A, C)
hanoi(0, B, C, A)
B => C
hanoi(0, B, C, A)
B => A
hanoi(1, B, A, C)
hanoi(0, C, A, B)
C => A
hanoi(0, C, A, B)
B => C
hanoi(2, B, C, A)
hanoi(1, A, C, B)
hanoi(0, A, B, C)
A => B
hanoi(0, A, B, C)
A => C
hanoi(1, A, C, B)
hanoi(0, B, C, A)
B => C
hanoi(0, B, C, A)
</pre>

=Backtrackin, vuelta atrás=
*https://es.wikipedia.org/wiki/Vuelta_atr%C3%A1s
Exemples:
*Sudoku
*Problema de los movimientos de un caballo
*Las ocho reinas
=Algoritmes voraços, greedy algorythms=
*https://en.wikipedia.org/wiki/Greedy_algorithm
{{Autor}}, juny 2017

Mètodes o esquemes algorítmics - Historial de revisió

Joan: /* Torres de Hanoi */