Aquí podéis encontrar 3 algoritmos básicos los cuales me parecen imprescindibles para programar:
Búsqueda dicotómica
La búsqueda dicotómica os ayudará a encontrar de forma rápida y eficiente lo que deseéis dentro de un vector ordenado.
Recordad que podéis modificar la función para adaptarla a vuestras necesidades.
#include <iostream>
#include <vector>
using namespace std;int posicio(double x, const vector<double>& v, int esq, int dre) {
if (esq > dre) return -1;
int pos = (esq + dre)/2; // posicio central de v[esq..dre]
if (x < v[pos]) return posicio(x, v, esq, pos – 1);
if (x > v[pos]) return posicio(x, v, pos + 1, dre);
return pos;
}
int main() {
int n;
double val;
cin >> n;
vector<double> v(n);for (int i = 0; i < n; ++i) cin >> v[i];
while (cin >> val) {
cout << posicio(val,v,0,int(v.size())-1) << endl;
}
}
Ordenación por inserción
La ordenación por inserción no es la forma más óptima de ordenar un vector, sin embargo, es una buena forma de ordenación. Además es un algoritmo fácil de entender y aprender.
#include <iostream>
#include <vector>
using namespace std;
// Pre: cap
// Post: v conte els elements inicials i esta ordenat creixentment
void ordena_per_insercio(vector<double>& v) {
// Inv: v[0..i-1] esta ordenat creixentment
for (int i = 1; i < v.size(); ++i) {
double x = v[i];
int j = i;
while (j > 0 and v[j – 1] > x) {
v[j] = v[j – 1];
–j;
}
v[j] = x;
}
}int main() {
int n;
cin >> n;
vector<double> v(n);for (int i = 0; i < n; ++i) cin >> v[i];
ordena_per_insercio(v);
for (int i = 0; i < n; ++i) cout << v[i] << » «;
cout << endl;}
Búsqueda de un String dentro de otro
Como dice el propio título, este algoritmo óptimo sirve para buscar un string dentro de otro.
#include <string>
using namespace std;
// Pre: cap
// Post: o be 0<=i< y.size() i x==y[i..i+x.size()-1] i x no apareix abans a y,
// o be i==-1 i x no apareix enlloc dins de y
int posicio (const string& x, const string& y) {
int i = 0;
bool trobat = (x.size() == 0);
int n = int(y.size()) – int(x.size());
// Inv: no hi ha cap ocurrencia de x en y que
// comenci en posicions 0..i-1
while (not trobat and i <= n) {
int j = 0;
bool encaixa = true;
// Inv: …, i a mes x[0..j-1] == y[i..i+j-1]
while (encaixa and j < x.size()) {
encaixa = (x[j] == y[i+j]);
++j;
}
if (encaixa) trobat = true;
else ++i;
}
if (trobat) return i;
else {
i = -1;
return i;
}
}
// Pre: cap
// Post: o be 0<=i<y.size() i x==y[i..i+x.size()-1],
// o be i==-1 i x no apareix enlloc dins de y
int posicio_alternativa (const string& x, const string& y) {
int i,j;
i=j=0;
int n = int(y.size()) – int(x.size());
// Inv: no hi ha cap ocurrencia de x en y
// que comenci en posicions 0..i-1,
// i a mes x[0..j-1] == y[i..i+j-1]
while (j < x.size() and i <= n) {
if (x[j] == y[i+j]) ++j;
else {
j=0;
++i;
}
}
if (j == x.size()) return i;
else {
i = -1;
return i;
}
}
int main() {
string x,y;
while (cin >> x >> y) {
cout << posicio(x,y) << endl;
}
}