Libro de Pascal
Libro de Pascal
Libro de Pascal
Computacin y Programacin
con el lenguaje Pascal
Nstor Aguilera
Ao 2007
ndice general
ndice de figuras
ndice de cuadros
1.
2.
3.
4.
5.
Preliminares
1.1. Temas que vemos . . . . . .
1.2. Organizacin y convenciones
1.3. Ideas y consejos sueltos . . .
1.4. Por qu Pascal . . . . . . .
1.5. Sobre la versin 2007 . . . .
El
2.1.
2.2.
2.3.
2.4.
. . . . . . .
que usamos
. . . . . . .
. . . . . . .
. . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
primer contacto
Un poco muy poco sobre cmo funciona la
Programas: edicin, compilacin, ejecucin . . .
El puntapi inicial . . . . . . . . . . . . . . . .
Comentarios Bibliogrficos . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
1
1
2
3
4
computadora
. . . . . . . .
. . . . . . . .
. . . . . . . .
.
.
.
.
.
.
.
.
5
5
6
7
10
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
11
11
13
15
16
17
20
22
23
Tomando control
4.1. If . . . . . . . . . . . . . . . . .
4.2. Begin-end . . . . . . . . . . . .
4.3. While . . . . . . . . . . . . . .
4.4. Repeat . . . . . . . . . . . . . .
4.5. For . . . . . . . . . . . . . . . .
4.6. Ingresando muchos datos: eoln .
4.7. Read . . . . . . . . . . . . . . .
4.8. Comentarios Bibliogrficos . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
24
25
27
29
33
34
36
39
40
Aplicaciones
5.1. Clculo numrico elemental . . . . . . . . .
5.1.1. Mezclando nmeros grandes y pequeos
5.1.2. Mtodos iterativos: puntos fijos . . . .
5.1.3. El mtodo babilnico . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
41
41
41
43
46
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Pg. ii
5.2. Nmeros enteros . . . . .
5.2.1. Algoritmo de Euclides
5.2.2. Ecuaciones diofnticas
5.2.3. Nmeros de Fibonacci
5.3. Comentarios Bibliogrficos
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
49
49
52
53
54
6.
Arreglos
55
6.1. Dimensionamiento de arreglos . . . . . . . . . . . . . . . . . . . . 55
6.2. Bsqueda Lineal . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
6.3. Polinomios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
7.
Funciones y Procedimientos
7.1. Funciones . . . . . . . . . . . . . .
7.2. El mtodo de la biseccin . . . . .
7.3. Procedimientos . . . . . . . . . . .
7.4. Pasando por valor o por referencia
7.5. Comentarios Bibliogrficos . . . . .
8.
9.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
62
62
66
70
72
75
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
76
76
77
80
80
81
82
84
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
89
89
90
92
95
98
11. Recursin
99
11.1. Funciones y procedimientos definidos recursivamente . . . . . . . 100
11.2. Los Grandes Clsicos de la Recursin . . . . . . . . . . . . . . . . 103
11.3. Comentarios Bibliogrficos . . . . . . . . . . . . . . . . . . . . . . 106
12. Objetos combinatorios
12.1. Pilas y colas . . . . . . . . . . . . .
12.2. Generando Subconjuntos . . . . . .
12.3. Caminante, no hay caminos... . . .
12.4. Generando permutaciones . . . . .
12.5. Objetos combinatorios generados al
. . .
. . .
. . .
. . .
azar
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
107
107
109
111
113
114
ndice general
Pg. iii
14. Grafos
14.1. Representacin de grafos en la computadora
14.2. Recorriendo un grafo . . . . . . . . . . . . .
14.3. Recorrido en profundidad y a lo ancho . . .
14.4. Grafos con pesos . . . . . . . . . . . . . . .
14.5. Camino ms corto: Dkstra . . . . . . . . .
14.6. Mnimo rbol generador: Prim . . . . . . . .
14.7. Comentarios Bibliogrficos . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
122
124
127
129
133
136
140
143
A. Programas mencionados
Problema 2.2: holamundo . . . .
Problema 3.2: sumardos . . . . .
Problema 3.4: leerentero . . . .
Problema 3.5: raiz . . . . . . . .
Problema 3.6: segundos . . . . .
Problema 3.10: enteroareal . . .
Problema 3.17: positivo . . . . .
Problema 3.19: caracteres1 . . .
Problema 4.2: valorabsoluto . . .
Problema 4.4: comparar . . . . .
Problema 4.5: caracteres2 . . . .
Problema 4.11: resto . . . . . .
Problema 4.12: tablaseno1 . . .
Problema 4.13: gauss . . . . . .
Problema 4.16: cifras . . . . . .
Problema 4.17: epsmin . . . . .
Problema 4.18: potencia . . . . .
Problema 4.23: eolnprueba . . .
Problema 4.24: eco . . . . . . .
Problema 4.25: sumardatos . . .
Problema 4.27: palabras . . . . .
Problema 5.11: babilonico . . . .
Problema 5.13: euclides . . . . .
Problema 6.1: unidades . . . . .
Problema 6.2: renglon . . . . . .
Problema 6.3: busquedalineal . .
Problema 7.2: potencias . . . . .
Problema 7.3: biseccion . . . . .
Problema 7.6: tablaseno2 . . . .
Problema 7.7: intercambio . . .
Problema 8.8: deconsolaaarchivo
Problema 8.8: dearchivoaconsola
Problema 9.1: dado . . . . . . .
Problema 9.2: dados . . . . . . .
Problema 13.1: arbolbinario . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
144
144
144
144
145
145
145
146
146
147
147
147
148
148
149
149
150
150
151
151
152
152
153
154
154
155
156
157
158
159
160
161
162
162
163
163
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
166
166
166
166
166
167
167
Pg. iv
B.3. Nombres reservados . . . . . . . . . . . . . . . . . . . . . . . . . . 168
C. Algunas notaciones y smbolos usados
C.1. Lgica . . . . . . . . . . . . . . . . . . . .
C.2. Conjuntos . . . . . . . . . . . . . . . . . .
C.3. Nmeros: conjuntos, relaciones, funciones
C.4. Nmeros importantes en programacin . .
C.5. Generales . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
169
169
169
170
171
171
Bibliografa
172
ndice alfabtico
173
ndice de figuras
2.1.
2.2.
2.3.
2.4.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
6
6
7
8
12
12
19
45
45
56
59
66
70
73
94
96
.
.
.
.
.
.
117
117
118
119
119
119
ndice de cuadros
4.1. Prueba de escritorio . . . . . . . . . . . . . . . . . . . . . . . . .
30
77
83
94
Captulo 1
Preliminares
En este curso se van entrelazando la introduccin de los elementos de programacin estructurada con la resolucin de problemas de matemticas, incluyendo temas de anlisis y clculo numrico, teora de nmeros, combinatoria
y grafos, sirviendo tanto de introduccin de algunos temas como de repaso y
fortalecimiento de otros. Por el contrario, se cubre muy poco de las aplicaciones
informticas como bases de datos.
Pg. 2
Preliminares
A veces hay texto intercalado entre los problemas, por lo que para indicar
el fin del enunciado de un problema est el signo $, que puede leerse como la
cortamos ac.
Intercalados entre texto y enunciados de problemas, hay algunas notas y
comentarios, en tipo de letra ms chico para no distraer demasiado del texto
principal, y puede omitirse su lectura.
En los comentarios, en itlica, se hacen referencias histricas, orientadoras,
curiosidades, etc. Son de la forma
Esto es un comentario.
Por otra parte, las notas son en general de ndole ms tcnica, y son de la
forma
- Esto es una nota.
Los nombres de los programas aparecen con otro tipo de letra, as, mientras
que lo que escribiremos en la computadora est indicado en monotipo, as,
algunas veces entre comillas dobles, para recalcar algn fragmento o tratando
de evitar confusiones, como ste, reservando las comillas simples para caracteres, como a , que imitando la usanza en Pascal. Tambin algunas veces los
espacios en blanco de un texto se ponen de esta forma para distinguirlos.
Siguiendo la tradicin norteamericana, la computadora expresa los nmeros
poniendo un punto decimal en vez de la coma, y para no confundirnos
seguimos esa prctica. As, 1.589 es un nmero entre 1 y 2, mientras que 1589
es un nmero entero, mayor que mil. A veces dejamos pequeos espacios entre
las cifras para leer mejor los nmeros, como en 123 456.789.
Tambin se hace complicado trabajar con tildes (como en ) o virgulillas
(como en ) al escribir los programas o mostrar resultados por pantalla, de
modo que en la escritura de cdigos los obviaremos (escribiendo a o ni, y
paragero quedar como paraguero).
En fin, en el texto indicamos con <retorno> el pulsado de la tecla retorno
(o return en teclados ingleses) para iniciar un nuevo rengln. Dependiendo del
sistema operativo, es posible que debas pulsar en cambio la tecla intro (o
enter en ingls).
Donde nunca se encuentra lo que uno busca, como en las guas telefnicas.
Pg. 3
Pg. 4
Preliminares
El lenguaje C tambin deriva del Algol, y es mucho ms popular ahora que
Pascal. Sin embargo, para hacer un mnimo programa ya necesitamos mencionar qu son las bibliotecas, para leer un dato tenemos que saber qu es pasar
por valor o referencia, y su sintaxis puede ser francamente crptica para los no
iniciados. En sntesis, requiere de un esfuerzo extra que dejara menos tiempo
para lo que verdaderamente importa: aprender algoritmos y resolver problemas
de matemticas.
El aprendizaje de Pascal da una slida base para programar en otros lenguajes, como Fortran o C, y sistemas, como Matlab o Maple, que s son usados
profesionalmente.
No est dems comentar que este curso comenz a dictarse en el ao 1995 basado en uno de los sistemas que ms se usan actualmente en aplicaciones cientficas. Como resultado vimos que no se aprenda una disciplina de programacin,
y se confundan conceptos bsicos como que nmeros enteros y fraccionarios son
bien distintos para la computadora.
En http://math.unl.edu.ar/~aguilera/compiladores_pascal.html hay
indicaciones de cmo conseguir compiladores Pascal gratis de internet. Especialmente recomendado es el compilador GNU Pascal (gpc). Otras recomendaciones
son Free Pascal (fpc) y Turbo Pascal. gpc y fpc no tienen un editor de textos
integrado (que se puede agregar) pero estn disponibles para todos los sistemas
operativos preponderantes. Son mucho ms modernos que Turbo Pascal, que s
viene con un editor integrado, pero usa el sistema operativo MS-DOS y tiene
serias limitaciones en el tamao de las variables.
Captulo 2
El primer contacto
2.1. Un poco muy poco sobre cmo funciona
la computadora
Conceptualmente, la computadora es una mquina que toma o accede a
datos, los procesa y devuelve resultados. Los datos o entradas y los resultados
o salidas pueden ser simples como nmeros o letras, o mucho ms complicados
como una matriz o una base de datos,(1) que podemos esquematizar como
entrada
procesamiento
salida
El primer contacto
consola
Pg. 6
pantalla
teclado
memoria
(datos)
discos
CPU
(procesamiento)
impresora
otros
Figura 2.1: Esquema de transferencia de datos en la computadora.
que s/no o blanco/negro, los bits se agrupan en cajas un poco ms grandes llamadas bytes, que generalmente tienen 8 bits, conceptualmente alineados,
puesto que queremos que 00001111 sea distinto de 11110000. Ver esquema en la
figura 2.2.
un byte
}|
0
bits
Figura 2.2: Bits y byte.
Problema 2.1. Suponiendo que un byte tenga 8 bits:
a) Cuntas ristras distintas de 0 y 1 puede tener? Sugerencia: hacer la
cuenta primero para un byte de 1 bit, luego para un byte de 2 bits, luego
para un byte de 3 bits,...
b) Si no importara el orden de los bits que forman el byte, y entonces 00001111,
11110000, 10100101 fueran indistinguibles entre s, cuntos elementos distintos podra contener un byte? Sugerencia: si el byte tiene 8 bits puede ser
que hayan 8 ceros y ningn uno, o 7 ceros y 1 uno, o...
$
A su vez, para las computadoras ms recientes, estas unidades resultan demasiado pequeas para alimentar a la CPU, por lo que los bits o bytes se agrupan
formando cajas de, por ejemplo, 32, 64 o 128 bits (usualmente potencias de 2),
siempre conceptualmente alineadas.
Pg. 7
En la mayora de los casos an para gente experimentada habr problemas en la compilacin (por ejemplo, por errores de sintaxis), o al ejecutar
el programa los resultados no sern los esperados. Esto da lugar a un ciclo de
trabajo esquematizado en la figura 2.3.
Editar
fuente
Compilar
ejecutable
Ejecutar
Corregir
Pg. 8
El primer contacto
programa
ejecutable
datos
instrucciones
Memoria
Figura 2.4: Esquema del programa ejecutable en la memoria.
programa mediante program nombre(input,output) y otras sentencias que
iremos viendo.
- Siguiendo el estndar Pascal. Muchos compiladores aceptan la omisin de
(input, output), e inclusive algunos ignoran completamente esa parte.
a) Observar con cuidado los signos de puntuacin y qu hace cada una de las
instrucciones:
El rengln inicial que comienza con program..., y que termina en ;.
En este programa es la nica sentencia de la parte declarativa.
El comentario inmediatamente despus de program..., explicando al
que lee el programa fuente cul es el propsito.
El cuerpo principal que empieza con begin y termina en end..
Hay tres sentencias en la parte principal, separadas por dos ;.
writeln escribe un rengln en la pantalla, y el texto a escribir se encierra
entre (comillas simples). Si no tiene argumentos, writeln escribe un
rengln vaco, i.e., sin caracteres.
b) Eliminar, repetir o cambiar las instrucciones. Por ejemplo:
i) eliminar el segundo writeln,
ii) y despus tambin el tercero,
iii) cambiar writeln por WRITELN, y despus por Writeln,
iv) cambiar Hola Mundo! por HOLA MUNDO!,
v) modificar el programa para que se escriba bye, bye en vez de y
Chau!.
c) En general, al escribir el programa usamos sangras, i.e., espacios al comienzo de algunos de los renglones, y a veces renglones enteros en blanco, para
resaltar la estructura del programa. Esto no es necesario, e inclusive podra
escribirse el programa en un nico rengln, y un espacio o varios no hacen
diferencia:
i) Eliminar o agregar espacios al comienzo, en el medio y/o al final de
algunos renglones, compilar el programa y verificar que se obtiene el
mismo resultado.
ii) Agregar renglones en blanco o poner dos (o todos los que se quiera)
renglones en uno solo, y verificar que se obtiene el mismo resultado (y
recordar que ; se usa en Pascal como en castellano: para separar
sentencias).
- A los fines del programa fuente, los espacios, tabulaciones (tecla tab o
similar) y renglones son intercambiables (mientras no estn encerrados
entre comillas simples).
Pg. 9
Pg. 10
El primer contacto
Captulo 3
Pg. 12
a
char
verdadero
boolean
1234
integer
4321
integer
123.456
real
98.7654
real
a
codigo
verdadero
fin
1234
a
4321
m
123.456
x
98.7654
y
nunca hay que usar el valor de una variable sin antes haber hecho una asignacin a la variable!
aunque hay compiladores que automticamente ponen algn valor al hacer las
declaraciones.
Para tratar de entender esta jerigonza, pasemos a estudiar algunos ejemplos
comenzando con los tipos numricos integer y real, para luego considerar los
tipos boolean y char.
Pg. 13
Pg. 14
3.3. Readln
j) Agregar una variable c, de tipo entero o real segn corresponda, hacer la
asignacin c := a + b e imprimir c en vez de a + b.
k) Modificarlo de modo de escribir tambin la resta (-), producto (*) y
divisin (div para enteros y / para reales), tanto en el caso de enteros
como de reales.
l) Qu pasa cuando se divide por 0?
$
Conceptualmente hay que distinguir en Pascal entre la variable, el identificador y el valor, i.e., entre la caja, su nombre y lo que contiene.
A fin de no ser demasiado latosos, es comn tanto en Pascal como en matemticas o la vida real, no distinguir entre identificador, valor y variable, uso
que nosotros seguiremos salvo cuando lleve a confusin: cuando decimos Jos
es simptico, en general queremos decir la persona cuyo nombre es Jos tiene
la cualidad de ser simptica, y no que el nombre en s es simptico, en cuyo
caso diramos el nombre Jos es simptico.
En Pascal no est predeterminado cmo se escribirn los enteros o reales a la
salida, y distintos compiladores ponen sus propios formatos, i.e., cuntos lugares
ocupa cada nmero escrito. Pero contamos con la opcin de especificar nosotros
mismos la cantidad de lugares, modificando lo establecido por el compilador.
Para usar esta opcin,(1) ponemos writeln(a:5) si queremos que el entero
a se escriba en exactamente 5 lugares (contando el eventual signo ). Si el
entero ocupara menos lugares, se ponen espacios en blanco a la izquierda. Si por
casualidad se necesitaran ms lugares, entonces se usarn los espacios necesarios,
de modo de no perder dgitos.
Para reales la cosa es parecida, pero algo distinta, ya que tenemos la parte
decimal o fraccionaria (la que viene despus de la coma decimal que para
nosotros es un punto). Si a es un nmero real, poniendo writeln(a:10) har
que a se escriba con exactamente 10 lugares, eventualmente poniendo espacios
a la izquierda si sobran lugares, u ocupando ms lugares si fuera necesario,
usando la notacin cientfica con exponentes y punto flotante. Pero si ponemos
writeln(a:10:5), entonces indicamos que queremos la notacin con punto fijo
en la que la parte decimal ocupa 5 lugares.
En realidad, las reglas son algo ms complejas, pero lo mejor es probar un
poco:
Problema 3.3 (Formatos de salida para nmeros). Modificar las instrucciones write y writeln del programa sumardos, experimentando con los
formatos de salida tanto con enteros como con reales.
$
3.3. Readln
Es un poco tedioso estar cambiando los valores en el programa fuente para
hacer los clculos. Mucho ms razonable es ingresar los datos a nuestro antojo:
Problema 3.4. El programa leerentero (pg. 144) lee un entero ingresado por
terminal y lo imprime. Observar la sintaxis e instrucciones, similares al programa
sumardos, la nica novedad es el uso de readln.
a) Compilar y ejecutar el programa, comprobando su funcionamiento.
b) Ingresar, en ejecuciones sucesivas del programa, los siguientes datos (lo que
est entre las comillas , pero sin las comillas) seguidos de <retorno>,
conservando los espacios intermedios cuando corresponda:
(1)
Pg. 15
Pg. 16
Pg. 17
Pg. 18
En la mquina slo pueden representarse un nmero finito de nmeros, ya sean enteros o reales. En
otras palabras, la gran mayora de los nmeros no se
pueden representar exactamente en la computadora.
Problema 3.9. Hacer un programa para imprimir el valor de maxint correspondiente al compilador que se usa: no declarar variables y poner el rengln
writeln( El entero mximo es: , maxint)
- En los compiladores ms viejos, maxint = 32767, pero en compiladores ms
recientes puede ser maxint = 2147483647.
$
Sea que las variables de tipo integer y real ocupen el mismo lugar o no,
su codificacin como cadenas de bits es bien distinta. Los enteros se representan
consecutivamente (del menor al mayor), mientras que para representar los nmeros reales se dividen los bits en dos grupos, uno representando la mantisa y
otro el exponente, como se hace en la notacin cientfica al escribir 0.123 1045
(0.123 es la mantisa y 45 el exponente en base 10, pero la computadora trabaja
en base 2).
La representacin de nmeros reales mediante mantisa y exponente hace que
a diferencia de lo que sucede con los nmeros enteros la distancia entre un
nmero real que se puede representar y el prximo vaya aumentando a medida
que sus valores absolutos aumentan. Esta propiedad de densidad variable trae
inconvenientes para el clculo aproximado, como veremos en el problema 4.17
y en la seccin 5.1.
- Para entender la densidad variable, puede pensarse que hay la misma
cantidad de nmeros representados entre 1 (inclusive) y 2 (exclusive) que
entre 2 y 4, o que entre 4 y 8, etc. Por ejemplo, si hubieran slo 4 puntos en
cada uno de estos intervalos, tendramos un grfico como el de la figura 3.3.
Por el contrario, hay tantos nmeros enteros representados entre 10
(inclusive) y 20 (exclusive), como entre 20 y 30, etc. Es decir, entre 20 y 40
hay el doble de nmeros enteros representados que entre 10 y 20. En este
caso, la densidad es constante.
1 2
Pg. 19
16
Pg. 20
x
x
x
x
x
x
x
x
x
n
n
n
:=
:=
:=
:=
:=
:=
:=
:=
:=
:=
:=
:=
3.7; n
3.7; n
3.5; n
3.7; n
3.5; n
3.7; n
3.5; n
3.7; n
3.5; n
maxint
maxint
maxint
:= x;
:= trunc(x);
:= trunc(x);
:= trunc(-x);
:= trunc(-x);
:= round(x);
:= round(x);
:= round(-x);
:= round(-x);
div 2; n := n * (n+1) / 2;
div 2; n := n * (n+1) div 2;
div 2; x := n * (n+1) / 2;
De aqu en ms supondremos que compilars y ejecutars cada programa mencionado en los problemas,
probndolo con distintos datos. En lo sucesivo, generalmente omitiremos esta consigna.
Pg. 21
1 = 2.
1 2.
1 < 2 < 3.
1 < 2 o 2 < 0.
{a, b, c} = {b, a, c}.
ii)
iv)
vi)
viii)
x)
1 > 2.
4 5 > 43 .
1 < 2 < 0.
1 = cos 1.
{0, 1, 2, 3} N.
<
Pascal
=
<>
>
>=
<
<=
Pascal
(a > 0) (b > 0)
(a > 0) (b > 0)
(a > 0)
pero la expresin matemtica a < b < c debe escribirse en Pascal como (a <
b) and (b < c). Tambin observamos que para preguntar si a 6= b en Pascal
puede ponerse tanto a <> b o como not (a = b), y de modo similar para
las desigualdades.
Pg. 22
3.7. Caracteres
As como la computadora guarda internamente los nmeros como ristras de
ceros y unos en la computadora, tambin las letras se guardan como ristras de
ceros y unos. La forma en que se hace esta codificacin depende del sistema
operativo, pero un cdigo particularmente usado es el ASCII con el que se convierten a nmeros entre 0 y 127 algunos caracteres: letras como a , b ,..., z
o A ,..., Z , nmeros (dgitos) como 0,1,...,9, y smbolos como + , $ , etc.
En ASCII, los caracteres imprimibles como letras y smbolos empiezan a partir de 32, pero no todas las letras estn representadas, como la o las vocales
acentuadas del castellano. A fin de codificar tambin estos caracteres, hay extensiones para cubrir caracteres con nmeros hasta 255, pero estas extensiones
no son del estndar ASCII y dependen en general del sistema operativo.
En Pascal, dado un carcter podemos encontrar su nmero de orden mediante ord y recprocamente, dado un entero podemos ver qu carcter le corresponde mediante la funcin chr.(3) El estndar Pascal establece que:
Los caracteres 0 , 1 ,..., 9 estn numricamente ordenados y son consecutivos, pero
las letras minsculas, a , b ,..., z , si bien estn ordenadas, no son necesariamente consecutivas!
y lo mismo para las letras maysculas.
Afortunadamente, el cdigo ASCII con el que trabajaremos satisface
estos requisitos, y ms an, las letras minsculas a ,..., z son consecutivas y
lo mismo para las maysculas.
Desafortunadamente, si bien para nosotros est entre n y o , esto no
es as en el cdigo ASCII, pues la letra ni siquiera est codificada. Ni qu
hablar de ch o ll, que se consideran (en cada caso) como dos caracteres distintos.
Todo esto puede traer problemas al clasificar u ordenar alfabticamente.
Si bien los digrafos ch ( che) y ll ( elle) son consideradas como letras
en el abecedario espaol desde 1803 (la cuarta y decimocuarta, respectivamente), y por lo tanto son indivisibles, en 1994 el dcimo congreso de la Asociacin
de Academias de la Lengua Espaola acord que para su alfabetizacin se consideren como letras separadas (c-h y l-l, respectivamente).
- Como ya mencionamos, no vamos a usar ch, ll, ni tildes en los datos que
ingresemos a nuestros programas.
(3)
Pg. 23
Captulo 4
Tomando control
Con las operaciones que hemos visto no podemos hacer mucho ms que lo
que hace una calculadora sencilla. Las cosas empiezan a ponerse interesantes
cuando disponemos de estructuras de control de flujo, esto es, instrucciones que
nos permiten tomar decisiones sobre si realizar o no determinadas instrucciones
o realizarlas repetidas veces.
Al disponer de estructuras de control, podremos verdaderamente comenzar a
describir algoritmos, es decir, instrucciones (no necesariamente en un lenguaje de
programacin) que nos permiten llegar a determinado resultado, y apuntar hacia
el principal objetivo de este curso: pensar en los algoritmos y cmo traducirlos
a un lenguaje de programacin.
Como es conocido, la palabra algoritmo deriva del nombre de Abu Jafar
Muhammad ibn Musa al-Khwarizmi.
Es interesante ubicar cronolgicamente a Al-Khwarizmi. Se presume que
naci alrededor de 780 en Bagdad (Irak), cuando Harun al-Rashid el califa
de Las mil y una noches comenzaba su califato, y muri en 850. Al-Mamun,
ho y sucesor de al-Rashid, continu la tradicin de su padre de patrocinar
las ciencias y fund la academia Casa del saber, a la que se incorpor AlKhwarizmi.
Al-Khwarizmi escribi y tradujo varios textos cientficos (de matemtica,
geografa, etc.) del griego al rabe. El ms importante de ellos es Hisab al-jabr
wal-muqabala, de donde surge la palabra lgebra con la que ahora designamos
a esa rama de la matemtica.
Tambin escribi un tratado sobre nmeros indo-arbigos que se ha perdido,
pero se conserv una traduccin al latn llamada Algoritmi de numero Indorum,
para indicar su autor, dando lugar a la palabra algoritmo.
4.1. If
Pg. 25
4.1. If
Supongamos que al cocinar decidimos bajar el fuego si el agua hierve, es decir
realizar cierta accin si se cumplen ciertos requisitos. Podramos esquematizar
esta decisin con la sentencia:
si el agua hierve entonces bajar el fuego.
A veces queremos realizar una accin si se cumplen ciertos requisitos y adems realizar una accin alternativa si no se cumplen. Por ejemplo, si para ir al
trabajo podemos tomar el colectivo o un taxi que es ms rpido pero ms caro que el colectivo dependiendo del tiempo que tengamos decidiramos tomar
uno u otro, que podramos esquematizar como:
si es temprano entonces tomar el colectivo en otro caso tomar el taxi.
En Pascal podemos tomar este tipo de decisiones, usando la construccin
if...then... para el esquema si...entonces..., mientras que para la variante si...entonces...en otro caso... usamos if...then...else... Por supuesto,
entre if y then tenemos que poner una condicin (una expresin lgica), llamada condicin de control que pueda evaluarse como verdadera o falsa.
Recordando que ; separa expresiones,
Problema 4.1.
a) Agregar el siguiente rengln al programa leerentero (pg. 144):
if (a > 10) then writeln(chr(7));
inmediatamente despus del rengln writeln(El entero...);.
Cul es el efecto de agregar este rengln?
b) Modificar el programa leerentero de modo que la computadora emita un
sonido cuando el nmero entrado es mayor que 0 y menor o igual a 10 (y
no haga nada en otro caso).
$
Problema 4.2. El valor absoluto para x R se define como
(
x
si x 0,
|x| =
x en otro caso.
El programa valorabsoluto (pg. 147) realiza este clculo. Observar en especial la estructura if...then...else... Qu pasa si se eliminan los parntesis despus del if ?, y si se cambia >= por > ?, y si se agrega ; antes
de else?
La funcin abs de Pascal hace el clculo del valor absoluto. Incorporarla al
programa y verificar que se obtienen los mismos resultados.
$
Problema 4.3. Hacer un programa que, dado un nmero real, encuentre su
piso y su techo.
Sugerencia: recordar el problema 3.13.
Sugerencia si la anterior no alcanza: usar algo como
Pg. 26
Tomando control
y := trunc(x); (* o round(x) *)
if (y >= x) then techo := y else techo := y + 1;
if (x >= y) then piso := y else piso := y - 1;
4.2. Begin-end
Pg. 27
Problema 4.8. Desarrollar un programa que, tomando como entrada un nmero natural entre 1 y 3000, lo escriba en romano (e.g., entrando 2999 se debe
obtener MMCMXCIX). Sugerencia: primero hacer un programa para tratar el
caso entre 1 y 30, y despus ir agregando posibilidades.
- Las letras usadas para nmeros romanos son I, V, X, L, C, D, M, correspondientes respectivamente a 1, 5, 10, 50, 100, 500, 1000.
- El problema es ciertamente tedioso para escribir, pero es tpico de muchas aplicaciones, en las que no hay atajos, o donde perdemos ms tiempo
tratando de encontrar un atajo que en escribir el programa.
$
4.2. Begin-end
A veces es conveniente y an necesario agrupar instrucciones, lo que en
Pascal se hace mediante begin...end como en la parte principal de todo
programa.
- La expresin end. (con punto) slo debe aparecer al final del programa
fuente.
Pg. 28
Tomando control
4.3. While
Pg. 29
iii) a = 2, b = 1, n = 1, z = 0;
iv) a = 2, b = 1, n = 1, z = 0;
c) Decir si el rengln es equivalente a:
i) if (n > 0) then begin
if (a > b) then z := a else z := b end;
ii) if (n > 0) then begin
if (a > b) then z := a end else z := b;
4.3. While
La estructura while es una estructura para realizar repetidas veces una
misma tarea. Junto con repeat y for que veremos ms adelante reciben
el nombre comn de lazos o bucles para indicar esta capacidad de repeticin.
Supongamos que voy al supermercado con cierto dinero para comprar la
mayor cantidad posible de botellas de cerveza. Podra ir calculando el dinero
que me va quedando a medida que pongo botellas en el carrito: cuando no
alcance para ms botellas, ir a la caja. Una forma de poner esquemticamente
esta accin es
mientras me alcanza el dinero, poner botellas en el carrito.
En Pascal, este esquema se realiza con la construccin while...do...,
donde do reemplaza a la , en la sentencia anterior, y entre while y do
debe ponerse una expresin lgica.
Observamos desde ya que:
Si la condicin no es cierta al comienzo, nunca se realiza la accin: si el
dinero inicial no me alcanza, no pongo ninguna botella en el carrito.
En cambio, si la condicin es cierta al principio, debe modificarse con
alguna accin posterior, ya que en otro caso llegamos a un lazo infinito,
que nunca termina.
Por ejemplo, si tomamos un nmero positivo y le sumamos 1, al resultado le sumamos 1, y as sucesivamente mientras los resultados sean
positivos. O si tomamos un nmero positivo y lo dividimos por 2, luego
otra vez por 2, etc. mientras el resultado sea positivo.
- Al menos en teora. Como veremos en los problemas 4.15 y 4.17, la
mquina tiene un comportamiento propio.
Por cierto, en el ejemplo de las botellas en el supermercado podramos realizar directamente el cociente entre el dinero disponible y el precio de cada botella,
en vez de realizar el lazo mientras. Es lo que vemos en el prximo problema:
Problema 4.11. El programa resto (pg. 148) calcula el resto de la divisin de
a N por b N mediante restas sucesivas.
a) Antes de compilar y ejecutar el programa, hacemos una prueba de escritorio.
Por ejemplo, si ingresamos a = 10 y b = 3, podramos hacer como se indica
en el cuadro 4.1, donde indicamos los pasos sucesivos que se van realizando
y los valores de las variables a, b y r (el ltimo valor que aparece es el
que tiene antes de ejecutarse el paso correspondiente). Podemos comprobar
entonces que los valores de a y b al terminar el programa son los valores
originales, mientras que r se modifica varias veces.
Pg. 30
Tomando control
Paso
0
1
2
3
4
5
6
7
8
9
10
11
accin
(antes de empezar)
leer a
leer b
r := a
r b: verdadero
r := r - b
r b: verdadero
r := r - b
r b: verdadero
r := r - b
r b: falso
imprimir r
sin valor
10
sin valor
sin valor
3
10
7
4
1
b) Hacer una prueba de escritorio con otros valores de a y b, por ejemplo con
0 < a < b (en cuyo caso la instruccin dentro del lazo while no se realiza).
c) Compilar y ejecutar el programa, verificando que coinciden los resultados
del programa y de las pruebas de escritorio.
d) Observar que es importante que a y b sean positivos: dar ejemplos de a y b
donde el lazo while no termina nunca (sin correr el programa!).
e) Modificar el programa para comparar el valor obtenido con el resultado de
la operacin a mod b.
f ) Vamos a modificar el programa de modo de contar el nmero de veces que
se realiza el lazo while. Para ello agregamos un contador k, declarado como
entero, que antes del lazo while se inicializa a 0 poniendo k := 0 y dentro
del lazo se incrementa en 1 con k := k + 1. Hacer estas modificaciones
(recordando usar begin...end dentro del lazo while), imprimiendo el
valor final de k antes de finalizar el programa.
g) Modificar el programa para calcular tambin el cociente de a por b, digamos
c, mediante c := a div b. Qu diferencia hay entre el cociente y el valor
obtenido en el inciso f )?, podras explicar por qu?
h) Hay algn ejemplo donde tenga sentido declarar alguna de las variables a, b
4.3. While
Pg. 31
n
X
i=1
i,
Pg. 32
Tomando control
que, segn la frmula de Gauss, es
sn =
n (n + 1)
.
2
c) Determinar cuntos ceros hay al final de la expresin decimal de 30!, y comparar con la cantidad de ceros que aparecen en el resultado del programa.
Sugerencia: contar las veces que 2 y 5 son factores de 30!.
- 30! tiene 33 cifras decimales.
$
Problema 4.15. Recordando que la suma y producto de enteros son enteros,
nos preguntamos si el siguiente programa termina o no:
program terminaono(input, output);
var i: integer;
begin
i := 1;
while (i * i <= maxint) do i := i + 1;
writeln(El i maximo es: , i);
writeln; writeln(** Fin **)
end.
4.4. Repeat
Pg. 33
4.4. Repeat
Si estando en casa queremos ir al bar caminando, podramos poner
repetir caminar hasta llegar.
esquema que en Pascal se pone como repeat...until...
La estructura repeat es muy similar a la de while. Observamos que en
while la condicin de control va al comienzo, mientras que en repeat va al
final. As, la principal diferencia es que la accin se realiza siempre al menos
una vez con repeat, mientras con while puede no realizarse si la condicin de
control es inicialmente falsa.
Otra diferencia, pero de carcter formal, es que para ejecutar varias instrucciones en un lazo while debemos agruparlas con begin...end, mientras que
en un lazo repeat no es necesario usar begin...end pues ya estn agrupadas
entre repeat y until.
Problema 4.16. El programa cifras (pg. 149) calcula la cantidad de cifras en
base 10 de un nmero entero, sin tener en cuenta el signo pero considerando
que el nmero 0 tiene una cifra.
a) Observar el uso del contador c, anlogo al usado en el problema 4.11.f ).
b) Para qu est el rengln if (a < 0) then b := -a else b := a;?
c) Cambiar el lazo repeat por otro while de modo que ahora se considere que
el nmero 0 tiene 0 cifras.
$
Los errores numricos al trabajar con el tipo real estn relacionados con
la representacin interna de este tipo, como ya observamos al mencionar la
densidad variable en la seccin 3.5.
En el prximo problema calculamos dos indicadores importantes de esta
propiedad: mn , el psilon mnimo, que es el menor nmero real potencia de
2 positivo que se puede representar; y mq , el psilon de mquina, que es el
menor nmero positivo potencia de 2 que sumado a 1 da mayor que 1.
Problema 4.17. El programa epsmin (pg. 150) calcula mn y mq . Debemos
destacar que en principio los resultados exhibidos son slo aproximaciones segn
la mquina a potencias de 2, puesto que en su clculo o en su impresin pueden
intervenir errores numricos.
a) Observar que mn mq . Esto permite que en el clculo de mq podamos
multiplicar por 2, pero no para calcular mn : ver qu sucede si para calcular
mn tomamos
Pg. 34
Tomando control
eps := 1;
repeat eps := eps/2 until (eps = 0);
eps := 2 * eps;
writeln(epsmin es: , eps);
b) Qu pasa si se calcula mq mediante
eps := 1;
repeat eps := eps/2 until (1 + eps = 1);
eps := 2 * eps;
writeln(epsmaq es: , eps);
?
- Es posible que los valores sean distintos, debido a la forma de trabajo
interna de la mquina.
Nunca deben compararse nmeros reales por igualdad sino por diferencias suficientemente pequeas!
- Esto est relacionado con la diferencia entre error absoluto y relativo, que
no estudiaremos en el curso. Ver tambin los comentarios despus del problema 5.11.
4.5. For
Hay veces que queremos repetir una accin un nmero fijo de veces. Por
ejemplo, al subir una escalera con 10 escalones haramos algo como
hacer 10 veces: subir un escaln.
En Pascal no existe una estructura que traduzca esta accin directamente.
En cambio, cuenta con una estructura un poco ms flexible que nos permite
imitarla: si contamos los escalones con el contador e, que variar entre 1 y
10, podramos poner el esquema
para e desde 1 a 10 hacer subir el e-simo escaln.
Este esquema se reproduce en Pascal (habiendo declarando e como de tipo
entero) con la estructura
for e := 1 to 10 do subir el e-simo escaln
que ciertamente podra cambiarse por un lazo while:
e := 1;
while (e <= 10) do begin
subir el e-simo escaln;
e := e + 1
end
4.5. For
Pg. 35
d) Agregar sentencias para considerar tambin el caso de n negativo. Sugerencia: ab = 1/ab , usar la funcin abs y/o condicional if.
e) Una variante de for...to...do..., que va incrementando la variable de
control usada de a 1, es usar for...downto...do..., que va disminuyndola en 1 en cada paso.
Cambiar el rengln
for i := 1 to n do pot := pot * x;
por el siguiente:
for i := n downto 1 do pot := pot * x;
y verificar que el comportamiento es el mismo. Observar que con downto
el valor inicial debe ser mayor o igual que el valor final para que se realice
algn paso.
f ) Algunos compiladores admiten la operacin x ** y, que no es del estndar Pascal, para el clculo de la potencia xy (x R+ , y R). Verificar si
el compilador usado admite esta sentencia y, en caso afirmativo, comparar
con el resultado anterior cuando y N.
g) Otra forma de calcular la potencia en general es usar xy = eyln x . Incorporar esta frmula al programa para comparar con los resultados anteriores.
- Es posible que difieran debido a errores numricos.
- La frmula xy = eyln x se puede usar cuando y no es entero. Por
otro lado, cuando x e y son ambos enteros, seguramente tendremos
problemas de aproximacin al usarla.
$
Muchos de los problemas que hemos visto usando while o repeat pueden
hacerse con for con modificaciones sencillas, observando que para considerar
Pg. 36
Tomando control
valores descendientes con for, se debe usar downto en vez de to. Por ejemplo,
en el programa gauss (pg. 149) el lazo
while (n > 0) do begin suma := suma + n; n := n-1 end;
podra reemplazarse por el lazo
for i := n downto 1 do suma := suma + i;
donde la variable i es de tipo entero.
Sin embargo, no siempre se puede o es sencillo usar for, en particular, si no
sabemos de antemano cuntas veces debemos realizar el lazo.
Problema 4.19.
a) Modificar los programas tablaseno1 (pg. 148) y gauss (pg. 149) cambiando
el lazo while por uno for.
b) Podra cambiarse el lazo while por uno for en el programa resto (problema 4.11)?, y el lazo repeat por uno for en el programa epsmin (problema 4.17)?
$
Tampoco la solucin del problema anterior es del todo satisfactoria. Es tediosa cuando hay muchos datos, y por prudencia deberamos volver a preguntar por
s/no si se ingresa algo que no sea s o n , lo que complica la programacin.
- Pero volveremos a esta idea en captulos posteriores.
Problema 4.23. El programa eolnprueba (pg. 151) es una prueba del funcionamiento de eoln, en el que se usa la variable a para entender el flujo de las
instrucciones.
a) Compilar y ejecutar el programa, observando que luego de imprimir el valor
de a antes del lazo, queda a la espera del ingreso de datos:
i) Ingresar <retorno>, sin otros caracteres, y observar el valor final de a.
Cules de las instrucciones en if se ejecutaron?, qu valor ha dado
eoln y por qu?
Pg. 37
Pg. 38
Tomando control
ii) Si en vez de ingresar slo <retorno>, se ingresa <retorno> (con un
espacio antes), cul ser el valor de a que se imprime al final? Verificar
la respuesta ejecutando el programa con esa entrada.
b) Despus del rengln writeln(Ahora el valor... agregar los renglones
write(Entrar un nuevo valor de a (entero): );
readln(a);
writeln(El valor final de a es , a);
i) Ejecutar el programa e ingresar <retorno> y 3<retorno> (con un 3
antes), cules son los valores sucesivos de a?, por qu?
ii) Si en la nueva variante ingresamos 4<retorno> (con un 4 antes) y
luego 5<retorno> (con un 5 antes), cules son los valores sucesivos
$
de a?, por qu?
Problema 4.24. En el programa eco (pg. 151) se hace un eco (echo en ingls) por pantalla de cada dato ingresado: cada vez que ingresamos un dato, se
imprime.
En este programa, slo se dan instrucciones al principio de cmo ingresar los
datos, no se pone un nuevo cartel para cada dato, y se termina la entrada de
datos ingresando un <retorno> sin dato.
a) Observar el uso de eoln para detectar que se ha entrado un <retorno> sin
dato, dando por finalizada la lectura de datos.
b) Qu pasa si se ingresa como dato 1?, y 1 ?
c) Qu pasa si en el programa fuente se agrega readln; al terminar el lazo
while?
d) Modificarlo para leer nmeros reales.
e) Modificarlo para leer caracteres. Qu pasa si se ingresa abc como uno de
los datos?
f ) Modificarlo para que al final imprima la cantidad de datos ingresados. $
Problema 4.25. El programa sumardatos (pg. 152) calcula la suma de nmeros reales entrados por terminal, finalizando la entrada de datos con <retorno>
sin dato. A diferencia del programa eco (pg. 151), se pone un cartel para cada
dato.
a) Observar las diferencias entre los programas eco y sumardatos.
b) Observar el uso de eoln para detectar que se ha entrado un <retorno> sin
dato, y el uso de readln para leer el fin de lnea que ha quedado. Qu
pasa si se elimina este readln?
c) Modificar el programa para que a la salida indique tambin la cantidad de
datos ingresados.
d) Modificar el programa para que tambin indique el promedio de los datos
entrados.
- El promedio debe ser una variable de tipo real, y no entera.
4.7. Read
Pg. 39
Y por
while (not eoln) do begin
write(Entrar un dato (fin = <retorno>): );
readln(x); s := s + x
end
?
Explicar en cada caso, eventualmente haciendo un programa para verificar
$
que las respuestas son correctas.
4.7. Read
Cuando queremos ingresar varios nmeros por la consola, no est mal ingresar uno por rengln como hemos hecho hasta ahora. Es posible poner una
instruccin como readln(a,b,c) para leer los nmeros a, b y c, que si se ingresan en un mismo rengln deben separarse por uno o ms espacios (la mquina
no puede saber si cuando ponemos 123 queremos poner 1 y 23 o 1, 2, 3, etc.),
pero no hay mucha diferencia para el usuario entre ingresar un espacio en blanco
( ) o un <retorno>.
Ms complicado es si queremos entrar un texto con varias palabras, ya que
no sera muy razonable entrar un carcter por rengln. En estos casos viene a
nuestro auxilio la funcin read: read(a) lee la variable a, sin importar si se
ha llegado a fin de lnea o no. Como ya mencionamos, para leer el fin de lnea
debemos usar readln sin argumentos.
- Claro que no se lee nada hasta que no hayamos ingresado <retorno>,
dndonos la posibilidad de modificar la entrada si hemos cometido algn
error.
- Recordar el problema 3.4.b). Si pusiramos readln(c), leeramos c y se
ignoraran los restantes caracteres hasta el fin de lnea.
en las 23 variables x1
Pg. 40
Tomando control
Problema 4.28. Modificar el programa eco (pg. 151) con las ideas del programa palabras (pg. 152), para hacer un eco de los renglones ingresados. $
Problema 4.29. Hacer un programa que dado un nmero romano, entre 1 y
3000 como en el problema 4.8, lo escriba como nmero en base 10. Sugerencia:
usar las ideas del programa palabras del problema 4.27, pero leyendo un nico
rengln.
$
Captulo 5
Aplicaciones
En este captulo mostramos que se pueden hacer bastantes matemticas con
los recursos de programacin que hemos visto.
Hn = 1 +
(1)
!!!
X1
1 1
1
+ + + =
.
2 3
n
i
i=1
Pg. 42
Aplicaciones
As, H1 = 1, H2 = 3/2, H3 = 11/6, H4 = 25/12, H5 = 137/60.
a) Desarrollar un programa (siguiendo las ideas del problema 4.13 sobre suma
de Gauss), para calcular Hn aproximadamente.
b) En este caso particular, puede demostrarse que es ms preciso hacer la
suma de atrs hacia adelante que de adelante hacia atrs. Comprobar
que para n grande difieren los resultados realizando las sumas en estas dos
formas.
c) En los cursos de anlisis o clculo matemtico se ve que a medida que n
crece, Hn crece indefinidamente como ln n.
Ver que efectivamente la diferencia Hn ln n es aproximadamente constante para valores grandes de n (esta constante es la constante de Euler
= 0.5772156649 . . .), por ejemplo calculando las diferencias para n =
100, 1 000, 10 000.
Leonhard Euler (17071783) fue uno de los ms grandes y prolficos
matemticos, y muchas de las cosas que vemos estn relacionadas con su
nombre. Hizo contribuciones fundamentales en anlisis, teora de nmeros,
teora de grafos, la topologa, etc. La constante de Euler es relativamente
una contribucin menor.
Fue tan grande la influencia de Euler en las matemticas que se unificaron notaciones que el ide, como
la de (= 3.14159 . . .), del griego perypheria o circunferencia; i (= 1) por imaginario; y e (= 2.71828 . . .), del
$
alemn einhalt o unidad.
El siguiente problema muestra algunos de los inconvenientes al restar cantidades grandes y similares.
Problema 5.3 (Problemas numricos en la ecuacin cuadrtica). Como
es sabido, la ecuacin cuadrtica
ax2 + bx + c = 0
(5.1)
b + d
x1 =
2a
x2 =
b d
.
2a
(5.2)
El siguiente problema muestra dificultades no slo computacionales sino tambin matemticas al considerar una sucesin que se aproxima a 1 pero que es
elevada a potencias cada vez ms grandes.
Problema 5.4. Consideremos la sucesin
1 n
an = 1 +
para n N.
n
a) Hacer un programa para generar an dado n (de qu tipos sern n y an ?),
y usarlo para varios valores de n. En base a la experiencia, podras decir
que an es creciente (i.e., si an < an+1 para todo n N) o decreciente?
b) En los cursos de clculo o anlisis matemtico se demuestra que a medida
que n aumenta, an se parece cada vez ms a e = 2.718 281 828 459 . . .
Modificar el programa del inciso anterior para ver este comportamiento,
donde el usuario entra la tolerancia deseada, e.g., = 0.001, y el programa
dice el primer valor de n para el cual |an e| < .
- Para valores de pequeos, es muy posible que n supere maxint, por
lo que hay que tener cuidado en la implementacin.
$
x (= x1/2 ).
|
{z
}
n races
Pg. 43
Pg. 44
Aplicaciones
b) Ejecutar el programa para distintos valores de x positivo, y n ms o menos
grande dependiendo de x. Qu se observa?
$
Como habrs comprobado en el problema anterior, a medida que aumentamos el nmero de iteraciones, i.e., el valor de n, nos aproximamos cada vez ms
a 1. Por supuesto que si empezamos
con x = 1, obtendremos siempre el mismo
(
x sen 1/x si x 6= 0,
f (x) =
0
si x = 0
pues cerca de x = 0 oscila demasiado,
y hay funciones que no son continuas como
signo(x) para x R, pues pega un salto en x = 0,
la funcin de Dirichlet,
(
1 si x Q,
f (x) =
0 si x R \ Q,
una funcin imposible de visualizar.
Pg. 45
y
y=x
1
0.5
y = cos x
x
0.5
1.5
para n = 0, 1, 2, . . .,
0.5
x
0.5
1.5
Pg. 46
Aplicaciones
Sugerencia: cambiar el lazo for a uno while o repeat.
Sugerencia si la anterior no alcanza: si x0 es el dato inicial y n el nmero
mximo de iteraciones, usando repeat podramos poner:
k := 0; y := x0;
repeat k := k + 1; x := y; y := cos(x)
until ((k >= n) or (abs(y - x) < eps))
- Observar que la condicin |xk+1 xk | < es idntica a |f (xk )xk | < . $
Pg. 47
seccin es una versin actualizada de una tcnica usada por los babilonios hace
miles de aos para aproximar a la raz cuadrada.
El mtodo resulta ser un caso particular de otro desarrollado por Newton
para funciones mucho ms generales. La idea de Newton es que si x es una raz
de la funcin derivable f , y x es un punto prximo a x , tendremos
f (x ) = 0 f (x) + f 0 (x) (x x),
y despejando x , suponiendo f 0 (x) 6= 0, queda
x x
f (x)
.
f 0 (x)
f (xn )
f 0 (xn )
para n = 0, 1, . . . ,
(5.3)
1
a
xn1 +
2
xn1
para n = 1, 2, . . . ,
(5.4)
a partir de un valor inicial x0 dado (x0 > 0). Es decir xn = ga (xn1 ), donde
ga : R+ R+ est definida como
ga (x) =
1
a
x+
.
2
x
Pg. 48
Aplicaciones
que es el nmero
Pg. 49
n
X
(2k 1).
k=1
Cuando a, b Z, definimos
mcd(a, b) = mcd(|a|, |b|)
y
mcd(0, z) = mcd(z, 0) = |z|
para todo z Z, z 6= 0.
Pg. 50
Aplicaciones
Sin embargo, la factorizacin en primos es computacionalmente difcil, y en
general bastante menos eficiente que el algoritmo de Euclides, que an despus
de 2000 aos, es el ms indicado (con pocas variantes) para calcular el mximo
comn divisor.
Euclides (alrededor de 325265 a.C., aunque hay discusin sobre si se trata
de una persona o un grupo) escribi una serie de libros de enorme influencia en
las matemticas, inclusive en las actuales. En la proposicin 1 del libro VII, se
enuncia:
Dados dos nmeros distintos, y restando sucesiva y continuamente
el menor del mayor, si el nmero que queda nunca mide el anterior a
l hasta que queda una unidad, los nmeros originales sern primos
entre s.
Y en la proposicin 2,
Dados dos nmeros y no primos entre s, encontrar su mxima medida comn.
procediendo a construirlo. En lenguaje moderno, nos dice que para encontrar
el mximo comn divisor, la mxima medida comn, entre a y b, debemos
restar el menor del mayor hasta que los dos sean iguales.
- En los tiempos de Euclides se pensaba en nmeros como longitudes de
segmentos, y la multiplicacin de nmeros como un rea.
Un poco antesde Euclides, con Pitgoras y el descubrimiento de la
irracionalidad de 2, surgi el problema de la conmensurabilidad de segmentos, es decir si dados dos segmentos de longitudes a y b existe otro de
longitud c tal que a y b son mltiplos enteros
de c, i.e., c es la mxima
Pg. 51
Problema 5.14. Pablito y su pap caminan juntos tomados de la mano. Pablito camina 2 metros en exactamente 5 pasos, mientras que su padre lo hace en
exactamente 3 pasos. Si empiezan a caminar juntos, cuntos metros recorrern
hasta marcar nuevamente el paso juntos?, y si el padre caminara 2 12 metros
en 3 pasos? Aclaracin: Se pregunta si habiendo en algn momento apoyado simultneamente los pies izquierdos, cuntos metros despus volvern a apoyarlos
simultneamente.
- Recordando el tema de la conmensurabilidad mencionado al introducir el
algoritmo de Euclides, no siempre el problema tiene
solucin. Por ejemplo,
si Pablito hace 1 metro cada 2 pasos y el pap 2 metros cada 2 pasos.
$
Pg. 52
Aplicaciones
Pg. 53
Tries
0
0
1
3
Tries convertidos
0
3
1
0
Penales
7
0
3
2
f2 = 1,
para n 3.
fn = fn1 + fn2
(5.5)
(1 +
5) (1
2n 5
5)
(5.6)
Pg. 54
Aplicaciones
e) Comparar el nmero de Fibonacci fn con el redondeo (round) de
n
(1 + 5)
.
2n 5
A partir de qu n son iguales?, podras decir por qu?
(3)
Captulo 6
Arreglos
A veces queremos tener muchas variables del mismo tipo, por ejemplo una
lista de los 10 primeros cuadrados perfectos,
1, 4, 9, 16, 25, 36, 49, 64, 81, 100.
(6.1)
Escribir un nombre para cada una de las variables ya sera engorroso, pero
qu pasa si ahora el problema requiere una lista de 100 o 1000 en vez de 10
datos? Para guardar los datos en casos como ste, es conveniente pensar una
estructura similar a la de vector, como en otras ramas de la matemtica o la
fsica, y que representamos como v = (v1 , v2 , . . . , vn ). En programacin, esta
estructura se llama arreglo (unidimensional).
Por ejemplo, podramos guardar los nmeros de (6.1) en el vector o arreglo
v = (v1 , v2 , . . . , v10 ) donde
v1 = 1,
v6 = 36,
v2 = 4,
v7 = 49,
v3 = 9,
v8 = 64,
v4 = 16,
v9 = 81,
v5 = 25,
v10 = 100.
Pg. 56
Arreglos
1
v[1]
4
9
v[2] v[3]
16
v[4]
25
36
49
64
81
100
v[5] v[6] v[7] v[8] v[9] v[10]
Pg. 57
Pg. 58
Arreglos
de dato a ingresar es uno ms que el nmero de datos ya ingresado, se
mantiene ndatos adelantado en 1, y al terminar se lo retrocede.
El programa decide con un lazo repeat si x es o no un elemento del arreglo
recorriendo el arreglo linealmente, es decir comparando sucesivamente
a1 , a2 , . . . , andatos con x, terminando cuando se encuentra coincidencia o
cuando se han analizado todos los elementos.
a) Sin embargo, al ingresar datos no se verifica si el nmero de datos ledo es
ya MAXN . Modificar el lazo de modo de que esa constante sea tenida en
cuenta (impidiendo que se entren ms de MAXN datos).
b) Manteniendo la modificacin anterior, cambiar el programa para que en vez
de ingresar un arreglo de longitud mxima 20, se pueda ingresar un arreglo
de longitud mxima 50. Sugerencia: slo habr que cambiar un nmero.
c) Observar que en la impresin del arreglo inicial se usa la funcin mod para
imprimir un mximo de 5 datos por rengln.
i) Por qu se pone el rengln
if ((ndatos mod 5) <> 0) then writeln;
ii) El 5 que indica la cantidad de datos por rengln se usa en dos lugares,
de modo que si se cambia el 5 por otro nmero, hay que acordarse de
cambiar ambos.
Definir la constante maxrenglon al principio del programa para eliminar este problema.
iii) Ahora modificar el programa de modo de imprimir 8 datos por rengln
como mximo, cambiando el programa en un nico lugar.
d) Para buscar x en el arreglo, se usa un lazo repeat. Cambiarlo por uno while
(y que el programa siga funcionando correctamente!).
e) Cambiar el lazo principal de modo que, de estar x en el arreglo, se obtenga
el ltimo ndice i tal que ai = x, en vez del primero como hace el programa.
Sugerencia: empezar recorriendo desde atrs.
f ) Podra cambiarse la ltima parte del programa original por
(* lazo principal *)
i := ndatos;
while ((a[i] <> x) and (i > 1)) do i := i - 1;
(* resultados *)
if (x <> a[i]) then writeln(no se encontro)
else writeln(se encontro en el lugar , i:1); ?
En caso negativo, decir por qu no, y en caso afirmativo, qu ventajas
y desventajas tendra. Sugerencia: cul es el ltimo valor de i si x no est
en el arreglo?
g) Modificar el lazo principal de modo que al terminar el programa diga cuntas
veces aparece x en el arreglo, y los ndices correspondientes (i.e., los i para
los cuales ai = x).
- Observar que el lazo principal cambia sustancialmente.
6.3. Polinomios
Pg. 59
veces := veces + 1;
indice[veces] := i
end;
y luego imprimir el arreglo indice (entre 1 y veces si veces > 0). Observar
que en esta variante no es necesaria la variable seencontro.
$
Problema 6.4.
a) Hacer un programa que dado el arreglo a = (a1 , a2 , . . . , an ) de enteros,
encuentre el mximo. Por ejemplo, si a = (1, 3, 2, 3, 1, 0), el mximo es
3.
b) Modificarlo para que tambin encuentre el primer lugar donde aparece el
mximo. En el ejemplo anterior, el primer ndice es 2.
c) Modificarlo para que imprima todos los lugares donde aparece el mximo.
$
En el ejemplo, el mximo es 3 y aparece en los lugares 2 y 4.
Problema 6.5. Hacer un programa que dados los arreglos a = (a1 , a2 , . . . , am )
y b = (b1 , b2 , . . . , bn ) de enteros (ambos dimensionados por MAXN ), forme un
tercer arreglo c = (c1 , c2 , . . . , cm+n ) (dimensionado por 2 MAXN ), consistente
en los elementos de a seguidos por los de b.
Por ejemplo, si a = (1, 3, 5, 3) y b = (7, 1, 5, 8, 3), tendremos m = 4, n = 5, y
$
c = (1, 3, 5, 3, 7, 1, 5, 8, 3).
Problema 6.6. Hacer un programa para purgar el arreglo de enteros a ingresado, i.e., eliminar los elementos repetidos.
Por ejemplo, si inicialmente a = (3, 5, 2, 6, 2, 1, 3, 2), al final del programa
debe ser a = (3, 5, 2, 6, 1). Sugerencia: buscar cada elemento entre los ya
$
puestos para decidir si agregarlo o no.
6.3. Polinomios
Los polinomios son las funciones ms sencillas que podemos considerar, para
su clculo slo se necesitan sumas y productos. Adems los usamos diariamente,
por ejemplo un nmero en base 10 es en realidad un polinomio evaluado en 10.
Pero tambin los polinomios sirven para aproximar tanto como se desee a
casi cualquier funcin, lo que constituye un tema central de las matemticas,
y se estudia tanto en los cursos tericos de anlisis matemtico como en los
aplicados de anlisis numrico.
A modo de ejemplo visual, en la figura 6.2 mostramos cmo se podra aproximar a la funcin sen x para x cercano a 0, mediante los denominados polinomios interpoladores de Lagrange, tomando los valores del seno en los puntos
x = 0, /4, /2 y . Como se puede apreciar, cerca de x = 0 se obtiene una muy
buena aproximacin. Tratamos este ejemplo con ms detalle en el problema 6.8.
1
0.5
Pg. 60
Arreglos
Problema 6.7 (Evaluacin de Polinomios). Hacer un programa que dada
una lista de coeficientes (reales) de un polinomio, (a0 , a1 , a2 , . . . , an ) y un nmero
x R, entrados por terminal, evale el polinomio an xn + an1 xn1 +
+ a1 x + a0 .
Hacerlo de tres formas:
a) Calculando la suma de trminos como se indica, calculando xk como en el
problema 4.18.
b) Como el anterior, pero las potencias en la forma xk+1 = xk x, guardando
xk en cada paso.
c) Usando la regla de Horner
(( ((an x + an1 ) x + an2 ) + ) x + a1 ) x + a0 .
- En las dos primeras versiones se hacen n sumas, n productos y se calculan
n 1 potencias, que en la primera versin representan otros 1 + 2 + +
(n 1) = n(n 1)/2 productos, mientras que en la segunda, los productos
provenientes de las potencias se reducen a n 1. Finalmente, en la regla
de Horner, tenemos slo n sumas y n productos.
William George Horner (17861837) fue indudablemente una persona muy
capaz: a los 18 aos era director de la escuela Kingswood (en Bristol, Inglaterra). Sin embargo, sus contribuciones matemticas no han sido demasiadas, y
conservamos el nombre de regla de Horner pues De Morgan la denomin as y
le dio amplia difusin en los muchos artculos que escribi. De todos modos, el
mtodo era conocido por Zhu Shie unos 500 aos antes.
$
n+1
X
i=1
yi
Y x xj
.
xi xj
(6.2)
j6=i
a) Ver que efectivamente, P (x) definido por la ecuacin (6.2) satisface P (xi ) =
yi para i = 1, . . . , n + 1.
b) Desarrollar un procedimiento para evaluar P (x) dado por la ecuacin (6.2),
donde los datos son (xi , yi ), 1 i n + 1, y x. Aclaracin: slo se pide una
traduccin literal de la ecuacin (6.2).
c) Utilizarlo en un programa que calcule los coeficientes del polinomio de grado
a lo sumo 3 que pasa por los puntos (1, 0), (0, 1), (1, 0), (2, 2), en el punto
x = 2.
6.3. Polinomios
Pg. 61
d) Ampliar el programa para calcular una aproximacin de sen /4, usando los
valores del seno para 0, /6, /2 y .
- Como mencionamos en el problema 4.12, es usual poner = 4
arctan 1, aunque en este problema en particular no se necesita un valor
especfico de (considerar la funcin sen x en vez de sen x).
k
X
ai bi ,
donde ai Z y 0 ai < b,
(6.3)
i=0
Captulo 7
Funciones y Procedimientos
Nuestros programas se han hecho cada vez ms largos, y a medida que avancemos lo sern an ms. La longitud y complejidad de los programas profesionales es tal que una sola persona no puede siquiera escribirlos completamente.
A fin de abordar esta dificultad, se han desarrollado una serie de tcnicas, y
en este captulo daremos los primeros pasos hacia una de ellas, la modularizacin,
para lo cual Pascal cuenta con dos mecanismos: funciones y procedimientos.
Aunque la ventaja de usar funciones o procedimientos ir quedando ms
clara con los ejemplos que veremos en ste y otros captulos, podemos decir que
en general son convenientes para:
poner en un nico lugar clculos idnticos que se realizan en distintas
partes del programa,
o poner por separado alguna accin permitiendo su fcil reemplazo (y con
menor posibilidad de error),
y no menos importante, haciendo el programa ms fcil de entender,
dejando una visin ms global y no tan detallada en cada parte (viendo
el bosque y no el rbol).
Seguramente recordars el uso que con el mismo espritu hemos dado a
const, por ejemplo en el problema 6.3, para hacer un nico cambio que afecta
a varias partes del programa.
7.1. Funciones
Como hemos visto, Pascal cuenta con una serie de funciones pre-definidas,
como cos o ln, de una variable, o la suma, +, que se aplica a dos o ms
variables. Pero necesariamente no puede tener todas las funciones y slo
algunas se han incluido. Por ejemplo, la potencia xn (x R y n N) no est
incluida en Pascal, pero hemos hecho su clculo en el problema 4.18.
Supongamos que queremos hacer un programa para comparar los valores xn
m
y y , donde x, y R y n, m N son datos ingresados por el usuario. Nuestro
programa tendra los siguientes pasos:
1.
2.
3.
4.
7.1. Funciones
Pg. 63
Claro que si contramos con una funcin de Pascal para calcular xn para x
R y n N, digamos potencia(x,n), podramos reemplazar los dos renglones
anteriores por
xn := potencia(x,n); ym := potencia(y,m);
Aunque Pascal no cuenta con una funcin que realice este clculo, nos da un
mecanismo para definirla nosotros.
En Pascal, las funciones (y procedimientos que veremos en un rato) se declaran en la parte declarativa(1) del programa, formando un bloque de estructura
similar a la de los programas.
Por ejemplo, para definir la funcin potencia (2) pondramos antes del cuerpo
principal del programa,
function potencia(a: real; b: integer): real;
var k: integer; z: real;
begin
z := 1;
for k := 1 to b do z := z * a;
potencia := z
end;
Observamos que
Se comienza con el nombre de la funcin, anteponiendo function (o
procedure para procedimientos) en vez de program, luego una parte
de declaraciones propias, y despus un cuerpo principal encerrado entre
begin y end; (con ; en vez de . porque no es el final del programa).
Los argumentos de la funcin deben ser declarados. En nuestro ejemplo
hay dos argumentos, a, de tipo real, y b, de tipo integer. Por supuesto,
el orden de los argumentos es importante: 23 6= 32 .
Las funciones en Pascal calculan un valor de alguno de los tipos elementales boolean, char, integer o real.
- Tambin podran ser de tipo puntero, que no veremos en este curso.
Segn el estndar no deben ser de otro tipo, como arreglos, aunque
muchos compiladores lo permiten.
El tipo del valor calculado debe ser declarado, lo que se hace colocando : luego de la declaracin de argumentos. En nuestro ejemplo, el
resultado es de tipo real.
Decimos que la funcin devuelve o retorna el valor calculado.
Dentro del bloque correspondiente a la funcin, el nombre de sta debe
ser asignado, y ser el valor retornado a otras partes del programa.
(1)
Pg. 64
Funciones y Procedimientos
En estos casos decimos que el programa llama (en ingls call) o invoca
a la funcin. Por ejemplo, con la instruccin
xn := potencia(x,n)
estamos llamando a la funcin potencia y asignando el resultado a xn.
Problema 7.2. En el programa potencias (pg. 157) hemos incorporado la
funcin potencia. Leerlo, estudiando las distintas instrucciones, y ejecutarlo.
Observemos que la variable k no est definida al comienzo del programa,
sino slo en la funcin potencia: es local a la funcin pero desconocida para
el resto del programa.
a) Incluir el rengln
writeln( El valor de k es: , k:1);
inmediatamente antes del cartel final del programa. El compilador seguramente rechazar esta accin pues k no est declarada.
b) Manteniendo el rengln problemtico, incluir una declaracin de k al principio del programa (fuera de la funcin), y hacer la asignacin k := 1 antes
del rengln del inciso anterior. Compilar y ejecutar nuevamente el programa,
observando que ahora no hay inconvenientes.
c) Repetir los pasos anteriores cambiando k por z , comprobando que z vive
slo dentro de la funcin.
Al declarar la funcin, los argumentos a y b se separan con ;, pero al
llamar la funcin se separan con ,: potencia(x,n).
d) Cambiar ; por , en la declaracin de la funcin, i.e., poner
function potencia(a: real, b: integer): real;
y comprobar que el compilador no acepta el cambio.
e) De modo similar, cambiar xn := potencia(x,n); por
xn := potencia(x;n);
y comprobar que este cambio tampoco es aceptado.
- Sin embargo, si dos o ms argumentos consecutivos son del mismo tipo,
podemos separarlos con una coma juntando las declaraciones. Para ejemplificar, si a y b son de tipo real, podemos declarar tanto
function f(a: real; b: real):...
7.1. Funciones
Pg. 65
como
function f(a, b: real):...
Es decir, el uso es similar a las , que se usan al declarar variables
con var. Veremos un ejemplo en el problema 7.7.
Las variables que son argumentos de la funcin tambin son locales a ella,
y es posible que coincidan con los nombres de otras variables del programa,
llamadas globales.
f ) Cambiar la definicin de la funcin a
function potencia(x: real; n: integer): real;
var k: integer; z: real;
begin
z := 1;
for k := 1 to n do z := z * x;
potencia := z
end;
y comprobar (compilando y ejecutando el programa) que el comportamiento
es el mismo.
La localidad de los argumentos tambin se traduce en que podemos modificarlos dentro de la funcin, sin modificar otras variables con el mismo
identificador del programa.
f ) Por ejemplo, cambiar la declaracin de la funcin poniendo
function potencia(x: real; n: integer): real;
var z: real;
begin
z := 1;
while (n > 0) do begin
z := x * z; n := n - 1 end;
potencia := z
end;
El valor final de z es el mismo en uno u otro caso, pero el valor de la
variable n (local a la funcin) se va modificando con la nueva definicin.
g) Ejecutar el programa, y verificar que sin embargo, el valor de n que se
imprime al final es el mismo que el ingresado inicialmente: corresponde a la
variable global n, y no a la variable n local a la funcin.
- Si bien podemos poner cualquier identificador a los argumentos, no
deben ser los mismos que las otras variables locales a la funcin. Por
ejemplo no debemos poner
function potencia(x: real; n: integer): real;
var k: integer; x: real;
.
.
.
Pg. 66
Funciones y Procedimientos
?
end;
a = a0
c0 = a1 = a2
c1 = b2
b = b0 = b1
c2
Figura 7.1: Una funcin continua con distintos signos en los extremos.
En el mtodo de la biseccin se comienza tomando a0 = a y b0 = b, y para
i = 0, 1, 2, . . . se va dividiendo sucesivamente en dos el intervalo [ai , bi ] tomando
el punto medio ci , y considerando como nuevo intervalo [ai+1 , bi+1 ] al intervalo
[ai , ci ] o [ci , bi ], manteniendo la propiedad que en los extremos los signos de f
son opuestos (que podemos expresar como f (ai )f (bi ) < 0). Se finaliza cuando
se obtiene un valor de x tal que |f (x)| es suficientemente chico, |f (x)| < y , o
se han realizado un mximo de iteraciones, condiciones que llamamos criterios
de parada.
- Recordando la filosofa de comparar papas con manzanas, el valor y a
poner depender del problema que se trate de resolver.
- Tambin en este sentido, observamos que 210 = 1 024 103 y 220 =
1 048 576 106 , por lo que el intervalo inicial se divide aproximadamente
en 1000 despus de 10 iteraciones y en 1 000 000 = 106 despus de 20 iteraciones. Es decir, despus de 10 iteraciones el intervalo mide el 0.1 % del
intervalo original, y despus de 20 iteraciones mide el 0.0001 % del intervalo
original. No tiene mucho sentido considerar mucho ms de 10 iteraciones en
este mtodo, salvo que los datos originales y la funcin f puedan calcularse
con mucha precisin.
Problema 7.3 (Mtodo de la biseccin para encontrar races). El programa biseccion (pg. 158) utiliza el mtodo de biseccin para encontrar races
en el caso particular
f (x) = x(x + 1)(x + 2)(x 4/3).
(3)
Pg. 67
Pg. 68
Funciones y Procedimientos
f ) Agregar tambin la impresin de carteles apropiados cuando f (poco)
f (mucho) 0 y no se est en las condiciones del inciso anterior.
g) El programa no verifica si poco < mucho, y podra suceder que poco >
mucho. Tiene esto importancia?
h) Teniendo en cuenta las notas al principio de la seccin, tendra sentido
agregar al programa un criterio de modo de parar si los extremos del intervalo estn suficientemente cerca? Si la nueva tolerancia fuera x , cuntas
iteraciones deben realizarse para alcanzarla, en trminos de x y los valores
originales de mucho y poco?
i) Modificar el programa de modo que en vez de considerar hasta un mximo
de iteraciones, el programa termine cuando o bien se ha encontrado x tal que
|f (x)| < y o bien se llega a poco y mucho de modo que |poco mucho| <
$
x .
El mtodo de la biseccin es bien general y permite encontrar las races de
muchas funciones. Al programarlo, hemos separado la declaracin de la funcin
f de modo de poder cambiarla fcilmente segn la aplicacin, sin necesidad de
recorrer todo el programa buscando las apariciones de f (habr, s, que cambiar
tambin los carteles iniciales).
Problema 7.4. Cambiar la definicin de la funcin en el programa biseccion,
para responder a los siguientes ejemplos (hacer primero un bosquejo del grfico
para estimar valores iniciales de poco y mucho):
a) Resolver aproximadamente las ecuaciones:
i) x2 5x + 2 = 0,
ii) x3 x2 2x + 2 = 0.
Resolver tambin estas ecuaciones en forma exacta y comparar con los resultados obtenidos.
- La primera ecuacin tiene 2 races y la segunda 3.
b) Encontrar una solucin aproximada de cos x = x y comparar con los resultados del problema 5.8.
c) Obtener una solucin aproximada de cada una de las ecuaciones
2 ln x = x
x3 sen x + 1 = 0.
Pg. 69
c1 = b1 p,
b2 = tc1 ,
c2 = b2 p, . . .
y en general
cm = bm p = t cm1 p,
(7.1)
Pg. 70
Funciones y Procedimientos
7.3. Procedimientos
Los procedimientos y funciones son muy parecidos entre s, y a veces se
los engloba bajo el nombre comn de rutinas.(5) De hecho, en lenguajes como
C no hay distincin entre ellos. En Pascal, la diferencia ms obvia es que los
procedimientos no tienen un resultado visible.
Pascal nos permite mezclar funciones y procedimientos, con la nica restriccin de que se deben declarar en el orden en que son usados: una funcin o
procedimiento no puede llamar a una funcin o procedimiento que no ha sido
an declarada.
- Una posibilidad intermedia es el uso de forward, que no veremos.
Ms an, como veremos en el problema 7.6.d) y en el problema 7.8.b), es posible poner una funcin o procedimiento dentro de otra funcin o procedimiento,
y aqullos sern locales a stos (desconocidos para otras partes del programa).
Esta accin se llama anidamiento de funciones o procedimientos.
Podemos pensar, recordando la figura 2.4, que al alojarse en la memoria el
programa ejecutable, hay un espacio reservado para funciones y procedimientos,
como se indica en la figura 7.2. A su vez, funciones y programas pueden repetir
el esquema si hay anidamiento.
datos
globales
funciones,
procedimientos
instrucciones
(parte
principal)
datos
locales
instrucciones
locales
datos
locales
instrucciones
locales
programa
ejecutable
Poner carteles.
Leer los datos, en este caso inicial , final e incremento.
Hacer e imprimir la tabla.
Sealar el fin del programa.
Pascal nos permite poner cada uno de estos pasos como procedimiento, poniendo en el cuerpo principal del programa:(6)
begin
cartelesiniciales;
leerdatos;
imprimirtabla;
(5)
7.3. Procedimientos
Pg. 71
cartelfinal
end.
donde cartelesiniciales, leerdatos, imprimirtabla y cartelfinal son procedimientos
que realizarn las acciones correspondientes.
La ventaja de hacerlo es que podemos preocuparnos por cada uno de los
procedimientos y si las hubiera, funciones por separado. As, podramos
definir el procedimiento cartelesiniciales como
procedure cartelesiniciales;
begin
writeln(Hacer una tabla del seno dando valores);
writeln(inicial, final, y del incremento (en grados).);
writeln
end;
Problema 7.6. En el programa tablaseno2 (pg. 159) hemos reescrito el programa tablaseno1, con las modificaciones mencionadas.
a) Comparar ambos programas, observando cmo se han declarado los procedimientos en tablaseno2 y cmo se corresponden con las sentencias de
tablaseno1.
Observar que las variables inicial , final e incremento se han declarado
como globales, puesto que se usan en distintas partes, mientras que grados
y radianes son locales al procedimiento imprimirtabla, pues es el nico que
las usa.
b) Compilar y ejecutar tablaseno2 verificando su comportamiento.
c) En el problema 4.12 nos preocupamos por cmo dar un valor aproximado de
, teniendo las alternativas de definirlo manualmente o usar una frmula
como = 4 arctan 1, a la que podramos agregar el uso de la tcnica de
punto fijo del problema 5.9.
Eliminar la declaracin de pi como constante en el programa tablaseno2,
declararlo en cambio como variable real e incluir el procedimiento:
procedure calculodepi;
begin pi := 4 * arctan(1) end;
como primer procedimiento, incluyendo la sentencia calculodepi en el cuerpo
principal del programa. Compilar y ejecutar el programa con estas modificaciones.
d) En realidad, el valor de pi se usa slo para pasar de grados a radianes.
Eliminar las declaraciones de pi , calculodepi y la sentencia calculodepi del
programa, y en cambio colocarlas dentro del procedimiento imprimirtabla.
Debera quedar algo como:
procedure imprimirtabla;
var
grados: integer;
radianes, pi: real;
procedure calculodepi;
begin pi := 4 * arctan(1) end;
begin
calculodepi;
writeln(Angulo
Seno);
Pg. 72
Funciones y Procedimientos
grados := inicial;
while (grados <= final) do begin
radianes := grados * pi/180;
writeln(grados:5, sin(radianes):15:5);
grados := grados + incremento
end
end;
mientras que el cuerpo principal y las variables globales son como el en la
$
versin original de tablaseno2.
u
1
Pg. 73
v
3
Pg. 74
Funciones y Procedimientos
begin i := j;
if (h = 0) then P(j) else if h = 1 then P(i) else R;
writeln( i, j, k)
end;
begin i := 0; j := 1; k := 2; Q(0,k); Q(1,i); Q(2,j)
end.
- Observar que el procedimiento R es local al procedimiento Q, y desconocido
globalmente. Recordar el problema 7.6.d).
$
Pg. 75
Captulo 8
Pg. 77
Pg. 78
Pg. 79
(recordar los problemas 4.24 y 4.28), pero guardando los datos ingresados
en un arreglo.
$
Problema 8.3.
a) Desarrollar un programa que, dado un arreglo de enteros entrado como en el
problema 8.1, y sin usar otro arreglo adicional, lo invierta, i.e., si el arreglo
inicialmente es (a1 , a2 , . . . , an ), el arreglo final es (an , . . . , a2 , a1 ).
Sugerencia: hacer los intercambios a1 an , a2 an1 ,...
Sugerencia si la anterior no alcanza:
i := 1; j := n;
while (i < j) do begin
t := a[i]; a[i] := a[j]; a[j] := t;
i := i + 1; j := j - 1
end;
Pg. 80
Por ejemplo, los procedimientos leerarreglo y escribirarreglo en el problema 8.1 nos dan una plantilla (template en ingls) para leer o imprimir arreglos
de nmeros eventualmente modificando el ndice inicial, e.g., array[1..MAXN],
o el tipo de dato del arreglo, e.g real en vez de integer.
Problema 8.5 (La Caja de Herramientas). Copiar en sendos archivos de
texto,(2) los procedimientos leerarreglo y escribirarreglo del problema 8.1, y practicar incorporarlos en un programa para leer y escribir un arreglo de enteros
(como en el problema 8.1).
$
Seguramente habr muchos procedimientos o funciones que querrs incorporar a la caja de herramientas, algunos que ya hemos visto como el mtodo de la
biseccin (seccin 7.3), y otros que veremos ms adelante, como alguno de los
mtodos de bsqueda y clasificacin del captulo 10.
8.5. Strings
Pg. 81
b) Incorporar un procedimiento para escribir renglones, y verificar que el proceso de lectura desarrollada en el inciso anterior es correcto.
- A veces arreglos como texto y cenr se dicen paralelos, pues la informacin se va actualizando simultneamente. Cuando veamos registros, en la
$
seccin 10.4, veremos otra forma de guardar informacin de este tipo.
8.5. Strings
Problema 8.7. El tipo string no es estndar en Pascal, pero existe en casi
todos los compiladores, en particular en Turbo Pascal. Probar el comportamiento del compilador con un programa que lee un rengln entrado por terminal, va
readln(s), donde se declara s como string[100], indicando su longitud, y/o
simplemente como string.
- Ms precisamente, segn el estndar Pascal el tipo string es una denominacin genrica para el tipo char y para arreglos empaquetados de
caracteres, que se declaran con algo como
var s: packed array[1..10] of char
Lo que no se admite en el estndar es una declaracin como
var s: string[10]
que es ms o menos equivalente en los compiladores que la aceptan.
En ambos casos, podemos pensar que se tiene un arreglo mixto, donde
el primer ndice indica la cantidad de caracteres, y los restantes lugares son
los caracteres. En el proceso se cambia de tipo char a integer o viceversa,
Pg. 82
Estndar
rewrite(archivo, nombre)
reset(archivo, nombre)
Turbo Pascal
assign(archivo, nombre);
rewrite(archivo)
assign(archivo, nombre);
reset(archivo)
Cuadro 8.2: Diferencias entre el estndar y Turbo Pascal para leer o escribir
archivos.
Luego de leer el nombre externo y relacionarlo con el interno, debemos leer
de consola e ir escribiendo el archivo en un caso, y recprocamente, leer del
archivo y escribir en consola en el otro.
En el primer caso vemos una estructura similar a la lectura de renglones
del problema 8.6, excepto que no usamos write(c) sino write(archivo, c)
para escribir c en el archivo y no la consola, debiendo incorporar el nombre
del archivo. Del mismo modo, writeln(archivo) (sin el argumento c) escribe
un fin de lnea terminando el rengln en el archivo.
En el segundo caso, cuando leemos del archivo en dearchivoaconsola e
imprimimos en la terminal, volvemos a encontrar una estructura conocida,
excepto que ahora el fin de datos que anteriormente sealbamos con
<retorno> vaco, ahora se seala de un modo especial para archivos de
textos: el fin de archivo.
De modo similar a eoln, eof(archivo) pregunta si ya hemos llegado
a esta seal en el archivo que estamos leyendo.
- Hay que tener cuidado pues no debe llamarse a eoln si se ha llegado al
final del archivo, ya que un archivo de texto puede no tener fin de lnea:
primero siempre debe llamarse a eof.
Pg. 83
Pg. 84
a) Compilar y ejecutar el programa deconsoloaarchivo, y verificar su comportamiento abriendo el archivo creado con un editor de textos.
- El directorio en el cual el programa crear o buscar el archivo depende
del compilador, del sistema operativo, y si lo hubiere, de la ubicacin
e instalacin del ejecutable.
- Como ya mencionamos, en algunos sistemas operativos es conveniente
que los archivos de texto tengan la extensin .txt.
Captulo 9
Nmeros Aleatorios y
Simulacin
Muchas veces se piensa que en matemticas las respuestas son siempre exactas, olvidando que las probabilidades forman parte de ella y que son muchas
las aplicaciones de esta rama de las matemticas.
Una de estas aplicaciones es la simulacin, tcnica muy usada por fsicos,
ingenieros y economistas cuando es difcil llegar a una frmula que describa el
sistema o proceso. As, simulacin es usada para cosas tan diversas como el
estudio de las colisiones de partculas en fsica nuclear y el estudio de cuntos
cajeros poner en el supermercado para que el tiempo de espera de los clientes
en las colas no sea excesivo.
La simulacin mediante el uso de la computadora es tan difundida, que hay
lenguajes de programacin (en vez del Pascal o C) especialmente destinados a
este propsito.
Pg. 86
- Si no se dispone de una rutina para generar nmeros aleatorios, es necesario instalar una propia. Sin embargo, obtener nmeros aleatorios con la
computadora no es tan sencillo como tirar dados, y hay mucha teora matemtica detrs de los buenos generadores: los interesados puede consultar
el excelente libro de Knuth [8, vol. 2].
Una posibilidad es usar las rutinas que aparecen como ejemplo en el
mismo estndar de Pascal extendido (ISO 10206) adaptado al estndar de
Pascal sin extensiones que es el que usamos.(1)
9.2. Aplicaciones
Problema 9.1. El programa dado (pg. 162) hace una simulacin de tirar un
dado mediante nmeros aleatorios obtenidos con la sentencia random.
a) La sentencia randomize sirve para comenzar una nueva serie de nmeros
aleatorios. Eliminarla, comentndola, ejecutar repetidas veces el programa
y comprobar que siempre se obtienen los mismos resultados (o sea no es
muy al azar).
- Salvo para programas que tienen un tiempo de ejecucin grande, no
debe hacerse ms de una llamada a randomize.
b) Modificar el programa para simular tirar una moneda con resultados cara
o ceca.
$
Problema 9.2. El programa dados (pg. 163) hace una simulacin para encontrar la cantidad de veces que se necesita tirar un dado hasta que aparezca un
nmero prefijado, entrado por el usuario. Gracias a la sentencia randomize, el
resultado en general ser distinto con cada ejecucin. Observar que si el usuario
entra un nmero menor que 1 o mayor que 6, el programa no termina nunca.
a) Ejecutar el programa varias veces, para tener una idea de cunto tarda en
aparecer un nmero.
b) En vez de correr varias veces el programa, modificarlo de modo de realizar
n simulaciones (n entrado por el usuario), mostrando como resultado el
promedio(2) de los tiros que tard en aparecer el nmero predeterminado.
Sugerencia: encerrar el lazo repeat dentro de un lazo for, y tener cuidado
con el tipo de dato donde se guardan las acumuladas.
c) Modificar el programa original a fin de simular que se tiran simultneamente
dos dados, y contar el nmero de tiros necesarios hasta obtener un resultado
ingresado por el usuario (entre 2 y 12).
$
Problema 9.3. Tomando como base el problema anterior y el programa dados,
hacer un programa que diga cuntas veces debi tirarse un dado hasta que
aparecieron k seis consecutivos, donde k es ingresado por el usuario. Sugerencia:
poner un contador c inicialmente en 0, y dentro de un lazo repeat (donde se
hace la llamada a random) el contador se incrementa en 1 si sali un seis y si no
se vuelve a 0.
(1) Una copia del estndar en formato pdf puede encontrarse en http://www.
pascal-central.com/standards.html
(2) Recordemos que el promedio debe ser una variable real.
9.2. Aplicaciones
Problema 9.4.
a) Desarrollar un programa para hacer una lista de r nmeros enteros, elegidos
aleatoria y uniformemente entre 0 y s 1, donde r, s N son entrados
por el usuario.
b) Modificar el programa de modo que, recorriendo linealmente la lista generada en el inciso anterior, al terminar imprima la cantidad de veces que se
repite cada elemento. Sugerencia: agregar un segundo arreglo para contar
las apariciones (ver tambin el problema 6.1).
- La cantidad de apariciones deberan ser muy similares, aproximadamente r/s cada uno, cuando r s.
$
Problema 9.5 (Dos con el mismo cumpleaos). Mucha gente suele sorprenderse cuando en un grupo de personas hay dos con el mismo da de cumpleaos: la probabilidad de que esto suceda es bastante ms alta de lo que se
cree normalmente.
Supongamos que en una sala hay n (n N) personas y supongamos, para
simplificar, que no hay aos bisiestos (no existe el 29 de febrero), de modo que
podemos numerar los posibles das de cumpleaos 1, 2, . . . , 365.
a) Para qu valores de n se garantiza que haya al menos dos personas que
cumplen aos el mismo da? Sugerencia: recordar el principio del casillero,
tambin conocido como del palomar o de Dirichlet.
- El principio de Dirichlet dice que si hay n + 1 objetos repartidos en n
casillas, hay al menos una casilla con 2 o ms objetos.
Pg. 87
Pg. 88
Captulo 10
Bsqueda y clasificacin
Siempre estamos buscando algo y es mucho ms fcil encontrarlo si los datos
estn clasificados u ordenados. No es sorpresa que bsqueda y clasificacin sean
temas centrales en informtica y que haya una enorme cantidad de material
escrito al respecto. Por ejemplo, en sus clsicos libros [8] Knuth dedica al tema
todo el volumen 3 (que por supuesto, usa material de los volmenes anteriores).
Ac hacemos una introduccin al tema siguiendo, en mnima proporcin, la
presentacin de Wirth en [12].
Pg. 90
Bsqueda y clasificacin
En el lazo while o repeat de los esquemas en el problema anterior para
bsqueda lineal se hacen dos comparaciones, pero podemos mejorarlo haciendo
una sola colocando a x como centinela en alguna posicin de modo que siempre
lo encontremos.
Por ejemplo, una modificacin del esquema del inciso d) del problema anterior que es correcto suponiendo que el arreglo a est dimensionado adecuadamente, es:
(* a debe ser declarado de modo de admitir a[0] *)
a[0] := x; i := n;
while (x <> a[i]) do i := i - 1;
if (i > 0) then... (* se encontro en la posicion i *)
Observamos que siempre termina, ya sea porque x es un elemento del arreglo
original, en cuyo caso i es el lugar que ocupa, o bien porque no se encontr, en
cuyo caso i = 0.
- No hay nada misterioso en ir desde atrs hacia adelante, podramos haber
puesto el centinela en la posicin n + 1 y recorrer de adelante hacia atrs.
Problema 10.2 (Bsqueda lineal con centinela). Hacer una implementacin con ambas variantes (con y sin centinela) como procedimientos, incluyendo
un contador para la cantidad de comparaciones en cada una, y probar el comportamiento en distintos ejemplos (entrar el arreglo como en el procedimiento
leerarreglo (pg. 77), o generar uno aleatoriamente).
$
Problema 10.3. En este problema queremos hacer un procedimiento para eliminar elementos repetidos del arreglo de enteros a = (a1 , a2 , . . . , an ), como
en el problema 6.6, pero cuando a est ordenado de menor a mayor, e.g., si
a = (1, 2, 2, 5, 6, 6, 9), queremos que al fin del procedimiento sea a = (1, 2, 5, 6, 9).
En este caso podemos poner algo como
procedure purgarordenado(var a: arreglo; var n: integer);
(* sacar elementos repetidos del arreglo
ordenado a de longitud n. *)
var i, m: integer;
begin
m := 1; (* a[1],...,a[m] son los elementos sin repetir *)
for i := 2 to n do
(* incluir a[i] si no es a[m] *)
if (a[m] < a[i]) then begin
m := m + 1; a[m] := a[i] end;
n := m
end;
to.
Pg. 91
(10.1)
(10.2)
Pg. 92
Bsqueda y clasificacin
ii) Verificar que si en cambio, mucho poco + 2, entonces poco < medio <
mucho.
c) Hacer un procedimiento implementando bsqueda binaria con el esquema:
poco := 1; mucho := n;
while (poco + 1 < mucho) do begin
medio := (poco + mucho) div 2;
if (a[medio] < x) then poco := medio
else mucho := medio
end;
(* a continuacin comparar x
con a[mucho] y con a[poco] *)
y aplicarlo en un programa para encontrar un elemento en un arreglo (or$
denado no decrecientemente!) ingresados por terminal.
n do begin
a[0] := x; j := i;
a[j-1]) do begin
a[j-1]; j := j-1
Pg. 93
k := j; x := a[k] end;
a[k] := a[i]; a[i] := x
end
- Comparar con el problema 6.4.
a = (6, 5, 4, 3, 2, 1),
a = (2, 6, 8, 7, 4, 5, 1, 3, 6, 4).
En el cuadro 10.1 mostramos una comparacin entre los tres mtodos con
arreglos de 10 000 enteros construidos de tres formas: ordenado, ordenado al
revs, y aleatorio. Los tiempos en el cuadro son para una mquina particular
(y no demasiado rpida para los estndares cuando se realizaron las pruebas) y
determinado compilador, y debe considerarse slo la proporcin entre ellos. Se
contaron las comparaciones y asignaciones de arreglos (y no cuando se comparan
o asignan ndices).
Observamos en la tabla que tanto seleccin directa como intercambio directo
realizan siempre el mismo nmero de comparaciones, n(n 1)/2, y que an
cuando no se hacen asignaciones (como en el caso de intercambio directo, cuando
el arreglo est ordenado), la enorme cantidad de comparaciones lleva tiempo.
En cuanto a las asignaciones, hemos de destacar que hemos tomado arreglos de
enteros, por lo que individualmente no llevan demasiado tiempo, y en el caso
de insercin directa con un arreglo aleatorio, hay muchas asignaciones pero
comparando con los otros mtodos elementales no llevan tanto tiempo.
Sera distinto si los elementos fueran arreglos, por ejemplo strings al clasificar
palabras, o registros (que veremos un poco ms adelante).
Muchos libros de programacin insisten en presentar el mtodo de intercambio directo o burbujeo y a veces ningn otro que es claramente inferior a
cualquiera de los otros: an en el caso del arreglo ordenado, se hace la misma
cantidad de comparaciones que seleccin directa, y ninguna asignacin, pero el
tiempo es superior! Hemos incluido este mtodo slo para que sepas que existe
y que es bastante malo.
Nosotros casi siempre elegiremos el de seleccin directa o insercin directa:
seleccin directa hace relativamente pocas asignaciones, insercin directa relativamente pocas comparaciones.
Pg. 94
Bsqueda y clasificacin
Arreglo ya ordenado
comparaciones
asignaciones
tiempo (segs.)
seleccin
49 995 000
29 997
1.10
intercambio
49 995 000
0
1.43
insercin
9 999
29 997
0.00
comparaciones
asignaciones
tiempo (segs.)
intercambio
49 995 000
149 985 000
1.87
insercin
50 004 999
50 024 997
1.45
Arreglo aleatorio
seleccin
49 995 000
103 894
1.10
comparaciones
asignaciones
tiempo (segs.)
intercambio
49 995 000
75 041 274
1.75
insercin
25 023 757
25 043 755
0.72
disposicin inicial
1
2
3
poniendo en cajas
disposicin final
Pg. 95
Pg. 96
Bsqueda y clasificacin
a b
re im
Figura 10.2: Esquema del registro de tipo complejo en memoria.
Si z 0 es otro nmero complejo, podemos hacer la asignacin
zp := z;
mientras que la suma z 00 = z + z 0 puede expresarse como:
zpp.re := z.re + zp.re; zpp.im := z.im + zp.im;
Las dos operaciones vlidas para variables de registro (completas) son la seleccin de componentes y la
asignacin.
Pg. 97
Pg. 98
Bsqueda y clasificacin
c) Hacer un programa para ingresar el arreglo a y clasificarlo segn curso o
nroid a eleccin del usuario, escribiendo por pantalla el resultado.
$
- Un mtodo de clasificacin se llama estable si el orden relativo de elementos
con llaves iguales permanece inalterado en el proceso de clasificacin.
Por ejemplo, el mtodo usado en el problema 10.11 ser estable si ordenando primero por nroid y despus por curso, personas con el mismo
nmero curso aparecen en orden creciente de nroid .
El mtodo de seleccin directa no es estable, mientras que insercin e
intercambio lo son (dependiendo de cmo se implementen).
Cantidad de apariciones
5
4
2
1
Captulo 11
Recursin
Teniendo en mente las sumas de Gauss del problema 4.13, supongamos que
queremos encontrar todas las sumas
s1 = 1,
s2 = 1 + 2,
s3 = 1 + 2 + 3,
...
sn = 1 + 2 + + n.
(11.1)
s2 = s1 + 2,
s3 = s2 + 3,
...
sn = sn1 + n,
(11.2)
n! = n (n 1)! para n N.
(11.3)
xn = x xn1
para n N,
Pg. 100
Recursin
- La importancia de las relaciones de recurrencia es tal que en cursos de matemtica discreta se estudian las soluciones de las relaciones de recurrencia
lineales, homogneas y con coeficientes constantes, que son de la forma
an = A an1 + B an2
para n > 1,
()
an = c rn + c0 (r0 ) ,
y la frmula de Binet (5.6) es un caso particular de esta ecuacin.
A su vez, estas relaciones estn muy emparentadas con las ecuaciones
diferenciales. Por ejemplo, la ecuacin () tiene el correlato
y 00 = A y 0 + B y,
donde y = y(t), y se dan los datos iniciales y(0) y y 0 (0), y se resuelve
usando la misma ecuacin caracterstica.
n! nn en 2n.
Pg. 101
Problema 11.2. Hacer programas que usen funciones recursivas en vez de lazos
for, while o repeat para los siguientes casos:
a) Calcular xn cuando n N, como en el problema 7.2.
b) Dar una definicin inductiva del mnimo de un arreglo (a1 , a2 , . . . , an ) de
enteros, y usarla para definir una funcin en un programa como en el problema 6.4.
c) Rehacer el problema 7.5, cambiando la definicin de la funcin saldo a una
recursiva, segn la ecuacin (7.1).
$
La recursin tambin puede usarse en procedimientos:
Problema 11.3. Usando el procedimiento recursivo
procedure imprimir(a: tipoarreglo; n: integer);
begin
if (n > 1) then imprimir(a, n-1);
writeln(a[n]) (* o write para caracteres o... *)
end
hacer un programa para imprimir un arreglo a = (a1 , a2 , . . . , an ) de enteros.
Qu pasa si se cambia el orden de los renglones (i.e., primero writeln...
y despus if...)?
$
La recursin se puede usar en ms de un argumento, i.e., no siempre se
llama a la funcin con n 1.
Problema 11.4. Usando recursin, reescribir el algoritmo de Euclides (seccin 5.2.1) para encontrar el mximo comn divisor entre dos enteros positivos.
Sugerencia: mcd(a, b) = mcd(a b, b) si a > b.
$
Pg. 102
Recursin
Problema 11.5. Hacer un programa para calcular el n-simo nmero de Fibonacci (ver problema 5.20), donde n N es ingresado por el usuario, usando
recursin sobre dos parmetros con dos condiciones iniciales.
Sugerencia: if n > 2 then fib := fib(n-1) + fib(n-2) else fib := 1.
$
Problema 11.6. Para m, n N, consideremos una cuadrcula rectangular de
dimensiones m n (4 3 en la figura 11.1), e imaginmosnos que se trata
de un mapa, donde los segmentos son calles y los puntos remarcados son las
intersecciones.
1
10
20
35
10
15
(m + n)!
(m + n) (m + n 1) (m + 1)
=
.
m! n!
n (n 1) 1
Pg. 103
Quin lo duda!
Con movimientos permitidos: recordar que el disco a pasar de una aguja a otra debe ser
menor que cualquier otro disco en esas agujas.
(2)
Pg. 104
Recursin
como consistente en los pasos pasar (k 1, x, z, y); pasar (1, x, y, z) y luego
pasar (k 1, z, y, x):
c) Usar el procedimiento del inciso a) en un programa que imprima una sucesin de movimientos para transferir n discos de una aguja a otra. Verificar
el programa para n = 1, 2, 3, 4, 5.
d) Agregar un contador para contar la cantidad de veces que se transfiere un
disco de una aguja a otra (en pasar ), e imprimirlo al terminar el programa.
En base a este resultado (para n = 1, 2, 3, 4, 5) conjeturar la cantidad de movimientos necesarios para transferir n discos de una aguja a otra, y demostrarlo. Sugerencia: 2n 1 = 1+2+4+ +2n1 = 1+2(1+2+ +2n2 ) =
1 + 2(2n1 1).
e) Suponiendo que transfieren un disco por segundo, cunto tardarn los monjes en transferir los 64 discos? Cuntos aos tardara una computadora en
calcular la solucin para n = 64, suponiendo que tarda un nanosegundo por
movimiento(3) (nano = dividir por mil millones)? Bajo la misma suposicin
sobre la velocidad de la computadora, cul es el valor mximo de n para
calcular los movimientos en 1 minuto?
- En el problema 11.8 se da una variante para resolver el problema de las
torres de Hanoi sin usar arreglos.
- La estructura que estamos usando para los arreglos, agregando atrs y
(3)
Pg. 105
Problema 11.8 (Torres de Hanoi sin arreglos). Flor, que siempre le lleva
la contra al profe y est compitiendo con l, hizo un programa para resolver el
problema de las torres de Hanoi sin usar arreglos. Ms an, cambi arreglos
por caracteres!:
program hanoisinarreglos(input, output);
(*
Solucion recursiva de las torres de Hanoi,
sin usar arreglos.
*)
type aguja = char;
var n: integer;
procedure pasar( n: integer; x, y, z: aguja);
(* pasar n discos de x a y usando z *)
begin
if (n > 1) then begin
pasar(n-1, x, z, y);
write(pasar el disco , n:1);
writeln( de ", x, " a ", y,");
pasar(n-1, z, y, x)
end
else begin
write(pasar el disco 1);
writeln( de ", x, " a ", y,")
Pg. 106
Recursin
end
end;
begin
writeln(** Problema de las torres de Hanoi:);
writeln(
Pasar n discos de la aguja "a" a la "b");
write(
usando la "c", mediante movimientos );
writeln( permitidos.);
writeln;
write( Entrar el numero de discos: ); readln(n);
writeln;
pasar(n, a, b, c);
writeln; writeln(** Fin **)
end.
Es correcto el programa de Flor? Por qu?
Captulo 12
Objetos combinatorios
Muchos de los problemas que vimos en el captulo anterior se pueden reescribir sin recursin con lazos for, como el factorial, seleccin directa, los nmeros
de Fibonacci, o an la cantidad de caminos del problema 11.6, y nos quedamos
con la impresin de que recursin no es muy til. Otro problema muy distinto
al de contar objetos es generarlos, por ejemplo para encontrar alguno o todos
los que satisfacen cierto criterio, y aqu es donde recursin muestra toda su
potencia.
Puesto que el nmero de objetos a generar puede ser muy grande, como 2n
o n!, es conveniente no tener por ejemplo un arreglo para cada uno de
ellos, sino tener uno solo que se va modificando a medida que vamos creando
los objetos. Una estructura particularmente til para esta modificacin es la de
pila, con la que comenzamos.
Pg. 108
Objetos combinatorios
No es casualidad que put y get sean nombres en Pascal de funciones o procedimientos para entrada o salida (que no cubriremos, siendo ms primitivas
que read y write). Efectivamente, la entrada y salida en la computadora se
implementan como colas fifo: los datos se leen o escriben en el orden en que
van surgiendo. Dado que put y get tienen significados especiales en Pascal, es
conveniente evitar estos nombres.
El concepto de cola, que tiene muchsimas generalizaciones, constituye un
tipo de datos abstracto (TDA): no importa tanto cmo se va a implementar o
representar en la mquina, sino saber que contamos con las operaciones de crear
o destruir la cola, agregarle o quitarle un elemento, etc.
Sin embargo, la implementacin de una cola como fifo o lifo puede tener
consecuencias decisivas en los algoritmos, como veremos en el captulo 14. Adems, en lenguajes no tan abstractos como Pascal, debemos tener cuidado en la
implementacin de TDA. Tanto con Pascal como con el lenguaje C se pueden
usar punteros y listas encadenadas , que son ms apropiados para implementar
colas. Sin embargo, en este curso nos arreglaremos con arreglos.
Como sabemos, si queremos trabajar con un arreglo tenemos que declararlo
al comienzo, dando su dimensin y el tipo de elementos. Por lo tanto, si vamos a
representar una cola con un arreglo, no podemos crearlo de la nada, y tenemos
que prever su existencia y dar una dimensin adecuada al problema. Del mismo
modo, no podemos destruirlo, y nos limitaremos a ignorarlo cuando no lo
necesitemos ms.
Suponiendo que hemos declarado el tipo dato, que puede ser un registro u
otro arreglo, podemos implementar una pila declarando
pila: array[1..MAXP] of dato
donde MAXP es una constante apropiada. Si npila es la cantidad de elementos,
declarado con la misma localidad que pila, podemos hacer:
Crear la pila:
procedure inicializar;
begin npila := 0 end;
Agregar un elemento e:
procedure push(e: dato);
begin
if (npila < MAXP) then begin
npila := npila + 1; pila[npila] := e end
end;
- Siguiendo con la filosofa de no poner en general mensajes de
aviso, tratando de ver el bosque y no el rbol, no hemos agregado
acciones para el caso en que npila = MAXP antes de incorporar
el dato.
Quitar un elemento:
procedure pop(var e: dato);
begin
if (npila > 0) then begin
Pg. 109
Observar la simetra entre las acciones de push y pop: una realiza exactamente los pasos inversos de la otra.
Para colas (fifo), las cosas son ligeramente diferentes. En vez de tener un
ndice como en el caso de la pila, mantenemos dos: uno, digamos ppocola, sealando el principio de la cola en el arreglo, y otro, digamos fincola, sealando
el final. fincola se incrementa al agregar un dato, mientras que ppocola aumenta cuando se extrae un dato, de modo que los elementos vivos en principio
estarn entre ppocola y fincola (inclusivo en ambos casos).
Claro que si la cola est definida como un arreglo de MAXC elementos,
las cosas se complican cuando agregamos ms de MAXC elementos a la cola,
an cuando hayamos quitado algunos y haya menos de MAXC elementos en
la cola. En este caso necesitamos usar aritmtica mdulo MAXC . No entramos
en detalles porque en los ejemplos que daremos en los captulos posteriores
supondremos que MAXC es lo suficientemente grande como para evitar este
problema.
Volviendo a las pilas, no podemos dejar de observar que los procedimientos
inicializar y push son viejos conocidos que usamos al leer los datos de un arreglo,
por ejemplo en el programa renglon (pg. 155). Tambin hemos visto un atisbo
del uso de pilas en el problema 11.7 de las torres de Hanoi, donde las agujas
eran pilas en s.
En la prxima seccin veremos que la tcnica de mezclar recursin con pilas
puede usarse para generar distintos objetos combinatorios, aunque las pilas no
siempre aparecern explcitamente.
Pg. 110
Objetos combinatorios
var i: integer;
begin
for i := 0 to 1 do begin
a[k] := i; (* poner 0 o 1 en el lugar k *)
if (k < n) then cadena(k+1)
else haceralgo(a, n) (* hacer algo cuando k = n *)
end (* for *)
end;
En este caso, haceralgo(a, n) ser un procedimiento para imprimir los valores
a1 , . . . , an .
Observar que usamos al arreglo a como una pila. Para k fijo, el elemento en
la posicin k tiene un valor de 0 cuando i = 0, que se mantiene para valores
superiores a k pero luego es cambiado para i = 1, y obviamente cambia varias
veces cuando es llamado desde valores inferiores a k. Sin embargo, k es el parmetro del procedimiento sobre el cual se hace la recursin, y no una variable
global.
a) Hacer una prueba de escritorio del procedimiento cuando n = 3.
b) Hacer un programa que dado n N imprima todas las cadenas de bits de
longitud n, siguiendo las indicaciones anteriores.
c) Agregar un contador (global) para contar las cadenas de longitud n, y ver
que la cantidad de cadenas es 2n .
d) En el procedimiento cadena propuesto se va hacia adelante, llamando a
cadena(1) en el cuerpo principal, y aumentando el valor del argumento k
en cada llamada del procedimiento hasta llegar a k = n, ya que n es global.
Esto contrasta con el uso de recursin en, por ejemplo, el factorial, donde
vamos hacia atrs disminuyendo el valor del argumento en cada llamada.
Redefinir el procedimiento cadena de modo que en l se compare k con
0 o 1 en vez de n, y se haga la llamada cadena(n) en el cuerpo principal. $
La tcnica que hemos usado es bastante general y puede usarse en muchos
problemas. Sin embargo, para encontrar las cadenas de bits no es necesario usar
recursin:
Problema 12.2. Resolver el problema 12.1 sin usar recursin, usando que las
cadenas de bits de longitud n pueden pensarse como los coeficientes en base 2
de los nmeros entre 0 y 2n 1. Sugerencia: para k = 0, . . . , 2n 1, construir
$
la lista de coeficientes en base 2 e imprimirla.
Problema 12.3 (Generando subconjuntos). En el problema 12.1 esencialmente se construyen todos los subconjuntos de {1, 2, . . . , n}, ya que las cadenas de bits de longitud n se pueden considerar como vectores caractersticos. Dado un conjunto A {1, 2, . . . , n} definimos su vector caracterstico,
b(A) = (b1 , b2 , . . . , bn ), mediante
(
1 si i A,
bi =
0 si no.
Es claro que dos conjuntos distintos tienen vectores caractersticos distintos,
y que por otro lado, dada una cadena de bits podemos encontrar un conjunto
A tal que b(A) sea esa cadena. Por lo tanto, hay una correspondencia biunvoca
entre cadenas de bits de longitud n y subconjuntos de {1, 2, . . . , n}.
Modificar el programa del problema 12.1 para que en vez de imprimir cadenas
de bits, imprima el subconjunto correspondiente en {1, 2, . . . , n}, representando
al conjunto vaco con una raya -.
Pg. 111
1 2
Una vez que sabemos cmo generar una familia de objetos, es ms sencillo
generar o contar objetos de la familia con caractersticas particulares, como
vemos en los siguientes problemas.
Problema 12.4. Supongamos que queremos contar la cantidad h(n) de cadenas
de n bits que no contienen dos ceros sucesivos:
a) Hacer un programa para calcular h(n) para n N, usando el programa
del problema 12.1 y donde el procedimiento haceralgo en vez de imprimir
haga una variante de bsqueda lineal para encontrar dos 0 consecutivos en
cada cadena construida, verificando si se trata de una cadena vlida antes
de aumentar un contador adecuado. Sugerencia: recordar el problema 9.3.
b) Comparar el nmero h(n) obtenido anteriormente con los nmeros de Fibonacci y hacer un nuevo programa para calcular h(n) directamente.
$
Problema 12.5. Hacer un programa que dado k y n, k, n Z, 1 k n,
cuente e imprima todos los subconjuntos de {1, . . . , n} con k elementos.
`
n!
- Hay nk = k!(nk)!
subconjuntos.
$
Pg. 112
Objetos combinatorios
k := k - 1 (* sacar la piedrita *)
end;
donde haceralgo es un procedimiento para imprimir los valores camino 1 ,. . . ,
camino r , y haremos la nica llamada llegardesde(0,0) en el cuerpo principal.
Estudiemos el procedimiento llegardesde, haciendo una prueba de escritorio en todo caso:
La recursin se hace sobre i y j, mientras que k es la cantidad de elementos
en la pila. Es decir, k es la cantidad de esquinas en el camino, y por lo
tanto su longitud.
Inicialmente deber ser k = 0, puesto que no tenemos camino.
A diferencia del problema 12.1, k es global y no el parmetro del procedimiento.
Al entrar al procedimiento, k se incrementa en 1, y se incorpora la interseccin (i, j) al camino en la (nueva) posicin k .
El comentario poner una piedrita se refiere a dejar una marca o
huella all para saber por dnde pasamos cuando volvemos.
Si i < m o j < n, se puede continuar (hacia la derecha o hacia arriba),
por lo que llamamos al procedimiento recursivamente, incrementando los
valores respectivos. Observar que no hay un else: queremos que cada
caso contribuya con un camino distinto.
Si i = m y j = n, hemos llegado a la esquina deseada, e imprimimos el
camino.
Una vez recorridos los caminos que siguen hacia el este, o el norte, o impreso el camino, debemos retornar, borrando nuestras huellas para permitir
que la posicin k pueda ser ocupada por otra esquina. Por eso se pone la
instruccin k := k - 1 al terminar el procedimiento.
En otras palabras, al terminar quitamos de la pila camino el elemento
(la piedrita) que habamos puesto al comienzo.
a) Hacer un programa con estas instrucciones, probando con valores pequeos,
e.g., m = 3 y n = 2 mientras se van corrigiendo los errores (recordar poner
k := 0 y la llamada llegardesde(0,0)).
b) Qu pasa si se elimina la instruccin k := k - 1 en el procedimiento
llegardesde?
c) Agregar un contador, de manera de ir contando la cantidad de caminos
encontrados y que la salida sea algo como
1:
2:
3:
Hay 3 caminos
cuando m = 2 y n = 1.
d) Como en el problema 12.1.d), no hay ningn misterio en ir hacia adelante.
Cambiar el procedimiento llegardesde por otro, digamos llegara, de modo
que en el cuerpo principal se haga la llamada llegara(m,n) en vez de
llegardesde(0,0) (atencin en imprimir el camino al derecho y no al
revs).
$
Pg. 113
Pg. 114
Objetos combinatorios
n!
(nk)!
de estas permutaciones.
Pg. 115
Pg. 116
Objetos combinatorios
- El problema de las manos es muy sencillo de plantear, y tiene aplicaciones ms all de los juegos, como en estadstica. Sin embargo, encontrar
algoritmos correctos y eficientes no es sencillo, a diferencia del caso de subconjuntos que se equiparan con las cadenas de bits (problema 12.9), que
a propsito tambin tiene aplicaciones en estadstica (para encontrar
una muestra al azar).
La correccin de un algoritmo se refiere a que 1) todas las permutaciones de 1, . . . , n se pueden generar de esta forma, y 2) con igual probabilidad.
Otro problema es el de decidir su eficiencia: cuntos pasos realiza en trminos de n. Ninguna de estas preguntas es fcil de responder desde la teora,
pero nosotros vamos a aprovechar el trabajo que otros han hecho: los algoritmos aqu presentados son correctos, aunque el ltimo es ms eficiente
en general.
El algoritmo en e) est presentado en el libro de Knuth [8, Vol. 2,
pg. 126], donde se hacen los anlisis de correccin y eficiencia. Es atribudo
independientemente a L. E. Moses y R. V. Oakford (1963) y R. Durstenfeld
(1964). Pero existen otros algoritmos que son ms eficientes cuando m es
chico comparado con n (ver, por ejemplo, el algoritmo de R. Floyd descripto
en libro de Bentley [1, pg. 139]).
$
Captulo 13
Pg. 118
Cantidad de apariciones
5
2
1
5
2
d 5
c 1
a 5
e 2
arreglo 1
arreglo 2
arreglo 3
arreglo 4
arreglo 5
Figura 13.3: Disposicin del arreglo de registros luego de ingresar los datos.
Para dar una estructura de rbol binario a los datos, hacemos lo siguiente: el
primer dato ingresado es la raz del rbol, y al ingresar cada dato subsiguiente lo
comparamos con los ya existentes, yendo hacia abajo a la izquierda si el nuevo
dato es menor o hacia la derecha si es mayor (o incrementando cuenta si es
igual). As, al terminar de ingresar los datos en nuestro ejemplo quedara un
rbol binario como el de la figura 13.4.
Despus de mirar un rato esta figura, nos damos cuenta que si proyectamos
los registros sobre una recta horizontal como en la figura 13.5, obtenemos los
(1)
Pg. 119
b 2
a 5
d 5
c 1
e 2
Figura 13.4: Disposicin del rbol binario luego de ingresar los datos.
registros clasificados alfabticamente. Despus de pensar otro rato ms, nos
damos cuenta que no se trata de una casualidad: en la figura 13.4 todo lo
que queda a la izquierda y abajo de un registro tiene que tener menor llave
y anlogamente hacia la derecha y abajo. As, en nuestro ejemplo, todo lo que
es menor que b , i.e. a , est a la izquierda, mientras que c , d y e estn
a la derecha. Cuando miramos a d , c est a la izquierda, pero tambin b
(que tena a d a su derecha) y a (que estaba a la izquierda de b ), etc.
a 5
b 2
c 1
d 5
e 2
b 2 4 2
d 5 3 5
c 1 0 0
a 5 0 0
e 2 0 0
Figura 13.6: Los registros con ndices para la estructura de rbol binario.
Ya estamos en condiciones de abordar el siguiente problema:
Problema 13.1. El programa arbolbinario (pg. 163), muestra la construccin
de un rbol binario ordenado usando arreglos como indicamos anteriormente.
En los nodos se guarda informacin, que en nuestro ejemplo es llave y cuenta.
En llave guardamos un entero, pero podra ser una palabra de un texto, o
Pg. 120
Pg. 121
Captulo 14
Grafos
Si tomamos un conjunto de ciudades y las carreteras que las unen, y representamos grficamente a las ciudades como puntos y a las carreteras como
segmentos o curvas uniendo esos puntos, obtenemos una figura similar a la 11.6,
en la cual pensbamos que los segmentos eran calles y los puntos las intersecciones.
La idea subyacente en ambos casos es la de grafo, un conjunto de vrtices (las
ciudades o intersecciones) que indicaremos por V , y un conjunto de aristas (las
rutas o calles), que indicaremos por E, cada una de las cuales queda definida
por dos vrtices. Si llamamos al grafo G, normalmente pondremos G = (V, E).
No slo los grafos estn relacionados con calles o rutas. En comunicaciones
tambin podemos pensar que los vrtices son computadoras y las aristas representan la posibilidad de que dos computadoras se conecten entre s. O, saliendo
de las comunicaciones, podemos pensar en un rbol genealgico, donde los vrtices son las personas y las aristas relacionan padres con hos. En fin, los ejemplos
de aplicaciones de grafos son muy variadas, y muchas veces sorprendentes.
En este captulo daremos una simple, y seguramente demasiado breve, descripcin de los trminos y propiedades que usaremos, dejando para los cursos
de matemtica discreta las definiciones rigurosas y las demostraciones. En el
proceso estableceremos nomenclatura y notaciones que pueden diferir entre autores.
A fin de distinguir los vrtices entre s es conveniente darles nombres, pero
para el uso computacional supondremos que si hay n vrtices, stos se denominan
1, 2, . . . , n, i.e., V = {1, 2, . . . , n}. Ms an, casi siempre usaremos el nombre n
(o algo que empiece con n) para el cardinal de V .
En los grafos que veremos, las aristas estn formadas por un par de vrtices,
y como el orden no importar, indicaremos la arista que une el vrtice a con el
vrtice b por {a, b}. Claro que decir {a, b} E es lo mismo que decir {b, a} E.
As como n es el nombre oficial de |V |, el nombre oficial para |E| es m.
Si e = {a, b} E, diremos que a y b son vecinos o adyacentes, que a y b
son los extremos de e, o que e incide sobre a (y b). A veces, un vrtice no tiene
vecinos no hay aristas que inciden sobre l y entonces decimos que es un
vrtice aislado.
Slo consideraremos grafos simples, en los que no hay aristas de la forma
{v, v} uniendo un vrtice con s mismo, ni aristas paralelas uniendo los mismos
vrtices.
En este caso, podemos relacionar n = |V | y m = |E|: si hay n elementos,
hay n2 = n (n 1)/2 subconjuntos de 2 elementos, de modo que m n2 .
Pg. 123
2
Pg. 124
Grafos
a)
b)
c)
d)
Pg. 125
La representacin mediante matriz de adyacencias es cmoda, y relativamente fcil de entender. Quizs sera ms eficiente para los algoritmos que
veremos dar para cada vrtice una lista de sus vecinos. Esta tercera forma
puede implementarse mediante arreglos, pero es mucho ms natural usar listas
encadenadas, que no veremos en este curso.
En esta seccin y las dos siguientes (salvo indicacin en contrario) supondremos las declaraciones:
const
MAXN = 20; (* maximo numero de vertices *)
MAXM = 100; (* maximo numero de aristas *)
type
arreglodevertices = array[1..MAXN] of integer;
tipoarista = record i, j: integer end;
arreglodearistas = array[1..MAXM] of tipoarista;
matrizNN = array[1..MAXN,1..MAXN] of integer;
var
ngrafo, mgrafo: integer;
aristasgrafo: arreglodearistas;
adyacencias: matrizNN;
usando para las aristas una representacin como arreglo de registros.
Usualmente el ingreso de datos es ms sencillo mediante la lista de aristas,
pues la matriz de adyacencias tiene n2 elementos y en general m n2 (y siempre
m n(n 1)/2 para grafos simples). De cualquier modo, es conveniente tener
a mano procedimientos para leer y para pasar de una a otra representacin:
Problema 14.2. En nuestros programas supondremos que ngrafo, el nmero
de vrtices del grafo, es entrado explcitamente (recordando que los vrtices
sern entonces 1, 2, . . . , ngrafo).
a) Hacer un procedimiento entrargrafo para ingresar por terminal el nmero
de vrtices, ngrafo, y las aristas, cada una representada por dos nmeros
enteros que son los vrtices que la determinan, formando un arreglo de
longitud mgrafo.
Sugerencia: seguir un esquema como
write(Ingresar el numero de vertices: ); readln(ngrafo);
writeln;
writeln(Ingresar las aristas, indicando sus extremos);
writeln(y fin de datos con <retorno> vacio);
mgrafo := 0;
nuevaarista := true;
while (nuevaarista) do begin
mgrafo := mgrafo + 1;
write( Entrar la arista , mgrafo:2);
writeln( (fin = <retorno>):);
write(
Entrar el primer vertice:
);
if (not eoln) then with aristasgrafo[mgrafo] do begin
read(i);
write(
Entrar el segundo vertice:
);
readln(j)
end (* with *)
else begin
nuevaarista := false;
Pg. 126
Grafos
mgrafo :=
readln (*
end (* if
end (* while
Vecinos
2 3
1 3 6
1 2 4
3 6
2
1
1
2
2
3
3
4
Pg. 127
2
3
3
6
4
6
6
Problema 14.4 (Grado de vrtices). Dado un grafo G = (V, E), para cada
vrtice v V se define su grado o valencia, (v), como la cantidad de aristas
que inciden en v, o equivalentemente, la cantidad de vecinos de v (excluyendo
al mismo v).
Por ejemplo, en el grafo de la figura 14.1, los grados son (1) = 2, (2) =
3, (3) = 4, (4) = 2, (5) = 0, (6) = 3.
a) Hacer un programa que dado un grafo calcule (v) para todo v V , imprimiendo el resultado como tabla.
b) Uno de los primeros teoremas que se ven en teora de grafos dice que si U
es el conjunto de vrtices de grado impar, entonces
X
(v) es par.
vU
Pg. 128
Grafos
Algoritmo recorrer
Entrada:
Salida:
Comienzo
Q {r};
mientras Q 6= hacer
sea i Q;
sacar i de Q;
visitar i ;
para todo j adyacente a i hacer
si j no est visitado y j
/ Q entonces agregar j a Q
Fin
Pg. 129
Por supuesto que si el grafo que queremos recorrer es ya un rbol, no se formar uno nuevo. Pero s que podemos tomar al vrtice r, con el que empezamos
el recorrido, como raz, y el arreglo padre justamente nos dir quin es el padre
de cada vrtice en el rbol que se forma.
Pondremos padre r = r para indicar que r es justamente la raz y no podemos
seguir ms arriba, de modo que tambin para i = r la condicin padre i > 0
es equivalente a que el vrtice i se ha incorporado alguna vez a la cola.
Otra cosa que necesitamos especificar es cmo elegir el vrtice en Q que se
sacar (si hay ms de uno). Lo ms sencillo es implementar a Q como pila, i.e.,
como cola lifo. Pero tambin podramos pensar en implementar como cola fifo
(sale primero el que lleg primero), o usar otros criterios para elegir el vrtice
que sale. De esta forma vamos a llegar a los distintos algoritmos que veremos en
el resto del captulo: recorrido en profundidad, recorrido a lo ancho, y cuando
las aristas tengan pesos, el algoritmo de Dkstra para encontrar el camino ms
corto y el de Prim para encontrar un rbol generador mnimo.
Pg. 130
Grafos
Pg. 131
Problema 14.7. Un clebre teorema de Euler dice que un grafo tiene un ciclo
que pasa por todas las aristas exactamente una vez, llamado ciclo de Euler, si
y slo si el grafo es conexo y el grado de cada vrtice es par.
Recordando el problema 14.4, modificar el programa del problema 14.6 para
que a la salida determine tambin si el grafo tiene o no un ciclo de Euler usando
el teorema.
- Un problema muy distinto es encontrar un ciclo de Euler en caso de existir.
Como ya mencionamos (pg. 42), Euler ha sido uno de los matemticos
ms destacados de todos los tiempos.
Entre otros tantos aportes fundamentales, Euler fue quien origin el estudio
de teora de grafos y la topologa al resolver en 1736 el famoso problema de
los puentes de Knigsberg (hoy Kaliningrad, en Rusia), donde el ro Pregel se
bifurcaba dejando dos islas (y dos costas), y las islas y las costas se unan por
siete puentes. Euler resolvi el problema, demostrando que no se podan recorrer
todos los puentes pasando una nica vez por ellos, demostrando el teorema que
$
hoy llamamos de grafos eulerianos.
Pg. 132
Grafos
camino[ncamino] := i
end;
(* dar vuelta el arreglo *);
i := 1; j := ncamino;
while (i < j) do begin
k := camino[i]; camino[i] := camino[j]; camino[j] := k;
i := i + 1; j := j - 1
end
end;
Pg. 133
2
2
3
1
1
2
6
1
3
3
4
Arista e
peso we
{1,2}
{1,4}
{1,5}
{2,3}
{2,4}
{3,4}
{3,5}
{3,6}
{4,6}
{5,6}
2
3
8
2
1
1
2
1
1
3
k1
X
i=1
w{vi ,vi+1 } .
Pg. 134
Grafos
Un rbol con estas propiedades se llama rbol generador mnimo. Podra haber
ms de un rbol con costo mnimo, por ejemplo si los costos de todas las aristas
son 1 y el grafo no es un rbol.
Volviendo al grafo de la figura 14.3, podemos formar un rbol generador con
las aristas {1, 2}, {1, 4}, {2, 3}, {3, 6}, {5, 6} (siempre un rbol generador debe
tener n 1 aristas), con peso total 2 + 3 + 2 + 1 + 3 = 11, y si reemplazamos la
arista {5, 6} por la arista {3, 5}, reducimos el costo en 1. En este ejemplo, dados
los datos, se forma un ciclo donde todas las aristas tienen peso 1, y por lo tanto
hay ms de un rbol mnimo (de peso total 7): podras encontrar dos de ellos
a simple vista?
En las secciones siguientes veremos algoritmos para resolver estos problemas,
el de la ruta ms corta y el del mnimo rbol generador, pero primero hagamos
los cambios necesarios sobre lo que vimos en la seccin 14.1, para incorporar los
pesos en las aristas, y adecuarlas a nuestros algoritmos.
El primer cambio es incorporar el costo en cada arista, lo que se puede hacer
agregando o cambiando las declaraciones para tener:
type
tipocosto = integer; (* podria ser real *)
tipoarista = record
i, j: integer; (* los extremos *)
w: tipocosto
(* el costo *)
end;
arreglodearistas = array[1..MAXM] of tipoarista;
Pg. 135
en otro caso,
por lo que declararemos
type
matrizNN = array[1..MAXN,1..MAXN] of tipocosto;
var
costos: matrizNN;
infinito: tipocosto;
Nuestro prximo objetivo es reproducir lo que hicimos en los problemas 14.2
y 14.3:
Problema 14.11. Haciendo las declaraciones de constantes, tipos y variables
mencionadas:
a) Hacer un procedimiento entrargrafo, de modo de leer de un archivo de texto
los datos ngrafo y luego los extremos y costos de cada arista, en forma
similar al problema 14.3.
Por ejemplo, el grafo de la figura 14.3 tendra asociado un archivo con
las entradas:
6
1
1
1
2
2
3
3
3
4
5
2
4
5
3
4
4
5
6
6
6
2
3
8
2
1
1
2
1
1
3
Pg. 136
Grafos
costos[i,j] := infinito;
for k := 1 to mgrafo do
with aristasgrafo[k] do begin
costos[i,j] := w; costos[j,i] := w
end
end;
Nuevamente habr tres clases de vrtices: los visitados, los que estn en
la cola y no han sido an visitados, y los que nunca estuvieron en la cola.
Como novedad, para cada i V consideraremos el valor di de la distancia ms
corta de s a i mediante caminos de la forma (s = v1 , v2 , . . . , vk , i) donde todos
los vrtices excepto i ya han sido visitados. A fin de indicar que no existe tal
camino, pondremos di = , siendo ste el valor inicial para todo i (cuando no
hay nodos visitados).
A diferencia de los recorridos de grafos de secciones anteriores, donde se
visitan los vrtices tomando ya sea el ltimo o el primero en entrar a la cola, en
el algoritmo de Dkstra elegimos el vrtice de la cola con menor distancia di .
El algoritmo termina cuando t es el vrtice que se visita, y entonces dt es la
distancia del menor camino de s a t, o cuando la cola es vaca, en cuyo caso no
existe un camino desde s hacia t y necesariamente el grafo no es conexo.
Al visitar un vrtice i y examinar un vrtice vecino j, verificamos si
di + w{i,j} < dj .
(14.1)
Pg. 137
Si esta desigualdad es vlida, quiere decir que el camino ms corto para ir desde
s a j (slo por vrtices ya visitados) es ir desde s a i con el camino para i, y luego
usar la arista {i, j}. Por lo tanto, actualizamos dj poniendo dj = di + w{i,j} .
Tambin agregaremos j a la cola si no se ha agregado an.
Es una propiedad del algoritmo, que no demostraremos, que si j es un vecino de i el vrtice que se est visitando y j ya se ha visitado, la desigualdad (14.1) no puede darse, por lo que, a diferencia del algoritmo recorrer no es
necesario verificar si j ya ha sido visitado.
- Para demostrar esta propiedad y que el algoritmo es correcto se usa
de forma esencial que we 0 para todo e E. Nosotros dejaremos estas
propiedades para cursos de matemtica discreta o teora de grafos.
Otra simplificacin respecto del algoritmo recorrer es que dado que estamos
poniendo w{i,j} = cuando {i, j}
/ E, los vrtices j adyacentes a i se caracterizan por w{i,j} < , y los vrtices j que no han ingresado en la cola son los que
satisfacen dj = . El algoritmo resultante est esquematizado en seudo-cdigo
en el cuadro 14.2.
- Observar que ponemos w{i,i} = . Cuando i se incorpora a Q es di <
y la desigualdad (14.1) no es vlida, de modo que i no vuelve a ponerse en
la cola Q ni se modifica di .
Algoritmo de Dkstra
Entrada:
Salida:
Comienzo
para todo i V hacer di ;
ds 0; Q {s};
repetir
sea i Q tal que di = mnjQ dj ;
si i 6= t entonces
sacar i de Q;
( examinar vecinos )
para todo j V hacer
si di + w{i,j} < dj entonces
si dj = entonces agregar j a Q;
dj di + w{i,j}
hasta que i = t o Q =
Fin
Pg. 138
Grafos
(* variables auxiliares *)
i, j, k, kmin: integer;
d, dmin: tipocosto;
begin
(* inicializacion *)
for i := 1 to ngrafo do begin
padre[i] := 0; dist[i] := infinito end;
(* s es la "raiz" y el unico en la cola al comenzar *)
padre[s] := s; dist[s] := 0; hay := 1; avisitar[1] := s;
repeat (* aca hay > 0 *)
(* nuevo i: el de minima distancia en la cola *)
kmin := hay; i := avisitar[hay]; dmin := dist[i];
for k := 1 to hay - 1 do begin
j := avisitar[k]; d := dist[j];
if (d < dmin) then begin
kmin := k; i := j; dmin := d end
end;
(* ahora tenemos el nuevo i *)
if (i <> t) then begin
(* intercambiamos i con el ultimo en la cola *)
avisitar[kmin] := avisitar[hay];
(* y sacamos i de la cola *)
hay := hay - 1;
(* examinar vecinos de i *)
for j := 1 to ngrafo do
if (dist[i] + costos[i,j] < dist[j]) then begin
if (dist[j] = infinito) then begin
(* agregar j a la cola *)
hay := hay + 1; avisitar[hay] := j end;
(* actualizar dist y padre *)
dist[j] := dist[i] + costos[i,j];
padre[j] := i
end
end (* if i <> t *)
until ((i = t) or (hay = 0))
end;
Observemos que:
La distancia desde s al vrtice i, usando como vrtices intermedios slo
vrtices ya visitados, se indica por dist i . Inicialmente dist i = para todo
i.
El arreglo padre es similar al visto en los procedimientos profundidad
(en el problema 14.6) o ancho (en el problema 14.9), y nos servir para
reconstruir el camino de s a t (ver tambin el problema 14.8.a)). padre
puede eliminarse si no se desea conocer este camino, pues para reconocer
si un vrtice ha ingresado alguna vez a la cola podemos usar dist.
La cola de vrtices a visitar se guarda en el arreglo avisitar , que inicialmente slo contiene al vrtice s.
En el lazo principal, se busca en la cola el vrtice con menor valor de
dist y se lo intercambia con el ltimo de la cola. El procedimiento para
encontrar el mnimo y modificar la cola es similar al proceso de seleccin
directa (pg. 92).
Pg. 139
(4)
Alguna?
Pg. 140
Grafos
(14.2)
Algoritmo de Prim
Entrada:
Salida:
Comienzo
para todo i V hacer di ;
Q {r}; dr 0;
V (T ) ; costoarbol 0;
mientras Q 6= hacer
Sea i Q tal que di = mnjQ dj ;
sacar i de Q;
( actualizar datos de T )
poner i en V (T ); costoarbol costoarbol + di ;
( examinar vecinos de i )
para todo j V hacer
si j
/ V (T ) y w{i,j} < dj entonces
si dj = entonces agregar j a Q;
dj w{i,j} ;
si |V (T )| < |V | entonces el grafo no es conexo
en otro caso el costo mnimo es costoarbol
Fin
procedure arbolminimo;
var
avisitar: arreglodevertices; (* la cola Q *)
visitado: array[1..MAXN] of boolean; (* V(T) *)
hay: integer; (* la cantidad de elementos en la cola *)
(* variables auxiliares *)
i, j, k, kmin: integer;
d, dmin: tipocosto;
begin
(* inicializacion *)
for i := 1 to ngrafo do begin
padre[i] := 0;
dist[i] := infinito;
visitado[i] := false
end;
narbol := 0;
costoarbol := 0;
(* r es la raiz *)
padre[r] := r; dist[r] := 0; hay := 1; avisitar[1] := r;
repeat (* aca hay > 0 *)
(* nuevo i: el de minima distancia en la cola *)
kmin := hay; i := avisitar[hay]; dmin := dist[i];
for k := 1 to hay - 1 do begin
j := avisitar[k]; d := dist[j];
Pg. 141
Pg. 142
Grafos
Pg. 143
Apndice A
Programas mencionados
Problema 2.2: holamundo
program holamundo(input, output);
(* primer programa *)
begin
writeln(Hola Mundo!);
writeln;
writeln(y Chau!)
end.
writeln;
write(Entrar un entero: ); readln(a);
writeln;
writeln(El entero leido es , a);
writeln; writeln(** Fin **)
end.
Pg. 145
Pg. 146
Programas mencionados
var
a: integer;
x: real;
begin
writeln(** Asignar un entero a un real);
writeln;
write(Entrar el valor del entero: ); readln(a);
x := a;
writeln;
writeln( a, cambiado a real es: , x);
writeln; writeln(** Fin **)
end.
Pg. 147
Pg. 148
Programas mencionados
readln(inicial);
write(Entrar el valor final (en grados): );
readln(final);
write(Entrar el valor de incremento (en grados): );
readln(incremento);
writeln;
writeln(Angulo
Seno);
grados := inicial;
while (grados <= final) do begin
radianes := grados * pi/180;
writeln(grados:5, sin(radianes):15:5);
grados := grados + incremento
end;
writeln; writeln(** Fin **)
end.
Pg. 149
Pg. 150
Programas mencionados
var a, b, c: integer;
begin
writeln(** Determinar la cantidad de cifras de un);
writeln( entero (sin tener en cuenta el signo));
writeln;
write(Entrar el numero: ); readln(a); writeln;
if (a < 0) then b := -a else b := a;
c := 0;
repeat
c := c + 1;
b := b div 10
until b = 0;
writeln(La cantidad de cifras de , a:1, es , c:1);
writeln; writeln(** Fin **)
end.
x, pot: real;
n, i: integer;
begin
writeln(** Calculo de la potencia x a la n);
writeln;
write(Entrar x (real): ); readln(x);
write(Entrar n (entero positivo): ); readln(n);
pot := 1;
for i := 1 to n do pot := pot * x;
writeln;
writeln(x, a la , n:1, es , pot);
writeln; writeln(** Fin **)
end.
Pg. 151
Pg. 152
Programas mencionados
end.
inicializacion *)
= <retorno>): );
true
s + x end
read(c);
if (c = ) then enpalabra := false
else if (not enpalabra) then (* nueva palabra *)
begin enpalabra := true; cuenta := cuenta + 1 end
until eoln; (* fin del renglon *)
readln (* leer fin del renglon *)
end;
readln; (* leer fin de linea de renglon vacio *)
writeln(Se ingresaron , cuenta:1, palabras);
writeln; writeln(** Fin **)
end.
Pg. 153
Pg. 154
Programas mencionados
writeln;
(* inicializar el arreglo *)
for digito := 0 to 9 do terminaen[digito] := 0;
(* entrar datos *)
write(Entrar un entero (fin = <retorno>): );
while (not eoln) do begin
readln(dato);
digito := abs(dato) mod 10;
terminaen[digito] := terminaen[digito] + 1;
write(Entrar un entero (fin = <retorno>): )
end;
readln;
(* salida *)
writeln;
writeln( Digito
numero de datos);
for digito := 0 to 9 do
writeln( digito:4, terminaen[digito]:20);
writeln; writeln(** Fin **)
end.
Pg. 155
Pg. 156
Programas mencionados
(* salida: imprimirlo *)
writeln;
writeln(El renglon ingresado es: );
writeln;
for i := 1 to n do write(r[i]);
writeln;
(* Fin *)
writeln; writeln(** Fin **)
end.
Pg. 157
Pg. 158
Programas mencionados
write(Implementacion para );
writeln(f(x) = x (x + 1) (x + 2) (x - 4/3));
writeln;
(* datos de entrada *)
write( Entrar cota inferior para x: ); readln(poco);
write( Entrar cota superior para x: ); readln(mucho);
writeln;
(* inicializacion *)
ypoco := f(poco); ymucho := f(mucho);
seguir := (ypoco * ymucho < 0);
iter := 0;
(* lazo principal *)
while (seguir) do begin
iter := iter + 1;
x := (poco + mucho) / 2;
y := f(x);
if (abs(y) < dify) then seguir := false
else if (iter = maxiter) then seguir := false
else if (y * ypoco < 0) then mucho := x
else begin poco := x; ypoco := y end
end;
(* salida *)
if (iter > 0) then (* hay una solucion, aceptable o no *)
begin
writeln( Solucion obtenida:
, x);
writeln( Valor de f:
, y);
writeln( Iteraciones realizadas: , iter:1);
if (abs(y) > dify) then begin
writeln;
write(* La respuesta puede no estar );
writeln(cerca de una raiz *)
end
end;
(* fin *)
writeln; writeln(** Fin **)
end.
Pg. 159
Pg. 160
Programas mencionados
begin
writeln(** Hacer una tabla del seno dando valores);
writeln( inicial, final, y del incremento (en grados).);
writeln
end;
procedure leerdatos;
begin
write(Entrar el valor inicial (en grados): );
readln(inicial);
write(Entrar el valor final (en grados): );
readln(final);
write(Entrar el valor de incremento (en grados): );
readln(incremento);
writeln
end;
procedure imprimirtabla;
var
grados: integer;
radianes: real;
begin
writeln(Angulo
Seno);
grados := inicial;
while (grados <= final) do begin
radianes := grados * pi/180;
writeln(grados:5, sin(radianes):15:5);
grados := grados + incremento
end
end;
procedure cartelfinal;
begin writeln; writeln(** Fin **) end;
begin
cartelesiniciales;
leerdatos;
imprimirtabla;
cartelfinal
end.
begin
writeln(** Prueba de intercambio de variables);
writeln;
x := 5; y := 2;
writeln(Antes: x = , x:2, , y = , y:2);
incorrecto(x,y);
writeln(Despues: x = , x:2, , y = , y:2);
writeln; writeln(** Fin **)
end.
Pg. 161
Pg. 162
Programas mencionados
Pg. 163
Pg. 164
Programas mencionados
const
MAXN = 100; (* maximo numero de datos a guardar *)
nada = 0; (* para cuando no hay hijos *)
type
indice = integer; (* para senialar los indices *)
tipodato = char; (* el tipo de datos a ingresar *)
nodo = record
llave: tipodato;
(* dato *)
cuenta: integer;
(* veces que aparecio *)
izquierda: indice; (* hijo a la izquierda *)
derecha: indice
(* hijo a la derecha *)
end;
tipoarbol = array[1..MAXN] of nodo;
var
narbol: integer;
arbol: tipoarbol;
raiz: indice;
dato: tipodato;
(*
(*
(*
(*
begin
if (w <> nada) then
with arbol[w] do begin
enorden(izquierda);
writeln(llave:10, cuenta:20);
enorden(derecha)
end
end;
begin
(* carteles *)
writeln(** Arbol binario); writeln;
write( Entrar caracteres y contar);
writeln( las veces que aparecieron);
writeln;
(* inicializacion *)
narbol := 0;
raiz := nada;
(* lectura de datos y construccion del arbol *)
while (entrardatos(dato)) do binario(dato, raiz);
(* salida y fin *)
writeln;
writeln(Impresion en orden:);
writeln;
writeln(
Caracter
Cantidad de Apariciones);
enorden(raiz);
writeln; writeln(** Fin **)
end.
Pg. 165
Apndice B
operacin
operando
resultado
identidad
inversin de signo
suma
resta
producto
divisin entera
divisin
resto
entero o real
entero o real
entero o real
entero o real
entero o real
entero
entero o real
entero
B.1.2. Relacionales
Operador
=
<>
<
>
<=
>=
operacin
operando
resultado
igualdad
desigualdad
menor
mayor
menor o igual
mayor o igual
lgico
lgico
lgico
lgico
lgico
lgico
B.1.3. Lgicos
Operador
operacin
operando
resultado
not
or
and
negacin
disyuncin
conjuncin
lgico
lgico
lgico
lgico
lgico
lgico
Pg. 167
B.1.4. Precedencia
Operador
*
=
/
<>
Clasificacin
negacin lgica
multiplicacin
adicin
relacin
not
div mod and
+ - or
> < >= <= in
maxint
true
Tipos
boolean
char
integer
real
text
Variables
input
output
operacin
argumento
resultado
abs
arctan
chr
exp
ln
odd ()
round ()
sin
sqr
sqrt
trunc ()
valor absoluto
arco tangente
carcter en orden
exponencial (ex )
logaritmo (base e)
si impar
redondeo
seno
cuadrado
raz cuadrada
truncar
entero o real
entero o real
entero
entero o real
entero o real
entero
real
real o entero
real o entero
real o entero ( 0)
real
entero o real
real
carcter
real
real
lgico
entero
real
real o entero
real
entero
()
()
round (x) = trunc(x + 0.5) para x 0, y round (x) = trunc(x 0.5) para
x 0.
(
()
trunc(x ) =
bxc
dxe
si x 0,
si x < 0.
Otras funciones
eof
eoln
ord
Procedimientos
dispose get
read
readln
writeln
pred
new
reset
succ
pack
rewrite
page
unpack
put
write
Pg. 168
array
do
goto
not
record
until
begin
else
if
of
repeat
var
case
end
in
or
set
while
const
file
label
packed
then
with
div
for
mod
procedure
to
Apndice C
Algunas notaciones y
smbolos usados
Ponemos aqu algunas notaciones, abreviaturas y expresiones usadas (que
pueden diferir de algunas ya conocidas), slo como referencia: deberas mirarlo
rpidamente y volver cuando surja alguna duda.
C.1. Lgica
si y slo si. Significa que las condiciones a ambos lados son equivalentes.
Por ejemplo x 0 |x| = x se lee x es positivo si y slo si...
C.2. Conjuntos
diferencia de conjuntos, A \ B = {x : x A y x
/ B}.
Pg. 170
| |,
#
R+
|x|
El valor
p absoluto o mdulo del nmero x. Si z = a + b i C con a, b R,
|z| = a2 + b2 .
bxc
[x]
dxe
2, , etc., que
ex ,
exp(x) La funcin exponencial de base e = 2.718281828459 . . .
logb x
ln x
Pg. 171
tan x
si x > 0,
1
signo(x) = 0
si x = 0,
1 si x < 0.
- Algunos autores consideran que signo(0) no est definido.
P
Q
Pn
ai = a1 + a2 + + an .
Qn
Indica producto, i=1 ai = a1 a2 an .
Indica suma,
i=1
mq
C.5. Generales
i.e.
e.g.
Bibliografa
[1] J. L. Bentley: More Programming Pearls, Addison-Wesley, 1988.
(Pg. 116.)
[2] N. L. Biggs: Introduction to Computing with Pascal, Oxford Science Publications, 1989. (Pg. 23.)
[3] A. Engel: Exploring Mathematics with your computer, The Mathematical
Association of America, 1993. (Pg. 3.)
[4] K. Jensen y N. Wirth: PascalUser Manual and Report, Springer Verlag, 1985. (Pgs. 3, 84 y 98.)
[5] R. Johnsonbaugh: Matemticas Discretas (4"a ed.), Prentice Hall, 1999.
[6] Sir T. L. Heath: The thirteen books of Euclids Elements, vol. 2, Dover
Publications, 1956. (Pg. 54.)
[7] B. W. Kernighan y D. M. Ritchie: El lenguaje de programacin C
(2"a ed.), Prentice-Hall Hispanoamericana, 1991. (Pgs. 10 y 121.)
[8] D. E. Knuth: The Art of Computer Programming, Addison-Wesley. Vol. 1
(3"a ed.), 1997; vol. 2 (3"a ed.), 1997; vol. 3 (2"a ed.), 1997. (Pgs. 52, 86,
89 y 116.)
[9] C. H. Papadimitriou y K. Steiglitz: Combinatorial Optimization, Algorithms and Complexity, Dover, 1998. (Pgs. 139 y 143.)
[10] K. H. Rosen: Elementary Number Theory and its Applications (3"a ed.),
Addison Wesley, 1993. (Pg. 40.)
[11] N. Wirth: Introduccin a la Programacin Sistemtica, El Ateneo, 1984.
(Pgs. 3 y 75.)
[12] N. Wirth: Algoritmos y Estructuras de Datos, Prentice-Hall Hispanoamericana, 1987. (Pgs. 3, 40, 75, 89, 98 y 121.)
ndice alfabtico
mq , 33, 171
mn , 18, 33, 171
, ver pi
;, 8
antes de else, 25
antes de end, 28
ao bisiesto, 26
adyacencia (matriz de), 124
adyacente (vrtice), 122
aguja (en Hanoi), 103, 109
Al-Khwarizmi, 24
algoritmo, 24
de bsqueda, ver bsqueda
de clasificacin, ver clasificacin
Dkstra, 136
Euclides, 49
Floyd-Warshall, 139
para generar caminos, 111
para grafos, ver grafo
para permutaciones, 113
para subconjuntos, 109
Prim, 140
recorrer, 127
Ana, 87
and, 21
aproximacin, ver tambin convergencia, mtodo Monte Carlo
factorial, 100
nmero armnico Hn , 42
raz cuadrada, 46
raz de ecuacin, 66
sen x, 61
rbol
binario ordenado, 117
caracterizacin, 124
de expansin, 128
definicin, 123
generador, 128
mnimo, 134
hoja, 124
rama, 124
archivo
caja de herramientas, 80
de texto, 82, ver tambin editor
de textos
para guardar programa, 8
arista
de grafo, 122
extremo, 122
lista de, 124
array, ver arreglo
arreglo, 55
dimensin, 55
ASCII (cdigo), 22, 23
backtracking, ver rastreo inverso
begin-end, 27
en parte principal, 8
para funciones y procedimientos, 63
Beli, 68, 69
Bigollo, ver Fibonacci
Binet, 54
biseccin (mtodo), 66
bit, 5
Boole, 11
boolean, ver variable lgica
bucle (lazo), 29
bsqueda
binaria, 90
en grafo, 127
lineal, 57
lineal con centinela, 89
byte, 6
catico, 48
caja de herramientas, 80
clculo
numrico, ver sec. 5.1
suma o producto, 31
calendario (juliano y gregoriano), 26
camino
uv, 123, 131
en grafo, 123
carcter
comparacin, 26
Pg. 174
imprimible, 22
y ordinal, 23
case, 24
char, 11, ver tambin carcter
chr, 22
ciclo
de Euler, 131
en grafo, 123
clasificacin
rbol binario, 117
caracteres, 26
comparacin de mtodos, 94
estabilidad, 98
insercin directa, 92
intercambio directo, 93
mtodos, 92
por conteo, 94
registros, 97, 98
seleccin directa, 92
cola, 107
de prioridad, 139
fifo, 107, 132
lifo (pila), 107, 132
componente conexa, 123
condicin
de control, 25
consola, 5
const, 31, 57, 62
contador, 30, 31, 33, 86, 110112,
114
en for, ver variable de control
en arreglo, 56
en lazo, 67, 90, 93, 95
control
condicin de, 25
variable de, 35
convergencia, 43, 44, ver tambin sec.
5.1
mtodo de punto fijo, 43, 48
polinomios, 59
CPU, 5
criterio de parada, 46, 48, 66, 68
cuadrado perfecto, 55
dato
tipo de, 11
de Moivre, A., 54
De Morgan, 60
leyes de, 22
densidad, 18
Dkstra, 136, 140
algoritmo, 136
Diofanto, 52
ndice alfabtico
Dirichlet, 44
principio de, 87
div, 15
do
y for, 34
y while, 29
downto, 35, 36, ver tambin for-do
Durstenfeld R., 116
e (= 2.718 . . .), 35, 43, 100, 170
Monte Carlo, 88
eco, 38
de renglones, 40, 78
ecuacin
cuadrtica, 42
diofntica, 52
no lineal, 53
editor de textos, 7, 84, ver tambin
archivo de texto
else, ver tambin if-then
; antes de, 25
end, ver tambin begin-end
; antes de, 28
sin begin, 95
entero, ver integer
entrada, 5
eof, 83
eoln, 36
psilon
mquina (mq ), 33
mnimo (mn ), 33
error
absoluto y relativo, 34, 48
numrico, 32, 33, 35, 41, 42, 45,
67
estrategia, ver mtodo
Euclides, 50
algoritmo para mcd, 49, 50, 52
Euler, 42, 54
ciclo de, 131
constante de (), 42
Excel, 69
exponente, 18
factorial, 32, 53
recursivo, 100
Fermat, 52
Fibonacci, 54
nmero de, 53, 111
Flor, 105
Floyd R., 116, 139
Floyd y Warshall (algoritmo), 139
for-do, 34
ndice alfabtico
formato
a la salida, 15
para caracteres, 23
para entero, 15
para real, 15
para variables lgicas, 21
frmula
Euler-Binet, 53
Gauss, 32, 49, 99
para xy , 35
Stirling para n!, 100
forward, 70
funcin, ver tambin procedimiento,
ver cap. 7
function, ver cap. 7
Gauss, 32
suma de, 31, 41, 99
generador, ver rbol generador
Geri, 52
get (en Pascal), 108
get (en cola), 108
grafo, 122, 127
arista, 122
con pesos, 133
conexo, 123
dirigido (digrafo), 124
representacin, 124
simple, 122
vrtice, 122
Gregorio (Papa), 26
Guille, 52
Hanoi (torres de), 103
Horner, 60
regla, 60
Pg. 175
Leonardo de Pisa, ver Fibonacci
lineal
estructura de arreglo, 117
lista, ver tambin arreglo
de aristas, 124
encadenada, 108, 125
llamar
funcin o procedimiento, 64
Maggie, 114
mantisa, 18
matriz
arreglo multidimensional, 80
de adyacencias, 124
mximo comn divisor, ver mcd
maxint, 18, 171, ver tambin integer
mcd, 49, 52
recursivo, 101, 102
memoria (de computadora), 5
mtodo
babilnico, 46
barrido, 52
biseccin, 66
clasificacin, ver clasificacin
Monte Carlo
e, 88
, 88
Newton-Raphson, 47
punto fijo, 43
mnimo comn mltiplo (mcm), 51
mod, 17
Moses L. E., 116
Kruskal, 140
Newton, 47
nivel (en rbol), 124
normalizacin, 48
not, 21
notacin
cientfica, 14, 15, 18
punto fijo, 15
punto flotante, 15
nmero
armnico (Hn ), 41
de Fibonacci, ver Fibonacci
entero, ver tambin seccin 5.2,
integer
factorial, ver factorial
primo, 49, ver primo
real, ver real
romano, 27, 40
Lagrange, 60, 61
lazo, 29
Pg. 176
ord, 22
ordinal y carcter, 23
output (al comienzo de programa),
8
Pablito, 51
packed array, 81
parmetro
formal, 72
real, 72
pasar (por valor o referencia), 72
Pascal (Blaise), 7
permutacin
de n en k, 114
pi (), 31, 61
en programa, 31, 71
Monte Carlo, 88
punto fijo, 46
pila, 107
en recorrido, 129
piso, 20, 170
Pitgoras, 50
terna pitagrica, 52
polinomio, 59
Lagrange, 59, 60
pop (en pila), 108
potencia (clculo de), 35, 62, 64
Prim, 140
algoritmo, 140
primo, 49, 105
primos entre s (coprimos), 49
principio
de Dirichlet, casillero o palomar,
ver Dirichlet, principio de
problema
cajas, 91
de manos, 114
del cumpleaos, 87
inters sobre saldo, 68
numrico, 42
torres de Hanoi, 103, 105
procedimiento, ver funcin, procedure
procedure, ver cap. 7
programa, 6
corrida, 6
ejecucin, 6
ejecutable, 7
fuente, 7
mencionado
arbolbinario, 119, 133, 163
babilonico, 48, 153
biseccion, 66, 68, 158
busquedalineal, 57, 77, 89, 156
ndice alfabtico
caracteres1, 23, 146
caracteres2, 26, 147
cifras, 33, 149
comparar, 26, 147
dado, 86, 162
dados, 86, 163
dearchivoaconsola, 82, 84, 161
deconsolaaarchivo, 82, 84, 161
eco, 38, 39, 151
enteroareal, 19, 145
eolnprueba, 37, 151
epsmin, 33, 36, 150
euclides, 50, 154
gauss, 32, 36, 149
holamundo, 7, 8, 144
intercambio, 72, 160
leerentero, 15, 25, 144
palabras, 39, 152
positivo, 21, 22, 146
potencia, 35, 150
potencias, 64, 72, 157
raiz, 17, 145
renglon, 57, 109, 155
resto, 29, 36, 148
segundos, 17, 145
sumardatos, 38, 39, 56, 57, 152
sumardos, 13, 15, 20, 144
tablaseno1, 31, 36, 70, 71, 148
tablaseno2, 71, 72, 159
unidades, 56, 154
valorabsoluto, 25, 146
prueba de escritorio, 29
puntero, 63, 108
push (en pila), 108
put (en Pascal), 108
put (en cola), 108
Raphson, 47
rastreo inverso, 121, 129
read, 16
readln, 15
real, 11
record, 95
recorrido de grafo, 127
a lo ancho, 129, 132
en profundidad, 129
redondear, 19, ver tambin truncar
registro, 95
regla de Horner, 60
relacin de recurrencia, 99
repeat-until, 33
reset, 82
ndice alfabtico
retornar (en funcin o procedimiento), 63
rewrite, 82
romano, ver nmero romano
rutina, 70, ver tambin funcin, procedimiento
salida, 5
seudo-cdigo, 128
signo (funcin), 44, 171
Stirling, 100
string, 81, ver tambin cadena de
caracteres
subndice, 55, ver tambin ndice
techo, 20, 170
tcnica, ver mtodo
teorema
caracterizacin de rboles, 124
Euler, 131
suma de grados, 127
terminal, 5
terna pitagrica, 52
text, ver tambin archivo de texto
como argumento, 82
tipo, 82
texto, ver editor de, archivo de
then, ver if-then
tipo (de variable), 11
to, ver for-do
truncar, 19, ver tambin redondear
type, 76
until, ver repeat-until
var
declaracin de variable, 12
pasar por referencia, 73
variable, 11
auxiliar, 53
carcter (char), 11, 22
de control en for, 35
elemental, 11
entera (integer), 11, 13
global, 65
lgica (boolean), 11, 20
local, 64
real (real), 11, 13
temporal, 53, 72
vrtice
adyacente, 122
aislado, 122
de grafo, 122
grado, 127
Pg. 177
von Neumann, 5
Warshall
y Floyd (algoritmo), 139
while-do, 29
Wiles, 52
with, 96
write, 14
writeln, 9