Fundamentos De Programación

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 de bú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) : ENTERO VARIABLES 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 algoritmo es 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í sucesivamente hasta 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 ) FIN_MIENTRAS SI v[ medio ] = numBuscado busquedaLineal ← medio 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 = busquedaBinaria( 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 binaria devuelve -1, entonces es que no se encontró; en otro caso, se devuelve la posición en la que se encontró. A continuación, se incluye la implementación en C++ estructurado de este algoritmo. // Algoritmo de búsqueda binaria #include const int MaxElementos = 100; int busquedaBinaria(int v[], int numBuscado, int numElem) { int alto = numElem; int bajo = 0; int medio = bajo + ( ( alto - bajo ) / 2 ); while( v[ medio ] != numBuscado && medio > bajo ) { if ( numBuscado > v[ medio ] ) bajo = medio; else alto = medio; medio = bajo + ( ( alto - bajo ) / 2 ); }

}

if ( v[ medio ] == numBuscado) return medio; 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 = busquedaBinaria( v, num, MaxElementos ); // Informar if ( pos > -1 ) printf( "\nEncontrado en %d.\n", pos ); else printf( "\nNo encontrado.\n" ); return 0; }

La velocidad de ejecución mejora ampliamente la del algoritmo anterior. Ahora, el tiempo de ejecución sólo depende del número de veces que el número total de elementos del vector pueda dividirse entre 2, es decir log2 MaxElementos. El único problema que presenta es que es necesario

tener el vector ordenado previamente.

2.2 Ordenación 2.2.1 Ordenación por inserción La ordenación por inserción precisa del doble de memoria de la que el vector ocupa. En un segundo vector, en principio vacío (aunque del mismo tamaño máximo que el primero), se van introduciendo los elementos del primero, secuencialmente, pero insertándolos de manera ordenada. Al final del recorrido del vector original, todos los elementos estarán ordenados en el segundo vector. ALGORITMO OrdenaciónPorInserción CONSTANTES MaxElementos : ENTERO = 100 TIPOS Vector = vector[MaxElementos] de ENTERO PROCEDIMIENTO ordenaInsercion(E/S v: Vector, E numElem: ENTERO) VARIABLES i: ENTERO j: ENTERO k: ENTERO v2: Vector numOcupados: ENTERO INICIO numOcupados ← 0 { Preparar el vector } DESDE i ← 0 HASTA MaxElementos - 1 v2[ i ] ← v[ i ] FIN_DESDE { Insertar ordenadamente } DESDE i ← 0 HASTA numElem – 1 { buscar la pos } j ← 0 MIENTRAS j < numOcupados Y v[ i ] > v2[ j ] j ← j + 1 FIN_MIENTRAS { desplazar el vector } DESDE k ← numOcupados HASTA j v[ k + 1 ] = v[ k ]; FIN_DESDE { insertar ordenado en vector } numOcupados ← numOcupados + 1 v[ j ] = v2[ i ]; FIN_DESDE FIN_FUNCION VARIABLES v: Vector num: ENTERO pos: ENTERO i: ENTERO INICIO { Preparar el vector } DESDE i ← 0 HASTA MaxElementos SI ( ( i mod 2 ) == 0 )

v[ i ] ← i / 2; v[ i ] ← i * 2

SINO FIN_DESDE

{ Ordenar } LEER( num ); ordenaInsercion( v, MaxElementos ); { Informar } DESDE i ← 0 HASTA MaxElementos ESCRIBIR( v[ i ] ) FIN_DESDE FIN_ALGORITMO

El funcionamiento del algoritmo es obvio: primero se le da al vector de enteros valores iniciales desordenados, y entonces el vector se ordena, mostrándole el resultado al usuario. A continuación, se incluye la implementación en C++ estructurado de este algoritmo. // Algoritmo OrdenaciónPorInserción #include const int MaxElementos = 10; void ordenaInsercion(int v[], int numElem) { int posVorg; int posDesp; int posOrd; int v2[MaxElementos]; int numOcupados = 0; // Preparar el vector auxiliar for(posVorg = 0; posVorg < numElem; ++posVorg) { v2[ posVorg ] = v[ posVorg ]; } // Insertar ordenadamente for(posVorg = 0; posVorg < numElem; ++posVorg) { // buscar la pos posOrd = 0; while ( posOrd < numOcupados && v2[ posVorg ] > v[ posOrd ] ) { ++posOrd; } // desplazar el vector for(posDesp = numOcupados; posDesp >= posOrd; --posDesp) { v[ posDesp + 1 ] = v [ posDesp ]; } // insertar ordenado en vector ++numOcupados; v[ posOrd ] = v2[ posVorg ]; } }

return;

int main() {

int int int int

i; num; pos; v[MaxElementos];

// Preparar el vector for(i = 0; i < MaxElementos; ++i) { if ( ( i % 2 ) == 0 ) v[ i ] = 120 + ( i / 2 ); else v[ i ] = 120 + ( i * 2 ); } // Pedir el num y buscar ordenaInsercion( v, MaxElementos ); // Informar for(i = 0; i < MaxElementos; ++i) { printf( "%d ", v[ i ] ); } printf( "\n" ); return 0; }

La velocidad de ejecución mejora ampliamente la alternativa más simple, que es el algoritmo de la burbuja (no explicado en este documento). Es necesario tener en cuenta, sin embargo, que este algoritmo es una variación del original: se utiliza un vector de destino, en un principio vacío, para evitar en lo posible que la eficiencia dependa del cuadrado de MaxElementos. La velocidad de ejecución del algoritmo de ordenación por la burbuja depende de MaxElementos2, mientras que en este caso suele comportarse, en media, mucho mejor que el de la burbuja, si bien, en el peor de los casos (curiosamente, que el vector ya esté ordenado, pero a la inversa), es cierto que tambíen depende de MaxElementos2.

3 Algoritmos recursivos Los algoritmos recursivos se denominan de esta forma debido a que se llaman a sí mismos para completar una ejecución. Hacer esto sin control de ningún tipo supondría un error de ejecución, ya que el programa se quedaría eternamente llamando a la misma función. Por eso, en un algoritmo recursivo es necesario prestar atención a dos casos: ● El caso base, el que termina la recursión. ● El caso repetitivo, el que realiza la recursión.

3.1 Cálculo del factorial Un ejemplo típico es el cálculo del factorial de un número. El factorial de un número n, factorial( n ), puede entenderse como n * factorial( n – 1 ), siempre y cuando se tenga en cuenta que factorial( 1 ) es 1, es decir, no provoca ninguna llamada recursiva. Este último caso es el caso base. El primero, n ← n * factorial( n – 1 ), es el caso repetitivo. El algoritmo recursivo de cálculo del factorial sería, por tanto: FUNCION factorial(E n: ENTERO) : ENTERO INICIO SI ( n == 1 ) factorial ← 1 SINO factorial ← n * factorial( n – 1 ) FIN_SI FIN_FUNCION

Esta misma función, en C++ estructurado sería: int factorial(int n) { if ( n == 1 ) return 1; else return n * factorial( n – 1 ); }

La sucesión de llamadas si se lanzase la ejecución con n = 4, sería la siguiente: ●

1: factorial( 4 ) ○ 2: factorial( 3 ) ■ 3: factorial( 2 ) ● 4: factorial( 1 )

Se detendría en factorial( 1 ) porque esta llamada no provoca ninguna llamada recursiva, sino que ya es el caso base: devuelve 1. Es ahora cuando se produce el primer retorno. La cuarta llamada devuelve 1, por lo que la tercera llamada factorial( 2 ), puede ya continuar su ejecución, sólo tiene que sustituir la expresión en la que estaba suspendida: n * factorial( n -1). n es 2, y la llamada recursiva acaba de devolver 1, por lo que la llamada tercera devuelve el resultado de multiplicar 2 * 1, a la segunda llamada, factorial( 3 ). Esta llamada se había quedado suspendida mientras se calculaba factorial( 2 ), en la ya conocida expresión n * factorial( n -1), puesto que n es 3. La expresión, por tanto, queda finalmente como 3 * 2, que es lo que la segunda llamada devuelve a la primera, la que inició el proceso, que se había quedado suspendida en el mismo punto que las otras. Para esta primera llamada n es 4, y factorial( 3 ) acaba de devolver 6, por lo que la expresión n * factorial( n -1), quedaría como 4 * 6, que es el resultado que finalmente devolvería la primera llamada, la que inicio la ejecución.

Figura 1: Representación gráfica del proceso recursivo del cálculo factorial para n = 4

Un esquema gráfico de este proceso puede verse en la figura 1, en el que las flechas punteadas representan las llamadas que se producen inicialmente, que dejan suspendidas a las funcione llamadoras, y las flechas sólidas representan el proceso inverso que ocurre después de que se produzca el primer retorno.

3.2 Multiplicación de dos números enteros positivos Un ejercicio similar al anterior sería el de la suma. Supóngase que no existe el operador '*', y por lo tanto la multiplicación se debe programar. La versión iterativa de este ejercicio sería: FUNCION multiplicacion(E a, b: ENTERO) : ENTERO VARIABLES i: ENTERO resultado: ENTERO INICIO resultado ← 0 DESDE i ← 0 HASTA b - 1 resultado ← resultado + a FIN_DESDE suma ← resultado FIN_FUNCION

Pero esta función podría transformarse en recursiva, si se tiene en cuenta que la multiplicacion( a, b ) puede entenderse recursivamente como a + multiplicacion( a, b – 1 ). FUNCION multiplicacion(E a, b: ENTERO) : ENTERO INICIO SI b = 0 multiplicacion ← 0 SINO multiplicacion ← a + multiplicacion( a, b – 1 ) FIN_SI FIN_FUNCION

Así, la multiplicación de tres por cuatro supondría las siguientes llamadas recursivas (los valores entre corchetes son las operaciones que se realizan una vez llegados hasta la base de la recursión): ● multiplicacion( 3, 4 ) = 3 + multiplicacion( 3, 3 ) [=3 + 6] ○ multiplicacion( 3, 3 ) = 3 + multiplicacion( 3, 2 ) [= 3 + 6] ■ multiplicacion( 3, 2 ) = 3 + multiplicacion( 3, 1 ) [= 3 + 3] ● multiplicacion( 3, 1 ) = 3 + multiplicacion( 3, 0 ) [= 3 + 0] ○ multiplicacion( 3, 0 ) [= 0]

La programación del algoritmo en C++ estructurado es prácticamente directa: int multiplicacion(int a, int b) { if ( b == 0 ) return 0; else return ( a + multiplicacion( a, b – 1 ) ); }

3.3 Búsqueda binaria La búsqueda binaria es, por su propia naturaleza, recursiva: se busca el elemento en una mitad, después en otra, dentro de la misma, hasta que finalmente se encuentra (o no). La transformación de este algoritmo en recursivo depende por tanto de las variables alto y bajo, que por tanto deben pasar a formar parte de los parámetros de la función. FUNCION busquedaBinaria(E v: Vector, numBuscado, bajo, alto: ENTERO) : ENTERO VARIABLES medio: ENTERO INICIO medio = bajo + ( ( alto – bajo ) / 2 ) SI v[ medio ] <> numBuscado SI medio == bajo medio ← -1 SINO SI numBuscado > v[ medio ] bajo = medio SINO alto = medio FIN_SI medio = busquedaBinaria( v, numBuscado, bajo, alto ); FIN_SI FIN_SI busquedaBinaria ← medio FIN_FUNCION

El modo de trabajo de esta función recursiva es el mismo que el de la versión iterativa, con la diferencia de que cada llamada se encarga de sólo una mitad del vector donde buscar, y en caso de no encontrar el elemento buscado, realiza una llamada recursiva hacia otra de las mitades. El proceso, para un vector de cuatro posiciones, en el que se busca el 10, sería el siguiente: 5 ●

10

15

20

busquedaBinaria( v, 10, 0, 4 ) [=1] ○ busquedaBinaria( v, 10, 0, 2 ) [= 1]

En cursiva se marcan los valores que se retornan después del retorno del caso base. ¿Qué sucedería si el elemento a buscar fuese el 11? ●

busquedaBinaria( v, 10, 0, 4 ) [=-1] ○ busquedaBinaria( v, 10, 0, 2 ) [=-1] ■ busquedaBinaria( v, 10, 0, 1 ) [ =-1]

Nótese que al ser división entera (puesto que los miembros de la expresión son enteros), el resultado de dividir 1 / 2 es 0. A continuación, se incluye el código fuente en C++ estructurado:

// Algoritmo BusquedaBinariaRecursiva #include const int MaxElementos = 100; int busquedaBinaria(int v[], int numBuscado, int bajo, int alto) { int medio = bajo + ( ( alto - bajo ) / 2 ); if ( v[ medio ] != numBuscado ) { if ( medio == bajo ) { medio = -1; } else { if ( numBuscado > v[ medio ] ) bajo = medio; else alto = medio; }

medio = busquedaBinaria( v, numBuscado, bajo, alto );

} }

return medio;

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 = busquedaBinaria( v, num, 0, MaxElementos ); // Informar if ( pos > -1 ) printf( "\nEncontrado en %d.\n", pos ); else printf( "\nNo encontrado.\n" ); return 0; }

4 Conclusiones En este tema se han visto algoritmos básicos de búsqueda y ordenación, a la vez que se ha introducido la recursividad. Tal y como se ha visto, el resultado es el mismo en ambos casos, sea el algoritmo recursivo o iterativo, y su eficiencia teórica no cambia. Un factor que sí se debe tener en cuenta es que el algoritmo recursivo supone realizar llamadas a funciones en lugar de iteraciones de bucles, y en general lo primero es bastante más complejo, y consume más recursos (como memoria en la pila de llamadas) que lo segundo. Siendo así, es posible plantearse siquiera la necesidad de utilizar algoritmos recursivos. Las ventajas de estos algoritmos no radican en su eficiencia, sino en la superior abstracción que se obtiene con ellos (es decir, el diseño de ciertos algoritmos complejos se hace más sencillo).

Supóngase el siguiente ejemplo: una calculadora debe evaluar expresiones como (6+(5*4)) / 2, de manera que siempre haya una pareja de paréntesis antes de cada subexpresión, y no se incluyan espacios. Por supuesto este problema se puede resolver de manera iterativa, pero de manera recursiva la solución es mucho más simple, como se puede ver a continuación: ALGORITMO Calculadora FUNCION calcular(E operando1: ENTERO, operador: CARACTER, operando2: ENTERO) : ENTERO VARIABLES resultado: ENTERO INICIO { Prec. Operador = '*' O '/', O '+' O '-' } CASO DE operador '*': resultado ← '/': resultado ← '+': resultado ← '-': resultado ← FIN_CASO calcular ← resultado FIN_FUNCION

operando1 operando1 operando1 operando1

* / + –

operando2 operando2 operando2 operando2

FUNCION evaluar(E expresion: Cadena, E/S pos: ENTERO) : ENTERO VARIABLES operando1: ENTERO operando2: ENTERO operador: CARACTER INICIO { tomar primer operando } SI expresion[ pos ] = '(' pos ← pos + 1 operando1 = evaluar( expresion, pos ) pos ← pos + 1 SINO operando1 = convertirCadenaNumero( expresion, pos ) FIN_SI { tomar operador } operador = expresion[ pos ] pos ← pos + 1 { tomar segundo operando } SI expresion[ pos ] = '(' pos ← pos + 1 operando2 = evaluar( expresion, pos ) pos ← pos + 1 SINO operando2 = convertirCadenaNumero( expresion, pos ) FIN_SI evalua ← calcular( operando1, operador, operando2 ) FIN_FUNCION

FUNCION convertirCadenaNumero( E entrada : CADENA, E/S pos:ENTERO) VARIABLES aux: CADENA INICIO MIENTRAS entrada[ pos ] >= '0' Y entrada[ pos ] <= '9' Y pos < longitud( cadena ) aux ← aux + entrada[ pos ] pos ← pos + 1 FIN_MIENTRAS convertirCadenaNumero ← convertirANumero( aux ) FIN_FUNCION

{ atoi( aux ) en C++ }

FUNCION evaluarExpresion(E entrada: CADENA) : ENTERO VARIABLES pos: ENTERO INICIO pos ← 0 evaluarExpresion ← evaluar( entrada, pos ) FIN_FUNCION VARIABLES entrada: CADENA INICIO LEER( entrada ); ESCRIBIR( resultado, evaluarExpresion( entrada ) ) FIN_ALGORITMO

La función convertirANumero() se ha marcado en negrita porque depende del lenguaje de programación utilizando. En C++, esta función sería exactamamente atoi(), (convierte una cadena con un número en su interior a ese número). Las llamadas recursivas que se producirían para una la expresión matemática anterior, serían las indicadas en la figura 2.

Figura 2: Esquema de ejecución de la calculadora: evaluar( 5 * 4) es la base de la recusión en este ejemplo.

Este pseudocódigo demuestra que los algoritmos recursivos ayudan a un diseño de más alto nivel, sin preocuparse tanto del cómo hacerlo, sino de qué es lo que hay que hacer.