Contingut 1 Introducció 2 Classificació 3 Divide y vencerás 3.1 Torres de Hanoi 4 Backtrackin, vuelta atrás 5 Algoritmes voraços, greedy algorythms

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:

-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

Divide y vencerás

Torres de Hanoi

• https://ca.wikipedia.org/wiki/Torres_de_Hanoi

// 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
}

$ g++ -o torres_hanoi torres_hanoi.cpp

Millorant la sortida per pantalla per tal de què quedi clara la recursivitat:

// 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
}

I el resultat per 3 i 4 discs:

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)

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

---

creat per Joan Quintana Compte, juny 2017