Mètodes o esquemes algorítmics

De Wikijoan
Dreceres ràpides: navegació, cerca

Contingut

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:

Algoritmes voraços, greedy algorythms


creat per Joan Quintana Compte, juny 2017

Eines de l'usuari
Espais de noms
Variants
Accions
Navegació
IES Jaume Balmes
Màquines recreatives
CNC
Informàtica musical
joanillo.org Planet
Eines