Búsqueda avanzada
(por colaborador, editorial, año de edición, formatos)
Contenido
Introducción 15
Parte 1. Conceptos 17
Definiciones 19
Esquema de una solución recursiva 25
Introducción 25
Pensando de forma recursiva 26
El problema de calcular la cantidad de cifras
de un número dado 28
El problema de determinar si un número es par 29
El problema de determinar si un número es primo 30
El problema de calcular el residuo de la división
entre dos números 32
El problema de calcular la suma de los números
entre uno y un número dado 32
Ejemplos 34
Calcular el factorial de un número entero positivo 35
Calcular la potencia de dos números enteros positivos 37
Calcular la potencia de forma más eficiente 38
Calcular un término dado de la serie de Fibonacci 39
Calcular el máximo común divisor de dos números enteros 40
Calcular la suma de dos números enteros positivos 42
Ejercicios propuestos 43
Funcionamiento de la recursión 47
Introducción 47
Acciones que se realizan 47
Ejemplo práctico 49
Tiempos de ejecución 62
Clases de recursión 63
Recursión lineal o simple 63
Recursión lineal de cola 64
Recursión lineal no de cola 65
Recursión directa 65
Recursión indirecta, mutua o cruzada 66
Recursión múltiple 68
Recursión versus iteración 71
Problemática 71
Ventajas y desventajas de utilizar recursión 75
Ventajas que presenta el uso de la recursión 76
Desventajas del uso de la recursíón 76
Eliminación de la recursión 79
Eliminar recursión lineal de cola 79
Eliminar recursión lineal no de cola 82
Eliminar recursión no lineal de cola 85
Eliminar recursión no lineal no de cola 87
Parte 2. Solución de problemas 91
Manejo de arreglos 93
Definiciones 93
Arreglos de una dimensión - vectores 93
Ejercicios resueltos con vectores 95
Mostrar recursivamente el contenido de un arreglo o vector
en orden inverso (desde el último hasta el primero) 95
Mostrar recursivamente el contenido de un arreglo
en orden normal o directo (desde el primero hasta el último) 96
Sumar recursivamente el contenido de un vector de números
enteros utilizando un acumulador y recorriendo el arreglo
en orden inverso (del último al primer elemento) 97
Sumar recursivamente el contenido de un vector de números
enteros sin acumulador y recorriendo el arreglo en orden
inverso (desde el último hasta el primer elemento) 98
Invertir recursivamente el contenido de un vector
que contiene números enteros 99
Encontrar de forma recursiva el mayor elemento de un arreglo
conformado por números enteros recorriendo desde el último
hasta el primer elemento 100
Determinar recursivamente si un vector que contiene los
dígitos de un número cumple con las características
de capicúa (que se lee igual de izquierda a derecha
que de derecha a izquierda) 101
Manejo de arreglos de dos dimensiones - matrices 102
Ejercicios resueltos con matrices 104
Mostrar recursivamente el contenido de una matriz 104
Calcular recursivamente la traza de una matriz que contiene
números enteros (suma de los elementos de la diagonal principal) 106
Sumar recursivamente el contenido de una matriz
con números enteros 107
Calcular la matriz transpuesta de una matriz dada que contiene
números enteros 108
Ejercicios propuestos 110
El problema de la búsqueda 111
Introducción 111
Búsqueda recursiva desde el final del arreglo 111
Búsqueda recursiva desde el principio del arreglo
incrementando el índice de búsqueda en uno
hasta llegar a su final 113
Búsqueda binaria en un arreglo no ordenado 114
Búsqueda binaria en un arreglo ordenado ascendentemente 116
El problema de los ordenamientos 119
Introducción 119
Ordenamiento por burbuja 119
Ordenamiento por intercambio 121
Ordenamiento por inserción 124
Ordenamiento rápido 125
Ordenamiento por mezcla 128
Ordenamiento por montículo 131
Programación dinámica 135
Introducción 135
Forma general 136
Problemas resueltos 137
Calcular el factorial de un número entero positivo 137
Calcular el n-ésimo término de la serie de Fibonacci 138
Cálculo del coeficiente binomial 140
Cálculo de la potencia de dos números enteros positivos 142
Calcular los factores primos de un número entero positivo 143
Ejercicios propuestos 146
Técnica de vuelta atrás o retroceso 149
Introducción 149
Forma general 150
Problemas resueltos 151
Subconjuntos de un conjunto 151
Encontrar todos los subconjuntos que sumen un valor dado 153
Hallar todas las permutaciones de un conjunto
de números enteros 155
Acomodar ocho (8) reinas en un tablero de ajedrez
de tal manera que no se ataquen unas a otras 157
El juego del sudoku 164
Ejercicios propuestos 168
Manejo de árboles binarios y grafos 171
Introducción 171
Definiciones 172
Representación 173
Representación de árboles binarios con arreglos 174
Representación de árboles con listas 176
Representación de grafos con matrices 176
Recorridos en un árbol binario 178
Recorrido en entre orden 178
Recorrido en preorden 179
Recorrido en posorden 180
Recorrido por niveles 181
Árboles binarios de búsqueda 183
Problemas resueltos con árboles y grafos 183
Cálculo de la altura de un árbol binario 183
Cálculo de la suma de los valores almacenados
en los nodos de un árbol binario 185
Cálculo del mayor elemento de un árbol binario 186
Contabilizar el número de nodos de un árbol binario 186
Determinar si un árbol binario está balanceado 187
Coloreado de mapas 188
Búsqueda de caminos en un laberinto 194
Ejercicios propuestos 199
Técnica de divide y vencerás 201
Introducción 201
Forma general 202
Problemas resueltos 202
Las torres de Hanói 202
Determinar si un valor dado está almacenado
en un árbol binario de búsqueda 205
Encontrar el máximo en un conjunto de n números 206
Dada una secuencia de n números enteros, encontrar
el máximo valor que se puede obtener al sumar elementos
consecutivos de la secuencia 209
Ejercicios propuestos 214
Referencias 215
Anexos 217
Anexo 1. Lenguaje algorítmico 217
Anexo 2. Implementación de la estructura de datos: pila 220
índice temático 223