Mètodes o esquemes algorítmics
Salta a la navegació
Salta a la cerca
Contingut
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
// 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