Mètodes o esquemes algorítmics

De wikijoan
La revisió el 15:33, 6 juny 2017 per Joan (discussió | contribucions) (→‎Torres de Hanoi)
(dif) ← Versió més antiga | Versió actual (dif) | Versió més nova → (dif)
Salta a la navegació Salta a la cerca

Introducció

Es tracta de mostrar els dissenys típics que s'estudien en algorismes, i exemples clàssics i il.lustratius.

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

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

Exemples:

  • Sudoku
  • Problema de los movimientos de un caballo
  • Las ocho reinas

Algoritmes voraços, greedy algorythms


creat per Joan Quintana Compte, juny 2017