Algoritmos

Fundamentos de Programación Tema 4: Algorítmica básica
1 Introducción
Existen dos tipos de algoritmos: los iterativos (básicamente, utilizan bucles para resolver los problemas), y recursivos (se llaman a sí mismos para resolver problemas). En cuanto a funcionalidad, los algoritmos más básicos son los de búsqueda y ordenación. En este documento se describirán dos algoritmos de este tipo, el debúsqueda binaria y el de ordenación por inserción (y el de búsqueda lineal, casi no tenido en cuenta por simple). Posteriormente, se aplicarán como ejemplo para introducir los algoritmos de tipo recursivo.

2 Algoritmos iterativos
2.1 Búsqueda 2.1.1 Búsqueda lineal
La búsqueda lineal consiste en, dado un vector o matriz, recorrerlo desde el principio hasta el final, de elelemento en elemento.Supóngase un vector que almacena cadenas: la búsqueda lineal consistirá en revisar todos los elementos hasta encontrar el que se busca. Entonces, se devuelve su posición, o -1 en caso de no ser encontrado.
ALGORITMO BúsquedaLineal CONSTANTES MaxElementos : ENTERO = 100 TIPOS Vector = vector[MaxElementos] de ENTERO FUNCION busquedaLineal(E v: Vector, numBuscado, numElem: ENTERO) : ENTEROVARIABLES i: ENTERO INICIO i ← 0 MIENTRAS v[ i ] numBuscado Y i < numElem i ← i + 1 FIN_MIENTRAS SI v[ i ] = numBuscado busquedaLineal ← i SINO busquedaLineal ← -1 FIN_FUNCION VARIABLES v: Vector num: ENTERO pos: ENTERO INICIO { Preparar el vector } DESDE i ← 0 HASTA MaxElementos - 1 v[ i ] ← i * 2 FIN_DESDE { Buscar } LEER( num );

pos = busquedaLineal( v, num, MaxElementos ); { Informar} SI pos >-1 ESCRIBIR( “Encontrado en “, pos ) SINO ESCRIBIR( “No encontrado” ) FIN_ALGORITMO

El funcionamiento del algoritmo es obvio: primero se le da al vector de enteros valores iniciales, y después se le pide un número al usuario. Si la búsqueda lineal devuelve -1, entonces es que no se encontró; en otro caso, se devuelve la posición en la que se encontró. El único problema que tiene este algoritmoes que depende directamente de la longitud del vector. En este caso, sea como sea la máquina donde se ejecute, su velocidad de ejecución dependerá de MaxElementos. A continuación, se incluye la implementación en C++ estructurado de este algoritmo.
// Algoritmo BúsquedaLineal #include const int MaxElementos = 100; int busquedaLineal(int v[], int numBuscado, int numElem) { int i = 0; while( v[ i] != numBuscado && i < numElem ) { ++i; } if ( v[ i ] == numBuscado) return i; else return -1; } int main() { int int int int

i; num; pos; v[MaxElementos];

// Preparar el vector for(i = 0; i < MaxElementos; ++i) { v[ i ] = i * 2; } // Pedir el num y buscar printf( "Introduzca un número a buscar: " ); scanf( "%d", &num ); pos = busquedaLineal( v, num, MaxElementos ); // Informar if ( pos >-1 ) printf( "\nEncontrado en %d.\n", pos ); else printf( "\nNo encontrado.\n" ); } return 0;

2.1.2 Búsqueda binaria
La búsqueda binaria consiste en, dado un vector, comprobar la mitad del vector, con lo que, según el elemento a buscar, estará en una de las mitades. Este proceso se repite con la mitad donde esté el elemento, comprobando si el medio es el elemento buscado, y así sucesivamentehasta encontrarlo (de estar). Ésto implica una limitación básica para que este algoritmo pueda funcionar: el vector tiene que haberse ordenado previamente, sus elementos deben estar ordenados para poder elegir la mitad correcta en la que buscar a continuación. Como el algoritmo anterior, devuelve la posición o -1 en caso contrario.
ALGORITMO BúsquedaBinaria CONSTANTES MaxElementos : ENTERO =100 TIPOS Vector = vector[MaxElementos] de ENTERO FUNCION busquedaBinaria(E v: Vector, numBuscado, numElem: ENTERO) : ENTERO VARIABLES alto: ENTERO bajo: ENTERO medio: ENTERO INICIO alto = numElem; bajo = 0; medio = bajo + ( ( alto – bajo ) / 2 ) MIENTRAS v[ medio ] numBuscado Y medio > bajo SI numBuscado > v[ medio ] bajo = medio SINO alto = medio FIN_SI medio = bajo + ( ( alto – bajo ) / 2 )...