A nuestros compañeros y alumnos

Índice

Presentación xix

Tema I Algoritmos e introducción a Pascal 1

Capı́tulo 1 Problemas, algoritmos y programas 3

1.1 Solución de problemas mediante programas . . . . . . . . . . . . 3
1.2 Concepto de algoritmo . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Una definición de algoritmo . . . . . . . . . . . . . . . . . 6
1.2.2 Una definición formal de algoritmo . . . . . . . . . . . . . 8
1.3 Aspectos de interés sobre los algoritmos . . . . . . . . . . . . . . 11
1.3.1 Computabilidad . . . . . . . . . . . . . . . . . . . . . . . 11
1.3.2 Corrección de algoritmos . . . . . . . . . . . . . . . . . . 14
1.3.3 Complejidad de algoritmos . . . . . . . . . . . . . . . . . 15
1.4 Lenguajes algorı́tmicos y de programación . . . . . . . . . . . . . 16
1.5 Desarrollo sistemático de programas . . . . . . . . . . . . . . . . 18
1.6 Conclusión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.7 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.8 Referencias bibliográficas . . . . . . . . . . . . . . . . . . . . . . 21

Capı́tulo 2 El lenguaje de programación Pascal 23

2.1 Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2 Otros detalles de interés . . . . . . . . . . . . . . . . . . . . . . . 24
2.3 Origen y evolución del lenguaje Pascal . . . . . . . . . . . . . . . 24
2.4 Pascal y Turbo Pascal . . . . . . . . . . . . . . . . . . . . . . . . 25

Capı́tulo 3 Tipos de datos básicos 27

3.1 Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
viii Índice

3.2 El tipo integer . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3.3 El tipo real . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.4 El tipo char . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.5 El tipo boolean . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.6 Observaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.7 El tipo de una expresión . . . . . . . . . . . . . . . . . . . . . . . 43
3.8 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

Capı́tulo 4 Elementos básicos del lenguaje 47

4.1 Un ejemplo introductorio . . . . . . . . . . . . . . . . . . . . . . 47
4.2 Vocabulario básico . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.2.1 Constantes y variables . . . . . . . . . . . . . . . . . . . . 52
4.3 Instrucciones básicas . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.3.1 Asignación . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.3.2 Instrucciones de escritura . . . . . . . . . . . . . . . . . . 54
4.3.3 Instrucciones de lectura . . . . . . . . . . . . . . . . . . . 57
4.4 Partes de un programa . . . . . . . . . . . . . . . . . . . . . . . . 59
4.4.1 Encabezamiento . . . . . . . . . . . . . . . . . . . . . . . 59
4.4.2 Declaraciones y definiciones . . . . . . . . . . . . . . . . . 60
4.4.3 Cuerpo del programa . . . . . . . . . . . . . . . . . . . . . 62
4.4.4 Conclusión: estructura general de un programa . . . . . . 63
4.5 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

Capı́tulo 5 Primeros programas completos 67

5.1 Algunos programas sencillos . . . . . . . . . . . . . . . . . . . . . 68
5.1.1 Dibujo de la letra ‘‘C’’ . . . . . . . . . . . . . . . . . . . . 68
5.1.2 Suma de dos números . . . . . . . . . . . . . . . . . . . . 69
5.2 Programas claros ⇒ programas de calidad . . . . . . . . . . . . . 69
5.3 Desarrollo descendente de programas . . . . . . . . . . . . . . . . 71
5.4 Desarrollo de programas correctos . . . . . . . . . . . . . . . . . 73
5.4.1 Estado de los cómputos . . . . . . . . . . . . . . . . . . . 73
5.4.2 Desarrollo descendente con especificaciones . . . . . . . . 78
5.5 Observaciones finales . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.6 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
Índice ix

Tema II Programación estructurada 83

Capı́tulo 6 Instrucciones estructuradas 85

6.1 Composición de instrucciones . . . . . . . . . . . . . . . . . . . . 86
6.2 Instrucciones de selección . . . . . . . . . . . . . . . . . . . . . . 88
6.2.1 La instrucción if-then-else . . . . . . . . . . . . . . . . . 88
6.2.2 La instrucción case . . . . . . . . . . . . . . . . . . . . . 92
6.3 Instrucciones de iteración . . . . . . . . . . . . . . . . . . . . . . 94
6.3.1 La instrucción while . . . . . . . . . . . . . . . . . . . . . 94
6.3.2 La instrucción repeat . . . . . . . . . . . . . . . . . . . . 98
6.3.3 La instrucción for . . . . . . . . . . . . . . . . . . . . . . 100
6.4 Diseño y desarrollo de bucles . . . . . . . . . . . . . . . . . . . . 103
6.4.1 Elección de instrucciones iterativas . . . . . . . . . . . . . 103
6.4.2 Terminación de un bucle . . . . . . . . . . . . . . . . . . . 105
6.4.3 Uso correcto de instrucciones estructuradas . . . . . . . . 106
6.5 Dos métodos numéricos iterativos . . . . . . . . . . . . . . . . . . 113
6.5.1 Método de bipartición . . . . . . . . . . . . . . . . . . . . 113
6.5.2 Método de Newton-Raphson . . . . . . . . . . . . . . . . 115
6.5.3 Inversión de funciones . . . . . . . . . . . . . . . . . . . . 117
6.6 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

Capı́tulo 7 Programación estructurada 123

7.1 Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
7.2 Aspectos teóricos . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
7.2.1 Programas y diagramas de flujo . . . . . . . . . . . . . . . 125
7.2.2 Diagramas y diagramas propios . . . . . . . . . . . . . . . 126
7.2.3 Diagramas BJ (de Böhm y Jacopini) . . . . . . . . . . . . 130
7.2.4 Equivalencia de diagramas . . . . . . . . . . . . . . . . . . 135
7.2.5 Teoremas de la programación estructurada . . . . . . . . 137
7.2.6 Recapitulación . . . . . . . . . . . . . . . . . . . . . . . . 138
7.3 Aspectos metodológicos . . . . . . . . . . . . . . . . . . . . . . . 139
7.3.1 Seudocódigo . . . . . . . . . . . . . . . . . . . . . . . . . . 139
7.3.2 Diseño descendente . . . . . . . . . . . . . . . . . . . . . . 141
7.4 Refinamiento correcto de programas con instrucciones
estructuradas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
x Índice

7.4.1 Un ejemplo detallado . . . . . . . . . . . . . . . . . . . . 147

7.4.2 Recapitulación . . . . . . . . . . . . . . . . . . . . . . . . 150
7.5 Conclusión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
7.6 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
7.7 Referencias bibliográficas . . . . . . . . . . . . . . . . . . . . . . 153

Tema III Subprogramas 155

Capı́tulo 8 Procedimientos y funciones 157

8.1 Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
8.2 Subprogramas con parámetros . . . . . . . . . . . . . . . . . . . . 162
8.2.1 Descripción de un subprograma con parámetros . . . . . . 162
8.2.2 Parámetros formales y reales . . . . . . . . . . . . . . . . 165
8.2.3 Mecanismos de paso de parámetros . . . . . . . . . . . . . 165
8.2.4 Consistencia entre definición y llamada . . . . . . . . . . 168
8.3 Estructura sintáctica de un subprograma . . . . . . . . . . . . . . 169
8.4 Funcionamiento de una llamada . . . . . . . . . . . . . . . . . . . 170
8.5 Ámbito y visibilidad de los identificadores . . . . . . . . . . . . . 174
8.5.1 Tipos de identificadores según su ámbito . . . . . . . . . . 174
8.5.2 Estructura de bloques . . . . . . . . . . . . . . . . . . . . 175
8.5.3 Criterios de localidad . . . . . . . . . . . . . . . . . . . . 181
8.5.4 Efectos laterales . . . . . . . . . . . . . . . . . . . . . . . 181
8.6 Otras recomendaciones sobre el uso de parámetros . . . . . . . . 183
8.6.1 Parámetros por valor y por referencia . . . . . . . . . . . 183
8.6.2 Parámetros por referencia y funciones . . . . . . . . . . . 183
8.6.3 Funciones con resultados múltiples . . . . . . . . . . . . . 184
8.7 Desarrollo correcto de subprogramas . . . . . . . . . . . . . . . . 184
8.8 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186

Capı́tulo 9 Aspectos metodológicos de la programación con

subprogramas 189
9.1 Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
9.2 Un ejemplo de referencia . . . . . . . . . . . . . . . . . . . . . . . 190
9.3 Metodologı́a de la programación con subprogramas . . . . . . . . 192
9.3.1 Diseño descendente con subprogramas . . . . . . . . . . . 193
Índice xi

9.3.2 Programa principal y subprogramas . . . . . . . . . . . . 194

9.3.3 Documentación de los subprogramas . . . . . . . . . . . . 195
9.3.4 Tamaño de los subprogramas . . . . . . . . . . . . . . . . 196
9.3.5 Refinamiento con subprogramas y con instrucciones
estructuradas . . . . . . . . . . . . . . . . . . . . . . . . . 197
9.4 Estructura jerárquica de los subprogramas . . . . . . . . . . . . . 199
9.5 Ventajas de la programación con subprogramas . . . . . . . . . . 201
9.6 Un ejemplo detallado: representación de funciones . . . . . . . . 203
9.7 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207

Capı́tulo 10 Introducción a la recursión 211

10.1 Un ejemplo de referencia . . . . . . . . . . . . . . . . . . . . . . . 212
10.2 Conceptos básicos . . . . . . . . . . . . . . . . . . . . . . . . . . 213
10.3 Otros ejemplos recursivos . . . . . . . . . . . . . . . . . . . . . . 216
10.3.1 La sucesión de Fibonacci . . . . . . . . . . . . . . . . . . 216
10.3.2 Torres de Hanoi . . . . . . . . . . . . . . . . . . . . . . . 216
10.3.3 Función de Ackermann . . . . . . . . . . . . . . . . . . . . 219
10.4 Corrección de subprogramas recursivos . . . . . . . . . . . . . . . 219
10.4.1 Principios de inducción . . . . . . . . . . . . . . . . . . . 220
10.5 Recursión mutua . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
10.6 Recursión e iteración . . . . . . . . . . . . . . . . . . . . . . . . . 226
10.7 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
10.8 Referencias bibliográficas . . . . . . . . . . . . . . . . . . . . . . 228

Tema IV Tipos de datos definidos por el programador 231

Capı́tulo 11 Tipos de datos simples y compuestos 233

11.1 Tipos ordinales definidos por el programador . . . . . . . . . . . 234
11.1.1 Tipos enumerados . . . . . . . . . . . . . . . . . . . . . . 235
11.1.2 Tipo subrango . . . . . . . . . . . . . . . . . . . . . . . . 238
11.2 Definición de tipos . . . . . . . . . . . . . . . . . . . . . . . . . . 240
11.2.1 Observaciones sobre la definición de tipos . . . . . . . . . 242
11.3 Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
11.3.1 Operaciones sobre el tipo conjunto . . . . . . . . . . . . . 245
11.3.2 Observaciones sobre el tipo conjunto . . . . . . . . . . . . 247
xii Índice

11.3.3 Un ejemplo de aplicación . . . . . . . . . . . . . . . . . . 248

11.4 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250

Capı́tulo 12 Arrays 253

12.1 Descripción del tipo de datos array . . . . . . . . . . . . . . . . . 253
12.1.1 Operaciones del tipo array y acceso a sus componentes . . 257
12.1.2 Caracterı́sticas generales de un array . . . . . . . . . . . . 260
12.2 Vectores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
12.3 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
12.4 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268

Capı́tulo 13 Registros 271

13.1 Descripción del tipo de datos registro . . . . . . . . . . . . . . . . 271
13.1.1 Manejo de registros: acceso a componentes y operaciones . 273
13.1.2 Registros con variantes . . . . . . . . . . . . . . . . . . . . 276
13.2 Arrays de registros y registros de arrays . . . . . . . . . . . . . . 279
13.3 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282

Capı́tulo 14 Archivos 285

14.1 Descripción del tipo de datos archivo . . . . . . . . . . . . . . . . 285
14.2 Manejo de archivos en Pascal . . . . . . . . . . . . . . . . . . . . 286
14.2.1 Operaciones con archivos . . . . . . . . . . . . . . . . . . 288
14.3 Archivos de texto . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
14.4 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298

Capı́tulo 15 Algoritmos de búsqueda y ordenación 301

15.1 Algoritmos de búsqueda en arrays . . . . . . . . . . . . . . . . . 301
15.1.1 Búsqueda secuencial . . . . . . . . . . . . . . . . . . . . . 302
15.1.2 Búsqueda secuencial ordenada . . . . . . . . . . . . . . . 304
15.1.3 Búsqueda binaria . . . . . . . . . . . . . . . . . . . . . . . 304
15.2 Ordenación de arrays . . . . . . . . . . . . . . . . . . . . . . . . . 306
15.2.1 Selección directa . . . . . . . . . . . . . . . . . . . . . . . 307
15.2.2 Inserción directa . . . . . . . . . . . . . . . . . . . . . . . 309
15.2.3 Intercambio directo . . . . . . . . . . . . . . . . . . . . . . 310
15.2.4 Ordenación rápida (Quick Sort) . . . . . . . . . . . . . . 312
15.2.5 Ordenación por mezcla (Merge Sort) . . . . . . . . . . . . 316
Índice xiii

15.2.6 Vectores paralelos . . . . . . . . . . . . . . . . . . . . . . 318

15.3 Algoritmos de búsqueda en archivos secuenciales . . . . . . . . . 320
15.3.1 Búsqueda en archivos arbitrarios . . . . . . . . . . . . . . 321
15.3.2 Búsqueda en archivos ordenados . . . . . . . . . . . . . . 321
15.4 Mezcla y ordenación de archivos secuenciales . . . . . . . . . . . 322
15.5 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
15.6 Referencias bibliográficas . . . . . . . . . . . . . . . . . . . . . . 330

Tema V Memoria dinámica 333

Capı́tulo 16 Punteros 335

16.1 Introducción al uso de punteros . . . . . . . . . . . . . . . . . . . 336
16.1.1 Definición y declaración de punteros . . . . . . . . . . . . 337
16.1.2 Generación y destrucción de variables dinámicas . . . . . 338
16.1.3 Operaciones básicas con datos apuntados . . . . . . . . . 339
16.1.4 Operaciones básicas con punteros . . . . . . . . . . . . . . 341
16.1.5 El valor nil . . . . . . . . . . . . . . . . . . . . . . . . . . 343
16.2 Aplicaciones no recursivas de los punteros . . . . . . . . . . . . . 344
16.2.1 Asignación de objetos no simples . . . . . . . . . . . . . . 345
16.2.2 Funciones de resultado no simple . . . . . . . . . . . . . . 346
16.3 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348

Capı́tulo 17 Estructuras de datos recursivas 351

17.1 Estructuras recursivas lineales: las listas enlazadas . . . . . . . . 351
17.1.1 Una definición del tipo lista . . . . . . . . . . . . . . . . . 352
17.1.2 Inserción de elementos . . . . . . . . . . . . . . . . . . . . 353
17.1.3 Eliminación de elementos . . . . . . . . . . . . . . . . . . 355
17.1.4 Algunas funciones recursivas . . . . . . . . . . . . . . . . 355
17.1.5 Otras operaciones sobre listas . . . . . . . . . . . . . . . . 358
17.2 Pilas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362
17.2.1 Definición de una pila como lista enlazada . . . . . . . . . 363
17.2.2 Operaciones básicas sobre las pilas . . . . . . . . . . . . . 363
17.2.3 Aplicaciones . . . . . . . . . . . . . . . . . . . . . . . . . . 365
17.3 Colas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370
17.3.1 Definición del tipo cola . . . . . . . . . . . . . . . . . . . 371
xiv Índice

17.3.2 Operaciones básicas . . . . . . . . . . . . . . . . . . . . . 371

17.3.3 Aplicación: gestión de la caja de un supermercado . . . . 374
17.4 Árboles binarios . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
17.4.1 Recorrido de un árbol binario . . . . . . . . . . . . . . . . 378
17.4.2 Árboles de búsqueda . . . . . . . . . . . . . . . . . . . . . 379
17.4.3 Aplicaciones . . . . . . . . . . . . . . . . . . . . . . . . . . 383
17.5 Otras estructuras dinámicas de datos . . . . . . . . . . . . . . . . 387
17.6 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389
17.7 Referencias bibliográficas . . . . . . . . . . . . . . . . . . . . . . 391

Tema VI Aspectos avanzados de programación 393

Capı́tulo 18 Complejidad algorı́tmica 395

18.1 Conceptos básicos . . . . . . . . . . . . . . . . . . . . . . . . . . 396
18.2 Medidas del comportamiento asintótico . . . . . . . . . . . . . . 402
18.2.1 Comportamiento asintótico . . . . . . . . . . . . . . . . . 402
18.2.2 Notación O mayúscula (una cota superior) . . . . . . . . 404
18.2.3 Notación Ω mayúscula (una cota inferior) . . . . . . . . . 405
18.2.4 Notación Θ mayúscula (orden de una función) . . . . . . 405
18.2.5 Propiedades de O, Ω y Θ . . . . . . . . . . . . . . . . . . 406
18.2.6 Jerarquı́a de órdenes de frecuente aparición . . . . . . . . 407
18.3 Reglas prácticas para hallar el coste de un programa . . . . . . . 408
18.3.1 Tiempo empleado . . . . . . . . . . . . . . . . . . . . . . 408
18.3.2 Ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . 411
18.3.3 Espacio de memoria empleado . . . . . . . . . . . . . . . 417
18.4 Útiles matemáticos . . . . . . . . . . . . . . . . . . . . . . . . . . 418
18.4.1 Fórmulas con sumatorios . . . . . . . . . . . . . . . . . . 419
18.4.2 Sucesiones de recurrencia lineales de primer orden . . . . 419
18.4.3 Sucesiones de recurrencia de orden superior . . . . . . . . 421
18.5 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422
18.6 Referencias bibliográficas . . . . . . . . . . . . . . . . . . . . . . 425

Capı́tulo 19 Tipos abstractos de datos 427

19.1 Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428
19.2 Un ejemplo completo . . . . . . . . . . . . . . . . . . . . . . . . . 429
Índice xv

19.2.1 Desarrollo de programas con tipos concretos de datos . . 430

19.2.2 Desarrollo de programas con tipos abstractos de datos . . 431
19.2.3 Desarrollo de tipos abstractos de datos . . . . . . . . . . . 434
19.3 Metodologı́a de la programación de TADs . . . . . . . . . . . . . 440
19.3.1 Especificación de tipos abstractos de datos . . . . . . . . 440
19.3.2 Implementación de tipos abstractos de datos . . . . . . . 441
19.3.3 Corrección de tipos abstractos de datos . . . . . . . . . . 443
19.4 Resumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446
19.5 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447
19.6 Referencias bibliográficas . . . . . . . . . . . . . . . . . . . . . . 448

Capı́tulo 20 Esquemas algorı́tmicos fundamentales 449

20.1 Algoritmos devoradores . . . . . . . . . . . . . . . . . . . . . . . 450
20.1.1 Descripción . . . . . . . . . . . . . . . . . . . . . . . . . . 450
20.1.2 Adecuación al problema . . . . . . . . . . . . . . . . . . . 451
20.1.3 Otros problemas resueltos vorazmente . . . . . . . . . . . 452
20.2 Divide y vencerás . . . . . . . . . . . . . . . . . . . . . . . . . . . 453
20.2.1 Equilibrado de los subproblemas . . . . . . . . . . . . . . 454
20.3 Programación dinámica . . . . . . . . . . . . . . . . . . . . . . . 455
20.3.1 Problemas de programación dinámica . . . . . . . . . . . 455
20.3.2 Mejora de este esquema . . . . . . . . . . . . . . . . . . . 457
20.3.3 Formulación de problemas de programación dinámica . . 460
20.4 Vuelta atrás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462
20.4.1 Mejora del esquema de vuelta atrás . . . . . . . . . . . . 466
20.5 Anexo: algoritmos probabilistas . . . . . . . . . . . . . . . . . . . 468
20.5.1 Búsqueda de una solución aproximada . . . . . . . . . . . 468
20.5.2 Búsqueda de una solución probablemente correcta . . . . 469
20.6 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470
20.7 Referencias bibliográficas . . . . . . . . . . . . . . . . . . . . . . 473

Apéndices 475

Apéndice A Aspectos complementarios de la programación 477

A.1 Subprogramas como parámetros . . . . . . . . . . . . . . . . . . . 477
A.1.1 Ejemplo 1: derivada . . . . . . . . . . . . . . . . . . . . . 479
xvi Índice

A.1.2 Ejemplo 2: bipartición . . . . . . . . . . . . . . . . . . . . 480

A.1.3 Ejemplo 3: transformación de listas . . . . . . . . . . . . 482
A.2 Variables aleatorias . . . . . . . . . . . . . . . . . . . . . . . . . . 482
A.2.1 Generación de números aleatorios en Turbo Pascal . . . . 483
A.2.2 Simulación de variables aleatorias . . . . . . . . . . . . . . 484
A.2.3 Ejemplos de aplicación . . . . . . . . . . . . . . . . . . . . 486
A.3 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488
A.4 Referencias bibliográficas . . . . . . . . . . . . . . . . . . . . . . 490

Apéndice B El lenguaje Turbo Pascal 491

B.1 Elementos léxicos . . . . . . . . . . . . . . . . . . . . . . . . . . . 492
B.2 Estructura del programa . . . . . . . . . . . . . . . . . . . . . . . 492
B.3 Datos numéricos enteros . . . . . . . . . . . . . . . . . . . . . . . 492
B.4 Datos numéricos reales . . . . . . . . . . . . . . . . . . . . . . . . 493
B.5 Cadenas de caracteres . . . . . . . . . . . . . . . . . . . . . . . . 494
B.5.1 Declaración de cadenas . . . . . . . . . . . . . . . . . . . 494
B.5.2 Operadores de cadenas . . . . . . . . . . . . . . . . . . . . 495
B.5.3 Funciones de cadenas . . . . . . . . . . . . . . . . . . . . 496
B.5.4 Procedimientos de cadenas . . . . . . . . . . . . . . . . . 496
B.6 Tipos de datos estructurados . . . . . . . . . . . . . . . . . . . . 498
B.7 Instrucciones estructuradas . . . . . . . . . . . . . . . . . . . . . 498
B.8 Paso de subprogramas como parámetros . . . . . . . . . . . . . . 499
B.9 Archivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 500
B.10 Memoria dinámica . . . . . . . . . . . . . . . . . . . . . . . . . . 501
B.11 Unidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501
B.11.1 Unidades predefinidas de Turbo Pascal . . . . . . . . . . . 502
B.11.2 Unidades definidas por el usuario . . . . . . . . . . . . . . 503
B.11.3 Modularidad incompleta de Turbo Pascal . . . . . . . . . 505

Apéndice C El entorno integrado de desarrollo 507

C.1 Descripción del entorno . . . . . . . . . . . . . . . . . . . . . . . 507
C.2 Desarrollo completo de un programa en Turbo Pascal . . . . . . 508
C.2.1 Arranque del entorno . . . . . . . . . . . . . . . . . . . . 508
C.2.2 Edición del programa fuente . . . . . . . . . . . . . . . . . 510
C.2.3 Grabar el programa fuente y seguir editando . . . . . . . 510
Índice xvii

C.2.4 Compilación . . . . . . . . . . . . . . . . . . . . . . . . . 512

C.2.5 Ejecución . . . . . . . . . . . . . . . . . . . . . . . . . . . 514
C.2.6 Depuración . . . . . . . . . . . . . . . . . . . . . . . . . . 514
C.2.7 Salida de Turbo Pascal . . . . . . . . . . . . . . . . . . . . 516
C.3 Otros menús y opciones . . . . . . . . . . . . . . . . . . . . . . . 517
C.3.1 Search (Búsqueda) . . . . . . . . . . . . . . . . . . . . . . 517
C.3.2 Tools (Herramientas) . . . . . . . . . . . . . . . . . . . . . 517
C.3.3 Options (Opciones) . . . . . . . . . . . . . . . . . . . . . . 517
C.3.4 Window (Ventana) . . . . . . . . . . . . . . . . . . . . . . 519
C.3.5 Help (Ayuda) . . . . . . . . . . . . . . . . . . . . . . . . . 519
C.4 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519
C.5 Referencias bibliográficas . . . . . . . . . . . . . . . . . . . . . . 520

Bibliografı́a 521

Índice alfabético 527

Presentación

Este libro trata sobre métodos de resolución de problemas mediante el desa-

rrollo de algoritmos y estructuras de datos, desde el principio y paso a paso, y
su materialización en programas de computador.
Desde luego, no es el primer libro sobre este tema; de hecho, ha habido
en los últimos quince años un gran aluvión de textos sobre algoritmos y sobre
programación. La razón para ello ha sido sin lugar a dudas doble: por un
lado, la difusión que estos temas han tenido y siguen teniendo, integrándose
en los estudios más diversos; por otro, la evolución que está experimentando el
desarrollo de algoritmos y programas, pasando de ser un arte (reinventado por
cada programador a base de técnicas personales, estrechamente vinculadas con
su lenguaje de programación) a una actividad más cientı́fica, metodológica y
disciplinada.
Por consiguiente, resulta necesario aclarar cuál es el enfoque adoptado en este
libro. Examinando la bibliografı́a existente actualmente sobre programación a
un nivel introductorio permite afirmar las siguientes conclusiones:
• Una parte importante de los libros existentes han adoptado un enfoque
práctico puro, no metodológico, que es el más tradicional, y aún subsiste
en demasiados libros. Se confunde la enseñanza de la programación con
la de un lenguaje concreto, ofreciendo muchas veces un mero “manual
de referencia” del lenguaje elegido. Bajo el atractivo de los llamativos
resultados inmediatos (programas que funcionan), este enfoque ignora la
base conceptual y metodológica necesaria, y propicia los peores hábitos de
programación, que son además difı́ciles de erradicar.
• Otra postura extrema se centra en el análisis y desarrollo de soluciones
algorı́tmicas puras, de forma independiente de cualquier lenguaje de pro-
gramación. Esta independencia permite ignorar las peculiaridades de los
lenguajes reales, yendo a los conceptos; sin embargo, esa independencia de
los lenguajes de programación es a nuestro entender innecesaria e inconve-
niente en los primeros pasos, ya que obliga al aprendiz de la programación
a estudiar aparte los detalles concretos del lenguaje de programación con
que necesariamente debe desarrollar sus prácticas.
xx Presentación

En cambio, encontramos este enfoque interesante en niveles superiores de

la enseñanza de la programación, donde interesa concentrarse en los con-
ceptos, más difı́ciles y donde ya no supone obstáculo alguno expresar las
ideas en cualquier lenguaje de programación.

El enfoque adoptado en este libro recoge ambos aspectos: por un lado, viene a
cubrir la necesidad de un enfoque metodológico en el aprendizaje y en el ejercicio
de la programación, pero también la necesidad de experimentar con programas
concretos, expresarlos en un lenguaje real y hacerlos funcionar con un traduc-
tor concreto. En resumen, intentamos compaginar las ventajas de los enfoques
anteriores, presentando la base conceptual y metodológica necesaria para desa-
rrollar los algoritmos de forma razonada y disciplinada, sin olvidar por ello la
conveniencia de expresarlos en un lenguaje de programación, materializándolos
y experimentando con ellos, y que el lector ha de ser instruido también en esta
tarea.
En relación con el enfoque metodológico que se impone actualmente, se con-
sidera necesario atender a la corrección de los programas. El tratamiento que
se le da en la literatura ha llevado nuevamente a dos posturas artificialmente
extremas:

• Algunos autores ignoran completamente el estudio de la corrección, con-

tentándose con algunas comprobaciones para deducir que un programa es
correcto.

• En cambio, otros adoptan un tratamiento exhaustivo, utilizando técnicas

formales de especificación o verificación.

A nuestro entender, es incuestionable la importancia de garantizar que los

programas desarrollados funcionarán de la forma deseada. Sin embargo, la ve-
rificación formal de los programas de cierto tamaño es impracticable. Por ello,
asumimos de nuevo una posición intermedia y realista consistente en los siguien-
tes planteamientos:

• Plantear el desarrollo de programas correctos con el empleo de técnicas

semiformales.

• Limitar el estudio de la corrección a los elementos que resulten delicados,

bien por su dificultad o por su novedad.

• Atender a la corrección de los algoritmos durante su desarrollo en lugar de

a posteriori. Esta idea resulta ser una ayuda esencial en el aprendizaje de
la programación.
Presentación xxi

En resumidas cuentas, este libro va dirigido a aquéllos que desean introdu-

cirse en la programación, con una base sólida, con una buena metodogı́a de
diseño y desarrollo de programas correctos y con hábitos disciplinados desde una
perspectiva realista y pragmática. Se presentan las técnicas con un cierto ni-
vel de abstracción para identificar los conceptos esenciales e independientes del
lenguaje de programación empleado, y al mismo tiempo se aterriza expresando
estas técnicas en un lenguaje concreto.
El lenguaje escogido para estas implementaciones ha sido Pascal. Esta elec-
ción se debe a que este lenguaje es simple y tiene una sintaxis sencilla, que
hace que sea fácil de aprender, y al mismo tiempo es lo bastante completo como
para plasmar las diferentes técnicas y métodos necesarios en programas de com-
plejidad media-alta. Esto lo hace una herramienta pedagógica idónea para el
aprendizaje de la programación. A todo esto hay que sumar las numerosas im-
plementaciones existentes y su accesibilidad, ası́ como su evolución y continua
puesta al dı́a para permitir técnicas de programación actuales (por ejemplo, mo-
dular u orientada a los objetos) y su gran difusión y aceptación en el ámbito
académico.

Organización del libro

El libro está estructurado en siete partes. En cada una de ellas se estudian

las técnicas y mecanismos nuevos, conceptualmente primero, detallando luego
su tratamiento en Pascal y, finalmente, compaginando ambas facetas con el as-
pecto metodológico. Cada tema se ha dividido en varios capı́tulos para evitar
una excesiva fragmentación. En cada capı́tulo se ha incluido una lista de ejerci-
cios propuestos de dificultad aproximadamente creciente. Al final de cada tema
se desarrolla un ejemplo completo pensado para mostrar a la vez los aspectos
más destacados del mismo, ası́ como unas pocas referencias comentadas que se
sugieren como lecturas complementarias o de consulta.

Contenido

El contenido se ha seleccionado partiendo de las directrices señaladas en

[DCG+ 89] y [Tur91]. Incluye los contenidos cursos CS1 y CS2 [GT86, KSW85]
salvo los aspectos de organización de computadores, que se estudian en [PAO94],
de los mismos autores que este libro.
En el primer tema se presentan, entre otros, los conceptos esenciales de algo-
ritmo, dato y programa. Se introduce el lenguaje Pascal y la estructura de los
programas escritos en él, ası́ como los elementos básicos del lenguaje. Se incluyen
xxii Presentación

algunos programas sencillos, y se adelantan la técnica descendente de diseño de

programas y algunos apuntes sobre la corrección.
El segundo tema se dedica a la programación estructurada. Se pone espe-
cial énfasis en el diseño descendente o por refinamientos sucesivos partiendo de
especificaciones escritas en pseudocódigo, y se muestra cómo compaginar esta
técnica con la derivación de programas correctos.
En el tercer tema se estudian los subprogramas. Al igual que en el tema
anterior, se detalla cómo enfocar la corrección en el uso de esta técnica. Se
concluye con un capı́tulo de introducción a la recursión.
En la mayorı́a de los programas no basta con los tipos de datos básicos, sino
que es necesario que el programador defina otros más complejos. A ello se dedica
el cuarto tema.
El quinto tema estudia las técnicas propias de la gestión de memoria dinámica.
Se justifica su necesidad, y se presenta su principal aplicación, que es la definición
de estructuras de datos recursivas.
El sexto tema introduce tres aspectos avanzados: la programación con tipos
abstractos de datos, el coste de los algoritmos y los principales esquemas de
diseño de algoritmos. Aunque, ciertamente, su estudio en profundidad rebasa un
primer curso, es frecuente introducir –o siquiera mencionar– sus ideas básicas.
Por supuesto, siempre es altamente recomendable consultar otras referencias
(nosotros mismos las seleccionamos para cada tema), pero también es cierto
que el alumno se ve obligado con frecuencia a usar varios textos básicos para
cubrir diferentes partes de la materia. Justamente, estos últimos capı́tulos se
incluyen para que el lector interesado se pueda asomar a ellos sin verse obligado
a consultar los capı́tulos introductorios de otros libros.
Finalmente se incluyen tres apéndices: en el primero se introducen un par
de aspectos complementarios para un primer curso de programación (el paso
de subprogramas como parámetros y el uso de variables aleatorias); el segundo
es un prontuario de uso del entorno integrado de desarrollo Turbo Pascal; y el
tercero indica algunos detalles de Turbo Pascal en que se separa del estándar,
pero que son de uso frecuente.

Notación empleada
En la lectura de este texto se encontrarán fragmentos escritos en distintos
lenguajes:

• En castellano puro, donde se ha usado este tipo de letra.

• En Pascal, para lo que se ha elegido el teletipo, salvo las palabras reser-

vadas, que van en negrita.
Presentación xxiii

También se ha empleado el teletipo para indicar las salidas y entradas de

datos, porque es el tipo de letra más parecido al que aparece en el monitor.

• En seudocódigo, que se expresa con letra cursiva.

• En lenguaje matemático, en que se usan los sı́mbolos usuales.

• Otros sı́mbolos especiales:

à El espacio en blanco (véase la página 206)

; Uno o más pasos al evaluar una expresión (véase la página 30)
• Fin de archivo (véase la página 57)
← Fin de lı́nea (véase la página 57)

Advertencia para el alumno

No existe un método general para resolver problemas mediante algoritmos;
por ello, es de gran importancia estudiar las técnicas de forma gradual, yendo
de lo fácil a lo difı́cil y vinculándolas con situaciones ampliamente conocidas.
Nosotros pretendemos haber cumplido con este objetivo, proporcionando
ejemplos de fácil comprensión y ejercicios a la medida de lo explicado. Y eso es
lo bueno. Lo malo es que el alumno puede percibir la sensación de comprenderlo
todo a la velocidad que lee. . . y aquı́ reside el peligro. Porque una mera lectura
del texto, o incluso una lectura atenta, no basta para asimilarlo, adquiriendo las
técnicas necesarias para resolver otros problemas de dificultad similar a la de los
planteados. Es preciso adoptar una actitud crı́tica durante la lectura, trabajar
minuciosamente con los problemas propuestos e incluso tatar de imaginar solu-
ciones alternativas a los ejemplos dados. Y cuanto antes se acepte esa realidad,
mejor que mejor.

Agradecimientos
Muchas personas han contribuido de diferentes maneras a que este libro sea
lo que es. En primer lugar, debemos a nuestros alumnos de estos años su ayuda,
aun sin saberlo, porque ellos han sido la razón de que emprendiéramos este
trabajo, y porque sus preguntas y comentarios, dı́a a dı́a, tienen una respuesta
en las páginas que siguen. En segundo lugar, debemos a muchos de nuestros
compañeros su aliento y apoyo, tan necesario cuando uno se enfrenta a un trabajo
de esta envergadura. Y por ello, lo dedicamos a ambos, alumnos y compañeros.
De un modo muy especial, deseamos expresar nuestro agradecimiento a Juan
Falgueras Cano, Luis Antonio Galán Corroto y Yolanda Ortega y Mallén por
su cuidadosa lectura de la primera versión completa del manuscrito, y por sus
xxiv Presentación

valiosos comentarios y sugerencias. No podemos olvidar tampoco la ayuda de

Manuel Enciso Garcı́a-Oliveros en los últimos retoques, ası́ como su proximidad
y apoyo durante todo el tiempo que nos ha ocupado este trabajo.
Por último, deseamos expresar nuestra gratitud y cariño a José Luis Galán
Garcı́a, que ha dejado en este libro muchas horas.
 Tema I

Algoritmos e introducción a
Pascal
Capı́tulo 1

Problemas, algoritmos y programas

1.1 Solución de problemas mediante programas . . . . . . 3

1.2 Concepto de algoritmo . . . . . . . . . . . . . . . . . . . 5
1.3 Aspectos de interés sobre los algoritmos . . . . . . . . 11
1.4 Lenguajes algorı́tmicos y de programación . . . . . . . 16
1.5 Desarrollo sistemático de programas . . . . . . . . . . 18
1.6 Conclusión . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.7 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.8 Referencias bibliográficas . . . . . . . . . . . . . . . . . . 21

En este primer capı́tulo se trata la resolución de problemas por medio de

un computador. Puesto que éste no es más que un mero ejecutor de tareas, es
fundamental conocer un método de resolución del problema en cuestión, esto
es, un algoritmo. La escritura de este algoritmo como un conjunto de órdenes
comprensibles por el computador es lo que se llama programa.

1.1 Solución de problemas mediante programas

Los computadores desempeñan una gran variedad de tareas, liberando ası́

al hombre de tener que realizarlas personalmente. Para ello, es preciso enseñar
al computador cuál es su trabajo y cómo llevarlo a cabo, esto es, programarlo,
4 Capı́tulo 1. Problemas, algoritmos y programas

dándole instrucciones precisas (programas) en un lenguaje que comprenda (Pas-

cal, Modula-2, C, etc.). Una vez “aprendido” el programa, el computador seguirá
ciegamente sus instrucciones cuantas veces sea requerido.
Precisamente, la tarea de la programación consiste en describir lo que debe
hacer el computador para resolver un problema concreto en un lenguaje de pro-
gramación. Sin embargo, el programa es solamente el resultado de una serie de
etapas que no se pueden pasar por alto. Hablando en términos muy amplios, se
identifican de momento las siguientes fases:

1. Análisis del problema, estableciendo con precisión lo que se plantea.

2. Solución conceptual del problema, describiendo un método (algoritmo) que

lo resuelva.

3. Escritura del algoritmo en un lenguaje de programación.

En la primera fase es corriente partir de un problema definido vagamente, y

el análisis del mismo consiste en precisar el enunciado, identificando los datos
de partida y los resultados que se desean obtener. La descripción precisa de un
problema se llama especificación. Con frecuencia, el lenguaje natural no basta
para lograr la precisión deseada, por lo que se recurre en mayor o menor medida
a lenguajes formales, como la lógica o las matemáticas. Supongamos por ejemplo
que se plantea el problema de dividir dos números. En primer lugar, se necesita
saber si se trata de la división entera o de aproximar el resultado con decimales
y, en ese caso, hasta dónde. Pongamos por caso que interesa la división euclı́dea.
Una descripción precisa deberá tener en cuenta que los datos son dos enteros
(llamémosles dividendo y divisor, como es usual), de los que el segundo es no
nulo. El resultado es también un par de enteros (llamémosles cociente y resto,
como siempre) tales que

dividendo = divisor ∗ cociente + resto

Pero eso no es todo: si nos contentamos con ese enunciado, para todo par de
enteros (dividendo, divisor), el par (0, dividendo) siempre es una solución. Por
eso, hay que añadir que resto debe ser además tal que 0 ≤ resto < divisor.
Con este pequeño ejemplo se pretende resaltar la importancia de analizar
bien el problema planteado, definiendo con precisión los requisitos que deben
verificar los datos y las condiciones en que deben estar los resultados.
Sin embargo, en esta fase sólo se ha estudiado qué se desea obtener, y no
cómo lograrlo. Éste es el cometido de la segunda etapa: describir un método
(algoritmo) tal que partiendo de datos apropiados lleve sistemáticamente a los re-
sultados descritos en la especificación. Del concepto de algoritmo nos ocupamos
1.2. Concepto de algoritmo 5

1 2 3
¿Está abierto el Esperar
Principio
plazo de matrı́cula? a mañana
→2
sı́ → 4 no → 3 →2
4 5 6
Comprar impresos Leer instrucciones. Preguntar dudas
de matriculación ¿Tengo alguna duda? en Secretarı́a
→5 sı́ → 6 no → 7 →7
7 8 9
Rellenar el sobre
Entregar el sobre
y pagar en el banco Fin
→9
→8

Figura 1.1.

en el siguiente apartado. Es evidente que sólo se puede confiar en un algoritmo

si ha superado con éxito determinado control de calidad: la primera e inexcusa-
ble exigencia es que sea correcto; esto es, que resuelva el problema especificado.
Cuando un problema admita varios algoritmos como solución, convendrá dispo-
ner de criterios para escoger; y cuando un problema no tenga solución, no resulta
sensato buscar un algoritmo para resolverlo. Estos aspectos los estudiamos en el
apartado 1.3.
Finalmente, para que un computador resuelva problemas hay que escribir el
algoritmo en un lenguaje de programación; de ello hablaremos en el apartado
1.4.

1.2 Concepto de algoritmo

Los conceptos de algoritmo y de método son parecidos: los métodos para
efectuar procesos forman parte de las costumbres o rutinas que el hombre aprende
un dı́a y luego repite de manera inconsciente, sin reparar ya en las acciones, más
sencillas, que integran el proceso (por ejemplo andar, leer o conducir). Por eso
el concepto de algoritmo suele compararse a otros como método o rutina de
acciones.
La secuencia de pasos de la figura 1.1 describe un método para efectuar la
matrı́cula en la universidad.
Sin embargo, el término “algoritmo” tiene connotaciones más formales que
cualquier otro debido a su origen: se trata de una acomodación al castellano del
6 Capı́tulo 1. Problemas, algoritmos y programas

nombre de [Link] ibn Mūsā al-Jwārı̄zmı̄, matemático persa que popularizó

su descripción de las cuatro reglas (algoritmos) de sumar, restar, multiplicar y
dividir.

1.2.1 Una definición de algoritmo

Hablando informalmente, un algoritmo es la descripción precisa de los pasos

que nos llevan a la solución de un problema planteado. Estos pasos son, en gene-
ral, acciones u operaciones que se efectúan sobre ciertos objetos. La descripción
de un algoritmo afecta a tres partes: entrada (datos), proceso (instrucciones)
y salida (resultados).1 En este sentido, un algoritmo se puede comparar a una
función matemática:

+ : ZZ × ZZ −→ ZZ
(algoritmo) (entrada) (proceso) (salida)

Incluso en algoritmos no matemáticos es fácil identificar las tres partes: entra-

da, proceso y salida. Ası́ ocurre, por ejemplo, en las instrucciones para hacer la
declaración de la renta.

Caracterı́sticas de los algoritmos

La descripción de algoritmo que se ha dado es algo imprecisa. Una caracte-

rización más completa deberı́a incluir además los siguientes requisitos:

1. Precisión
Un algoritmo debe expresarse de forma no ambigua. La precisión afecta
por igual a dos aspectos:

(a) Al orden (encadenamiento o concatenación) de los pasos que han de

llevarse a cabo.
(b) Al contenido de las mismas, pues cada paso debe “saberse realizar”
con toda precisión, de forma automática.

Por lo tanto, una receta de cocina puede ser considerada como un método,
pero carece de la precisión que requieren los algoritmos debido al uso de
expresiones como añadir una pizca de sal, porque ¿qué debe entenderse por
una pizca?
1
Es habitual llamar “datos” a la entrada y “resultados” a la salida, aunque el concepto de dato
es más amplio, y abarca a toda la información que maneja un algoritmo, ya sea inicialmente o a
su término, ası́ como también durante el transcurso de su utilización.
1.2. Concepto de algoritmo 7

NO
Principio a b a = 0 a ← a-1 b ← b+1
1 2 3 4 5

6 SÍ

Fin

Figura 1.2. Diagrama de flujo de la “suma lenta”.

2. Determinismo
Todo algoritmo debe responder del mismo modo ante las mismas condicio-
nes.
Por lo tanto, la acción de barajar un mazo de cartas no es un algoritmo,
ya que es y debe ser un proceso no determinista.
3. Finitud
La descripción de un algoritmo debe ser finita.

Un primer ejemplo

Consideremos el ejemplo que, expresado gráficamente,2 aparece en la fi-

gura 1.2. El algoritmo descrito tiene por objetivo sumar dos cantidades enteras.
Si se anotan esas cantidades inicialmente en sendas casillas (a las que llamaremos
a y b para abreviar), este método consiste en ir pasando de a a b una unidad
cada vez, de forma que, cuando a = 0, el resultado será el valor de b.
Vemos un ejemplo de su funcionamiento con los datos 2 y 3 en la figura 1.3.
(Los números se han incluido para seguir mejor la evolución de los cálculos.)
Se observa que la descripción del algoritmo que se ha dado es, en efecto,
precisa (cada paso está exento de ambigüedad, ası́ como el orden en que se debe
efectuar) y determinista (el efecto de cada paso es siempre el mismo para unos
datos concretos cualesquiera). Estas dos caracterı́sticas son una consecuencia
del lenguaje escogido para expresar el algoritmo.
2
El lenguaje empleado es el de los diagramas de flujo, que estudiaremos en el capı́tulo 7,
apartado 7.2.1. Esperamos que, debido a su sencillez, el funcionamiento de este ejemplo resulte
comprensible directamente.
8 Capı́tulo 1. Problemas, algoritmos y programas

Posición Datos pendientes Resultados emitidos Var a Var b

1 [2, 3] [] ? ?
2 [3] [] 2 ?
3 [] [] 2 3
4 [] [] 2 3
5 [] [] 1 3
3 [] [] 1 4
4 [] [] 1 4
5 [] [] 0 4
3 [] [] 0 5
6 [] [] 0 5
7 [] [5] 0 5

Figura 1.3. Ejecución de la suma lenta con los datos 2 y 3.

En cambio, si bien es cierto que, con los datos del ejemplo, se ha obtenido
una solución, si se examina con detenimiento se verá que ese “algoritmo” no
siempre termina para dos cantidades enteras cualesquiera (v. g. − 3 y − 1).
De hecho, la terminación es una caracterı́stica escurridiza de la que hablaremos
más tarde (véase el apartado 1.3.1).

1.2.2 Una definición formal de algoritmo

La caracterización hecha hasta ahora de los algoritmos es satisfactoria a efec-
tos prácticos. Más concreta aún resulta a la vista de un lenguaje algorı́tmico
como el de los diagramas de flujo, que deja entrever dos aspectos:

• El mantenimiento de unas variables (a y b) y de unas posiciones (1, . . . , 7),

a lo que llamamos estado. Por ejemplo, cada fila de la tabla de la figura 1.3
representa un estado en la evolución del algoritmo 1.2.
• La descripción de transiciones entre estados, que vienen dadas por el propio
diagrama.

Estos aspectos de los algoritmos están ausentes de la primera definición,

por lo que puede resultar aún algo incompleta; surge pues la necesidad de una
definición más formal:
Definición: Un algoritmo es una cuádrupla que comprende los siguientes ele-
mentos:

1. El conjunto de los estados (llamémosle E) que pueden presentarse en todo

momento durante el cálculo.
1.2. Concepto de algoritmo 9

Un estado viene dado por una tupla, incluyendo:

• los valores de las variables que entran en juego;
• los datos sin leer y los resultados emitidos, y
• la marca, identificando la posición del algoritmo en la que se da este
estado de los cálculos.
Es decir, un estado se puede expresar ası́:

<Datos por leer; Resultados emitidos; Variables; Posición>

2. La identificación de los estados iniciales, I ⊂ E, o estados posibles al

comienzo del algoritmo.
3. La identificación de los estados finales, F ⊂ E, como posibles estados al
terminar el algoritmo.
4. Una función de transición entre estados,
t : E −→ E
que describe el efecto de cada paso del cómputo asociado al algoritmo.
Esta función deberá:
• Estar definida dentro de E, esto es, para cualquier e ∈ E debemos
tener que t(e) ∈ E. Ası́, las transiciones entre estados son precisas y
deterministas.
• A partir de cualquier estado inicial, la función de transición t debe
llevar a un estado final en un número finito de pasos, formalmente:
para cualquier e ∈ I existe un k ∈ IN tal que
t se aplica k veces
z }| {
t(t(· · · t(e) · · ·)) ∈ F
y, además, no tiene efecto alguno sobre los estados finales, es decir:
para cualquier e ∈ F ocurre que t(e) = e. De aquı́ se obtiene la
caracterı́stica de finitud.

Siguiendo con el algoritmo del diagrama de flujo de la figura 1.2, identificamos

los siguientes estados:

E = { < 1 ; [d1 , d2 ] ; [ ] ; — >

< 2 ; [d2 ] ; [] ; a ≡ a0 >
< p ; [] ; [ ] ; a ≡ a 0 , b ≡ b0 >
< 7 ; [] ; [r] ; — > }
10 Capı́tulo 1. Problemas, algoritmos y programas

donde d1 , d2 , a, b, r ∈ IN, p ∈ {3, . . . , 6}, y siendo

I = {< 1; [d1 , d2 ]; [ ]; — >}

y
F = {< 7; [ ]; [r]; — >}.

La función de transición t es la siguiente:

t(< 1; [d1 , d2 ]; [ ]; — >) = < 2; [d2 ]; [ ]; a ≡ d1 >

t(< 2; [d2 ]; [ ]; a ≡ d1 >) = < 3; [ ]; [ ]; a ≡ d1 , b ≡ d2 >
½
< 6; [ ]; [ ]; b ≡ b0 > si a = 0
t(< 3; [ ]; [ ]; a ≡ a0 , b ≡ b0 >) =
< 4; [ ]; [ ]; a ≡ a0 , b ≡ b0 > si a =6 0
t(< 4; [ ]; [ ]; a ≡ a0 , b ≡ b0 >) = < 5; [ ]; [ ]; a ≡ a0 − 1, b ≡ b0 >
t(< 5; [ ]; [ ]; a ≡ a0 , b ≡ b0 >) = < 3; [ ]; [ ]; a ≡ a0 , b ≡ b0 + 1 >
t(< 6; [ ]; [ ]; b ≡ b0 >) = < 7; [ ]; [b0 ]; — >
t(< 7; [ ]; [r]; — >) = < 7; [ ]; [r]; — >

Desde el punto de vista del usuario de un algoritmo, se puede considerar un

algoritmo como una caja opaca cuyos detalles internos se ignoran, aflorando sólo
la lectura de los datos y la escritura de los resultados. Estos aspectos observables
desde el exterior se llaman frecuentemente la interfaz externa. No obstante, el
mecanismo interno interesa al autor de algoritmos, esto es, al programador. Para
atender esta necesidad, algunos entornos de programación permiten “trazar”
programas, con lo que el programador puede ver evolucionar el estado interno
durante la marcha de su programa con el grado de detalle que desee (véanse
los apartados 5.4.1 y C.2.6). Esta posibilidad es interesante para depurar los
programas, esto es, para buscar los posibles errores y subsanarlos.
Para terminar este apartado, debemos decir que el esquema de funciona-
miento descrito a base de transiciones entre estados se conoce con el nombre de
modelo de von Neumann (véase el apartado 7.2.1 de [PAO94]). Se dice que este
modelo es secuencial, en el sentido de que los pasos se efectúan uno tras otro. De
hecho, no es posible acelerar el proceso efectuando más de un paso a un tiempo,
porque cada paso tiene lugar desde el estado dejado por el paso anterior. Este
“cuello de botella” es un defecto propio de las máquinas de von Neumann.

Cualidades deseables de un algoritmo

Es muy importante que un algoritmo sea suficientemente general y que se

ejecute eficientemente. Veamos con más detalle qué se entiende por general y
por eficiente:
1.3. Aspectos de interés sobre los algoritmos 11

1. Generalidad
Es deseable que un algoritmo sirva para una clase de problemas lo más
amplia posible. Por ejemplo, la clase de problemas “resolver una ecuación
de segundo grado, a + bx + cx2 = 0” es más general que la consistente
en “resolver ecuaciones de primer grado, a + bx = 0”.
2. Eficiencia
Hablando en términos muy generales, se considera que un algoritmo es
tanto más eficiente cuantos menos pasos emplea en llevar a cabo su come-
tido. Por ejemplo, para hallar la suma de dos números naturales, la regla
tradicional que se aprende en enseñanza primaria es más eficiente que el
rudimentario procedimiento de contar con los dedos, de uno en uno. Este
tema se revisará en el apartado 1.3.3, y será tratado con mayor detalle en
el capı́tulo 18.

Estas dos cualidades no son siempre conciliables, por lo que frecuentemente

hay que optar por una solución en equilibrio entre ambas cuando se diseña un
algoritmo. Por ejemplo, un algoritmo que estudia y resuelve “sistemas de ecua-
ciones” es más general que uno que resuelve “sistemas de ecuaciones lineales”, y
éste a su vez es más general que otro que sólo considera “sistemas de dos ecua-
ciones lineales con dos incógnitas”. Sin embargo, a mayor generalidad se tiene
también una mayor complejidad puesto que hay que tratar más casos y no se
pueden aplicar algoritmos especı́ficos. Por consiguiente, si un buen número de
situaciones puede resolverse con un algoritmo rápido aunque poco general, es
preferible adoptar éste.

1.3 Aspectos de interés sobre los algoritmos

1.3.1 Computabilidad
Con el aumento de potencia y el abaratamiento de los computadores, cada vez
se plantean aplicaciones más sorprendentes y de mayor envergadura, capaces de
resolver problemas más generales. Da la impresión de que cualquier problema que
se plantee ha de ser computable (esto es, ha de tener una solución algorı́tmica),
sin otra limitación que la potencia de la máquina ejecutora.
Sin embargo, esto no es ası́. Por rotunda que pueda parecer esta afirmación,
se debe aceptar que

hay problemas no computables

La cuestión que se plantea es algo delicada: adviértase que, si no se conoce

algoritmo que resuelva un problema planteado, sólo se puede asegurar “que no
12 Capı́tulo 1. Problemas, algoritmos y programas

se conoce algoritmo que resuelva ese problema”; en cambio, establecer que un

problema “no es computable” requiere demostrar que nunca se podrá encontrar
ningún algoritmo para resolver el problema planteado.
Los siguientes son ejemplos de problemas no computables:

• Décimo problema de Hilbert.

Resolver una ecuación diofántica con más de una incógnita.
Esto significa encontrar soluciones enteras de una ecuación de la forma
P (x1 , x2 , . . .) = 0, donde P es un polinomio con coeficientes enteros.
• Problema de la parada.
Determinar si un algoritmo a finaliza o no cuando opera sobre una entrada
de datos d: 
 Sı́ si a(d) ↓
Stop(a, d) =

No si a(d) ↑
donde a(d) ↓ (resp. a(d) ↑) expresa que el algoritmo a, aplicado al dato d,
sı́ para (resp. no para).

Examinaremos con más atención el problema de la parada, y después veremos

cuán escurridizo puede resultar determinar si un algoritmo particular para o no
considerando un sencillo ejemplo. Claro está que esto no demuestra nada salvo,
en todo caso, nuestra incapacidad para analizar este algoritmo en concreto. Por
ello, incluimos seguidamente una demostración de que es imposible hallar un
algoritmo capaz de distinguir entre los algoritmos que paran y los que no.
Obsérvese que se plantea aquı́ estudiar “algoritmos que operan sobre algorit-
mos, vistos como datos”. Por extraño que parezca al principio, en Computación
se desarrollan frecuentemente programas que manejan otros programas con di-
versos fines.

El problema de la parada no es computable

El problema de la parada, definido más arriba, se puede expresar como sigue:

¿se puede examinar cualquier algoritmo y decidir si para? Demostraremos que
no existe, ni puede existir, el algoritmo Stop que distinga si un algoritmo a para
cuando se aplica a los datos d.
Procederemos por reducción al absurdo: Suponiendo que existe ese algoritmo
(descrito más arriba como Stop), a partir de él es posible construir otro similar,
Stop’, que averigüe si un algoritmo a para cuando se aplica “a su propio texto”:
(
Sı́ si p(p) ↓
Stop’(p) = Stop(p, p) =
No si p(p) ↑
1.3. Aspectos de interés sobre los algoritmos 13

Y entonces, también se puede definir el siguiente algoritmo a partir del an-

terior:
( ) (
↑ si Stop’(p) = Sı́ ↑ si p(p) ↓
Raro(p) = =
No si Stop’(p) = No No si p(p) ↑
Veamos que el algoritmo Raro tiene un comportamiento verdaderamente
extraño cuando se aplica a sı́ mismo:

(
↑ si Stop’(Raro) = Sı́
Raro(Raro) =
No si Stop’(Raro) = No
(
↑ si Raro(Raro) ↓
=
No si Raro(Raro) ↑
lo que resulta obviamente imposible.
La contradicción a que hemos llegado nos lleva a rechazar la hipótesis inicial
(la existencia de un algoritmo para el problema de la parada), como querı́amos
demostrar.

Números pedrisco

Como ejemplo de la dificultad de examinar un algoritmo y decidir si concluirá

tarde o temprano, consideremos la siguiente función t: IN → IN:

 3n + 1 si n es impar
t(n) =

n/2 si n es par
Partiendo de un número natural cualquiera, le aplicamos t cuantas veces sea
necesario, hasta llegar a 1. Por ejemplo,
t t t t t t t
3 −→ 10 −→ 5 −→ 16 −→ 8 −→ 4 −→ 2 −→ 1 · · ·

Esta sencilla sucesión genera números que saltan un número de veces impre-
decible,
t111
27 −→ 1
de manera que cabe preguntarse si todo natural n alcanza el 1 tras una cantidad
finita de aplicaciones de t, o por el contrario existe alguno que genera términos
que saltan indefinidamente.3
Se ha comprobado, por medio de computadores, que la sucesión llega a 1 si
se comienza con cualquier número natural menor que 240 ' 1012 , pero aún no se
ha podido demostrar para todo n.
3
Este problema también se conoce como problema 3n+1.
14 Capı́tulo 1. Problemas, algoritmos y programas

1.3.2 Corrección de algoritmos

El aspecto de la corrección es de crucial importancia para quien desarrolla un
algoritmo. Sin embargo, es imposible detectar los posibles errores de una forma
sistemática. Con frecuencia, la búsqueda de errores (depuración) consiste en la
comprobación de un algoritmo para unos pocos juegos de datos. Sin embargo, eso
no garantiza nada más que el buen funcionamiento del algoritmo para esos juegos
de datos y no para todos los posibles. Volviendo al algoritmo de la suma lenta, la
comprobación con los juegos de datos [2, 3] y [3, -1] ofrecerı́a resultados correctos,
y sin embargo el algoritmo únicamente termina cuando el primer sumando es (un
entero) positivo.
Frente a la comprobación, la verificación consiste en la demostración del buen
funcionamiento de un algoritmo con respecto a una especificación. Esto es, la
verificación trata de garantizar que, para todos los datos considerados (descritos
en la especificación), el algoritmo lleva a los resultados (también descritos en la
especificación) deseados. Por eso, aunque frecuentemente se habla de corrección
de un algoritmo, sin más, en realidad hay que decir corrección de un algoritmo
con respecto a una especificación.
Por lo general, la verificación se basa en establecer aserciones (propiedades)
del estado de la máquina en cada paso del algoritmo. Se profundizará en esta
idea a lo largo de todo el texto. Por ejemplo, para verificar el funcionamiento del
algoritmo de “suma lenta”, consideremos que se hace funcionar sobre dos enteros
genéricos m y n. Claramente, al llegar a la posición 3 por vez primera, a = m y
b = n. Por otra parte, en la posición 3 se tiene invariablemente la propiedad

a+b=m+n

independientemente de las vueltas que se den y de las modificaciones que se

efectúen sobre a y b,4 ya que cada unidad que se reste a a se le suma a b. Ahora
bien, cuando se pasa de la posición 3 a la 6 es por ser a = 0, con lo que se tiene,
simultáneamente, el invariante a + b = m + n y a = 0, es decir:

b=m+n

lo que asegura que la salida es correcta. . . cuando ésta se produzca. Un algoritmo

que ofrece una solución correcta cuando para, pero del que no sepamos si para
o no, se dice parcialmente correcto. Ese es el caso de la suma lenta de números
enteros.
Además, si inicialmente a es un número natural, es seguro que el algoritmo
para, ya que la operación a ← a − 1 lo llevará a cero, precisamente en a vueltas
del bucle. Si se asegura que un algoritmo es parcialmente correcto y que para
4
Por ello, esta propiedad se conoce como invariante.
1.3. Aspectos de interés sobre los algoritmos 15

en un tiempo finito, se dice que el algoritmo es (totalmente) correcto. Ése es el

caso de la suma lenta de pares de números, siendo el primero de ellos entero y
positivo.
La verificación de algoritmos no es una tarea fácil. Al contrario, verificar
completamente un algoritmo involucra el uso de lógica matemática, y con fre-
cuencia resulta incluso más complicado que desarrollarlo. De ahı́ el interés que
tiene esmerarse, desde el principio, en escribir algoritmos correctos, adquiriendo
un buen estilo y esforzándose en emplear metodologı́as apropiadas para ello.

1.3.3 Complejidad de algoritmos

Resulta de gran interés poder estimar los recursos que un algoritmo necesita
para resolver un problema. En máquinas secuenciales, estos recursos son el
tiempo y la memoria.5
Muchas veces, un algoritmo tarda tanto en ofrecer el resultado que resulta,
en realidad, inútil. Un ejemplo de esta situación se da en sistemas de control
de procesos, en donde la respuesta a determinadas circunstancias debe disparar
mecanismos de seguridad en un tiempo crı́tico (por ejemplo, en centrales nu-
cleares). Análogamente para el espacio, es posible que la máquina en que ha
de funcionar un programa disponga de una capacidad de memoria limitada y
nos veamos obligados a elegir algoritmos que usen poca memoria. Por lo tanto,
existen situaciones en las que si disponemos de varios algoritmos para un mismo
problema, deberemos decidir cuál es el más rápido o el que menos cantidad de
memoria requiere. En el capı́tulo 18 se ahondará en esta idea.
Como el tiempo requerido por los programas depende en gran medida de la
potencia de la máquina ejecutora, es frecuente medir en “pasos” (de coste fijo)
el coste del algoritmo correspondiente. Para concretar un poco, y siguiendo con
el ejemplo de la suma lenta, consideremos que cada bloque o caja del diagrama
es un paso y, por tanto, cuesta una unidad. Entonces, es fácil deducir que sumar
los naturales m y n lleva 3m + 4 pasos.
En efecto, llamando tm al coste de sumar m y n, se tiene que

t0 = 4 pasos
tm = tm−1 + 3, si n ≥ 1

pues para sumar 0 y n hay que realizar cuatro pasos (véase la figura 1.2) y si
m 6= 0 hay que realizar tres pasos para reducir m en una unidad; resumiendo

t0 = 4
5
En los últimos años, también está interesando medir el número de procesadores en máquinas
de procesamiento en paralelo (véase el apartado 3.5 de [PAO94]).
16 Capı́tulo 1. Problemas, algoritmos y programas

t1 = t0 + 3 = 4 + 3 · 1
t2 = t1 + 3 = 4 + 3 · 2
.. .. ..
. . .
tm = tm−1 + 3 = 4 + 3 · m

independientemente de n.
Por otra parte, es frecuente concentrar el interés en el coste para datos gran-
des estudiando el comportamiento “asintótico”. De este modo, es posible redon-
dear el tiempo despreciando términos dominados por otros:
m→∞
3m + 4 ≈ 3m

También es frecuente despreciar factores de proporcionalidad, absorbidos por

las velocidades de proceso de máquinas con distinta potencia, con lo cual

3m ≈ m

de manera que, en resumen, se dirá que el algoritmo estudiado tiene coste li-
neal. Naturalmente, podemos encontrarnos algoritmos con coste constante, lo-
garı́tmico, lineal, cuadrático, exponencial, etc.
Hallar el coste de un algoritmo no es en general una tarea fácil. Con fre-
cuencia requiere una fuerte base matemática. Sin embargo, también es útil
comprender, desde el principio, que la potencia de los computadores no es ilimi-
tada, y que la ejecución de los programas consume sus recursos. Ése es el interés
de que merezca la pena esforzarse por estudiar y encontrar algoritmos eficientes,
aunque ello requiere muchas veces sacrificar su simplicidad.

1.4 Lenguajes algorı́tmicos y de programación

La descripción de un algoritmo incluye organizar los datos que intervienen
en el mismo, ası́ como las acciones que se deben llevar a cabo sobre ellos. Una
vez ideado el algoritmo, el modo más natural e inmediato (y también el menos
formal) de expresar esa organización es redactándolo con palabras y frases del
lenguaje cotidiano. En el extremo opuesto se sitúan, por su rigidez, los lenguajes
de programación.
Entre la libertad, flexibilidad y ambigüedad de los lenguajes naturales y la
precisión, rigidez y limitaciones de expresividad de los lenguajes de programación
se sitúan los lenguajes algorı́tmicos. Éstos tienen las siguientes cualidades:

1. Tienden un puente entre la forma humana de resolver problemas y su

resolución mediante programas de computador.
1.4. Lenguajes algorı́tmicos y de programación 17

2. Tienen cierta independencia de los lenguajes de programación particulares,

de modo que están libres de sus limitaciones y ası́ los algoritmos escritos
en ellos se pueden traducir indistintamente a un lenguaje de programación
u otro.

Por ello, los lenguajes algorı́tmicos constituyen una herramienta expresiva

con una libertad y flexibilidad próxima a la de los naturales y con el rigor de los
de programación.
En realidad, las únicas restricciones que deberı́an imponerse a estos lenguajes
proceden de las caracterı́sticas que tienen los algoritmos: expresar sus acciones
(qué deben realizar y cuándo) con la precisión necesaria, y que estas acciones
sean deterministas.
Por consiguiente, todo lenguaje algorı́tmico debe poseer mecanismos con que
expresar las acciones ası́ como el orden en que han de llevarse a cabo. Las
acciones, se expresan mediante instrucciones (también llamadas órdenes o sen-
tencias), que son comparables a verbos en infinitivo: asignar. . , leer. . , escribir. . .
y otras. La concatenación de las instrucciones expresa en qué orden deben suce-
derse las acciones; esto es, cómo se ensamblan unas tras otras. Los modos más
usados para ensamblar órdenes son la secuencia, la selección y la repetición, y
los estudiaremos en el capı́tulo 7.
A la vista de las observaciones anteriores es lógico cuestionar que los lenguajes
naturales sean algorı́tmicos (debido sobre todo a la ambigüedad que es inherente
a ellos). Además, resulta más práctico utilizar medios de expresión normalizados,
facilitándose la comunicación entre diseñadores y usuarios de los algoritmos y
las personas que los desarrollan.
Los diagramas de flujo constituyen uno de los lenguajes algorı́tmicos que
mayor difusión han alcanzado, aunque su uso está menguando drásticamente en
los últimos años en favor de otros métodos más apropiados desde el punto de
vista formativo.6 Entre ellos, debe citarse el seudocódigo, que aportará valiosas
ideas para la adquisición de un buen estilo de programación y, en definitiva, para
aprender cómo enfocar la resolución de problemas complicados. Seguidamente,
describimos el algoritmo de la suma lenta mediante seudocódigo:

Sean a, b ∈ ZZ
Leer a y b ½
a←a−1
Mientras a 6= 0, hacer
b←b+1
Escribir b

6
De hecho, nosotros desaconsejamos su uso como lenguaje de desarrollo de algoritmos, limi-
tando su estudio a mostrar, precisamente, lo que no es la programación estructurada (véase el
apartado 7.2.1).
18 Capı́tulo 1. Problemas, algoritmos y programas

En la práctica, el seudocódigo se usa como un medio expresivo de camino

hacia un lenguaje de programación concreto. Por tanto, es lógico que los algorit-
mos seudocodificados tengan un parecido notorio con los programas escritos en
ese lenguaje. En concreto, compárese por ejemplo el seudocódigo anterior con el
programa siguiente, escrito en Pascal:

Program SumaLenta (input, output);

{Se suman dos enteros, pasando unidades de uno a otro}
{PreC.: input = [m n], enteros}
var
a, b: integer;
begin
ReadLn (a, b);
{Inv.: a + b = m + n}
while a <> 0 do begin
a:= a-1;
b:= b+1
end; {while}
WriteLn(b)
end. {SumaLenta}

1.5 Desarrollo sistemático de programas

En los últimos años, las aplicaciones comerciales se han hecho cada vez más
grandes y complejas y, por tanto, su desarrollo resulta cada vez más caro, lento
y sujeto a numerosos errores. Este problema fue tremendamente importante
hacia los años sesenta (se hablaba entonces de “crisis del software”), y para
tratar de solucionarlo surgió entonces la Ingenierı́a del software, que considera
el desarrollo de programas y aplicaciones como un proceso productivo donde se
aplican técnicas de ingenierı́a. El desarrollo del software se organiza en fases,
que en conjunto se conocen como el ciclo de vida.7 Son las siguientes:

Planificación: En esta fase inicial hay que constatar la verdadera necesidad del
producto que se va a desarrollar y valorar los recursos humanos y técnicos
que precisa su desarrollo. Esta valoración se traduce en coste económico y
tiempo de elaboración. Si se aprueba el proyecto, se pasa a la fase siguiente.
7
La organización de estas fases da lugar a diversas variantes del ciclo de vida, siendo uno de
los más aplicados el conocido como ciclo de vida clásico. Existen crı́ticas importantes a éste,
básicamente por su carácter secuencial y por la dificultad de establecer inicialmente todas las
especificaciones. En respuesta a estas crı́ticas se han creado otros modelos de desarrollo como son
la utilización de prototipos y de lenguajes de cuarta generación (4GL) y el llamado modelo en
espiral.
1.5. Desarrollo sistemático de programas 19

Análisis: En la fase de análisis se establecen cuáles deben ser la funciones que

debe cumplir la aplicación y cómo debe realizarse el trabajo conjunto de los
diferentes módulos en que se va a dividir. Dentro de esta fase se determina
un sistema de pruebas que permita detectar los posibles errores y asegurar
el funcionamiento correcto de la aplicación y las condiciones para unir los
módulos de forma fiable. Como resultado de esta fase se redactan las
especificaciones detalladas del funcionamiento general del software.

Diseño: En esta fase se diseña el conjunto de bloques, se dividen en partes y

se asignan a los equipos de programadores. Cada equipo elabora su parte,
escribiéndola en un lenguaje algorı́tmico y probándola de forma manual.
Como resultado de esta fase se obtienen algoritmos escritos en lenguaje
algorı́tmico.

Codificación: La fase de codificación se confunde muchas veces con la pro-

gramación y consiste en escribir los algoritmos en un lenguaje de progra-
mación. Es un proceso casi automático.

Validación: La fase de validación consiste en aplicar el sistema de pruebas a los

módulos, a las conexiones entre ellos (prueba de integración) y, por último,
a la totalidad de la aplicación (prueba de validación). Como resultado
de esta fase se genera la aplicación habiendo corregido todos los errores
detectados en las pruebas.

Mantenimiento: En la fase de mantenimiento se redacta la documentación

actualizada, tanto para el programador como para el usuario. Se inicia
la explotación de la aplicación y se detectan y corrigen los errores y de-
ficiencias no advertidas en las fases anteriores, lo que puede suponer un
coste añadido importante. El resultado de esta fase es una aplicación en
explotación.

Evidentemente, en un curso como éste, los programas que vamos a desarro-

llar no requieren, por su reducido tamaño, la ejecución de todas estas fases. Sin
embargo, conviene advertir que la tarea de la programación no consiste en la
codificación (escritura de un programa) directa, ni siquiera para programas sen-
cillos, sino que incluye otras fases: es necesario comprender primero el problema
que se plantea; si se puede dividir en subproblemas, esto reduce la complejidad,
aunque en ese caso hace falta acoplar los diferentes módulos (por el momento,
digamos que se trata de fragmentos de programa); y, por supuesto, es ineludible
que el programa sea correcto, de forma que este requisito necesario merece toda
nuestra atención.
20 Capı́tulo 1. Problemas, algoritmos y programas

1.6 Conclusión
La importancia de los algoritmos y de los lenguajes algorı́tmicos reside en
su capacidad para expresar procesos, encaminados a ofrecer la solución a pro-
blemas planteados, con independencia de los lenguajes de programación, y aun
de la máquina, siendo ası́ posible el desarrollo de algoritmos para computado-
res todavı́a no creados: de hecho, muchos de los programas actuales responden
a algoritmos concebidos mucho antes de que apareciera el primer computador:
considérese por ejemplo el método que ideó Euclides en el siglo iv a. C. para
hallar el máximo común divisor de dos números naturales. Los lenguajes de
programación son también importantes, ya que permiten materializar los algo-
ritmos, razón por la que se ha avanzado tanto en el estudio de éstos en las últimas
décadas.
Por otra parte, tratar el método (algoritmo) como objeto de estudio supone
un salto de nivel en la resolución de problemas, ya que ahora no sólo se requiere la
aplicación de un determinado procedimiento de resolución, sino que cobra impor-
tancia la invención y descripción del mismo. Es decir, para resolver un problema
habrá que identificar qué acciones conducen a la solución, y cómo describirlas y
organizarlas.
En otras palabras, en este capı́tulo, nuestro modus operandi ha consistido en:

1. Disponer de un problema y un método.

2. Resolverlo; es decir, aplicar el método al problema.

mientras que, a partir de ahora, sólo disponemos de un problema y no del método

que debemos aplicar, por lo que deberemos diseñar y desarrollar el mismo para
poder aplicarlo al problema planteado. En resumidas cuentas, la resolución de
un problema general requerirá:

1. Diseñar un algoritmo apropiado.

2. Escribir el programa correspondiente en un lenguaje de computador.

3. Ejecutar el programa correspondiente para el juego de datos del problema.

1.7 Ejercicios
1. Considere la relación de problemas:
(i) Resolver una ecuación de primer grado de la forma a + bx = 0.
(ii) Sumar dos fracciones.
(iii) Interpretar una partitura al violı́n.
1.8. Referencias bibliográficas 21

(iv) Hacer la cuenta atrás, desde 10 hasta 0.

Para cada uno de ellos, se pide que:
(a) Identifique cuáles son los datos y los resultados.
(b) Describa un problema más general y, si se puede, otro menos general.
(c) Distinga cuáles de esos problemas pueden resolverse mediante algoritmos y
cuáles no.
(d) Esboce, con sus propias palabras o en seudocódigo, un algoritmo para los
problemas (i), (ii) y (iv).
2. El problema de restar dos enteros positivos se puede resolver por un procedimiento
análogo al de la suma lenta: en vez de pasar unidades de una cantidad a la otra,

(2, 3) → (1, 4) → (0, 5) → 5

se van restando unidades a ambas a la vez:

(9, 2) → (8, 1) → (7, 0) → 7

Se pide que:
(a) Escriba un diagrama de flujo para este problema.
(b) Examine cómo evoluciona para el cálculo de 5 − 2.
(c) Estudie su complejidad.
(d) Estudie su corrección.
(e) Exprese el algoritmo en seudocódigo.
(f) Redacte el programa correspondiente en Pascal basándose en el programa
presentado para la suma lenta.

1.8 Referencias bibliográficas

Muchos de los conceptos que se estudian en este capı́tulo (y en algunas otras partes
de este libro) pueden consultarse también en [GL86], que ofrece una introducción clara
y amena a diversos aspectos teóricos y prácticos sobre los algoritmos y programas, su
desarrollo y ejecución, ası́ como sus implicaciones sociales. La formalización de los
algoritmos dada aquı́ es una adaptación de la presentada en [FS87].
El apartado de los lenguajes algorı́tmicos se amplı́a un poco en el capı́tulo 7 de
este mismo libro, donde se introducen el seudocódigo y los diagramas de flujo. Debe
advertirse sin embargo que esta referencia no anima al lector a estudiar los diagramas
de flujo ahora, sino más bien a esperar su momento y limitar su estudio al cometido con
que allı́ se introducen.
A pesar del tı́tulo del epı́grafe “lenguajes algorı́tmicos y de programación”, no se ha
dicho mucho sobre estos últimos: en realidad, la idea es establecer un primer vı́nculo
entre ellos. Para ampliar lo dicho aquı́ sobre los lenguajes de programación, remitimos
al capı́tulo 5 de [PAO94] y a la bibliografı́a que allı́ se refiere.
Capı́tulo 2

El lenguaje de programación Pascal

2.1 Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2 Otros detalles de interés . . . . . . . . . . . . . . . . . . 24
2.3 Origen y evolución del lenguaje Pascal . . . . . . . . . 24
2.4 Pascal y Turbo Pascal . . . . . . . . . . . . . . . . . . . . 25

En este breve capı́tulo se presenta el lenguaje de programación Pascal, resal-

tando algunas de sus caracterı́sticas más importantes, como la sencillez de sus
instrucciones, la estructuración de éstas y su capacidad expresiva, que permite
implementar algoritmos de muy diversa ı́ndole. Estas caracterı́sticas, entre otras,
son las que justifican que Pascal sea el lenguaje de programación utilizado en
este libro.

2.1 Introducción
Pascal es un lenguaje de alto nivel : se parece más al lenguaje natural hablado,
o al matemático, que al lenguaje de máquina (véase el cap. 5 de [PAO94]). Este
nivel se alcanza gracias a una pequeña colección de mecanismos simples pero
de una gran potencia: unos permiten estructurar acciones (secuencia, selección e
iteración), otros datos (arrays, registros, ficheros), y otros hacen posible extender
el lenguaje, dotándolo en general con conceptos (datos y operaciones) semejantes
a los empleados en el razonamiento humano sobre los problemas, como se mostró
en el apartado 1.4.
24 Capı́tulo 2. El lenguaje de programación Pascal

La gran expresividad debida a la particular estructuración de sus datos y de

su pequeña colección de instrucciones evita la necesidad de recurrir a otros meca-
nismos (probablemente enrevesados, difı́ciles de expresar y de analizar, como por
ejemplo la instrucción de bifurcación incondicional goto); por todo esto decimos
que es un lenguaje estructurado (véase el capı́tulo 7). Por otra parte, permite
crear módulos que extienden el lenguaje (por lo que se dice que es modular ; ver
el capı́tulo 9); esta caracterı́stica permite desarrollar programas dividiéndolos en
partes (módulos o subprogramas) más pequeñas, independientes, que se pueden
desarrollar por separado.
Una caracterı́stica positiva de Pascal es su reducido conjunto de instruc-
ciones, lo que lo hace relativamente compacto y fácil de aprender. En resumen,
el lenguaje Pascal facilita la adquisición de buenos hábitos de programación y
proporciona los instrumentos que permiten adaptarse a los principales métodos
de desarrollo de algoritmos: programación estructurada y modular y definición y
uso de tipos de datos. Estas técnicas han convertido en las últimas décadas a la
programación en una actividad disciplinada y guiada por una cierta metodologı́a,
y el lenguaje Pascal ha contribuido enormemente a su difusión y utilización. Por
ello, es además idóneo como primer lenguaje de programación, facilitando el
aprendizaje posterior de otros. Ası́ lo prueba su fuerte implantación.

2.2 Otros detalles de interés

La mayorı́a de los traductores del Pascal son compiladores (véase el apar-

tado 5.3.1 de [PAO94]): el programa en Pascal se traduce de una sola vez a
lenguaje máquina antes de ser ejecutado, y en ese proceso se detectan gran can-
tidad de errores de forma automática, permitiendo al programador enmendarlos
antes de la ejecución. Como ejemplo de las verificaciones que se efectúan durante
la compilación, una de las más importantes consiste en la compatibilidad de los
tipos de los objetos.
Antes de la aparición de Pascal existı́an lenguajes dirigidos a la programación
cientı́fica (como Fortran) y otros dirigidos a la de gestión (como Cobol). El
lenguaje Pascal trata de conciliar los dos tipos de programación, por lo que suele
decirse que Pascal es un lenguaje de propósito general.

2.3 Origen y evolución del lenguaje Pascal

Es obvio decir que Pascal toma el nombre del matemático francés Blaise
Pascal (1623–1662) que en 1642 inventó la primera máquina de calcular para
ayudar a su padre en su trabajo de tasador de impuestos.
2.4. Pascal y Turbo Pascal 25

El lenguaje Pascal fue concebido por Niklaus Wirth en 1968 y definido en

1970 en el Instituto Politécnico de Zurich para enseñar la programación a sus
alumnos. Desde que comenzó a utilizarse (1971), ha tenido un enorme desarrollo
y difusión, adaptándose a la mayorı́a de los computadores, grandes y pequeños.
Actualmente es uno de los lenguajes más usados en las universidades de muchos
paı́ses del mundo. Gracias a esta difusión, junto con los compiladores de este
lenguaje, se han desarrollado potentes entornos de programación de gran calidad
y bajo precio.
Algunas de las implementaciones del lenguaje son Turbo Pascal°c (que fun-
ciona en computadores compatibles PC, bajo el sistema operativo DOS y bajo
Windows), Macintosh Pascal°c , VAX Pascal°c , Microsoft Pascal°c y Quick Pascal°c .
Es un lenguaje estandarizado, estando recogido en el Pascal User Manual and
Report de K. Jensen y N. Wirth [JW85]. Por lo general, las distintas versiones
se adaptan al estándar y lo extienden. Por lo tanto, un programa escrito en
Pascal estándar (según el Pascal User Manual and Report) debe funcionar en la
mayorı́a de las versiones; en cambio, si una versión contiene extensiones, lo más
probable es que no funcione en las otras.
En cualquier caso, es ciertamente comprensible que las caracterı́sticas pre-
sentadas aquı́, sin conocer el lenguaje, pueden sonar a hueco, ya que el momento
apropiado para una valoración cabal es a posteriori , después de un conocimiento
más completo de este lenguaje e incluso otros: sólo ası́ puede apreciarse su ele-
gancia conceptual, la enorme influencia que ha tenido en el desarrollo de otros, en
la enseñanza de la programación y en la metodologı́a de desarrollo de programas
y, naturalmente, también sus limitaciones.
Quienes ya conozcan este lenguaje en mayor o menor medida, o quienes
deseen ampliar el contenido de este libro, pueden encontrar en [Wir93] una visión
panorámica, escrita por el propio Wirth.

2.4 Pascal y Turbo Pascal

La posición que se adopta en este libro acerca del lenguaje de programación

utilizado es intermedia, entre el estándar ideado inicialmente (lo que es con-
veniente para que los programas sean transportables) y un compilador real (lo
que tiene la ventaja de permitir la práctica en el desarrollo de programas). El
compilador concreto adoptado es Turbo Pascal, potente, rápido, de amplia di-
fusión y dotado con un entorno muy bien desarrollado que facilita la tarea del
programador.
El inconveniente consiste en que Turbo Pascal, como la mayorı́a de los com-
piladores existentes, incluye diferencias con respecto a Pascal estándar, aunque
26 Capı́tulo 2. El lenguaje de programación Pascal

éstas son mı́nimas: debe decirse que casi no tiene limitaciones, y que en cambio
ofrece una gran cantidad de extensiones.
Nuestra decisión ha sido trabajar con este compilador1 para que sea posible
al alumno desarrollar sus prácticas, haciendo uso de las mı́nimas herramientas
extendidas del mismo y señalando en todo caso las diferencias con respecto al
estándar. Además se incluye un apéndice sobre Turbo Pascal donde se presentan
las caracterı́sticas y diferencias más importantes con Pascal estándar.

1
Para nuestros propósitos es válida cualquier versión de Turbo Pascal desde la 4.0 hasta la 7.0,
ası́ como Turbo Pascal para Windows y Borland Pascal.
Capı́tulo 3

Tipos de datos básicos

3.1 Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2 El tipo integer . . . . . . . . . . . . . . . . . . . . . . . . 28
3.3 El tipo real . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.4 El tipo char . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.5 El tipo boolean . . . . . . . . . . . . . . . . . . . . . . . . 36
3.6 Observaciones . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.7 El tipo de una expresión . . . . . . . . . . . . . . . . . . 43
3.8 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

Es preciso adquirir desde el principio el concepto de dato, puesto que los

algoritmos (y por lo tanto los programas) los manejan constantemente,1 desde
la entrada (que puede considerarse como la colección inicial de datos) hasta la
salida (o conjunto de datos resultantes), pasando frecuentemente por un sinfı́n de
resultados provisionales que intervienen en los cálculos intermedios (tales como
las cifras “de acarreo” en una operación de multiplicar).
Este capı́tulo se dedica al estudio de los tipos de datos elementales de Pascal,
explicando sus dominios y operaciones, ası́ como la construcción de expresiones
con datos de dichos tipos.

1
De hecho, en un algoritmo se organizan dos aspectos inseparables: acciones y datos.
28 Capı́tulo 3. Tipos de datos básicos

3.1 Introducción

Un dato es simplemente la representación de un objeto mediante sı́mbolos

manejables por el computador.
El uso de números (enteros y reales), caracteres y valores lógicos es corriente
en programación. De hecho, casi todos los lenguajes disponen de ellos a priori,
por lo que se les llama también tipos de datos predefinidos o también estándar.
Ciertamente, es posible ampliar nuestro lenguaje con otros objetos a la me-
dida de los problemas que se planteen, tales como vectores o conjuntos (véanse
los capı́tulos 11 y 12). Éstos se construyen usando los datos predefinidos como
las piezas más elementales, por lo que también se les llama tipos de datos básicos
a los tipos de datos predefinidos.
Sin embargo, lo cierto es que, en principio, sólo se puede contar con los tipos
de datos mencionados, que en Pascal se llaman respectivamente integer, real,
char y boolean, y que estudiamos a continuación.2
Los tipos de datos se caracterizan mediante sus dominios (conjuntos de va-
lores) y las operaciones y funciones definidas sobre esos dominios.

3.2 El tipo integer

Dominio

Su dominio, denotado Z, incluye valores enteros positivos o negativos. De-

bido a las limitaciones de representación (véase el apartado 2.2.3 de [PAO94]),
el dominio de integer está acotado por la constante predefinida MaxInt, propia
de cada versión: en Turbo Pascal por ejemplo, MaxInt vale 32767, y el dominio
de integer es {-32768,..., 32767}. Los números integer se escriben lite-
ralmente sin espacios ni puntos entre sus cifras, posiblemente precedidos por el
signo más o menos, por ejemplo: 174, -273, +17, etc. El diagrama sintáctico
(véase apartado 5.2.1 de [PAO94]) de la figura 3.1 resume estos detalles.

Operaciones y funciones

Asociadas al tipo integer, se tienen las siguientes operaciones aritméticas:

2
En adelante, usaremos letra de molde para escribir el texto en Pascal, excepto las palabras
reservadas (véase el apartado 4.2) que aparecerán en negrilla.
3.2. El tipo integer 29

Nœmero Entero

+
Entero sin signo
--

Entero sin signo

D’gito

D’gito

...

0 1 ... 9

...

Figura 3.1.
30 Capı́tulo 3. Tipos de datos básicos

+ suma
- resta
* multiplicación
div división entera
mod resto de la división entera

Su funcionamiento es similar al que tienen en Matemáticas: son operaciones

binarias (tienen dos argumentos, salvo la operación -, usada también para hallar
el opuesto de un entero) e infijas (en las expresiones, se sitúan entre sus dos
argumentos). Emplearemos la notación matemática

div : Z × Z −→ Z

para expresar que los dos argumentos son de tipo entero y su resultado también lo
es. Todas las operaciones presentadas responden a este esquema. Las operaciones
div y mod expresan respectivamente el cociente y el resto de la división entera:3

7 div 2 ; 3 7 mod 2 ; 1
7 div -2 ; -3 7 mod −2 ; 1
-7 div 2 ; -3 −7 mod 2 ; −1
-7 div -2 ; 3 −7 mod −2 ; −1

Obsérvese que verifican la conocida regla:

dividendo = divisor ∗ cociente + resto

Además, existen las siguientes funciones predefinidas:

Abs valor absoluto del entero

Sqr cuadrado del entero
Pred entero predecesor
Succ entero sucesor

que son monarias (se aplican a un argumento único) y se aplican en forma prefija
(preceden a su argumento, dado entre paréntesis).
Estas operaciones y funciones son internas, puesto que convierten argumentos
integer en integer:

Abs : Z −→ Z

Sin embargo, debe observarse que las limitaciones que pesan sobre el tipo
integer afectan a las operaciones y funciones, cuyo resultado será correcto sólo
cuando no rebase los lı́mites del dominio.
3
Usaremos el sı́mbolo ; para expresar la evaluación de una operación o función.
3.2. El tipo integer 31

Expresiones

Al igual que ocurre en Matemáticas, es posible escribir expresiones combi-

nando los números con esas operaciones y funciones:

2 + 3 * Sqr(2)

Entonces, tiene sentido preguntarse en qué orden se reducirán las operaciones

involucradas, ya que el resultado puede depender de ello. Para deshacer la ambi-
güedad se conviene en evaluar las operaciones *, div y mod antes que + y -,
como se hace en Matemáticas; esta idea se expresa habitualmente diciendo que
la precedencia de unas operaciones (*, div y mod) es mayor que la de otras.
Por ejemplo, la expresión anterior se calcuları́a en tres pasos:
2 + 3 * Sqr(2) ; 2 + 3 * 4 ; 2 + 12 ; 14
Similarmente, una expresión puede resultar ambigua cuando sea posible apli-
car dos operaciones con la misma precedencia. Por ejemplo:

7 div 2 * 2

En este caso, se efectuará la valoración de las operaciones asumiendo la aso-

ciatividad a la izquierda:

7 div 2 * 2 ; 3 * 2 ; 6

Como ocurre en Matemáticas, es posible forzar un orden de evaluación dis-

tinto del convenido mediante el uso de paréntesis:

(2 + 3) * 4 ; 5 * 4 ; 20

7 div (2 * 2) ; 7 div 4 ; 1

Aunque las operaciones anteriores resultan sencillas, combinándolas apro-

piadamente es posible lograr expresiones que resuelven directamente un gran
número de problemas. Por ejemplo, si n representa una cierta cantidad (entera)
de dinero, en pesetas, n div 25 expresarı́a su cambio en monedas de cinco duros;
n mod 25 el número de pesetas restantes, que se podrı́an cambiar por n mod
25 div 5 duros y n mod 5 pesetas.
Con el uso de las funciones, las expresiones adquieren una gran potencia.
Como ejemplo, la expresión
(a + b + 1) div 2 + Abs(a - b) div 2
calcula el máximo de dos cantidades enteras representadas por a y b.
Por otra parte, el orden de aplicación de las funciones está exento de ambi-
güedad debido al uso obligatorio de los paréntesis.
32 Capı́tulo 3. Tipos de datos básicos

3.3 El tipo real

Dominio

Su dominio, en adelante R, incluye valores numéricos con parte decimal. Las

limitaciones en la representación de cantidades reales afectan ahora al dominio
en dos aspectos (véase el apartado 2.2.3 de [PAO94]): la magnitud de los valores
incluidos (en Turbo Pascal por ejemplo, el dominio de real está comprendido
aproximadamente entre ±1.7 ∗ 1038 ) y la precisión (hacia 10 cifras significativas
en Turbo Pascal).
Hay dos modos de escribir los números reales en Pascal: usando el punto
decimal (que debe tener algún dı́gito a su izquierda y a su derecha), o bien
usando la llamada notación cientı́fica o exponencial. A continuación tenemos
ejemplos de números reales en notación decimal y cientı́fica, respectivamente:

3.1415926 6.023E+23

El diagrama sintáctico de la expresión de números reales es el de la figura 3.2.

Operaciones y funciones

Existen las siguientes operaciones aritméticas relacionadas con el tipo real:

+ suma
- resta
* multiplicación
/ división

y las siguientes funciones predefinidas:

Abs valor absoluto

Sqr cuadrado
SqRt raı́z cuadrada
Sin seno
Cos coseno
ArcTan arcotangente
Ln logaritmo neperiano
Exp función exponencial

En las funciones trigonométricas, el ángulo se expresa en radianes. Las fun-

ciones logarı́tmica y exponencial son de base e.
3.3. El tipo real 33

Nœmero Real

+
Real sin signo
--

Real sin signo

cifras . cifras

+
E cifras

--

Cifras

D’gito

Figura 3.2.
34 Capı́tulo 3. Tipos de datos básicos

Reales y enteros

Se observa que los sı́mbolos de las operaciones +, -, y *, ası́ como las funciones
Abs y Sqr, coinciden con las correspondientes a los números enteros, por lo que
las siguientes descripciones resultan ambas correctas,

+ : Z × Z −→ Z

+ : R × R −→ R

ası́ como las siguientes para el caso de las funciones:

Abs : Z −→ Z

Abs : R −→ R

Este multiuso de ciertas operaciones y funciones se llama sobrecarga de ope-

radores, y de él aparecerán nuevos casos más adelante.
Otro aspecto en que el lenguaje se muestra flexible consiste en reconocer la
inclusión Z ⊂ R, y obrar en consecuencia: ası́, toda operación o función que
requiera expresamente una cantidad real aceptará una de tipo entero, realizando
automáticamente la correspondiente conversión. La descripción siguiente

+ : Z × R −→ R

es una consecuencia de ello, producida al convertir el primer argumento en un

real. En cambio, la conversión en sentido inverso no se realiza automáticamente.
Para ello, el lenguaje está dotado con funciones para convertir reales en enteros:

Trunc truncamiento (eliminación de la parte decimal)

Round redondeo al entero más próximo4

Por ejemplo,

Round(-3.6) ; -4
Trunc(-99.9) ; -99
-Round(99.9) ; -100
-Round(-99.9) ; 100

4
Inferior o superior.
3.4. El tipo char 35

Expresiones

La precedencia de las operaciones aditivas (+ y -) es menor que la de las

multiplicativas (* y /), igual que en Matemáticas.
El juego de operaciones y funciones predefinidas en Pascal tiene carencias
notables, tales como la potencia, la tangente, el arcoseno o los logaritmos de base
decimal o arbitraria. Sin embargo, combinando las presentadas anteriormente,
se logra fácilmente expresar las operaciones mencionadas, entre otras muchas.
Por ejemplo, en la siguiente tabla se dan algunas expresiones equivalentes (salvo
errores de precisión)5 a algunas funciones usuales:

función expresión equivalente

xy Exp(y * Ln(x)) para x > 0
π
tg(x) Sin(x)/Cos(x) para x 6= 2 + kπ
arcsen(x) ArcTan(x/SqRt(1 - Sqr(x)) para 0 < x < 1
logb (x) Ln(x)/Ln(b) para b > 1, x > 0

Como ejemplo final de la potencia de las operaciones y funciones presentadas,

damos la expresión

Trunc (Ln(n)/Ln(10)) + 1

que halla el número de cifras de un entero n > 0.

3.4 El tipo char

Dominio

El dominio de este tipo de datos, abreviadamente C, incluye el juego de

caracteres disponibles en el computador, que varı́a entre las diferentes versiones
desarrolladas, todas tienen en común el respeto al orden alfabético inglés y al
orden entre dı́gitos; por ejemplo, en Turbo Pascal se utiliza una codificación en
ASCII de 8 bits, por lo que existen hasta 256 posibles caracteres que se recogen
en la correspondiente tabla de códigos (véase el apartado 2.2.4 de [PAO94]).
Los valores de tipo char se escriben entre apóstrofes (por ejemplo, ’A’)
excepto el carácter apóstrofe (’), que se escribe mediante ’’’’.
5
Debe tenerse en cuenta que la imprecisión cometida al tratar con números reales puede hacerse
más importante a medida que se suceden las operaciones.
36 Capı́tulo 3. Tipos de datos básicos

Funciones

No existen operaciones internas entre caracteres; en cambio, sı́ se tienen las

siguientes funciones internas predefinidas:

Pred carácter anterior

Succ carácter sucesor

Además, existen las siguientes funciones de conversión entre char e integer:

Ord número de orden del carácter en el juego adoptado

Chr carácter asociado a un número de orden dado

El esquema de estas funciones es el siguiente:

Pred, Succ : C −→ C
Ord : C −→ Z
Chr : Z −→ C

Por ejemplo,

Pred(’Z’) ; ’Y’
Pred(’z’) ; ’y’
Succ(’7’) ; ’8’
Chr(Ord(’1’) + 4) ; ’5’

3.5 El tipo boolean

Dominio

Este tipo proviene del álgebra de Boole, como indica su nombre. Su dominio,
denotado mediante B en adelante, contiene solamente los dos valores lógicos
predefinidos: False y True. El tipo boolean es particularmente útil en tareas
de control de bucles y selecciones.

Operaciones y funciones internas

Asociadas al tipo boolean, se tienen las siguientes operaciones:

not negación lógica (con la precedencia más alta)

and conjunción lógica (precedencia multiplicativa)
or disyunción lógica (predecencia aditiva)
3.5. El tipo boolean 37

Son internas (convierten valores lógicos en valores lógicos):

not : B −→ B
and : B × B −→ B
or : B × B −→ B

y su funcionamiento viene dado por la siguiente tabla de verdad:

A B A and B A or B not A
False False False False True
False True False True True
True False False True False
True True True True False

Además, se tienen predefinidas las funciones sucesor, predecesor y orden, que

operan como sigue:

Succ(False) ; True
Pred(True) ; False
Ord(False) ; 0
Ord(True) ; 1

Operadores relacionales

Son las operaciones binarias de comparación siguientes:

= igual
<> distinto
< menor
<= menor o igual
> mayor
>= mayor o igual

Estas operaciones están sobrecargadas: permiten la comparación entre dos

valores de cualquiera de los tipos básicos, resultando de ello un valor lógico:
Es decir, si representamos los cuatro tipos introducidos mediante Z, R, C y B
respectivamente, se tiene

>= : Z × Z −→ B
>= : R × R −→ B
>= : C × C −→ B
>= : B × B −→ B

para cada una de las operaciones relacionales.

38 Capı́tulo 3. Tipos de datos básicos

Con respecto a la comparación de números reales, debemos remitirnos al

apartado 2.2.3 de [PAO94], de donde se deduce la escasa fiabilidad de estas
operaciones cuando los argumentos están muy próximos, como consecuencia de
las limitaciones de precisión en los sistemas de representación de estos números.
En cuanto a la comparación de datos no numéricos, el sı́mbolo < significa
“anterior” y no “menor” que, obviamente, no tiene sentido en tales casos. En
el caso concreto de char, esta anterioridad viene dada por sus posiciones en la
tabla adoptada (v.g. ASCII), y en el de boolean, se considera False anterior a
True.
Algunas operaciones relacionales reciben nombres especiales cuando trabajan
sobre valores booleanos:

= equivalencia lógica
<> o exclusivo
<= implicación

El funcionamiento de estas operaciones viene dado por las siguientes tablas

de verdad:

A B A = B A <> B A <= B
False False True False True
False True False True True
True False False True False
True True True False True

Las operaciones relacionales tienen menor precedencia que las aditivas. Por
ejemplo:

3 + 1 >= 7 - 2 * 3
; 3 + 1 >= 7 - 6 {ops. multiplicativos}
; 4 >= 1 {ops. aditivos}
; False {ops. relacionales}

Finalmente, se tiene la función de conversión que indica si un entero es impar:

Odd : Z −→ B


 True si n es impar
Odd(n) ;

False en otro caso
Aunque la función Odd(n) es equivalente a n mod 2 = 1, su uso es prefe-
rible al de ésta, ya que opera más eficientemente.
3.6. Observaciones 39

Circuito largo-corto

Sea la expresión booleana P and Q. Un modo de valorarla consiste en hallar

primero el valor de P, luego el valor de Q, y entonces deducir el valor de la
expresión de las tablas de la verdad. No obstante, si P hubiera resultado valer
False, el valor de la expresión será False, tanto si Q resulta ser True como
si resulta ser False, de manera que podrı́amos haber evitado hallar Q. Estos
dos modos de evaluar las expresiones booleanas se llaman respectivamente con
circuito largo y con circuito corto.
Su importancia no radica únicamente en la eficiencia conseguida al evitar
evaluar ciertos términos, sino que a veces el modo de evaluación tiene fines algo
más sutiles. Consideremos la valoración de la expresión siguiente, donde den
resulta valer 0:

(den <> 0) and (num/den = 0)

Si el modo de evaluación es con circuito corto, el resultado final es False,

para lo cual sólo se necesita hallar el valor de

den <> 0

En cambio, si se valora con circuito largo, el cálculo del segundo término

produce un error (“división por cero”), y la ejecución del programa fracasa.
Pascal estándar establece que la evaluación se produce con circuito largo, pero
Turbo Pascal ofrece la posibilidad de escoger entre ambos modos (véase el apar-
tado C.3).

3.6 Observaciones
Tipos ordinales

En los cuatro tipos de datos simples predefinidos existe una ordenación, de

manera que todos ellos son comparables con los operadores relacionales. Por
otra parte, es posible enumerar fácilmente los dominios Z, C y B, asignando a
sus elementos su número de posición: ése es el cometido de la función Ord, que
está definida para estos tres tipos de datos, y no para R.
Por ello, decimos que los tipos integer, char y boolean son ordinales, mien-
tras que real no lo es. Además de Ord, las funciones Succ y Pred son exclusivas
de los tipos ordinales, por lo que no es posible ni razonable obtener el siguiente
(o el anterior) de un número real dado.
40 Capı́tulo 3. Tipos de datos básicos

Resumen de expresiones con los tipos de datos básicos

Las expresiones en programación son similares a las empleadas en Matemáti-

cas, aunque sus elementos constituyentes no sólo son números, como hemos visto.
Las expresiones pueden consistir en una constante, una variable, una función
aplicada a una expresión o una operación entre expresiones. Aunque en princi-
pio puede resultar extraño definir expresiones en términos de expresiones, debe
observarse que estas últimas son componentes (esto es, más pequeñas), con lo
que finalmente, una expresión está compuesta por constantes o variables, piezas
básicas de las expresiones. En las figuras 3.3 y 3.4 se completa lo explicado hasta
ahora sobre la estructura sintáctica que tienen las expresiones válidas6 en Pascal.

Como se indicó anteriormente, las operaciones se aplican en las expresiones

por orden, según su precedencia, como se indica en la tabla de la figura 3.5. Si
coinciden en una expresión dos o más operaciones de la misma precedencia se
asocian de izquierda a derecha. El orden de aplicación de precedencias puede
alterarse mediante el paréntesis, igual que en Matemáticas.
Las funciones se aplican a sus argumentos entre paréntesis, por lo que no
existe ambigüedad posible.

Cadenas de caracteres

Si se observa la sintaxis de los literales, se ve que una posibilidad consiste

en escribir una cadena de ningún carácter, uno o más. Aunque este literal no
pertenece a ninguno de los tipos de datos básicos presentados, esta posibilidad
nos permitirá desde el principio emitir mensajes claros (véase 4.3.2).
Es válido por tanto escribir literales como los siguientes:

’Yo tengo un tı́o en América’

’’
’Carlos O’’Donnell’

para representar las frases encerradas entre apóstrofes, sin éstos, que actúan sólo
como delimitadores, y expresando el apóstrofe simple mediante dos de ellos.
Ası́ por ejemplo, los literales anteriores representan respectivamente la frase
Yo tengo un tı́o en América, la cadena vacı́a y Carlos O’Donnell.

6
En realidad, se consideran sólo las expresiones válidas “por el momento”. A medida que se
introduzcan posibilidades nuevas, se completarán los diagramas sintácticos.
3.6. Observaciones 41

Expresi—n

Miembro

Op. relacional Miembro

Miembro

+
TŽrmino
--

TŽrmino Op. aditivo

TŽrmino

Factor

Factor Op. multiplicativo

Factor

Literal sin signo

Identificador

Id. de funci—n ( Expresi—n )

( Expresi—n )

not Factor

Figura 3.3. Diagrama sintáctico de las expresiones (1).

42 Capı́tulo 3. Tipos de datos básicos

Literal sin signo

Real sin signo

Entero sin signo

’ Car‡cter ’

Op. relacional

< <= = <> > >=

Op. aditivo

+ - or

Op. multiplicativo

* / div mod and

Figura 3.4. Diagrama sintáctico de las expresiones (2).

op. monarios cambio de signo, not

op. multiplicativos *, /, div, mod, and
op. aditivos +, -, or
ops. de relación =, <>, <, >, <=, >=

Figura 3.5. Cuadro-resumen de prioridades.

3.7. El tipo de una expresión 43

3.7 El tipo de una expresión

El resultado de cada expresión tiene un tipo determinado, independiente
de su valor, y que puede conocerse aun ignorando los valores de sus elemen-
tos componentes, teniendo en cuenta sólo sus tipos. Ası́ por ejemplo, pueden
existir expresiones numéricas, bien enteras (como 2 + 3) o reales (como 3.14
* Sqr(2.5) por ejemplo), booleanas (como 2 + 2 = 5) y de caracteres (como
Succ(’a’)).
La información sobre el tipo de una expresión (y el de sus subexpresiones
componentes) juega en Pascal un importante papel: una vez escrito un pro-
grama, el compilador comprueba que las expresiones que intervienen en él son
correctas sintácticamente y que los tipos de las componentes de las mismas son
consistentes. Por ejemplo, la expresión siguiente podrı́a ser analizada ası́:

( (6 + 8) * 3.14 < Ord ( ’a’ ) ) or True

( (Z + Z) * R < Ord ( C ) ) or B
( Z * R < Z ) or B
( R < Z ) or B
B or B
B

aceptándose la comparación siguiente:

True = ((6 + 8) * 3.14 < Asc(’a’)) or False

y rechazándose en cambio esta otra:

2 = ((6 + 8) * 3.14 < Asc(’a’)) or True

3.8 Ejercicios
1. De las siguientes expresiones en Pascal, detecte las erróneas; en las que son co-
rrectas, indique qué tipo deben tener los identificadores, y deduzca su tipo y su
valor resultante, si es posible.
(a) x = y (b) Odd(k) or Odd(Succ(k))
(c) p = True (d) 10 div 3 = 10 / 3
(e) p > Succ(p) (f) P = Q or R
(g) Odd(n * (n - 1)) (h) Ord(’b’) - Ord(’a’) > 0

2. Sea α un ángulo, dado en grados. Escriba una expresión en Pascal que halle:
(a) el número de vueltas completas que da,
(b) el ángulo entre 0 y 359 al que equivale,
44 Capı́tulo 3. Tipos de datos básicos

(c) el número del cuadrante en que se encuentra (numerados éstos en sentido

inverso al de las agujas del reloj),
(d) el ángulo en radianes al que equivale,
(e) su tangente.
3. Evalúe las siguientes expresiones en el dominio de integer:

(2 * 2) div 4 = 2 * (2 div 4)
(10000 * 4) div 4 = 10000 * (4 div 4)

4. Usando el operador mod, escriba en Pascal una expresión que, para un entero n,
dé el número correspondiente al dı́a de la semana; esto es, para n = 1, 2, . . . , 7,
8, 9, . . . esa expresión resulte valer 1, 2, . . . , 7, 1, 2, . . .
5. Halle el valor de la expresión Ord(C) - Ord(’0’), donde C es de tipo char y
representa, sucesivamente, los valores ’0’, ’1’, . . . , ’9’.
6. Considere la correspondencia siguiente entre los caracteres alfabéticos y los números
naturales:
’A’ −→ 1
...
’Z’ −→ 26

Dé expresiones que pasen del carácter C, supuesto que es una mayúscula, al número
correspondiente, y del número N, supuestamente entre 1 y 26, a su carácter aso-
ciado.
7. Exprese la condición que deben cumplir las coordenadas de un punto del plano
(x, y) para:
(a) que su distancia al punto (1, 1) sea inferior a 5 unidades,
(b) estar en el primer cuadrante del plano,
(c) estar por debajo de la recta x + y = 6,
(d) cumplir simultáneamente los apartados anteriores.
8. Dados los catetos c1 y c2 de un triángulo rectángulo, escriba una expresión que
sirva para hallar la correspondiente hipotenusa.
9. Se sabe que la relación entre la temperatura, expresada en grados Farenheith (F )
y centı́grados (C) viene expresada por la fórmula F = 10 8C + 32.
(a) Escriba una expresión que sirva para calcular F a partir de C. Deducir el
tipo de la misma suponiendo primero que C es integer y luego que es real.
(b) Escriba una expresión que sirva para calcular C a partir de F ofreciendo un
resultado integer.
10. Encuentre una expresión en Pascal para cada uno de los siguientes apartados:
(a) 10x , para x ∈ IR
(b) log10 (x), para x ∈ IR, x > 0
3.8. Ejercicios 45

(c) (−1)n , para n ∈ ZZ

(d) xy , para x, y ∈ IR
q
(e) 5 n1 , para n ∈ IR
(f) Dado un entero n, quitarle las c últimas cifras
(g) Dado un entero n, dejar de él sólo sus últimas c cifras
(h) Dado un entero n, hallar la cifra c-ésima
11. Sea f : IR −→ IR una función derivable. La expresión

f (x + ε) − f (x)
ε
proporciona una aproximación de la derivada de f en x, para valores pequeños de
ε.
Tomando ε = 10−3 , escriba expresiones en Pascal que aproximen las derivadas de
las siguientes funciones
π
(a) f (x) = sen(x), en x = 3
(b) g(x) = 2x2 + 3x − 4, en x = e
Capı́tulo 4

Elementos básicos del lenguaje

4.1 Un ejemplo introductorio . . . . . . . . . . . . . . . . . 47

4.2 Vocabulario básico . . . . . . . . . . . . . . . . . . . . . . 48
4.3 Instrucciones básicas . . . . . . . . . . . . . . . . . . . . 52
4.4 Partes de un programa . . . . . . . . . . . . . . . . . . . 59
4.5 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

En este capı́tulo se presentan los rudimentos mı́nimos necesarios para poder

construir programas elementales en Pascal. El lector debe esforzarse aquı́ por
tener al término del mismo una visión global de las partes de un programa,
ası́ como del modo en que los programas captan los datos, los manipulan y,
finalmente, dan los resultados.

4.1 Un ejemplo introductorio

Consideremos el problema de hallar el área de un cı́rculo a partir de su
radio. Un procedimiento sencillo para ello consiste en aplicar la conocida fórmula
A = π · r2 , donde A y r son dos números reales que representan el área y el radio
del cı́rculo respectivamente. Para llevar a cabo el procedimiento, necesitaremos
conocer el valor de la constante π, a la que llamaremos pi (si no se necesita
una gran precisión, puede bastar con 3.14). Entonces, el cálculo consiste en
averiguar el valor del radio r y aplicar la fórmula para hallar A, que se ofrece
como el resultado.
48 Capı́tulo 4. Elementos básicos del lenguaje

Estas ideas pueden organizarse como se indica a continuación:

Manera de hallar el área de un cı́rculo:

Sean:
pi = 3.14
r, A ∈ IR (radio y área resp.)
Pasos que hay que llevar a cabo:
Averiguar el valor del radio r
Hallar el valor del área A, que es pi · r2
El área resulta ser el valor de A

La transcripción de este algoritmo en un programa en Pascal es casi directa:

Program AreaCirculo (input, output);

{Se halla el área de un cı́rculo conociendo su radio}
const
Pi = 3.14;
var
r, A: real; {radio y área}
begin
Write(’Cuál es el radio?: ’);
ReadLn(r);
A:= Pi * Sqr(r);
WriteLn(’Área = ’, A)
end. {AreaCirculo}

4.2 Vocabulario básico

En castellano las letras se agrupan para formar palabras, y éstas se combinan
entre sı́ y con los signos de puntuación para construir frases; análogamente, en
Pascal, se parte de un juego de caracteres básico (ASCII por ejemplo) para
componer los diferentes elementos de su vocabulario: las palabras reservadas,
los identificadores, los sı́mbolos especiales, los literales y los comentarios.

Palabras reservadas

Las palabras reservadas son componentes con significado fijo usadas en los
constructores del lenguaje. Se suelen escribir en negrita, facilitando ası́ la lectura
de los programas. Las palabras reservadas de Pascal estándar son las siguientes:

and, array, begin, case, const, div, do, downto, else, end, file,
for, forward, function, goto, if, in, label, mod, nil, not, of, or,
4.2. Vocabulario básico 49

packed, procedure, program, record, repeat, set, then, to,

type, until, var, while, with.

Además, en este libro se usarán las siguientes, añadidas en los compiladores

de Turbo Pascal:

implementation, interface, string, unit, uses

Cada palabra reservada tiene un cometido especı́fico que es inalterable; dicho

de otro modo, las palabras reservadas no son redefinibles.

Identificadores

Los identificadores desempeñan un papel similar al de los sustantivos (re-

presentando objetos), adjetivos (representando tipos, que califican los objetos)
y verbos (representando acciones) en las oraciones.
Los identificadores que están disponibles antes de empezar a escribir un pro-
grama se llaman predefinidos; damos la siguiente clasificación:

1. Archivos estándar de entrada/salida:

input, output.

2. Constantes:

False, MaxInt, True.

3. Tipos:

boolean, char, integer, real, text.

4. Funciones:

Abs, ArcTan, Chr, Cos, EoF, EoLn, Exp, Ln, Odd, Ord, Pred,
Round, Sin, Sqr, SqRt, Succ, Trunc.

5. Procedimientos:

Dispose, Get, New, Pack, Page, Put, Read, ReadLn, Reset, Rewrite,
Unpack, Write, WriteLn.

La posibilidad de extensión del lenguaje permite la creación de identificadores

(definidos por el programador) para representar archivos, constantes, variables,
tipos, funciones y procedimientos a la medida de nuestras necesidades (véase la
figura 4.1).
50 Capı́tulo 4. Elementos básicos del lenguaje

Identificador

LetraAZ

LetraAZ

D’gito

LetraAZ
...

a A ... z Z

...

Figura 4.1.

Cualquier cadena de caracteres no resulta válida como identificador: exis-

ten razones para limitarlas. Los identificadores deberán estar formados por las
letras1 y los dı́gitos,2 empezando por letra y sin espacios en blanco. En los
identificadores, las letras mayúsculas y minúsculas son indistinguibles para el
compilador.
Ejemplos de identificadores admitidos son:

max, LimSup, anno, MaxCoorY, EsPrimo, EsValido, Seat600D

En cambio, no son correctos:

primero-F, Primero F, 600D

Por otra parte, se recomienda la elección de identificadores mnemotécnicos,

que facilitan su uso al estar relacionados con el objeto que se nombra además
de aumentar la legibilidad de nuestros programas. Por ello, no es conveniente
que los identificadores sean excesivamente cortos (probablemente sin significado)
ni excesivamente largos (lo que incomoda su escritura e interpretación, y puede
1
En Pascal estándar (y también en Turbo Pascal) se excluyen la ~
n y las vocales acentuadas.
2
En Turbo Pascal también se permite el carácter de subrayado, luego son válidos los identifi-
cadores Max x o Area circulo. No obstante, se evitará su uso en este libro.
4.2. Vocabulario básico 51

provocar errores). A propósito de esto, en el apartado 5.2 se amplı́an estas

recomendaciones.
El lenguaje permite también dotar a los identificadores predefinidos con un
nuevo significado; sin embargo, este cambio es en general poco recomendable,
por lo que no consideraremos esta posibilidad.

Sı́mbolos especiales

Son similares a los signos de puntuación de las oraciones:

+ - * / := . , ; : = < > <= >= <>

( ) [ ] (* *) { } (. .) ..

Los que están formados por varios caracteres deben escribirse sin espacios en
blanco entre ellos.

Literales

En el curso de un programa, con frecuencia necesitamos escribir directamente

elementos del dominio de un tipo básico para expresar cantidades numéricas
enteras (como 365) o reales (como 3.141592), caracteres (como ’&’) o cadenas de
caracteres (como ’1 a~ no = 365 dı́as’, en las que es posible intercalar espacios
en blanco, ası́ como el carácter ~
n, las vocales acentuadas y otros sı́mbolos, pero
sin poderse partir una cadena entre más de una lı́nea). Esos valores escritos
directamente se llaman literales.
Entre los tipos básicos, los valores extremos del dominio de integer no
se suelen expresar directamente con literales, sino mediante identificadores con
un valor constante (por ejemplo MaxInt). Por otra parte, los literales que ex-
presan cadenas de caracteres no pertenecen obviamente a ninguno de los tipos
básicos, aunque existe la posibilidad de construir objetos apropiados (véanse los
capı́tulos 11 y siguientes), y su uso es tan frecuente que algunas versiones con-
cretas de Pascal proporcionan ese tipo ya predefinido (véase el apéndice B sobre
Turbo Pascal).

Comentarios

Para facilitar la lectura de los programas, es una buena costumbre intercalar

comentarios en castellano. Se distinguen del texto en Pascal por los delimitado-
res { y }, o bien (* y *). Por ejemplo:
52 Capı́tulo 4. Elementos básicos del lenguaje

{Programa que halla la hipotenusa de un triángulo rectángulo}

{Autor: Pitágoras, presumiblemente}
{Fecha: hacia el s. VI a. C.}

Cuando se encuentra un sı́mbolo { ó (*, todos los caracteres que lo siguen

hasta el primer sı́mbolo } ó *), respectivamente, son ignorados, emparejándose
{ con } y (* con *). El texto recorrido entre esos delimitadores es un comen-
tario, y se interpreta como un espacio en blanco. Por consiguiente, no serı́a
correcto interrumpir una palabra reservada, un identificador o un literal con un
comentario.
Los comentarios en Pascal no pueden anidarse, es decir, no se puede poner
un comentario dentro de otro.

4.2.1 Constantes y variables

En el ejemplo del apartado 4.1, se definió el valor de Pi: decimos que Pi
es una constante para expresar que su valor no será alterado en el curso del
programa; también se dice que es una constante con nombre para diferenciarla
de las constantes expresadas literalmente, a las que también se llama constantes
anónimas. En contraposición, los objetos r (radio) y A (área) pueden representar
diferentes valores, por lo que se llaman variables.
En los objetos constantes y variables mencionados se pueden considerar los
siguientes aspectos: el identificador (Pi, r y A), que es el término con el que
pueden referirse; su tipo (real, en los tres casos) y el valor (3.14 constantemente
para pi, y desconocidos de antemano para r y A, variables en el transcurso del
programa).
Para resaltar estos aspectos de los objetos constantes (con nombre) y varia-
bles, es corriente representarlos ası́:

pi
3.14

entendiendo que el tipo determina el espacio en donde reside el valor, de forma

que sólo son aceptables valores del correspondiente dominio.

4.3 Instrucciones básicas

4.3.1 Asignación
La instrucción de asignación se utiliza para dar un valor inicial a las variables
o para modificar el que ya tienen.
4.3. Instrucciones básicas 53

En algunos compiladores, una variable declarada presenta un valor indefinido

al iniciarse el programa; en efecto, se trata de un valor “basura”, representado por
el contenido de la memoria reservado cuando se declaró la variable. Lógicamente,
un programa que depende de valores indefinidos tiene un comportamiento inde-
terminado; por ello es necesario evitar el operar con tales variables, asignándoles
valores iniciales.
Una variable con valor indeterminado se puede representar ası́:

x1
?

La asignación graba un valor en la memoria y destruye su valor previo, tanto

si es un valor concreto como si es indeterminado. Consideremos la siguiente
sentencia de asignación:

x1:= (-b + SqRt(Sqr(b) - 4 * a * c))/(2 * a)

Consta de un identificador de variable (x1), el sı́mbolo de la asignación (que

es :=) y una expresión. El proceso de asignación se produce de la siguiente
forma: en primer lugar se evalúa la expresión, calculándose el valor final, y a
continuación se almacena el valor en la memoria.
Si asignamos un valor (1.74, por ejemplo) a la variable, ésta pasarı́a a repre-
sentarse ası́:

x1
1.74

Ejemplos de instrucciones de asignación:

base:= 10.0
altura:= 20.0
area:= base * altura / 2
contador:= contador + 1
acumulador:= acumulador + valor

La sintaxis de una instrucción de asignación viene dada por el diagrama de

la figura 4.2. Subrayamos que, semánticamente, el identificador debe representar
una variable, y que el resultado de la expresión debe ser del mismo tipo que la
variable.3
3
Salvo que la expresión sea integer y la variable real. (Véase lo comentado en el apar-
tado 3.3.)
54 Capı́tulo 4. Elementos básicos del lenguaje

Identificador := Expresi—n

Figura 4.2. Instrucción de asignación.

er er
Obsérvese la gran diferencia que existe entre una asignación (que es una
acción y tiene el efecto de alterar el valor de una variable) y una igualdad,
que es una proposición que afirma una relación entre objetos. Por ejemplo,
la asignación

contador:= contador + 1

es una instrucción que tiene por objeto incrementar en una unidad el valor
de la variable contador, mientras que la igualdad

contador = contador + 1

es una expresión booleana de una relación que, por cierto, es falsa cualquiera
que sea el valor de contador.

4.3.2 Instrucciones de escritura

En todo programa se tienen entradas y salidas de datos con las que el pro-
grama se comunica con el exterior. La lectura o entrada de datos se realiza a
través de dispositivos tales como el teclado, una unidad de disco, o fichas perfo-
radas en los computadores antiguos, etc. La escritura o salida de resultados se
realiza a través de dispositivos como la pantalla o la impresora.
Es habitual asumir un medio de entrada y uno de salida implı́citos, que se
utilizan mientras no se indique otro distinto. Frecuentemente en los computa-
dores personales se adopta la consola como medio estándar, de manera que los
datos se introducen a través del teclado y los resultados se escriben en el monitor.
La salida de resultados se expresa en Pascal con las órdenes Write y WriteLn,
que pueden tener varios argumentos consistentes en expresiones de diferentes
tipos:

Write(1 + 2 + 3)
WriteLn(’Un tigre, dos tigres, tres tigres, ...’)
WriteLn(1234, 56, 7)
WriteLn(’El doble de ’, n ,’ es ’, 2 * n)

El efecto de ambas se lleva a cabo en dos pasos sucesivos para cada uno de
sus argumentos: en primer lugar se evalúa la expresión; en segundo se escribe el
4.3. Instrucciones básicas 55

Write

WriteLn ( Expresi—n )

Figura 4.3. Instrucción de escritura.

resultado en el dispositivo de salida estándar. Los resultados de sus expresiones

se escriben sin espacio de separación, a no ser que se dé explı́citamente.
Estas instrucciones se diferencian en que la orden WriteLn genera un salto
de lı́nea, situando el cursor en el principio de la lı́nea siguiente, listo para seguir
la siguiente instrucción de escritura. Por ejemplo, si se efectuaran las cuatro
instrucciones del ejemplo consecutivamente, la salida serı́a ası́:

6Un tigre, dos tigres, tres tigres, ...

1234567
El doble de 15 es 30

suponiendo que n es el entero 15. El cursor salta y se queda en la cuarta lı́nea,

listo para continuar la escritura.
Ambas instrucciones pueden utilizarse sin argumentos: la instrucción Write
no produce efecto alguno, mientras que WriteLn provoca un salto de lı́nea. Por
lo tanto, la secuencia de instrucciones

Write; Write(’Hola’); WriteLn

equivale a la instrucción

WriteLn(’Hola’)

La sintaxis de estas instrucciones se describe en la figura 4.3.

Parámetros de formato de salida

• Con datos de tipo integer:

La salida de resultados mediante Write y WriteLn está bastante limitada:
incluso mediante el espaciado, los números quedan desalineados. Para
resolver este problema se utilizan las salidas con formato añadiendo un
56 Capı́tulo 4. Elementos básicos del lenguaje

número entero a cada una de las expresiones por escribir, que indica al
procedimiento Write o WriteLn en qué espacio debe justificar (por la de-
recha) cada uno de los valores numéricos. Por ejemplo, las instrucciones
siguientes sitúan sus resultados correctamente sangrados:4

WriteLn(1234:5,56:5,7:5) Ã1234ÃÃÃ56ÃÃÃÃ7
WriteLn(12:5,345:5,67:5) ÃÃÃ12ÃÃ345ÃÃÃ67

La salida puede rebasar el espacio reservado:

WriteLn(12345:3) 12345

• Con datos reales:

Mientras no se indique lo contrario, la salida de valores reales se escribe en
notación cientı́fica, que es bastante ilegible. Por ejemplo:

2.7315190000E+02

Como primera mejora de esta presentación, podemos justificar el resultado

a la derecha, como se ha hecho con los datos integer:

Write(a:15) Ã2.73151900E+02

añadiendo a la izquierda los espacios en blanco necesarios.

Aún mejor es añadir un doble formato, mostrándose el real en notación
decimal: el primer parámetro indica las posiciones totales, como se ha
visto, y el segundo el número de decimales

Write([Link]) ÃÃÃ273.152

redondeando las cifras visibles si es preciso.

• Con caracteres y cadenas de caracteres:

Los valores de tipo carácter pueden justificarse mediante un parámetro de
formato que expresa el espacio mı́nimo total, justificando la salida a la
derecha:

WriteLn(’A’:8) ÃÃÃÃÃÃÃA
WriteLn(’AEIOU’:8) ÃÃÃAEIOU
4
Indicamos de este modo las instrucciones (a la izquierda) junto con la salida que producen
en el output (derecha). Usaremos el sı́mbolo à para precisar el espacio ocupado por el carácter
blanco.
4.3. Instrucciones básicas 57

• Con datos de tipo boolean:

Se puede añadir un parámetro de salida a las expresiones booleanas que
justifica el resultado por la derecha:

WriteLn(ok:5) ÃTRUE

donde se ha supuesto que el valor de ok es True.

El diagrama sintáctico de la figura 4.3 se puede completar trivialmente para

que admita la posibilidad de incluir parámetros de formato.

El archivo output

Los resultados de un programa se escriben en el output, que frecuentemente

es el monitor. En realidad, el archivo output consiste en una secuencia de carac-
teres (véase el apartado 14.3), por lo que los resultados numéricos se convierten
en los caracteres que representan el correspondiente valor.
Entre esos caracteres existe una marca especial que representa el salto de
lı́nea (que suele representarse mediante ← ), ası́ como otra para indicar el final
del archivo (que representaremos mediante •). Por ejemplo, el final del output
de los ejemplos anteriores puede representarse ası́:
. . . ÃÃÃÃA← ÃÃÃAEIOU← ÃTRUE← . . . •
En los dispositivos usuales el carácter ← se interpreta como un retorno de carro
y un avance de lı́nea, confiriéndole a la salida el aspecto global de una sucesión de
lı́neas, de interpretación visual mucho más fácil que una sucesión de caracteres
sin más.

4.3.3 Instrucciones de lectura

Las operaciones de entrada se realizan en Pascal mediante los procedimientos
Read y ReadLn, cuya sintaxis se muestra en la figura 4.4. Como ejemplo de estas
instrucciones tenemos:
Read(x,y,z)
ReadLn(u)
que actúan sobre una o más variables, estando separadas por comas cuando se
trata de más de una.
Al llegar a esta instrucción, el computador lee los valores introducidos y los
asigna por orden a las variables argumento indicadas. Debe señalarse que cada
valor leı́do debe tener un tipo compatible con el de la variable en la que se
almacena.
58 Capı́tulo 4. Elementos básicos del lenguaje

Read

ReadLn ( [Link] )

Figura 4.4. Instrucción de lectura.

El archivo input

Los datos del programa se leen del input, que frecuentemente es el teclado.
Surgen ahora tres cuestiones que deben aclararse. En primer lugar, el archivo
input también consiste en realidad en una secuencia de lı́neas de caracteres
(véase el apartado 14.3), que deben convertirse en números cuando las variables
correspondientes sean de tipo numérico. Cuando haya varias variables numéricas,
se pueden escribir en una sola lı́nea separadas con espacios en blanco. En el
ejemplo5

ReadLn(var1, var2, var3) 123Ã456Ã789←

se asignarı́a 123 a var1, 456 a var2 y 789 a var3, manteniendo el orden de

lectura.
Por lo tanto, la introducción de datos, sean del tipo que sean, se realiza a
través de una secuencia de caracteres. Es posible que esta conversión no se pueda
llevar a cabo por incompatibilidad de tipos, produciéndose un error de ejecución.
Ası́ ocurrirı́a en el ejemplo

Read(var1) a←

si la variable var1 fuera de tipo numérico.

En segundo lugar, el efecto de la sentencia ReadLn consiste en captar los
datos del input y avanzar hasta rebasar el siguiente salto de fin de lı́nea. Ası́
por ejemplo, siendo las variables a, b y c de tipo numérico, en la siguiente
situación

ReadLn(a, b); 1Ã2Ã3Ã4Ã5←

Read(c) 6Ã7Ã8←
5
Ahora, la parte de la derecha representa el input.
4.4. Partes de un programa 59

las variables a, b y c tomarı́an los valores 1, 2 y 6, respectivamente. Cuando

se leen variables numéricas se saltan los blancos anteriores, que ası́ actúan como
separadores; en cambio, los caracteres se leen de uno en uno, sin separación de
ningún tipo.
Subrayamos que, en realidad, el input consiste en una única tira de caracte-
res:

1 2 3 4 5← 6Ã7Ã8← . . . •

Finalmente, usaremos en adelante el sı́mbolo • para expresar el fin del archivo

de entrada de datos.
Conviene indicar que, cuando se trabaja en el sistema operativo DOS, el
sı́mbolo ← representa a la vez el avance de lı́nea (A. L.) y el retorno de carro
(R. C.), tal como refleja su sı́mbolo usual:

A. L.

R. C.

Sin embargo, en algunos traductores de Pascal para computadores persona-

les, a veces se le atribuye el papel adicional de la cesión del control al computador
(desde el teclado) para que reanude su actividad (véase el apéndice C). Esta coin-
cidencia de papeles dificulta a veces observarlos aisladamente cuando el input
es el teclado.

4.4 Partes de un programa

En este apartado se reúnen las ideas expuestas en los anteriores, presentándo-
se las partes o secciones componentes de los programas en Pascal: encabeza-
miento, declaraciones y bloque o cuerpo de acciones.
Al fin disponemos de todos los elementos necesarios para escribir los primeros
programas, aunque se trata de programas muy simples, carentes por supuesto
de muchos mecanismos del lenguaje.
Por otra parte, además de reunir las ideas introducidas hasta ahora, el estu-
diante deberı́a en este punto conseguir poner a punto sus primeros programas en
un entorno de programación real.

4.4.1 Encabezamiento
El encabezamiento de un programa establece una identificación del mismo.
En cierto modo equivale al tı́tulo de un libro e incluye información sobre los
60 Capı́tulo 4. Elementos básicos del lenguaje

Program Identificador ( Identificador ) ;

Figura 4.5. Encabezamiento de un programa.

objetos, externos al programa, con que éste intercambia información: la inclusión

de éstos en el encabezamiento establece la comunicación correspondiente desde
el programa.
En los primeros programas estos objetos son sólo los archivos estándar: el
de entrada de datos (input) y el de salida (output), que en los computadores
personales representan a la consola (teclado y monitor respectivamente); am-
bos archivos se incluirán siempre que el programa deba realizar operaciones de
entrada y salida respectivamente, aunque conviene que el archivo output esté
siempre presente, para indicar al computador dónde comunicar las eventuales
situaciones de error. Más adelante, se verá cómo el programa podrá recibir in-
formación de otra procedencia (por ejemplo, una tabla estadı́stica situada en un
archivo de disco), o dirigir su salida a otros dispositivos (tales como la impresora).
El encabezamiento es obligatorio en Pascal estándar pero optativo en Turbo
Pascal y en otros traductores; sin embargo, es recomendable utilizarlo siempre,
para que los programas sean más claros y se puedan usar en otros entornos.
El encabezamiento empieza con la palabra reservada Program, seguida del
nombre del programa, que debe ser un identificador válido de Pascal y, entre
paréntesis, la lista de parámetros del programa. El encabezamiento se separa de
las siguientes secciones con un punto y coma (;). Por ejemplo:

Program AreaCirculo (input, output);

Program DeclaracRenta (input, output, tablaRetenciones);

Ası́ pues, la sintaxis del encabezamiento responde al diagrama de la figura 4.5.

4.4.2 Declaraciones y definiciones

Además de los identificadores predefinidos, el usuario casi siempre va a ne-
cesitar el uso de otros nuevos, en cuyo caso debe introducirlos y describirlos
(excepto el identificador del programa) antes de usarlos; este protocolo se corres-
ponde conceptualmente con la sentencia siguiente, de uso común en Matemáticas

Sean n ∈ ZZ, x ∈ IR, p = 3.14 y f : IR → IR tal que f (x) = pxn

4.4. Partes de un programa 61

literal

const Identificador = ;

+
Identificador
--

Figura 4.6. Definición de constantes.

legitimando el posterior uso de los identificadores n, x, p y f .

En Pascal, esta información de partida permite al compilador hacer las corres-
pondientes asignaciones de memoria y verificar que el uso de todos esos objetos
se ajusta a sus caracterı́sticas, avisando al programador en caso contrario.
La obligación de incluir declaraciones sólo se da cuando el programador nece-
site incluir objetos nuevos para usarlos en el programa. Estos objetos responden
a varias categorı́as: etiquetas, constantes, tipos, variables, procedimientos y fun-
ciones. Veremos con detalle cada una de ellas en su momento; por ahora, basta
con introducir la definición de constantes y la declaración de variables.

Definición de constantes

El diagrama sintáctico de la definición de constantes aparece en la figura 4.6.

En el apartado 4.2.1 se explicó la posibilidad de usar constantes literalmente,
escribiendo su valor; a menudo interesa expresar constantes mediante identi-
ficadores (v.g. Pi). Para utilizar constantes con nombre, hay que definirlas
previamente usando la palabra reservada const, del modo siguiente:

const
TempCongelaAgua = 0;
TempHierveAgua = 100;
Pi = 3.14;
MenosPi = - Pi;
PrimeraLetra = ’A’;
Vocales = ’aeiou’;

Una vez definidas las constantes, pueden intervenir en expresiones al igual

que los literales. Por ejemplo: Pi * Sqr(7.5).
En general, siempre que en un programa existan valores constantes, se re-
comienda su presentación mediante constantes con nombre. De este modo,
resulta el programa más legible (v.g. Pi, E, AnchoPantalla, AltoPantalla).
62 Capı́tulo 4. Elementos básicos del lenguaje

var Identificador : Tipo ;

Figura 4.7. Declaración de variables.

Además, cuando una constante se repita en varios puntos de un programa, bas-

tará con escribir una sola vez su valor, siendo ası́ muy fácil modificar el programa
adaptándolo a nuevos valores de las constantes.

Declaración de variables

La declaración de variables sigue el diagrama sintáctico de la figura 4.7, donde

la palabra Tipo es (por el momento) un identificador de entre integer, real,
char y boolean.
Como ya se ha dicho, las variables son objetos cuyo valor no se conoce a
priori, o bien puede cambiar a lo largo del programa. En cambio, el tipo de las
variables permanece inalterable desde que se establece al principio del programa;
los traductores de Pascal utilizan esta información para determinar la cantidad
de espacio reservado en la memoria para cada objeto y la forma en que se hará
la representación, ası́ como realizar las verificaciones aludidas en el apartado 3.7.
Para poder utilizar una variable es preciso declararla:

var
indice, contador, edad: integer;
altura, peso: real;
esPrimo, hayDatos: boolean;
inicial: char;

Deben recordarse las recomendaciones para elegir identificadores mnemotéc-

nicos que guarden relación con el objeto al que dan nombre y que no sean exce-
sivamente largos ni cortos.

4.4.3 Cuerpo del programa

En el cuerpo del programa es donde se relacionan las sucesivas sentencias
o instrucciones ejecutables que componen el programa. Va precedido por la
palabra reservada begin y termina con la palabra reservada end y un punto
final, y las instrucciones se separan con puntos y comas (véase la figura 4.8).
4.5. Ejercicios 63

begin Instrucci—n end .

Figura 4.8. Cuerpo de un programa.

Encabezamiento Declaraciones Cuerpo

Figura 4.9. Estructura básica de un programa

Los principales tipos de sentencias ejecutables son los siguientes: instruccio-

nes de asignación, de entrada o salida, estructuradas y llamadas a procedimien-
tos. Estas dos últimas las estudiaremos en capı́tulos posteriores.

4.4.4 Conclusión: estructura general de un programa

Sintetizando lo dicho hasta ahora, un programa tiene tres partes: encabeza-
miento, declaraciones y cuerpo, según la figura 4.9

1. El encabezamiento del programa se considerará obligatorio.

2. Téngase en cuenta que la sección de declaraciones, en realidad, sólo tiene

componentes optativas, por lo que puede haber programas sin declaración
alguna.

3. Finalmente, el cuerpo o bloque es también obligatorio.

4.5 Ejercicios
1. Considerando el primer programa del capı́tulo,
(a) Señale en él algunas palabras reservadas, sı́mbolos especiales, identificadores
predefinidos y definidos por el programador, literales y comentarios.
(b) Localice las constantes que aparecen, ya sea con nombre o literales.
(c) Delimite asimismo las tres secciones: encabezamiento, declaraciones y cuerpo.
2. Considérese el programa inicial de este capı́tulo. En el cuerpo de instrucciones,
¿es posible cambiar entre sı́ los identificadores Pi y r?
64 Capı́tulo 4. Elementos básicos del lenguaje

3. De las siguientes instrucciones de asignación, detecte las erróneas; averigüe el

efecto de realizar las correctas y dé el tipo que deben tener las variables que
intervienen en ellas para que sean aceptables.
(a) a:= 5 (b) l:= 2 < 1
(c) 1:= a (d) p:= Sqr(2) = Sqr(2.0)
(e) b:= 5 * a (f) MaxInt:= 32767
(g) a:= a + 1 (h) c:= 2 <= 7
(i) p:= 2 * r (j) c1:= c2
(k) ’x’:= ’y’ (l) p:= q = r = s
4. ¿Cuál es el efecto de llevar a cabo la siguiente lista de instrucciones sucesivamente?

(a)a := 2 (b)b := 3 (c)a := b (d)b := a

5. Efectúe lo siguiente, paso a paso, con varios pares a y b de tipo integer.

(a) a:= a + b (b) b:= a - b (c) a:= a - b

¿qué conclusión podemos extraer?

6. Considérese la siguiente fórmula (debida a Herón de Alejandrı́a), que expresa el
valor de la superficie S de un triángulo cualquiera en función de sus lados, a, b y
c: s µ ¶µ ¶µ ¶
a+b+c a+b+c a+b+c a+b+c
S= −a −b −c
2 2 2 2
Dé una secuencia de instrucciones para obtenerla, evitando el cálculo repetido del
semiperı́metro, sp = a+b+c
2 y almacenando el resultado finalmente en la variable
S.
7. Escriba una instrucción tal que, siendo i una variable integer con valor 10 y x
una variable real con valor 10 234567 ∗ 103 , ofrezca la salida

v(10)Ã=Ã1234.57

haciendo referencia a i y x.
8. Sean a, b, c, d, e y f variables reales. Escriba instrucciones de escritura que
ofrezcan los valores de las siguientes variables y su suma:
a c e
+ b d f
a+b c+d e+f

donde los valores de a y b están comprendidos entre 0 y 105, y su columna debe

mostrarse redondeada, sin decimales; c y d están comprendidos entre 0 y 3, y su
columna debe mostrarse redondeada con 2 decimales; e y f están comprendidos
entre 0 y 3, y su columna debe mostrarse con un dı́gito, despreciando la parte
decimal.
Obsérvese que el resultado ofrecido puede parecer erróneo, debido al redondeo o
al truncamiento. Dé un ejemplo de ello.
4.5. Ejercicios 65

9. Sean las instrucciones de lectura:

ReadLn(i1, c1, r1)
ReadLn(i2)

donde i1, i2 son variables integer, c1 es de tipo char y r1 es real. Dados los
inputs
(a) 1A1← 2Ã3← . . . •
(b) 1ÃA1← 2Ã← . . . •
(c) 1.2ÃA1.2← 1.2← . . . •
(d) -1123ÃÃ0.5Ã8← 13← . . . •
diga cuáles son correctos y en su caso cuáles son los valores recibidos por las distin-
tas variables. Explique por qué se producen los errores y la forma de subsanarlos.
10. Sean las variables m y n de tipo integer.
(a) Analice la compatibilidad de tipos en la siguiente expresión:
m < n or m = n
(b) Coloque los paréntesis necesarios para que sea correcta.
(c) ¿Puede ser correcta si m y n son de algún otro tipo?
Capı́tulo 5

Primeros programas completos

5.1 Algunos programas sencillos . . . . . . . . . . . . . . . . 68

5.2 Programas claros ⇒ programas de calidad . . . . . . 69
5.3 Desarrollo descendente de programas . . . . . . . . . . 71
5.4 Desarrollo de programas correctos . . . . . . . . . . . . 73
5.5 Observaciones finales . . . . . . . . . . . . . . . . . . . . 79
5.6 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

Con el conocimiento que ya se tiene de las instrucciones básicas de Pascal

es posible desarrollar algunos programas completos que servirán para resaltar
aspectos importantes que hay que tener en cuenta desde que se empieza a pro-
gramar.
A continuación se presentan algunos programas sencillos, con los que se
podrán efectuar las primeras prácticas, depurar errores y poner a punto los pri-
meros programas, integrando las distintas fases que intervienen en la resolución
de problemas mediante programas. Los problemas presentados como ejemplo y
propuestos como ejercicios nos permitirán descubrir la necesidad de desarrollar
los programas con naturalidad, afrontando las dificultades que planteen una a
una y con una metodologı́a que nos permita garantizar que el programa desarro-
llado es correcto.
A pesar de la simplicidad conceptual de los problemas resueltos en este
capı́tulo, no debe desdeñarse una lectura sosegada del mismo para adquirir bien
la base que se necesita para los capı́tulos posteriores.
68 Capı́tulo 5. Primeros programas completos

5.1 Algunos programas sencillos

5.1.1 Dibujo de la letra ‘‘C’’

El siguiente ejemplo es de lo más simple, aunque su efecto no produce tres

lı́neas de asteriscos, como parecen indicar los identificadores definidos, sino una
sola. Por la misma razón, los identificadores son inapropiados, ya que inducen a
pensar que el programa escribe tres lı́neas distintas.

Program LetraC (output);

{Dibujo de la letra ’C’}
const {Definición de constantes, que puede mejorarse}
linea1 = ’***’;
linea2 = ’*’;
linea3 = ’***’;
begin {Cuerpo del programa}
Write(linea1);
Write(linea2);
Write(linea3)
end. {LetraC}

Es fácil modificarlo para que produzca efectivamente tres lı́neas (en vez de
una sola) con 3, 1 y 3 asteriscos respectivamente, sustituyendo las instrucciones
Write por WriteLn. Una mejora trivial consiste en dejarlo con sólo dos constan-
tes, evitando repetirlas. Más aún, un programa tan sencillo no requiere definir
esas constantes, pudiendo usarse directamente los literales.
er er
Disposición clara de los programas. El programa anterior podrı́a ha-
berse escrito igualmente como sigue:

Program LetraC (output); {Dibujo de la letra ’C’}

const
{Definición de constantes, que puede mejorarse}
Linea1 = ’***’; Linea2 = ’*’; Linea3 = ’***’; begin
{Cuerpo del programa} Write(Linea1); Write(Linea2);
Write(Linea3) end.

Sin embargo, la presentación inicial tiene ventajas indiscutibles: el pro-

grama inicial está dispuesto con claridad, con lo que leer, revisar y analizar
el programa resulta más fácil. Asimismo, permite distinguir las componen-
tes del programa y su estructura.

Como se ve, Pascal es muy flexible en cuanto a la disposición del texto de los
programas, por lo que decimos que es un lenguaje de formato libre.
5.2. Programas claros ⇒ programas de calidad 69

La misma finalidad tiene la colocación adecuada de los comentarios, que no

tienen efecto alguno en el funcionamiento del programa y nos permiten en cambio
incluir explicaciones sobre la finalidad del programa o sobre su funcionamiento.
En el mismo sentido, no está de más volver a recordar que se recomienda
introducir identificadores mnemotécnicos, que sugieren el papel que juegan, fa-
cilitando también la lectura del programa.
El uso apropiado de una clara disposición del texto, la inclusión de comen-
tarios apropiados, y una buena elección de los identificadores, se conoce como
autodocumentación, y no es ningún lujo superfluo. Por el contrario, se considera
preciso adquirir desde el principio el hábito de desarrollar programas claros y
bien autodocumentados.

5.1.2 Suma de dos números

El siguiente programa halla la suma de dos números enteros:

Program Suma (input, output);

{Pide dos enteros y halla su suma}
var
a, b: integer; {los sumandos}
begin
{Lectura de los datos:}
Write(’Primer número: ’);
ReadLn(a);
Write(’Segundo número: ’);
ReadLn(b);
{Cálculos y resultados:}
WriteLn(a,’ + ’,b,’ = ’,a + b)
end. {Suma}

er er
Entradas y salidas claras. Además de la documentación interna del
programa, otra recomendación que debe tenerse en cuenta desde el principio
es que las lecturas de los datos y la salida de los resultados sean claras,
incluyendo para ello los mensajes necesarios y ofreciendo comprobaciones
de que los datos se han leı́do correctamente.

5.2 Programas claros ⇒ programas de calidad

Una recomendación de gran importancia para lograr que los programas sean
correctos consiste en habituarse a escribirlos de forma clara, diferenciando bien
sus distintos fragmentos para que sean fácilmente identificables y legibles. Otra
70 Capı́tulo 5. Primeros programas completos

razón para que los programas sean claros es que un programa se escribe una vez,
pero se lee muchas, bien para depurar sus posibles errores o para efectuar en
él modificaciones. Se ha dicho que un programa bien escrito debe poderse leer
tan fácilmente como una novela y, aunque esto puede resultar excesivo a veces,
conviene esmerarse desde el principio en intentarlo antes incluso que perseguir
la eficiencia.
En este sentido, conviene indicar que, de cara a mejorar la legibilidad de un
programa, también es esencial una buena estructuración y organización de las
acciones que lo componen, como se explica en los capı́tulos 6 y 7.
En la documentación de un programa se pueden observar, entre otros, los
aspectos siguientes:

• El sangrado o encolumnado,1 facilitando la identificación de fragmentos

con distinto cometido o subordinados a otros, etc.

• Los comentarios, aclarando los siguientes detalles:

– El cometido de los objetos introducidos.

– El funcionamiento del programa.
– Las condiciones requeridas o garantizadas en un determinado punto
del programa. A este respecto, véase el apartado 5.4.

• La elección adecuada de identificadores, de forma que reflejen su contenido.

Las siguientes indicaciones contribuyen a su rápida interpretación:

– Como las constantes, variables y funciones representan objetos, sue-

len nombrarse con sustantivos (Pi, x, sucesor) o sintagmas nomina-
les (MaxInt ' máximo entero), excepto cuando representan valores
lógicos, en que desempeñan el papel de sentencias (esPrimo ' es
primo), posiblemente abreviadas (primo, Odd, ok, EoLn).
– Los procedimientos representan acciones, por lo que se les suele nom-
brar con verbos en infinitivo (Escribir, Write)

Por otra parte, no debe escatimarse la longitud de los identificadores (aun-

que tampoco debe abusarse), cuando ello aclare el objeto identificado
(AreaTotal, PagaExtra, DistTierraSol) incluso usando varias palabras
para ello. En este caso, resulta aconsejable escribir con mayúscula la ini-
cial de cada palabra. Esta recomendación es válida para los identificadores
predefinidos (WriteLn, SqRt).
1
En algunos manuales puede leerse “indentado”, palabra que no existe en castellano.
5.3. Desarrollo descendente de programas 71

También se suelen usar las mayúsculas y las minúsculas con un criterio

uniforme, para que resulte sencillo interpretar la entidad de un identifica-
dor. Concretamente, la tipografı́a que seguimos para cada identificador es
la siguiente:

– Constantes definidas, empezando con mayúscula: Pi, N, Maximo.

– Variables, empezando con minúscula: x, miEdad.
– Funciones y procedimientos, empezando con mayúscula: SqRt, Write.
– Tipos, empezando con minúscula. Los definidos por el programador,
empezarán por t y luego seguirá una mayúscula.

Otra importante cualidad de los programas consiste en que las entradas de

los datos y las salidas de resultados se efectúen también de forma clara, con
mensajes concisos y apropiados, confirmando los datos capturados cuando su
lectura sea delicada, haciendo uso de los parámetros de formato, etc.

5.3 Desarrollo descendente de programas

En este apartado desarrollaremos un programa que tiene por objeto hallar la
hipotenusa de un triángulo rectángulo a partir de las longitudes de sus catetos.
Procederemos en tres pasos:

1. Obtención de los catetos.

2. Cálculo de la hipotenusa.

3. Escritura del resultado.

Esta primera aproximación puede expresarse en un estilo muy próximo a Pascal:

Program Cálculo de hipotenusa

begin
Obtener los catetos, catA , catB
Hallar la hipotenusa, hipo
Escribir el resultado, hipo
end.

Ahora, en una primera fase se desarrollan un poco estas acciones. Algunas

son tan sencillas que pueden transcribirse directamente en Pascal, aunque pue-
den mantenerse los comentarios para indicar el cometido de cada segmento de
programa:
72 Capı́tulo 5. Primeros programas completos

Program Hipotenusa (input, output);

begin
{Obtención de datos}
Write(’Catetos: ’);
ReadLn(catA, catB);
Hallar la hipotenusa, hipo
{Escritura de resultados}
WriteLn(’ Hipotenusa = ’, hipo)
end. {Hipotenusa}

añadiendo entonces los identificadores que van surgiendo:

var
catA, catB, {catetos}
hipo : real; {hipotenusa}

Otras instrucciones en cambio son algo más complicadas, pudiendo descom-

ponerse en varias más sencillas. Ası́ por ejemplo, el paso Hallar la hipotenusa
puede llevarse a cabo en dos:

Hallar la suma de los cuadrados de los catetos (SumCuadr)

Hallar la raı́z de SumCuadr, que es ya la hipotenusa

que pueden escribirse directamente como las instrucciones siguientes:

sumCuadr:= Sqr(catA) + Sqr(catB)

hipo:= SqRt(sumCuadr)

requiriéndose añadir la variable sumCuadr, de tipo real.

Finalmente, este desarrollo desemboca en un programa en Pascal:

Program Hipotenusa (input, output);

{Este programa pide las longitudes de los catetos de
un triángulo rectángulo y halla la correspondiente hipotenusa}
var
catA, catB, {longitudes de los catetos}
sumCuadr, {para guardar CatA2 + CatB2 }
hipo : real; {longitud de la hipotenusa}

begin {Prog. hipotenusa}

{Obtención de los datos y su comprobación:}
Write (’Introduce las longitudes de los catetos: ’);
ReadLn (catA, catB);
WriteLn (’un cateto mide ’, cat[Link], ’ y el otro ’, cat[Link]);
5.4. Desarrollo de programas correctos 73

{Cálculos:}
sumCuadr:= Sqr(catA) + Sqr(catB);
hipo:= SqRt(sumCuadr);
{Resultados:}
WriteLn (’La hipotenusa mide: ’, hipo:8:4)
end. {Prog. Hipotenusa}

Resumen

El programa Hipotenusa se ha desarrollado en fases sucesivas, a partir de un

boceto a grandes rasgos del mismo. En esta primera versión aparecen acciones
y datos escritos en los términos del propio problema.
Entonces empieza un proceso de refinamiento por pasos sucesivos, desarro-
llando esas acciones en cada fase: las más sencillas podrán escribirse directamente
en Pascal; otras requerirán varios pasos en esa dirección. En ambos casos pueden
aparecer nuevos objetos que será preciso incluir en las secciones de constantes o
variables.
Este modo de proceder se llama diseño descendente y refinamiento por pasos
sucesivos, ya que el desarrollo de un programa se lleva a cabo identificando
primero grandes acciones y descendiendo a sus detalles progresivamente. En el
apartado 7.3 se desarrollan estas ideas ampliamente.

5.4 Desarrollo de programas correctos

En este apartado se establece la base necesaria para razonar sobre la co-
rrección de los programas durante su desarrollo, en vez de hacerlo a posteriori.
Por el momento, atendemos al efecto que tienen las instrucciones elementales
sobre los datos manejados por el programa. De hecho, se puede garantizar
que un programa es correcto cuando el efecto que produce a partir de unos
datos genéricos consiste en desembocar en los resultados deseados. En suma, un
programa es correcto si cumple con su cometido para unos datos cualesquiera, o
sea, genéricos.
Nuestra propuesta consiste en habituarse, desde el principio, a concentrar la
dosis de atención necesaria para estar seguro de que un programa es correcto.
Para ello, se debe seguir este principio durante todas las fases del desarrollo.

5.4.1 Estado de los cómputos

El modelo de programación adoptado en este libro es el imperativo (véase

el apartado 5.1.3 de [PAO94]). En él, el efecto concreto de una instrucción en
74 Capı́tulo 5. Primeros programas completos

un momento dado puede variar dependiendo del conjunto de valores asociados

a los objetos (constantes y variables) en ese instante. Esos valores (ası́ como
el conjunto de los datos de entrada y los resultados producidos) constituyen
la noción de estado de un programa, que se altera mediante cualquiera de las
sentencias básicas a medida que avanza la ejecución del programa.
Por ejemplo, si consideramos declaradas a, b: integer, el efecto de la
instrucción Write(a + b) depende del estado (valor) de ambas variables, a y
b, por lo que su interpretación en los puntos del programa donde aparezca

...
ReadLn(a, b);
WriteLn(a + b);
a:= a + b;
WriteLn(a + b);
b:= Sqr(a);
WriteLn(a + b);
...

requiere una interpretación histórica basada en los sucesivos estados preceden-

tes. En concreto, si el input consiste en una lı́nea con los números 2 3← , las
instrucciones WriteLn(a + b) producen tres salidas distintas: 5, 8 y 30.

Trazado y depuración de un programa

Una forma de comprobar el comportamiento de un programa para un juego

concreto de datos de entrada consiste en simular su funcionamiento a mano y
seguir la evolución de los estados por los que atraviesa. Tı́picamente, esos estados
incluyen información sobre el input por leer, el output emitido, los valores de
las variables que intervienen y el punto en que estamos en un momento dado
(véase el apartado 1.2.2).
Siguiendo con el fragmento de programa anterior, el estado de los cómputos
se puede mantener en una tabla como la de la figura 5.1, en la que las posiciones
representan los estados sucesivos entre las instrucciones.
Ası́, resulta fácil analizar cómo las instrucciones modifican el valor de las
variables. Sin embargo, este sencillo método se vuelve inviable a poco que un
programa se complique. Por ello, algunos entornos de desarrollo de programas
incorporan facilidades para efectuar este seguimiento de forma automática, per-
mitiendo establecer las variables o expresiones de nuestro interés, ası́ como las
posiciones en que deseamos que se produzca una suspensión momentánea de los
cómputos para examinar su estado. Entre esos entornos se encuentra Turbo
Pascal (véase el apartado C.2.6).
5.4. Desarrollo de programas correctos 75

Posición Input Output a b

...
1 [2Ã3← ] [] ? ?
2 [] [] 2 3
3 [] [5← ] 2 3
4 [] [5← ] 5 3
 
 5← 
5 []   5 3
8
 ← 
 5← 
6 []   5 25
8
 ← 
 5← 
 
7 []  8  5 25
 ← 
 
30←
...

Figura 5.1.
76 Capı́tulo 5. Primeros programas completos

Precondiciones, postcondiciones y especificaciones

Otro inconveniente del seguimiento descrito es que sólo nos permite examinar
el funcionamiento de un programa para un juego de datos concreto, de donde no
podemos concluir que un programa es correcto para cualquier juego de datos de
entrada. Para examinar la corrección de un programa, debemos caracterizar en
general los puntos delicados, aportando una descripción (más o menos formal)
del estado de los cómputos en ese punto.
En general, si tras la instrucción de lectura los valores de las variables x e y
son x0 e y0 respectivamente, tenemos:

...;
{x =?, y =?}
Write(’Números: ’);
ReadLn(x, y);
{x = x0 , y = y0 }
x:= x + y;
{x = x0 + y0 , y = y0 }
WriteLn(x,y);
{x = x0 + y0 , y = y0 }
y:= Sqr(x);
{x = x0 + y0 , y = (x0 + y0 )2 }
WriteLn(x,y);
{x = x0 + y0 , y = (x0 + y0 )2 }
...

Los comentarios insertados ahora constituyen afirmaciones sobre el estado de

los cálculos en un momento dado, y tienen una función doble:

• Nos permiten analizar con detalle el funcionamiento de un programa o un

fragmento de programa. Por ejemplo, consideremos el programa siguiente,
cuyo objeto consiste en intercambiar el valor de dos variables de tipo char
entre sı́:

Program Intercambio (input, output);

var
c1, c2: char; {los dos caracteres}
begin
Write (’Caracteres: ’);
ReadLn(c1, c2);
c1:= c2;
c2:= c1;
WriteLn (’Invertidos: ’, c1, c2)
end. {Intercambio}
5.4. Desarrollo de programas correctos 77

Si llamamos a y b a los caracteres leı́dos del input, se pueden insertar los

siguientes predicados:

{c1 = a, c2 = b}
c1:= c2;
{c1 = b, c2 = b}
c2:= c1;
{c1 = b, c2 = b}

con lo que no se obtiene el resultado deseado.

En cambio, el siguiente programa sı́ consigue llevar a cabo el intercambio de
dos caracteres cualesquiera. La prueba de ello se da en el propio programa:

Program Intercambio (input, output);

var
c1, c2, {los dos caracteres}
aux : char; {variable auxiliar}
begin
Write (’Caracteres: ’);
ReadLn(c1, c2);
{c1 = a, c2 = b}
aux:= c1;
{c1 = a, c2 = b, aux = a}
c1:= c2;
{c1 = b, c2 = b, aux = a}
c2:= aux;
{c1 = b, c2 = a, aux = a}
WriteLn (’Invertidos: ’, c1, c2)
end. {Intercambio}

• En el razonamiento anterior, se ha partido de un programa y, para verificar

su funcionamiento, se han incluido aserciones sobre el estado de los cálculos,
averiguando ası́ el efecto que tienen una o varias instrucciones sobre los
mismos.
Recı́procamente, se puede partir del efecto que un (fragmento de) programa
debe producir para buscar instrucciones que lo logren. Por ejemplo, se
puede plantear la búsqueda de un fragmento de programa I que modifique
el valor de las variables x, y, z: integer del siguiente modo:

{x = x0 , y = y0 , z = z0 }
I
{x = y0 , y = z0 , z = x0 }
78 Capı́tulo 5. Primeros programas completos

Las situaciones del estado inmediatamente anterior a la ejecución de una

instrucción e inmediatamente posterior a la misma se llaman precondición
y postcondición respectivamente.
El planteamiento anterior es la especificación formal de un problema en
forma de ecuación, que puede leerse ası́: se pide un algoritmo I tal que,
si se ejecuta cuando x = x0 , y = y0 , z = z0 , a su término se obtiene
x = y0 , y = z0 , z = x0 . Para interpretar correctamente una especificación
deben tenerse en cuenta además las declaraciones de los objetos involucra-
dos.

En resumen, pueden entenderse las instrucciones como funciones que con-

vierten un estado en otro. Las condiciones por las que atraviesa la ejecución de
un programa pueden especificarse más o menos formalmente como comentarios,
ayudándonos a comprender el funcionamiento de un algoritmo y a verificar su
corrección.
Recı́procamente, es posible plantear un problema especificando las condicio-
nes inicial y final que el algoritmo solución debe verificar. Este modo de proceder
nos lleva a desarrollar algoritmos correctos, ya que el razonamiento sobre su fun-
cionamiento no surge a posteriori, sino durante el proceso de desarrollo. Por
supuesto, encontrar algoritmos que verifiquen una especificación dada requiere
cierta experiencia en el desarrollo de los mismos; precisamente en ello consiste
la programación.
Un medio aconsejable para adquirir el hábito de desarrollar algoritmos dis-
ciplinadamente consiste en esforzarse por razonar sobre la corrección de los pro-
gramas desde el principio, como se ha indicado en el punto primero, incluyendo
posteriormente la especificación de las condiciones necesarias en el desarrollo de
los algoritmos.

5.4.2 Desarrollo descendente con especificaciones

Incorporando aserciones en el proceso descendente de programación, resulta
que también las especificaciones van refinándose, indicando el cometido de cada
parte del programa y las condiciones iniciales en que se ejecuta cada pieza del
programa y las finales a su término. Ası́ por ejemplo, el paso “Obtener los
catetos, catA y catB”, tiene por objeto cambiar el valor de las variables catA y
catB, que es desconocido, y anotar en ellas los valores (digamos que a y b son
los valores verdaderos dados en el input), lo que se expresa ası́:

{CatA =?, catB =?}

Obtener los catetos, CatA y catB
{CatA = a, catB = b }
5.5. Observaciones finales 79

De hecho, la frase “Obtener los catetos, CatA y catB” refleja precisamente el

cometido de su especificación.
De esta forma, la primera fase del desarrollo del programa anterior puede
escribirse ası́:

Program Cálculo de hipotenusa

begin
{CatA =?, catB =?}
Obtener los catetos, CatA y catB
{CatA = a, catB = b }
Hallar la hipotenusa,
√ Hipo
{Hipo = a2 + b2 }
Escribir el resultado,
√ Hipo
{Output = a2 + b2 }
end.

En las fases sucesivas se irá refinando el algoritmo, que se va convirtiendo

poco a poco en un programa.

5.5 Observaciones finales

er er
Limitaciones del tipo integer. Se ha escrito y ejecutado el programa
siguiente en un compilador en que MaxInt es 32767. La ejecución del mismo
está representada en la columna de la derecha:

Program LimitacionesDeInteger (output);

{se asume la constante MaxInt = 32767}
var
n: integer;
begin
n:= 10000;
WriteLn(n); {10000}
n:= n*4;
WriteLn(n); {-25536}
n:= n div 4;
WriteLn(n) {-6384}
end. {LimitacionesDeInteger}

Se observa aquı́ que al ser Z, el dominio de integer, distinto de ZZ, las

operaciones correspondientes también tienen sus limitaciones. En el ejem-
plo anterior, se produce un desbordamiento en la segunda instrucción del
programa.
80 Capı́tulo 5. Primeros programas completos

er er
Limitaciones del tipo real. El siguiente programa tiene un resultado
imprevisto: aunque la expresión Ln(Exp(1)) = 1 es cierta, su evaluación
produce el valor False en el siguiente programa:

Program LimitacionesDeReal (output);

begin
...
WriteLn(Ln(Exp(1)) = 1) { False}
...
end. {LimitacionesDeInteger}

Ello se debe a que los números del tipo real se representan sólo aproxi-
madamente: a tı́tulo de ejemplo, la cantidad 0.1 es en binario un decimal
periódico, por lo que se truncan cifras en su representación (véase el apar-
tado 2.2.3 de [PAO94]). En esta referencia se identifican los peligros más
frecuentes que surgen al trabajar con números reales, como es en concreto
la comparación de cantidades reales.

er er
Variables sin valor inicial. En el siguiente programa se hace uso de
variables a las que no se ha dado valor alguno.

Program VariablesSinValorInicial (output);

var
x, y: real;
begin
{x =?, y =?}
WriteLn(x);
WriteLn(y);
WriteLn(x+y)
end. {VariablesSinValorInicial}

Por lo tanto, su funcionamiento produce resultados arbitrarios, como se

muestra a continuación, donde cada columna representa una ejecución dis-
tinta.
3.4304031250E+04 2.0689620625E-36 0.0000000000E+00
9.2923334062E+18 1.6805384925E+24 8.5444437667E+37
2.6086154722E-04 -0.0000000000E+00 1.9225485289E-17

La conclusión es ésta: si no se da a las variables valor inicial, éstas toman

valores arbitrarios.
5.6. Ejercicios 81

5.6 Ejercicios
1. Escriba programas que den cada una de las siguientes salidas:

***** Ã* ÃÃÃÃ*ÃÃÃÃ
***** ÃÃ* ÃÃÃ***ÃÃÃ
***** ÃÃÃ* ÃÃ*****ÃÃ
***** ÃÃÃÃ* Ã*******Ã
***** ÃÃÃÃÃ* ÃÃÃÃ*ÃÃÃÃ

2. Enmiende los errores cometidos en la escritura del siguiente programa:

program Par-o-impar (imput); {Este programa

pide un entero: si es par contesta "TRUE", y si
no, "FALSE" } beguin {datos} Write(’Dame un
entero y averigüaré si es par); ReadLn(n);
{cálculos} esPar:= not odd n {resultados}
WriteLn(’Solución: ’ esPar); end

3. Escriba un programa para cada uno de los siguientes problemas, documentándolo

debidamente. Incluir además bajo el encabezamiento la información concerniente
al autor (código, grupo, nombres, etc.), ası́ como la fecha de realización. Una vez
acabados, obténgase una copia escrita de ellos.

(a) Solución de una ecuación de la forma ax + b = 0, supuesto a6=0.

(b) Lectura de los coeficientes a, b y c de una ecuación de segundo grado
ax2 + bx + c = 0 y cálculo de sus raı́ces, en los siguientes casos:
i. Suponiendo que las raı́ces son reales. Ejecutarlo con los siguientes juegos
de datos:
1 2 1
1 0 -1
1 0 0
ii. Suponiendo que son imaginarias. Ejecutarlo con el siguiente juego de
datos:
1 1 1
(c) Desarrolle un programa que, para una cierta cantidad de dinero (en pesetas),
da el cambio apropiado, en billetes de mil, monedas de quinientas, de cien,
de veinticinco, de duro y de peseta.

 bill1000 ½
cantidad mon100
 resto1000
resto100 . . .

(d) Convierta una cantidad de tiempo (en segundos, ZZ), en la correspondiente

en horas, minutos y segundos, con arreglo al siguiente formato:
3817 segundos = 1 horas, 3 minutos y 37 segundos
82 Capı́tulo 5. Primeros programas completos

4. Escriba un programa que, en primer lugar, lea los coeficientes a2 , a1 y a0 de un

polinomio de segundo grado
a2 x2 + a1 x + a0
y escriba ese polinomio. Y, en segundo, lea el valor de x y escriba qué valor toma
el polinomio para esa x.
Para facilitar la salida, se supondrá que los coeficientes y x son enteros. Por
ejemplo, si los coeficientes y x son 1, 2, 3 y 2, respectivamente, la salida puede ser

1x^2 + 2x + 3
p(2) = 9

5. Razone, informalmente, la corrección o falsedad de los siguientes fragmentos de

programa, cuyo cometido se indica a continuación.
(a) Intercambio del valor de dos variables enteras.
x:= x+y;
y:= x-y;
x:= x-y
(b) Dado un entero n, hallar el menor m ≥ n que es par.
m:= n div 2 * 2
6. Los términos de la sucesión de Fibonacci2 se definen ası́:
• Los dos primeros son unos.
• Cada término es igual a la suma de los dos anteriores
Es decir: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, . . .
Suponiendo que a y b son dos términos consecutivos de esa sucesión, razone la
corrección de los siguientes fragmentos de programa desarrollados para hacer avan-
zar un paso esos términos:
(a) Siendo aux: integer una variable auxiliar para hacer el trasvase de valores:
aux:= a; a:= b; b:= aux + a
(b) Sin usar variable auxiliar alguna:
b:= a+b; a:= b-a

2
Descubierta por Leonardo da Pisa (1180-1250) y publicada en su Liber Abacci, en 1202.