Libro Pascal

Notas para los cursos deComputacin y Programacin

con el lenguaje Pascal

Nstor Aguilera

Ao 2007

ndice general

ndice de figuras v

ndice de cuadros v

1. Preliminares 11.1. Temas que vemos . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2. Organizacin y convenciones que usamos . . . . . . . . . . . . . . 11.3. Ideas y consejos sueltos . . . . . . . . . . . . . . . . . . . . . . . . 21.4. Por qu Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.5. Sobre la versin 2007 . . . . . . . . . . . . . . . . . . . . . . . . . 4

2. El primer contacto 52.1. Un poco muy poco sobre cmo funciona la computadora . . 52.2. Programas: edicin, compilacin, ejecucin . . . . . . . . . . . . . 62.3. El puntapi inicial . . . . . . . . . . . . . . . . . . . . . . . . . . 72.4. Comentarios Bibliogrficos . . . . . . . . . . . . . . . . . . . . . . 10

3. Tipos de datos elementales 113.1. Tipos, variables e identificadores . . . . . . . . . . . . . . . . . . 113.2. Tipos numricos: entero y real . . . . . . . . . . . . . . . . . . . . 133.3. Readln . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.4. Funciones numricas . . . . . . . . . . . . . . . . . . . . . . . . . 163.5. La codificacin de enteros y reales . . . . . . . . . . . . . . . . . . 173.6. Variables lgicas . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.7. Caracteres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.8. Comentarios Bibliogrficos . . . . . . . . . . . . . . . . . . . . . . 23

4. Tomando control 244.1. If . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254.2. Begin-end . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274.3. While . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294.4. Repeat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334.5. For . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344.6. Ingresando muchos datos: eoln . . . . . . . . . . . . . . . . . . . . 364.7. Read . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394.8. Comentarios Bibliogrficos . . . . . . . . . . . . . . . . . . . . . . 40

5. Aplicaciones 415.1. Clculo numrico elemental . . . . . . . . . . . . . . . . . . . . . 41

5.1.1. Mezclando nmeros grandes y pequeos . . . . . . . . . . . . 415.1.2. Mtodos iterativos: puntos fijos . . . . . . . . . . . . . . . . 435.1.3. El mtodo babilnico . . . . . . . . . . . . . . . . . . . . . . 46

Pg. ii

5.2. Nmeros enteros . . . . . . . . . . . . . . . . . . . . . . . . . . . 495.2.1. Algoritmo de Euclides . . . . . . . . . . . . . . . . . . . . . . 495.2.2. Ecuaciones diofnticas . . . . . . . . . . . . . . . . . . . . . . 525.2.3. Nmeros de Fibonacci . . . . . . . . . . . . . . . . . . . . . . 53

5.3. Comentarios Bibliogrficos . . . . . . . . . . . . . . . . . . . . . . 54

6. Arreglos 556.1. Dimensionamiento de arreglos . . . . . . . . . . . . . . . . . . . . 556.2. Bsqueda Lineal . . . . . . . . . . . . . . . . . . . . . . . . . . . 576.3. Polinomios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

7. Funciones y Procedimientos 627.1. Funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 627.2. El mtodo de la biseccin . . . . . . . . . . . . . . . . . . . . . . 667.3. Procedimientos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 707.4. Pasando por valor o por referencia . . . . . . . . . . . . . . . . . 727.5. Comentarios Bibliogrficos . . . . . . . . . . . . . . . . . . . . . . 75

8. Todos juntos: arreglos, funciones y procedimientos 768.1. Definiendo nuestros propios tipos de datos: type . . . . . . . . . . 768.2. Ingreso e impresin de arreglos . . . . . . . . . . . . . . . . . . . 778.3. La caja de herramientas . . . . . . . . . . . . . . . . . . . . . . . 808.4. Arreglos multidimensionales . . . . . . . . . . . . . . . . . . . . . 808.5. Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 818.6. Manejo elemental de archivos de texto . . . . . . . . . . . . . . . 828.7. Comentarios Bibliogrficos . . . . . . . . . . . . . . . . . . . . . . 84

9. Nmeros Aleatorios y Simulacin 859.1. Nmeros aleatorios . . . . . . . . . . . . . . . . . . . . . . . . . . 859.2. Aplicaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

10. Bsqueda y clasificacin 8910.1. Bsqueda lineal con centinela . . . . . . . . . . . . . . . . . . . . 8910.2. Bsqueda binaria . . . . . . . . . . . . . . . . . . . . . . . . . . . 9010.3. Mtodos elementales de clasificacin . . . . . . . . . . . . . . . . 9210.4. Registros (records) . . . . . . . . . . . . . . . . . . . . . . . . . . 9510.5. Comentarios Bibliogrficos . . . . . . . . . . . . . . . . . . . . . . 98

11. Recursin 9911.1. Funciones y procedimientos definidos recursivamente . . . . . . . 10011.2. Los Grandes Clsicos de la Recursin . . . . . . . . . . . . . . . . 10311.3. Comentarios Bibliogrficos . . . . . . . . . . . . . . . . . . . . . . 106

12. Objetos combinatorios 10712.1. Pilas y colas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10712.2. Generando Subconjuntos . . . . . . . . . . . . . . . . . . . . . . . 10912.3. Caminante, no hay caminos... . . . . . . . . . . . . . . . . . . . . 11112.4. Generando permutaciones . . . . . . . . . . . . . . . . . . . . . . 11312.5. Objetos combinatorios generados al azar . . . . . . . . . . . . . . 114

13. rboles binarios ordenados 11713.1. Comentarios Bibliogrficos . . . . . . . . . . . . . . . . . . . . . . 121

ndice general Pg. iii

14. Grafos 12214.1. Representacin de grafos en la computadora . . . . . . . . . . . . 12414.2. Recorriendo un grafo . . . . . . . . . . . . . . . . . . . . . . . . . 12714.3. Recorrido en profundidad y a lo ancho . . . . . . . . . . . . . . . 12914.4. Grafos con pesos . . . . . . . . . . . . . . . . . . . . . . . . . . . 13314.5. Camino ms corto: Dkstra . . . . . . . . . . . . . . . . . . . . . 13614.6. Mnimo rbol generador: Prim . . . . . . . . . . . . . . . . . . . . 14014.7. Comentarios Bibliogrficos . . . . . . . . . . . . . . . . . . . . . . 143

A. Programas mencionados 144Problema 2.2: holamundo . . . . . . . . . . . . . . . . . . . . . . . . . . 144Problema 3.2: sumardos . . . . . . . . . . . . . . . . . . . . . . . . . . . 144Problema 3.4: leerentero . . . . . . . . . . . . . . . . . . . . . . . . . . 144Problema 3.5: raiz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145Problema 3.6: segundos . . . . . . . . . . . . . . . . . . . . . . . . . . . 145Problema 3.10: enteroareal . . . . . . . . . . . . . . . . . . . . . . . . . 145Problema 3.17: positivo . . . . . . . . . . . . . . . . . . . . . . . . . . . 146Problema 3.19: caracteres1 . . . . . . . . . . . . . . . . . . . . . . . . . 146Problema 4.2: valorabsoluto . . . . . . . . . . . . . . . . . . . . . . . . . 147Problema 4.4: comparar . . . . . . . . . . . . . . . . . . . . . . . . . . . 147Problema 4.5: caracteres2 . . . . . . . . . . . . . . . . . . . . . . . . . . 147Problema 4.11: resto . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148Problema 4.12: tablaseno1 . . . . . . . . . . . . . . . . . . . . . . . . . 148Problema 4.13: gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149Problema 4.16: cifras . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149Problema 4.17: epsmin . . . . . . . . . . . . . . . . . . . . . . . . . . . 150Problema 4.18: potencia . . . . . . . . . . . . . . . . . . . . . . . . . . . 150Problema 4.23: eolnprueba . . . . . . . . . . . . . . . . . . . . . . . . . 151Problema 4.24: eco . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151Problema 4.25: sumardatos . . . . . . . . . . . . . . . . . . . . . . . . . 152Problema 4.27: palabras . . . . . . . . . . . . . . . . . . . . . . . . . . . 152Problema 5.11: babilonico . . . . . . . . . . . . . . . . . . . . . . . . . . 153Problema 5.13: euclides . . . . . . . . . . . . . . . . . . . . . . . . . . . 154Problema 6.1: unidades . . . . . . . . . . . . . . . . . . . . . . . . . . . 154Problema 6.2: renglon . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155Problema 6.3: busquedalineal . . . . . . . . . . . . . . . . . . . . . . . . 156Problema 7.2: potencias . . . . . . . . . . . . . . . . . . . . . . . . . . . 157Problema 7.3: biseccion . . . . . . . . . . . . . . . . . . . . . . . . . . . 158Problema 7.6: tablaseno2 . . . . . . . . . . . . . . . . . . . . . . . . . . 159Problema 7.7: intercambio . . . . . . . . . . . . . . . . . . . . . . . . . 160Problema 8.8: deconsolaaarchivo . . . . . . . . . . . . . . . . . . . . . . 161Problema 8.8: dearchivoaconsola . . . . . . . . . . . . . . . . . . . . . . 162Problema 9.1: dado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162Problema 9.2: dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163Problema 13.1: arbolbinario . . . . . . . . . . . . . . . . . . . . . . . . . 163

B. Breve referencia de Pascal 166B.1. Operadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166

B.1.1. Aritmticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166B.1.2. Relacionales . . . . . . . . . . . . . . . . . . . . . . . . . . . 166B.1.3. Lgicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166B.1.4. Precedencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

B.2. Identificadores estndares . . . . . . . . . . . . . . . . . . . . . . 167

Pg. iv

B.3. Nombres reservados . . . . . . . . . . . . . . . . . . . . . . . . . . 168

C. Algunas notaciones y smbolos usados 169C.1. Lgica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169C.2. Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169C.3. Nmeros: conjuntos, relaciones, funciones . . . . . . . . . . . . . 170C.4. Nmeros importantes en programacin . . . . . . . . . . . . . . . 171C.5. Generales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171

Bibliografa 172

ndice alfabtico 173

ndice de figuras

2.1. Esquema de transferencia de datos en la computadora. . . . . . . 62.2. Bits y byte. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.3. Esquema del desarrollo de un programa. . . . . . . . . . . . . . . 72.4. Esquema del programa ejecutable en la memoria. . . . . . . . . . 8

3.1. Datos de tipos elementales en la memoria. . . . . . . . . . . . . . 123.2. Los datos con sus identificadores. . . . . . . . . . . . . . . . . . . 123.3. Esquema de la densidad variable. . . . . . . . . . . . . . . . . . . 19

5.1. Grficos de y = cosx y y = x. . . . . . . . . . . . . . . . . . . . . 455.2. Aproximndose al punto fijo de cosx. . . . . . . . . . . . . . . . 45

6.1. Esquema del arreglo v guardado en memoria. . . . . . . . . . . . 566.2. Aproximacin de senx mediante un polinomio. . . . . . . . . . . 59

7.1. Una funcin continua con distintos signos en los extremos. . . . . 667.2. Programa, funciones y procedimientos en la memoria. . . . . . . 707.3. Intercambio de los valores de u y v. . . . . . . . . . . . . . . . . . 73

10.1. Ordenando por conteo. . . . . . . . . . . . . . . . . . . . . . . . . 9410.2. Esquema del registro de tipo complejo en memoria. . . . . . . . 96

11.1. Contando la cantidad de caminos posibles. . . . . . . . . . . . . . 10211.2. Las torres de Hanoi. . . . . . . . . . . . . . . . . . . . . . . . . . 105

13.1. Una estructura lineal. . . . . . . . . . . . . . . . . . . . . . . . 11713.2. Un rbol binario ordenado. . . . . . . . . . . . . . . . . . . . . . 11713.3. Disposicin del arreglo de registros luego de ingresar los datos. . 11813.4. Disposicin del rbol binario luego de ingresar los datos. . . . . . 11913.5. Los registros de la figura 13.4 proyectados. . . . . . . . . . . . 11913.6. Los registros con ndices para la estructura de rbol binario. . . . 119

14.1. Un grafo con 6 vrtices y 7 aristas. . . . . . . . . . . . . . . . . . 12314.2. Un grafo no conexo y un rbol. . . . . . . . . . . . . . . . . . . . 12314.3. Un grafo con pesos en las aristas. . . . . . . . . . . . . . . . . . . 133

ndice de cuadros

4.1. Prueba de escritorio . . . . . . . . . . . . . . . . . . . . . . . . . 30

8.1. Estructura de un programa Pascal. . . . . . . . . . . . . . . . . . 778.2. Diferencias entre el estndar y Turbo Pascal. . . . . . . . . . . . 83

10.1. Comparacin de algoritmos de clasificacin. . . . . . . . . . . . . 94

14.1. Esquema del algoritmo recorrer. . . . . . . . . . . . . . . . . . . . 12814.2. Esquema del algoritmo de Dkstra. . . . . . . . . . . . . . . . . . 13714.3. Esquema del algoritmo de Prim. . . . . . . . . . . . . . . . . . . 141

Captulo 1

Preliminares

En este curso se van entrelazando la introduccin de los elementos de pro-gramacin estructurada con la resolucin de problemas de matemticas, inclu-yendo temas de anlisis y clculo numrico, teora de nmeros, combinatoriay grafos, sirviendo tanto de introduccin de algunos temas como de repaso yfortalecimiento de otros. Por el contrario, se cubre muy poco de las aplicacionesinformticas como bases de datos.

1.1. Temas que vemosEn los captulos 2, 3, 4, 6, 7, 8, 10 y 11 cubrimos temas como tipos elementales

de datos, estructuras de control, arreglos, funciones, archivos de texto, bsqueda,clasificacin elemental y recursin. Estos temas son ms o menos comunes atodos los cursos de programacin, aunque ac el nfasis est repartido entre lasmatemticas y la programacin.

En cambio, los captulos 5 y 9 cubren temas de matemticas (tericas oaplicadas) que normalmente no se dan, como clculo numrico, nmeros enteroso uso de nmeros aleatorios, claro que puestos a un nivel muy elemental.

Pilas y colas es un tema normalmente incluido en cursos de programacin,pero la perspectiva que damos en los captulos 12 y 13 es bastante distinta.All trabajamos con objetos combinatorios, como subconjuntos, permutacionesy rboles binarios, donde aparece verdaderamente la fuerza de recursin.

El ltimo captulo tampoco se cubre en cursos tradicionales. Se incluye paracumplir con un requisito de las carreras ingenieriles, y para entenderlo a plenoes conveniente haber tenido algn contacto previo con la teora de grafos, adiferencia de los anteriores que no necesitan de mayores prerrequisitos (aunques cierta madurez matemtica).

1.2. Organizacin y convenciones que usamosEn los captulos 2 a 14 se presentan los temas y problemas, agrupados en

secciones y a veces subsecciones. Los problemas estn numerados comenzandocon 1 en cada captulo, de modo que el problema 4.5 se refiere al problema 5del captulo 4. De modo similar, la seccin 3.2 se refiere a la seccin 2 delcaptulo 3.

En varios de los problemas se mencionan programas completos, puestos jun-tos en el apndice A. Tambin entre los apndices incluimos una breve referenciade Pascal (apndice B) y notaciones usadas en el libro (apndice C).

Pg. 2 Preliminares

A veces hay texto intercalado entre los problemas, por lo que para indicarel fin del enunciado de un problema est el signo $, que puede leerse como lacortamos ac.

Intercalados entre texto y enunciados de problemas, hay algunas notas ycomentarios, en tipo de letra ms chico para no distraer demasiado del textoprincipal, 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 laforma- Esto es una nota.

Los nombres de los programas aparecen con otro tipo de letra, as, mientrasque lo que escribiremos en la computadora est indicado en monotipo, as,algunas veces entre comillas dobles, para recalcar algn fragmento o tratandode evitar confusiones, como ste, reservando las comillas simples para carac-teres, como a , que imitando la usanza en Pascal. Tambin algunas veces losespacios en blanco de un texto se ponen de esta forma para distinguirlos.

Siguiendo la tradicin norteamericana, la computadora expresa los nmerosponiendo un punto decimal en vez de la coma, y para no confundirnosseguimos esa prctica. As, 1.589 es un nmero entre 1 y 2, mientras que 1589es un nmero entero, mayor que mil. A veces dejamos pequeos espacios entrelas 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, demodo que en la escritura de cdigos los obviaremos (escribiendo a o ni, yparagero quedar como paraguero).

En fin, en el texto indicamos con el pulsado de la tecla retorno(o return en teclados ingleses) para iniciar un nuevo rengln. Dependiendo delsistema operativo, es posible que debas pulsar en cambio la tecla intro (oenter en ingls).

1.3. Ideas y consejos sueltosUno puede darse una idea de cmo cocinar mirando un libro de cocina, pero

seguramente la experiencia es mucho ms completa y satisfactoria si se tienenlos ingredientes, las cacerolas y la misma cocina. Del mismo modo, se puedeapreciar qu es la programacin mirando un libro, pero vas a sacar mucho msprovecho si dispons adems de una computadora y un compilador Pascal conlos que trabajar.

En programacin es muy importante copiar (y tomar ideas y estructurasde) programas ya hechos. Idealmente cuando trabajes con los contenidos deeste libro copiars (preferentemente de un diskette o de internet) los programaspresentados, y hars variaciones o copiars partes de uno o ms de ellos pararesolver problemas.

Con ese propsito inclu muchos programas completos que sirven como base.Unos cuantos no estn completos (pero funcionan), y tendrs que completar ocambiar partes para llegar a algo satisfactorio. En todos los casos trat de ponerprogramas claros (que se entiendan) antes que eficientes.

Muchos principiantes se ponen ansiosamente a escribir o copiar un programasin tener un plan especfico, quizs por su experiencia previa con la computado-

1.4. Por qu Pascal Pg. 3

ra. Una buena parte de los problemas que aparecen no son sencillos de resolver,y seguramente no se resuelven probando con distintos botones (no hay me-nes!). Inclusive hay varios problemas que no necesitan de la computadora.

Al principio el curso parece (y es) fcil y muchos estudiantes se dejan estar,pero ya hacia el final del captulo 3 las cosas se ponen ms movidas y es difcilde recuperar el tiempo perdido: es importante que mantengas el ritmo del cursoque, un poco ms o un poco menos, es de un captulo por semana.

Si quers sacar provecho del curso, muchas veces vas a tener que usar lpizy papel para trazarte un plan de resolucin antes de copiar o modificar los pro-gramas, pero para eso debs entender primero qu es lo que hacen las distintaspartes y por sobre todo a dnde se quiere llegar.

La adquisicin de conocimientos no es gratuita y requiere esfuerzo y tiempo,y las equivocaciones forman parte inevitable de este proceso: habr que estardispuesto a pasar un buen rato en la silla!

An cuando no podamos resolver un problema en programacin o en mate-mticas, es poco til que alguien nos cuente la solucin si antes no hemos hechoun trabajo propio: de este modo podremos apreciar, e inclusive criticar, la quenos proponen.

En algunos problemas se incluyen sugerencias para la resolucin, que estnpuestas como orientacin cuando ests perdido. La recomendacin es tapar lasugerencia, y recurrir a ella en segunda instancia o cuando ya hayas resuelto elproblema para ver si hay otras posibilidades de resolucin.

Esto nos trae al tema de que tanto en programacin como en matemticas,no hay una nica forma de hacer los programas o resolver los problemas. Lopresentado es slo una posibilidad.

A algunos les parecer que las sugerencias son oscuras o escasas, a otrosles parecer que el material presentado es excesivo, y habr otros que que-rrn resolver ms problemas. A todos les recomendamos los libros de Engel [3],Wirth [11, 12] autor del lenguaje que usamos, Pascal y Jensen y Wirth [4]para temas especficos de Pascal, que forman la base sobre la cual est hechoeste libro.

Finalmente, cuando ests perdido con alguna definicin, consult el apndi-ce B para referencias de Pascal, o el apndice C para notaciones y definicionesde matemticas, o el ndice alfabtico al final.(1)

1.4. Por qu PascalDesde cierto punto de vista, Pascal es un lenguaje obsoleto. Fue popular en

la dcada de 1980 con el auge de la computadoras personales, pero prcticamen-te no se usa profesionalmente en la actualidad. No tiene en su estndarfacilidades grficas, las rutinas de entrada y salida no son muy flexibles, e in-clusive no tiene incorporadas rutinas de nmeros aleatorios como usaremos enel curso. En fin, muchas veces su sintaxis hace que debamos hacer rodeos paraexpresar algo.

Los lenguajes de moda en estos das como Java ofrecen un paradigmams alejado de los algoritmos de matemticas, estando ms bien dirigidos a lasaplicaciones informticas.

Pascal fue creado como lenguaje para la enseanza de la programacin es-tructurada por N. Wirth, siguiendo ideas del lenguaje Algol, nombre derivadode ALGOrithmic Language, que expresa bien el propsito con el que fue creado.(1) Donde nunca se encuentra lo que uno busca, como en las guas telefnicas.

Pg. 4 Preliminares

El lenguaje C tambin deriva del Algol, y es mucho ms popular ahora quePascal. Sin embargo, para hacer un mnimo programa ya necesitamos mencio-nar qu son las bibliotecas, para leer un dato tenemos que saber qu es pasarpor valor o referencia, y su sintaxis puede ser francamente crptica para los noiniciados. En sntesis, requiere de un esfuerzo extra que dejara menos tiempopara lo que verdaderamente importa: aprender algoritmos y resolver problemasde matemticas.

El aprendizaje de Pascal da una slida base para programar en otros len-guajes, como Fortran o C, y sistemas, como Matlab o Maple, que s son usadosprofesionalmente.

No est dems comentar que este curso comenz a dictarse en el ao 1995 ba-sado en uno de los sistemas que ms se usan actualmente en aplicaciones cient-ficas. Como resultado vimos que no se aprenda una disciplina de programacin,y se confundan conceptos bsicos como que nmeros enteros y fraccionarios sonbien distintos para la computadora.

En http://math.unl.edu.ar/~aguilera/compiladores_pascal.html hayindicaciones de cmo conseguir compiladores Pascal gratis de internet. Especial-mente recomendado es el compilador GNU Pascal (gpc). Otras recomendacionesson Free Pascal (fpc) y Turbo Pascal. gpc y fpc no tienen un editor de textosintegrado (que se puede agregar) pero estn disponibles para todos los sistemasoperativos preponderantes. Son mucho ms modernos que Turbo Pascal, que sviene con un editor integrado, pero usa el sistema operativo MS-DOS y tieneserias limitaciones en el tamao de las variables.

1.5. Sobre la versin 2007Estas notas se van modificando en base a la experiencia que se gana en el

dictado del curso, de modo que a travs de los aos hay temas que se cambian,otros se eliminan, otros se agregan, y otros... reaparecen!

En esta ocasin reaparecieron la generacin de conjuntos y permutacionesaleatorias (al final del captulo 12), lo que empuj al tema de rboles binariosa un captulo separado. Tambin reescrib gran parte del captulo de grafos, quesigue ofreciendo dificultades a los alumnos (y a m para ensearlo).

Agradezco a Jorge DEla, Egle Haye, Alberto Marchi y Marcela Morvidonequienes me ayudaron a corregir errores (tipogrficos o conceptuales) en notas deaos anteriores. Especialmente agradezco a Luis Bianculli, cuyos comentarios yobservaciones me hicieron cambiar radicalmente la presentacin de arreglos dela versin de 2003 a la de 2004.

Captulo 2

El primer contacto

2.1. Un poco muy poco sobre cmo funcionala computadora

Conceptualmente, la computadora es una mquina que toma o accede adatos, los procesa y devuelve resultados. Los datos o entradas y los resultadoso salidas pueden ser simples como nmeros o letras, o mucho ms complicadoscomo una matriz o una base de datos,(1) que podemos esquematizar como

entrada procesamiento salida

En el modelo de computadora con el que trabajaremos (o de von Neumann),pensaremos que el procesamiento est a cargo de una nica unidad, llamadaCPU por Central Processing Unit o Unidad Central de Procesamiento, queaccede los datos y retorna los resultados secuencialmente, es decir, de a uno porvez, y los datos a los que accede se guardan en una lugar denominado memoria.

John von Neumann (19031957) se interes inicialmente en lgica, teorade conjuntos, de la medida, y mecnica cuntica, tocando luego temas de an-lisis funcional, teora ergdica, siendo fundador de la teora de juegos. En susltimos aos tambin tuvo influencia decisiva en ecuaciones en derivadas par-ciales y en teora de autmatas, en la que sintetiz sus conocimientos e ideasde lgica y grandes computadoras electrnicas.

En los programas que haremos normalmente nos comunicaremos con lacomputadora entrando los datos con el teclado y recibiendo los resultados enla pantalla, refirindonos en general como terminal o consola al conjunto com-binado de teclado y pantalla. Estos datos que entramos o recibimos no sondirectamente procesados por la CPU, sino que son transferidos a o desde lamemoria mediante la misma CPU u otro procesador dedicado.

Un esquema del movimiento de datos entre perifricos (consola, discos, im-presora, etc.), memoria y CPU est indicado en la figura 2.1.

Nos imaginaremos que la memoria, en donde se almacenan los datos, estconstituida por muchas cajitas pequeas llamadas bits por binary digit o dgitobinario, en cada una de las cuales slo se puede guardar un 0 o un 1. Puestoque esta caja es demasiado pequea para guardar informacin ms complicada

(1) Es como pensar en una mquina de hacer chorizos: ponemos los ingredientes (mezcla,tripa, etc.), y despus de dar vuelta la mana tenemos los chorizos.

Pg. 6 El primer contacto

(procesamiento)memoria(datos)

CPU

impresora

pantalla

teclado

discos

otros

cons

ola

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 gran-des llamadas bytes, que generalmente tienen 8 bits, conceptualmente alineados,puesto que queremos que 00001111 sea distinto de 11110000. Ver esquema en lafigura 2.2.

un byte 1 0 1 0 1 0 10

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, luegopara 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 dis-tintos podra contener un byte? Sugerencia: si el byte tiene 8 bits puede serque hayan 8 ceros y ningn uno, o 7 ceros y 1 uno, o... $

A su vez, para las computadoras ms recientes, estas unidades resultan dema-siado pequeas para alimentar a la CPU, por lo que los bits o bytes se agrupanformando cajas de, por ejemplo, 32, 64 o 128 bits (usualmente potencias de 2),siempre conceptualmente alineadas.

2.2. Programas: edicin, compilacin, ejecucinPor supuesto, queremos que la computadora haga algo con los datos que

le damos, pero tenemos que darle instrucciones sobre cmo hacerlo. El conjuntode instrucciones y datos para realizar determinada tarea es lo que llamaremosprograma, y los mismos programas pueden considerarse como un tipo especialde datos.

En particular, el sistema operativo de la computadora es un programa quealimenta constantemente a la CPU, y le va a indicar, por ejemplo, que ejecuteo corra nuestro programa, leyendo las instrucciones que contiene.

Los lenguajes de programacin son abstracciones que nos permiten escribirlas instrucciones de un programa de forma que un ser humano puede entenderms fcilmente que ristras de ceros y unos. Las instrucciones para la mquina

2.3. El puntapi inicial Pg. 7

se escriben como sentencias de acuerdo a las reglas del lenguaje en lo quese llama programa fuente.

Hay distintos tipos de lenguajes de programacin, cada uno con sus defectosy virtudes. Dentro de los que ms se usan en matemticas, estn (en orden ms omenos cronolgico) Fortran, C, Pascal, C++, y otros integrados a sistemas conposibilidades grficas y/o simblicas como Matlab, Maple o Mathematica. Enestas notas usaremos el lenguaje Pascal, que ha sido diseado para la enseanzade programacin.

N. Wirth dio el nombre de Pascal al lenguaje en honor al matemtico fran-cs Blaise Pascal (16231662), quien fue uno de los primeros en desarrollaruna calculadora mecnica, cuando tena unos 20 aos.

Sin embargo hubo muchas otras calculadoras antes, como las computadoraslunares y planetarias del astrnomo iran al-Kashi (13931449), o la de W.Schickard (15921635) que multiplicaba y divida, mientras que la de Pascal(construida entre los aos 16421644) slo sumaba y restaba.

Luego de elegir un lenguaje de programacin, al desarrollar un programa lousual es primero escribir el programa fuente (el que nosotros entendemos) conun editor de textos en la computadora, eventualmente guardando lo escrito enel disco rgido o un diskette.

El programa fuente debe ser traducido a algo que la CPU pueda entender,es decir las famosas ristras de 0 y 1. Este proceso se llama compilado, dandopor resultado un programa ejecutable, que es el que en realidad va a usar lacomputadora.- Esta descripcin basta para nuestros propsitos, en realidad todo el pro-

ceso requiere otros pasos intermedios que en nuestro caso sern hechosautomticamente.

- Algunos lenguajes son interpretados, es decir no existe la compilacin y nose crea el ejecutable.

En la mayora de los casos an para gente experimentada habr pro-blemas en la compilacin (por ejemplo, por errores de sintaxis), o al ejecutarel programa los resultados no sern los esperados. Esto da lugar a un ciclo detrabajo esquematizado en la figura 2.3.

Editar Compilar Ejecutar

Corregir

fuente ejecutable

Figura 2.3: Esquema del desarrollo de un programa.

En fin, al momento de usar el programa ejecutable, el sistema operativo loaloja en algn lugar disponible de la memoria, quedando un esquema como elde la figura 2.4.

2.3. El puntapi inicialPara lo que sigue, ser conveniente ir mirando el primer programa Pascal

con el que trabajaremos: el programa holamundo (pg. 144).En Pascal, todos los programas (fuentes) se dividen en dos partes o cuer-

pos. En la primera, a veces llamada de declaraciones, se coloca el nombre del


programaejecutable

instrucciones

datos

Memoria

Figura 2.4: Esquema del programa ejecutable en la memoria.

programa mediante program nombre(input,output) y otras sentencias queiremos viendo.- Siguiendo el estndar Pascal. Muchos compiladores aceptan la omisin de

(input, output), e inclusive algunos ignoran completamente esa parte.La segunda parte, a veces llamada principal, empieza con begin y termina

con end. (punto . incluido), y entre ellos se ponen sentencias para realizaracciones.

En ambas partes, de declaraciones y principal, las sentencias se separanmediante ;. En cualquier lugar se pueden agregar comentarios, encerradosentre (* y *) que nos ayudan a entender lo que hicimos cuando volvemosa mirar despus de un par de semanas.- Tambin se pueden encerrar comentarios entre { y } , pero no los

usaremos a fin de seguir una sintaxis ms parecida a otros lenguajes comoC o Mathematica.

Para evitar confusiones, normalmente se guarda el programa fuente en unarchivo con el mismo nombre que en la sentencia program nombre, y conextensin .p o .pas, para indicar que se trata de un programa Pascal. As, gene-ralmente guardaremos el programa fuente de nombre pepe en el archivo pepe.p opepe.pas. Al compilarlo (con xito) se crea el ejecutable. Dependiendo del com-pilador y el sistema operativo, es posible que se cambie la extensin a .exe, demodo que obtenemos el archivo pepe.exe, pero tambin es posible que (salvoindicacin en contrario) el nombre sea algo genrico como a.out.- O sea, la extensin para el ejecutable depende del sistema operativo y del

compilador, y puede no existir. Asimismo, puede no existir la extensinpara el programa fuente.

La prueba de fuego es editar, compilar y ejecutar el primer programa. Sinembargo, los detalles de cmo realizar el ciclo de edicin-compilacin-ejecucindependen del sistema operativo y el compilador (la marca del compilador) queestemos usando, de modo que habr que seguir las instrucciones de los manualeso pedir auxilio a algn conocido con este primer paso.

Problema 2.2 (Hola Mundo). Copiar, compilar y ejecutar el programa ho-lamundo, guardndolo en disco o diskette como holamundo.pas.- Muchos compiladores, entre ellos el muy difundido Turbo Pascal, hacen que

al ejecutar un programa como holamundo se abra una ventana distinta quese cierra automticamente al finalizar la ejecucin del programa. El procesopuede ser tan rpido que apenas nos damos cuenta de que ha sucedido algo.En estos casos es conveniente agregar un rengln con las instrucciones

writeln( para fin); readln

al terminar el programa, antes de end. y agregando un ; (punto ycoma) al fin del rengln anterior.

Otra posibilidad es aprender los comandos para poder pasar de unapantalla a otra.

2.3. El puntapi inicial Pg. 9

- Turbo Pascal y otros compiladores similares crean un ejecutable que quedaen memoria, y no guardan una copia en el disco salvo instruccin expresa.En la mayora de los casos no nos va a interesar guardarla.

a) Observar con cuidado los signos de puntuacin y qu hace cada una de lasinstrucciones:

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 alque 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 unrengln 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 comien-

zo de algunos de los renglones, y a veces renglones enteros en blanco, pararesaltar la estructura del programa. Esto no es necesario, e inclusive podraescribirse el programa en un nico rengln, y un espacio o varios no hacendiferencia:

i) Eliminar o agregar espacios al comienzo, en el medio y/o al final dealgunos renglones, compilar el programa y verificar que se obtiene elmismo 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 (yrecordar que ; se usa en Pascal como en castellano: para separarsentencias).- A los fines del programa fuente, los espacios, tabulaciones (tecla tab o

similar) y renglones son intercambiables (mientras no estn encerradosentre comillas simples).

d) Agregar y/o eliminar comentarios.Por ejemplo, agregar el comentario colorin, colorado despus de

writeln(y Chau!), en el mismo rengln y/o en el siguiente. $

El uso de ; en Pascal resulta un poco confuso al principio, pero debetenerse en mente que se usa como , o ; se usan al construir una oracinen castellano: para separar sentencias. Del mismo modo, . (punto) en Pascaltiene el mismo sentido que el punto final en castellano. En cambio, , (coma)se usa en forma distinta, por ejemplo, para separar argumentos de funcionescomo se hace en matemticas.

Pero no desesperar: por el momento no es necesario entender todo lo que sehace.


2.4. Comentarios BibliogrficosEl programa holamundo est tomado del libro de Kernighan y Ritchie [7], y

es clsica su inclusin al aprender a programar.

Captulo 3

Tipos de datos elementales

Recordemos que la informacin, incluyendo el programa ejecutable, se guar-da en un lugar de memoria, como ristras de ceros y unos. Como nmeros ycaracteres se representan de esta forma, la computadora al tomar un dato debesaber si se trata de uno u otro. Esto da lugar a distintos tipos de datos, comoestudiamos en este captulo.

3.1. Tipos, variables e identificadoresSupongamos que guardamos las letras siguiendo el orden del abecedario, a

como 0, b como 1, c como 10, y as sucesivamente. Vemos que no podra-mos distinguir entre el par de letras ba y la nica letra c, pues ambas serepresentaran como 10.

Para evitar esta confusin, se decide que todas las letras ocupen siempre elmismo espacio, por ejemplo un byte de 8 bits. De esta forma tendremos (ver elproblema 2.1) 28 = 256 posibilidades para los caracteres, lo cual es suficientepara guardar las letras de nuestro alfabeto (pero no los de algunos alfabetosorientales).

Habiendo decidido esto, nos toca ahora guardar nmeros. Como antes, esconveniente guardar a todos los nmeros en la misma cantidad de bits. Si us-ramos 8 bits como hicimos para las letras, tendramos slo 256 nmeros dispo-nibles, lo cual es bien pobre. Es conveniente que las cajas sean ms grandes.

Cuando la mquina lea estas cajas que guardan letras o nmeros, tiene quesaber cuntos bits juntos debe leer, e interpretar la ristra de bits segn sea unaletra o un nmero. Surgen as cuatro tipos elementales de datos, cada uno condistinta codificacin interna:

boolean o lgica, para guardar los valores true (verdadero) o false(falso),

char para guardar caracteres, i.e., letras, signos de puntuacin y otrosque veremos ms adelante,

integer para guardar nmeros enteros, como 1, 0,5, y real para guardar nmeros reales, i.e., nmeros como 123.456.

Llamamos a las variables lgicas booleanas, en honor a G. Boole (18151864), quien hizo importantes progresos al algebrizar la lgica.

En la figura 3.1 ilustramos algunas cajas con datos dentro de la memoria,con sus tipos correspondientes.

Pg. 12 Tipos de datos elementales

123.456a

verdadero 98.76544321

1234char integer real

boolean integer real

Figura 3.1: Datos de tipos elementales en la memoria.

Ahora tenemos el problema de cmo acceder a esas cajas que guardan carac-teres o nmeros. Esto es sencillo: les ponemos nombres para identificarlas. Lascajas as nombradas se llaman variables pues podremos colocar en ellas datosdistintos o (ejem!) variables y los nombres que reciben se llaman identificadores.

En la figura 3.2 mostramos algunos nombres posibles para las cajas quemostramos en la figura 3.1.

123.456a

verdadero 98.76544321

1234codigo a x

fin m y

Figura 3.2: Los datos con sus identificadores.

Cuando redactamos el programa, debemos indicar al compilador los nombresy tipos de variables que usaremos, procedimiento llamado de declaracin devariables. En el programa se pone una lista de variables y tipos despus de lapalabra clave var.

Una cosa trae a la otra, y tenemos el problema de que no podemos ponercualquier nombre. Por ejemplo, no es conveniente usar program o writeln queusa Pascal para instrucciones del lenguaje. Adems, en Pascal hay nombresreservados, que no podemos usar como identificadores.- En la seccin B.3 (pg. 168) est la lista completa de los nombres reserva-

dos.

Aparte de estas palabras prohibidas, los identificadores en Pascal pueden sercualquier sucesin de letras maysculas o minsculas y dgitos, pero

siempre tienen que empezar con una letra, no pueden tener espacios entre medio, ni pueden tener caracteres como $, _ (guin bajo), +, etc., y por supuesto, dos variables distintas no pueden tener el mismo nombre.

A diferencia de otros lenguajes (como C o Mathematica), segn el estndar

3.2. Tipos numricos: entero y real Pg. 13

Pascal no se distingue entre maysculas o minsculas tanto en los identificadorescomo en palabras claves. As, podemos poner sin problemas en alguna partewriteln y en otra WriteLn (como hemos hecho en el problema 2.2).- Sin embargo, algunos compiladores s diferencian entre maysculas y mi-

nsculas en identificadores y palabras reservadas.

Problema 3.1. Decidir cules de los siguientes son identificadores vlidos enPascal:

a) Pepe b) Pepe Grillo c) PepeGrillo d) mn32xye) 32xymn f ) mn32 xy g) M32nxY h) mn_32 $

Tambin tenemos otro problema: cmo colocar los datos en estas cajas ovariables, proceso que se llama asignacin.

Una forma de hacerlo es mediante := (sin espacios intermedios). As, siqueremos guardar un 2 en la variable n que es de tipo entero ponemos n := 2,y si queremos copiar los contenidos de la caja o variable a en la caja o variableb, ponemos b := a. Hay que tener un poco de cuidado en este ltimo caso,pues siempre se pueden hacer asignaciones entre variables del mismo tipo, perono es posible hacer asignaciones arbitrarias entre distintos tipos de variables, loque veremos con algn detalle en el problema 3.14.- Aunque no debe dejarse espacio entremedio en :=, los espacios a cada

lado no son necesarios. As, n:=2 o n := 2 tienen el mismo efecto.- Otros lenguajes usan otros smbolos para la asignacin, en vez de :=. Al

escribir en seudo cdigo, muchas veces se usa el smbolo , que parecemucho ms apropiado y evita confusiones con el smbolo =.

Otra forma de colocar datos en las respectivas variables es mediante lalectura de datos, por ejemplo, si a est declarado como real, la instruccinreadln(a) que veremos en la seccin 3.3 lee el nmero que se ingresapor terminal y lo guarda en la variable a.

Desde ya que

nunca hay que usar el valor de una variable sin an-tes haber hecho una asignacin a la variable!

aunque hay compiladores que automticamente ponen algn valor al hacer lasdeclaraciones.

Para tratar de entender esta jerigonza, pasemos a estudiar algunos ejemploscomenzando con los tipos numricos integer y real, para luego considerar lostipos boolean y char.

3.2. Tipos numricos: entero y realLa vida sera un tanto aburrida si slo pudiramos cambiar valores de lu-

gar, es ms divertida si podemos realizar operaciones entre estas variables. As,suponiendo que las variables a, b y c son del tipo adecuado, una instruccincomo a := b + c hace que la CPU tome los datos que estn en las cajas ovariables b y c, las sume, y coloque el resultado en la caja o variable a.

Problema 3.2. Compilar y ejecutar el programa sumardos (pg. 144) analizan-do la sintaxis y qu hacen las distintas instrucciones. Por ejemplo:


a) Cuntos comentarios tiene el programa fuente?, qu pasa si se los elimina?- Nosotros pondremos siempre un primer comentario en el programa

fuente para indicar qu hace el programa. A su vez, al ejecutar elprograma trataremos de imprimir un cartel similar para que el usuariosepa qu es lo que se pretende hacer. Usamos tambin esta filosofapara imprimir un cartel final, indicando que el programa ha terminadode ejecutarse.

b) La parte declarativa del programa tiene dos sentencias. En la primera estel nombre del programa y en la segunda se declaran a y b como de tipoentero, separando los identificadores con , (coma).

Ver qu ocurre si se cambia var a, b: integer; por

i) var a; b: integer;ii) var a: integer; var b: integer;iii) var a: integer; b: integer;

c) Qu pasa si cambiamos el nombre de a por sumardos?- El resultado puede depender del compilador. En general no es aconse-

jable usar como nombre del programa una de las palabras reservadasde Pascal o de una de las variables que aparecen en el mismo programafuente, an cuando el compilador lo acepte.

d) Cules son las instrucciones en el cuerpo principal?e) Observar el uso de la asignacin :=, como en a := 1 donde se guarda

el valor 1 en a. Cambiar el valor de a para que sea 1 y volver a ejecutarel programa.

f ) write escribe su/s argumento/s sin terminar un rengln, a diferencia dewriteln. En cualquier caso, los argumentos (si hay ms de uno) estn se-parados por , (coma).

i) Cambiar todas las ocurrencias de write por writeln, y observar loscambios en la salida del programa.

ii) Cambiar los rengloneswrite(La suma de , a);write( y , b);writeln( es , a + b);

por el nico renglnwriteln(La suma de , a, y , b, es , a + b);

Hay alguna diferencia en la salida?

g) La ltima lnea, writeln; writeln(** Fin **) es slo para avisaral usuario que el programa ha terminado, y el programa ya no realizaracciones. Eliminarla y verificar el comportamiento del programa (recordandola nota al principio del problema 2.2).

h) Cambiar las sentencias de modo de obtener la suma de nmeros reales, i.e.,poner real en vez de integer en la declaracin de variables. Compilary ejecutar el programa, observando los cambios en la salida.

i) Muchas veces uno se confunde al ingresar nmeros reales muy grande o muychicos, como 1 000 000 000 o .000 000 111 111. En estos casos usar la nota-cin cientfica puede ser til, escribiendo 109 o 1.11111 107. En Pascalpodemos escribirlos como 10e9 y -1.11111e-7, respectivamente.

Modificar el programa poniendo valores reales de esta forma.Qu pasa si se suman los dos nmeros anteriores?

3.3. Readln Pg. 15

j) Agregar una variable c, de tipo entero o real segn corresponda, hacer laasignacin c := a + b e imprimir c en vez de a + b.

k) Modificarlo de modo de escribir tambin la resta (-), producto (*) ydivisin (div para enteros y / para reales), tanto en el caso de enteroscomo de reales.

l) Qu pasa cuando se divide por 0? $

Conceptualmente hay que distinguir en Pascal entre la variable, el identifi-cador 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 ma-temticas o la vida real, no distinguir entre identificador, valor y variable, usoque nosotros seguiremos salvo cuando lleve a confusin: cuando decimos Joses simptico, en general queremos decir la persona cuyo nombre es Jos tienela cualidad de ser simptica, y no que el nombre en s es simptico, en cuyocaso diramos el nombre Jos es simptico.

En Pascal no est predeterminado cmo se escribirn los enteros o reales a lasalida, y distintos compiladores ponen sus propios formatos, i.e., cuntos lugaresocupa cada nmero escrito. Pero contamos con la opcin de especificar nosotrosmismos la cantidad de lugares, modificando lo establecido por el compilador.

Para usar esta opcin,(1) ponemos writeln(a:5) si queremos que el enteroa se escriba en exactamente 5 lugares (contando el eventual signo ). Si elentero ocupara menos lugares, se ponen espacios en blanco a la izquierda. Si porcasualidad 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 partedecimal o fraccionaria (la que viene despus de la coma decimal que paranosotros es un punto). Si a es un nmero real, poniendo writeln(a:10) harque a se escriba con exactamente 10 lugares, eventualmente poniendo espaciosa la izquierda si sobran lugares, u ocupando ms lugares si fuera necesario,usando la notacin cientfica con exponentes y punto flotante. Pero si ponemoswriteln(a:10:5), entonces indicamos que queremos la notacin con punto fijoen la que la parte decimal ocupa 5 lugares.

En realidad, las reglas son algo ms complejas, pero lo mejor es probar unpoco:

Problema 3.3 (Formatos de salida para nmeros). Modificar las ins-trucciones write y writeln del programa sumardos, experimentando con losformatos de salida tanto con enteros como con reales. $

3.3. ReadlnEs 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 porterminal y lo imprime. Observar la sintaxis e instrucciones, similares al programasumardos, 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 ,conservando los espacios intermedios cuando corresponda:

(1) O sea, no es obligatorio usarla, pero resulta conveniente muchas veces.


i) 23; ii) 2 ; iii) 2 3;iv) 2a; v) a2; vi) 2.

c) Si readln no tiene argumentos, se lee el rengln entrado lo escrito hasta y lo escrito no se guarda (como la instruccin en la nota alprincipio del problema 2.2, en la pgina 8).

Agregar el renglnreadln;

antes dewrite(Entrar un...

Qu pasa si se ingresa y luego 1?, y si seingresa 1 y luego 2?

d) Combinando los programas sumardos y leerentero, hacer un programa paraingresar por terminal dos nmeros enteros e imprimir su suma.- Adems de readln existe la funcin read, pero postergaremos su uso pa-

ra ms adelante (seccin 4.7). Basta decir por ahora que la instruccinreadln(a) es equivalente a las instrucciones read(a); readln.

As como con writeln y write podemos escribir ms de un argumento,con readln (y read) podemos leer varios argumentos a la vez, pero almenos por el momento no usaremos esta facilidad para evitar confusio-nes.

Los comportamientos de write y writeln para leer, y de read y readlnson prcticamente simtricos, aunque existen algunas diferencias importan-tes. Por ejemplo, en el tratamiento de los como hemos visto enel inciso b): readln(a) los ignora mientras no aparezca el dato a, perowriteln(a) escribe un nico rengln por vez. $

Cuando se programa profesionalmente, es muy importante que el programafuncione an cuando los datos ingresados sean errneos, por ejemplo si se ingre-sa una letra en vez de un nmero, o el nmero 0 como divisor de un cociente.Posiblemente se dedique ms tiempo a esta fase, y a la interfase entre la compu-tadora y el usuario, que a hacer un programa que funcione cuando las entradasson correctas.

Nosotros supondremos que el usuario siempre ingresa datos apropiados, yno haremos (salvo excepcionalmente) deteccin de errores. Tampoco nos preo-cuparemos por ofrecer una interfase estticamente agradable. En cambio:

Siempre trataremos de dejar claro mediante cartelesqu hace el programa, qu datos han de ingresarseen cada momento y dar una seal de finalizacin.

3.4. Funciones numricasPero volvamos a los tipos numricos.No slo podemos sumar o multiplicar nmeros sino que, al igual que en las

calculadoras, hay ya funciones predeterminadas como la raz cuadrada, que enPascal se indica por sqrt.- Una lista de las funciones predefinidas en Pascal est en el seccin B.1

(pg. 166).

3.5. La codificacin de enteros y reales Pg. 17

Problema 3.5. El programa raiz (pg. 145) calcula la raz cuadrada de unnmero no negativo entrado por terminal.

a) Compilar y ejecutar el programa, analizando qu hacen las distintas instruc-ciones. Probar el programa ingresando nmeros reales, enteros, positivos ynegativos.

b) A fin de escribir en pantallax, no es necesario hacer la asignacin previa

y := sqrt(x):

i) Reemplazar y por sqrt(x) en la sentencia writeln, compilar yejecutar el programa, verificando que el resultado es el mismo.

ii) Eliminar la variable y del programa por completo (eliminando inclusivesu declaracin).

c) Qu pasa si se ingresa un dato menor que 0?d) Muchas veces se confunde sqrt con sqr, que encuentra el cuadrado de

un nmero en vez de su raz cuadrada. Cambiar sqrt por sqr y verificar elcomportamiento del programa. $

Problema 3.6. El programa segundos (pg. 145) permite pasar de segundos ahoras, minutos y segundos, usando la funcin mod: a mod b da esencialmenteel resto de la divisin de a por b.

- El nmero de segundos a ingresar no debe muy grande (no debe superarmaxint que definimos luego).

a) Agregarle instrucciones de modo de poder verificar si el resultado es correcto,pasando de horas, minutos y segundos a segundos.

b) Qu pasa si se coloca el rengln writeln(hs, hs, ,... inmedia-tamente despus del rengln writeln(segs, segundos... y antes demins := segs div...? $

Problema 3.7.a) Hacer un programa para averiguar el comportamiento de mod, tomando

como entradas a = 7 y b = 3, calculando a mod b.- Las definicin de est en la seccin C.3.

b) Comprobar si el valor de (a div b) * b + (a mod b) coincide con elde a.

- El comportamiento de div y mod en Pascal es un tanto complicado cuandoalguno de los nmeros es negativo. Por ejemplo, segn el estndar a modb da error cuando b 0. Cuando b > 0, sin embargo, a mod b da el restode la divisin por b, entre 0 y b 1. $

3.5. La codificacin de enteros y reales

En Pascal, los nmeros ocupan un nmero fijo de bits, por ejemplo 16 bitspara el tipo integer y 32 bits para el tipo real,(2) por lo que

(2) La cantidad de bits en cada caso depende del compilador. Incluso ambos tipos podrantener asignados la misma cantidad de bits.


En la mquina slo pueden representarse un nme-ro finito de nmeros, ya sean enteros o reales. Enotras palabras, la gran mayora de los nmeros no sepueden representar exactamente en la computadora.

As, hay un mximo entero representable, que en Pascal se llama maxint ,y hay un menor nmero real positivo representable que llamaremos mn y delcual hablaremos en el problema 4.17.

Problema 3.8.

a) Suponiendo que el tipo integer tenga asignados 16 bits, cuntos nmerosenteros pueden representarse?

b) Anlogamente, si el tipo real tiene asignados 32 bits, cuntos nmerosreales pueden representarse a lo sumo en la mquina?- El resultado no estar del todo bien, dada la representacin interna

de los reales en la mquina con mantisa y exponente (que veremosa continuacin): un mismo nmero puede representarse con distintasmantisas y exponentes, e.g., 1 = 1 100 = 0.01 102. $

Problema 3.9. Hacer un programa para imprimir el valor de maxint corres-pondiente 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 msrecientes 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 representanconsecutivamente (del menor al mayor), mientras que para representar los n-meros reales se dividen los bits en dos grupos, uno representando la mantisa yotro 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 trabajaen base 2).

La representacin de nmeros reales mediante mantisa y exponente hace quea diferencia de lo que sucede con los nmeros enteros la distancia entre unnmero real que se puede representar y el prximo vaya aumentando a medidaque sus valores absolutos aumentan. Esta propiedad de densidad variable traeinconvenientes para el clculo aproximado, como veremos en el problema 4.17y 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) queentre 2 y 4, o que entre 4 y 8, etc. Por ejemplo, si hubieran slo 4 puntos encada 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 40hay el doble de nmeros enteros representados que entre 10 y 20. En estecaso, la densidad es constante.

Como todo nmero entero es en particular un nmero real, es convenientepoder pasar de la representacin como tipo integer a la representacin comotipo real. Esto se hace automticamente en Pascal: si a es de tipo integer yx es de tipo real, la asignacin

3.5. La codificacin de enteros y reales Pg. 19

1 2 4 8 16

Figura 3.3: Esquema de la densidad variable en la codificacin de nmeros reales.

x := a

hace que automticamente se guarde el valor que tiene a (un entero) en x , demodo que ahora el valor se codifica como real.- En general, la cantidad de bits (y los valores de stos) usados en la repre-

sentaciones como integer o real son distintas.- Tambin la conversin se hace automticamente al ingresar datos: si x es

de tipo real, y tenemos la instruccin readln(x), el ingreso de 1 comodato un entero hace que se guarde codificado como real en x . Verproblema 3.2.h).

Problema 3.10. Compilar y ejecutar el programa enteroareal (pg. 145). Ob-servar la declaracin de variables de distinto tipo en el mismo programa. $

Problema 3.11. Decir por qu las siguientes declaraciones de variables sonincorrectas:

i) var a, b, c: integer; c, d, e: real;ii) var a, b, c: integer; 2c, d, e: real;iii) var: a, b, c: integer; d, e: real;iv) var a, b, c: integer; var d, e: real;

- Es posible que el compilador no de error en la ltima declaracin.Sin embargo, debera haber una nica declaracin var. $

As como escribimos un entero como real, es posible que queramos pasar deun real a un entero:

Problema 3.12. Modificar el programa enteroareal de modo de leer x , hacerla asignacin a := x e imprimir a: cul es el resultado? $

Como puede observarse, no es posible cambiar de real a entero directamente:debe eliminarse primero la parte fraccionaria del real, lo que tradicionalmentese hace de dos formas distintas.

Una es truncar el real, eliminando la parte decimal. As, cuando truncamos:1.1 1, 1.9 1, 1.9 1.

Otra forma es redondear el nmero real reemplazndolo por el entero mscercano: 1.1 1, 1.9 2, 1.9 2. Claro que en el redondeo tenemosque decidir qu hacer con nmeros como 0.5, y en este caso en Pascal se usala convencin de redondear hacia arriba para positivos y hacia abajo paranegativos: 0.5 1, 0.5 1.Problema 3.13. Las funciones de Pascal trunc, correspondiente a truncar, yround, correspondiente a redondear, cuando aplicadas a un nmero real en laforma trunc(x) o round(x) dan nmeros enteros.

a) Hacer un programa para averiguar el comportamiento de estas funciones,tomando las 8 entradas 3,3.1,3.5,3.7.

b) Qu pasa si la entrada es 1010 (ingresado como 10e10)?c) Qu relacin hay entre estas funciones y las funciones piso, indicada porbxc, y techo, indicada por dxe?, es decir, cmo pueden escribirse unas entrminos de las otras y viceversa?


- Las definiciones de piso y techo estn en la seccin C.3. $

En el prximo problema abundamos sobre las asignaciones entre variablesnumricas de distinto tipo:

Problema 3.14 (Asignaciones entre distintos tipos). Supongamos quehemos declarado

var n: integer; x: real;

En los siguientes, decir cul es el valor de la ltima variable asignada o si seproduce un error (sugerencia: hacer un programa, compilarlo y ejecutarlo):

a) x := 3.7; n := x;b) x := 3.7; n := trunc(x);c) x := 3.5; n := trunc(x);d) x := 3.7; n := trunc(-x);e) x := 3.5; n := trunc(-x);f ) x := 3.7; n := round(x);g) x := 3.5; n := round(x);h) x := 3.7; n := round(-x);i) x := 3.5; n := round(-x);j) n := maxint div 2; n := n * (n+1) / 2;k) n := maxint div 2; n := n * (n+1) div 2;l) n := maxint div 2; x := n * (n+1) / 2; $

Tambin es posible hacer operaciones mezclando variables numricas de dis-tintos tipos:

Problema 3.15. Hacer un programa donde se declaren a de tipo entero y b detipo real, se lean a y b, y se escriban en pantalla los resultados de: a+ b, a b,a/b, b/a. De qu tipo son los resultados en cada caso? Sugerencia: modificarla declaracin de variables en el programa sumardos. $

De aqu en ms supondremos que compilars y ejecu-tars cada programa mencionado en los problemas,probndolo con distintos datos. En lo sucesivo, ge-neralmente omitiremos esta consigna.

3.6. Variables lgicasEstamos acostumbrados a valores numricos, y no es sorpresa que por ejem-

plo las variables del tipo integer o entero, admitan valores como 1 o 987.Sin embargo, cuesta acostumbrarse a las variables de tipo lgico o boolean, queslo admiten valores verdadero o true, y falso o false. Antes de trabajarcon estas variables en programacin, practiquemos un poco:

Problema 3.16. En cada caso, decidir si la expresin es verdadera o falsa:

3.6. Variables lgicas Pg. 21

i) 1 = 2. ii) 1 > 2.iii) 1 2. iv) 4 5 > 34 .v) 1 < 2 < 3. vi) 1 < 2 < 0.

vii) 1 < 2 o 2 < 0. viii) 1 = cos 1.ix) {a, b, c} = {b, a, c}. x) {0, 1, 2, 3} N. $

Habiendo estirado un poco los msculos, tiene sentido preguntarle a lacomputadora si un nmero es positivo o no, y que guarde el resultado en unavariable lgica:

Problema 3.17. Compilar y ejecutar el programa positivo (pg. 146), anali-zando qu hacen las distintas instrucciones.

a) Agregar una variable pos, declarada como lgica (boolean), incluir en elcuerpo del programa la asignacin pos := a > 0 e imprimir pos, en vezde a > 0.

b) As como podemos poner distintos formatos en la salida para nmeros, si a esuna variable lgica podemos usar writeln(a:1) para indicar que queremosimprimirla usando un nico lugar. Como en el problema 3.3, lo mejor esprobar: cambiar writeln(...,p) a writeln(...,p:1) y ver qu pasa.Probar con otros valores (en vez de 1). $

Debemos destacar que al comparar nmeros, Pascal usa a veces una sintaxisligeramente diferente a la usual:

Matemticas Pascal= =6= > > >=< < 0) (b > 0) (a > 0) and (b > 0)(a > 0) (b > 0) (a > 0) or (b > 0)(a > 0) not (a > 0)

pero la expresin matemtica a < b < c debe escribirse en Pascal como (a 0)y q = (b > 0), i.e., evaluar las expresiones a cada lado en la ley de DeMorgan y compararlas. $

3.7. CaracteresAs como la computadora guarda internamente los nmeros como ristras de

ceros y unos en la computadora, tambin las letras se guardan como ristras deceros y unos. La forma en que se hace esta codificacin depende del sistemaoperativo, pero un cdigo particularmente usado es el ASCII con el que se con-vierten 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 par-tir de 32, pero no todas las letras estn representadas, como la o las vocalesacentuadas del castellano. A fin de codificar tambin estos caracteres, hay ex-tensiones para cubrir caracteres con nmeros hasta 255, pero estas extensionesno son del estndar ASCII y dependen en general del sistema operativo.

En Pascal, dado un carcter podemos encontrar su nmero de orden me-diante ord y recprocamente, dado un entero podemos ver qu carcter le co-rresponde mediante la funcin chr.(3) El estndar Pascal establece que:

Los caracteres 0 , 1 ,..., 9 estn numricamente ordenados y son con-secutivos, pero

las letras minsculas, a , b ,..., z , si bien estn ordenadas, no son ne-cesariamente consecutivas!

y lo mismo para las letras maysculas.

Afortunadamente, el cdigo ASCII con el que trabajaremos satisfaceestos requisitos, y ms an, las letras minsculas a ,..., z son consecutivas ylo mismo para las maysculas.

Desafortunadamente, si bien para nosotros est entre n y o , esto noes as en el cdigo ASCII, pues la letra ni siquiera est codificada. Ni quhablar 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 letrasen el abecedario espaol desde 1803 (la cuarta y decimocuarta, respectivamen-te), y por lo tanto son indivisibles, en 1994 el dcimo congreso de la Asociacinde Academias de la Lengua Espaola acord que para su alfabetizacin se con-sideren como letras separadas (c-h y l-l, respectivamente).

- Como ya mencionamos, no vamos a usar ch, ll, ni tildes en los datos queingresemos a nuestros programas.

(3) No confundir char con chr!

3.8. Comentarios Bibliogrficos Pg. 23

Problema 3.19 (Ordinales y caracteres). El programa caracteres1 (pg.146) toma un carcter como entrada, retorna su nmero de orden y verifica lacorreccin.

a) Qu pasa si cambiamos el nombre del programa de caracteres1 achar ?, y a char1 ?- Recordar lo dicho sobre identificadores al principio del captulo y en el

problema 3.2.c).

b) Qu pasa si se escribe como entrada tonto ?c) Cules son los ordinales correspondientes a los caracteres a , A ,

(espacio), y tabulacin (tecla tab)?d) Tambin podemos especificar el formato de salida de caracteres como

ya lo hicimos para nmeros y variables lgicas poniendo por ejemplowriteln(c:5) para que se ocupen 5 espacios.

Cambiar el rengln writeln( es , chr(i)) a writeln( es ,chr(i):7) para verificar el comportamiento.

e) Hacer un programa que, inversamente, dado un nmero retorne el carctercorrespondiente.

f ) Averiguar si hay caracteres correspondientes a nmeros mayores que 127 (elresultado depender de la mquina). Y a nmeros mayores que 255?

g) Cul es el carcter correspondiente al nmero 7 (en ASCII)? $

3.8. Comentarios BibliogrficosLos problemas 3.1 y 3.11 estn basados en similares del libro de Biggs [2].

Captulo 4

Tomando control

Con las operaciones que hemos visto no podemos hacer mucho ms que loque hace una calculadora sencilla. Las cosas empiezan a ponerse interesantescuando disponemos de estructuras de control de flujo, esto es, instrucciones quenos permiten tomar decisiones sobre si realizar o no determinadas instruccioneso realizarlas repetidas veces.

Al disponer de estructuras de control, podremos verdaderamente comenzar adescribir algoritmos, es decir, instrucciones (no necesariamente en un lenguaje deprogramacin) que nos permiten llegar a determinado resultado, y apuntar haciael principal objetivo de este curso: pensar en los algoritmos y cmo traducirlosa un lenguaje de programacin.

Como es conocido, la palabra algoritmo deriva del nombre de Abu JafarMuhammad ibn Musa al-Khwarizmi.

Es interesante ubicar cronolgicamente a Al-Khwarizmi. Se presume quenaci alrededor de 780 en Bagdad (Irak), cuando Harun al-Rashid el califade 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 patrocinarlas ciencias y fund la academia Casa del saber, a la que se incorpor Al-Khwarizmi.

Al-Khwarizmi escribi y tradujo varios textos cientficos (de matemtica,geografa, etc.) del griego al rabe. El ms importante de ellos es Hisab al-jabrwal-muqabala, de donde surge la palabra lgebra con la que ahora designamosa 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.

Los programas irn aumentando en longitud, lo que nos obligar a encararde forma diferente su confeccin, debiendo pensar con ms cuidado primero enqu queremos hacer, luego en cmo lo vamos a hacer, y finalmente pasar a losdetalles. Pascal, y casi todos los lenguajes de programacin, son poco natura-les en este sentido, exigiendo por ejemplo la declaracin de variables alprincipio del programa fuente, mientras que nosotros pensaremos el programade abajo hacia arriba (o casi), y recin al final miraremos cmo declarar lasvariables necesarias.

En Pascal, las estructuras fundamentales de control son if, while, repeaty for, que pasamos a estudiar.- En Pascal hay otras estructuras de control, como case, que no veremos.

En otros lenguajes existen otras estructuras, pero casi siempre estnlos equivalentes de if y while, con las que se pueden simular las restantes.

4.1. If Pg. 25

4.1. IfSupongamos que al cocinar decidimos bajar el fuego si el agua hierve, es decir

realizar cierta accin si se cumplen ciertos requisitos. Podramos esquematizaresta decisin con la sentencia:

si el agua hierve entonces bajar el fuego.

A veces queremos realizar una accin si se cumplen ciertos requisitos y ade-ms realizar una accin alternativa si no se cumplen. Por ejemplo, si para ir altrabajo podemos tomar el colectivo o un taxi que es ms rpido pero ms ca-ro que el colectivo dependiendo del tiempo que tengamos decidiramos tomaruno 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 construccinif...then... para el esquema si...entonces..., mientras que para la varian-te si...entonces...en otro caso... usamos if...then...else... Por supuesto,entre if y then tenemos que poner una condicin (una expresin lgica), lla-mada condicin de control que pueda evaluarse como verdadera o falsa.

Recordando que ; separa expresiones,

Nunca debe ponerse un ; inmediatamente antesde un else.

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 unsonido cuando el nmero entrado es mayor que 0 y menor o igual a 10 (yno haga nada en otro caso). $

Problema 4.2. El valor absoluto para x R se define como

|x| ={x si x 0,x en otro caso.

El programa valorabsoluto (pg. 147) realiza este clculo. Observar en espe-cial la estructura if...then...else... Qu pasa si se eliminan los parn-tesis despus del if ?, y si se cambia >= por > ?, y si se agrega ; antesde else?

La funcin abs de Pascal hace el clculo del valor absoluto. Incorporarla alprograma y verificar que se obtienen los mismos resultados. $

Problema 4.3. Hacer un programa que, dado un nmero real, encuentre supiso 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; $

A veces es conveniente encadenar varios if:

Problema 4.4. El programa comparar (pg. 147) toma como datos los nmerosenteros a y b y determina cul es mayor o si son iguales.

a) Qu pasa si se escriben las lneas que empiezan con if y terminan en ;en un solo rengln?

b) Qu pasa si se incluyen ; al final de cada uno de los renglones originales?c) Modificar el programa para que siempre escriba en la salida el nmero a

primero (i.e., si a = 5 y b = 3 escriba -5 es menor que 3 en vez de 3es mayor que -5).

d) Modificarlo para que slo decida si a = b o a 6= b.e) Modificarlo para que slo decida si a > b o a b. $Problema 4.5 (Comparacin de caracteres). El programa caracteres2 (enla pg. 147) decide si un carcter entrado por terminal es una letra minsculao una mayscula o no es una letra, mediante comparacin.

Modificarlo de modo de hacer un programa para clasificar un carcter ingre-sado como uno de los siguientes:

a) una letra minscula vocal, b) una letra minscula consonante,c) una letra mayscula vocal, d) una letra mayscula consonante,e) un dgito (0, 1, . . . , 9), f ) ni letra ni dgito.- Recordando lo dicho al principio de la seccin 3.7, no deben ingresarse

vocales con tildes o . $

Problema 4.6. El Gobierno ha decidido establecer impuestos a las gananciasen forma escalonada: los ciudadanos con ingresos hasta $10 000 no pagarnimpuestos; aqullos con ingresos superiores a $10 000 pero que no sobrepasen$30 000, debern pagar 10% de impuestos; aqullos cuyos ingresos sobrepasen$30 000 pero no sean superiores a $50 000 debern pagar 20% de impuestos, ylos que tengan ingresos superiores a $50 000 debern pagar 35% de impuestos.

a) Hacer un programa para calcular el impuesto dado el monto de la ganancia.Qu tipos de datos habr que usar?

b) Modificarlo para determinar tambin la ganancia neta (una vez deducidoslos impuestos) del ciudadano.

c) Modificarlo de modo que los impuestos y ganancia neta se impriman hastael centavo (y no ms). Sugerencia: no se pide calcular sino imprimir, y talvez pueda usarse algn formato apropiado para escribir reales, pero tambinpodra usarse round para el clculo. $

Problema 4.7 (Aos bisiestos). Desarrollar un programa para decidir si unao dado es o no bisiesto.

Julio Csar (alrededor de 10044 a.C.) cambi el calendario egipcio, queestaba basado en un ao de exactamente 365 das, a un nuevo calendario, el ju-liano, con aos bisiestos cada 4 aos aproximando mejor la verdadera longituddel ao. Sin embargo, clculos posteriores mostraron que la longitud del aoes aproximadamente 365.2422 das. Con el paso de los siglos, las diferenciasanuales de 0.0078 das en promedio se fueron acumulando, y hacia el ao 1582el Papa Gregorio comenz un nuevo calendario (el gregoriano). Por un lado,

4.2. Begin-end Pg. 27

se agregaron 10 das a la fecha, de modo que el 5 de octubre de 1582 pas a serel 15 de octubre (y nunca existieron los das entre el 6 y el 14 de octubre deese ao). Por otro lado, se decidi que los aos bisiestos seran precisamentelos divisibles por 4, excepto que aqullos que fueran divisibles por 100 seranbisiestos slo cuando fueran divisibles por 400 (as el ao 1700 no es bisiestopero s el 2000). Con esta convencin, el ao promedio tiene 365.2425 das. Notodos los pases del mundo adoptaron este calendario inmediatamente. En GranBretaa y lo que es ahora Estados Unidos de Norteamrica, se adopt recinen 1752, por lo que se debieron agregar 11 das ms; Japn cambi en 1873,Rusia en 1917 y Grecia en 1923. An hoy algunas iglesias ortodoxas mantienenel calendario juliano, especialmente para determinar la fecha de las Pascuas.

- A veces con un pequeo esfuerzo podemos hacer el clculo ms eficiente.Un esquema para resolver el problema anterior, si anio es el ao ingresado,es

write(anio);if (anio mod 400 = 0) then writeln( es bisiesto)else if (anio mod 100 = 0) then writeln( no es bisiesto)else if (anio mod 4 = 0) then writeln( es bisiesto)else writeln( no es bisiesto)

Sin embargo, el esquema

write(anio);if (anio mod 4 0) then writeln( no es bisiesto)else if (anio mod 100 0) then writeln( es bisiesto)else if (anio mod 400 0) then writeln( no es bisiesto)else writeln( es bisiesto)

es ms eficiente, pues siendo que la mayora de los nmeros no son mltiplosde 4, en la mayora de los casos haremos slo una pregunta con el segundoesquema pero tres con el primero.

Nosotros no vamos a preocuparnos por la eficiencia del programa, peroharemos comentarios (como ste!) de tanto en tanto. $

Problema 4.8. Desarrollar un programa que, tomando como entrada un n-mero natural entre 1 y 3000, lo escriba en romano (e.g., entrando 2999 se debeobtener MMCMXCIX). Sugerencia: primero hacer un programa para tratar elcaso entre 1 y 30, y despus ir agregando posibilidades.- Las letras usadas para nmeros romanos son I, V, X, L, C, D, M, corres-

pondientes respectivamente a 1, 5, 10, 50, 100, 500, 1000.- El problema es ciertamente tedioso para escribir, pero es tpico de mu-

chas aplicaciones, en las que no hay atajos, o donde perdemos ms tiempotratando de encontrar un atajo que en escribir el programa. $

4.2. Begin-endA veces es conveniente y an necesario agrupar instrucciones, lo que en

Pascal se hace mediante begin...end como en la parte principal de todoprograma.- La expresin end. (con punto) slo debe aparecer al final del programa

fuente.

Este agrupar es similar al uso de parntesis en expresiones matemticas,( correspondiendo a begin y ) correspondiendo a end.

Como begin...end es similar a los parntesis, begin y end no son sen-tencias en s, por lo tanto


No tiene sentido poner un ; inmediatamente antesde un end.

Veamos un ejemplo donde podramos usar begin...end:

Problema 4.9. Sea f : R R la funcin definida como

f(x) =

{x2 si x > 0,0 si x 0.

a) Hacer un esquema del grfico de la funcin.b) Hacer un programa para que, dando x como entrada, se imprima f(x).c) Supongamos que queremos imprimir adems un cartel diciendo si el valor

entrado es positivo (y por lo tanto f(x) = x2) o si no lo es (y por lo tantof(x) = 0). Una posibilidad es, habiendo declarado a x y y como de tiporeal, poner dos if consecutivos, por ejemplo:

if (x > 0) then writeln( x, es positivo)else writeln( x, no es positivo);if (x > 0) then y := x*x else y := 0;writeln(El valor de la funcion es , y);

Incluir en el programa del inciso anterior estas modificaciones.d) Otra posibilidad, que puede parecer ms coherente, es poner un nico if,

agrupando las instrucciones en cada caso:if (x > 0) then begin

writeln( x, es positivo);y := x*xend

else beginwriteln( x, no es positivo);y := 0end;

writeln(El valor de la funcion es , y);

Modificar el programa del inciso b) incorporando esta variante. Qupasa si se elimina el end antes del else?, y si se pone ; entre end yelse? $

Otras veces el uso de begin...end evita confusiones:

Problema 4.10. Supongamos que hemos declaradovar a, b, n, z: integer;

y que tenemos el renglnif (n > 0) then if (a > b) then z := a else z := b;

a) Qu tiene de confuso este rengln?b) Decir cul es el valor de z inmediatamente despus de ejecutar el rengln

original cuando los valores de a, b, n y z son:

i) a = 1, b = 2, n = 1, z = 0;ii) a = 1, b = 2, n = 1, z = 0;

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. WhileLa estructura while es una estructura para realizar repetidas veces una

misma tarea. Junto con repeat y for que veremos ms adelante recibenel nombre comn de lazos o bucles para indicar esta capacidad de repeticin.

Supongamos que voy al supermercado con cierto dinero para comprar lamayor cantidad posible de botellas de cerveza. Podra ir calculando el dineroque me va quedando a medida que pongo botellas en el carrito: cuando noalcance para ms botellas, ir a la caja. Una forma de poner esquemticamenteesta 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 dodebe ponerse una expresin lgica.

Observamos desde ya que:

Si la condicin no es cierta al comienzo, nunca se realiza la accin: si eldinero inicial no me alcanza, no pongo ninguna botella en el carrito.

En cambio, si la condicin es cierta al principio, debe modificarse conalguna 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 re-sultado le sumamos 1, y as sucesivamente mientras los resultados seanpositivos. O si tomamos un nmero positivo y lo dividimos por 2, luegootra 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 reali-zar 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 dea 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 indicaen el cuadro 4.1, donde indicamos los pasos sucesivos que se van realizandoy los valores de las variables a, b y r (el ltimo valor que aparece es elque tiene antes de ejecutarse el paso correspondiente). Podemos comprobarentonces que los valores de a y b al terminar el programa son los valoresoriginales, mientras que r se modifica varias veces.


Paso accin a b r0 (antes de empezar) sin valor sin valor sin valor1 leer a 102 leer b 33 r := a 104 r b: verdadero5 r := r - b 76 r b: verdadero7 r := r - b 48 r b: verdadero9 r := r - b 110 r b: falso11 imprimir r

Cuadro 4.1: Prueba de escritorio para el problema 4.11.

- Pods hacer la prueba de escritorio como te parezca ms clara. Lapresentada es slo una posibilidad.

- Las pruebas de escritorio sirven para entender el comportamiento delprograma y detectar algunos errores (pero no todos). Son tiles alcomenzar a programar, en programas ni demasiado sencillos, como losque hemos visto hasta ahora, ni demasiado complicados como variosde los que veremos en los captulos siguientes.

Otra forma bastante ms primitiva de entender el comporta-miento de un programa y eventualmente encontrar errores, es probarlocon distintas entradas, como hemos hecho desde el comienzo, por ejem-plo en el problema 2.2 y prcticamente en todo el captulo 3.

Es conveniente que hagas las pruebas de escritorio de los restantesproblemas de este captulo y el siguiente.

- Las pruebas de escritorio a veces se llaman pruebas experimentales deprograma, para diferenciarlas de las verificaciones de programa, queson parte de la teora de computacin ms avanzada, y mediante lascuales se comprueba la correccin del programa.

b) Hacer una prueba de escritorio con otros valores de a y b, por ejemplo con0 < a < b (en cuyo caso la instruccin dentro del lazo while no se realiza).

c) Compilar y ejecutar el programa, verificando que coinciden los resultadosdel programa y de las pruebas de escritorio.

d) Observar que es importante que a y b sean positivos: dar ejemplos de a y bdonde el lazo while no termina nunca (sin correr el programa!).

e) Modificar el programa para comparar el valor obtenido con el resultado dela operacin a mod b.

f ) Vamos a modificar el programa de modo de contar el nmero de veces quese realiza el lazo while. Para ello agregamos un contador k, declarado comoentero, que antes del lazo while se inicializa a 0 poniendo k := 0 y dentrodel lazo se incrementa en 1 con k := k + 1. Hacer estas modificaciones(recordando usar begin...end dentro del lazo while), imprimiendo elvalor final de k antes de finalizar el programa.

g) Modificar el programa para calcular tambin el cociente de a por b, digamosc, mediante c := a div b. Qu diferencia hay entre el cociente y el valorobtenido 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

y r como de tipo real en vez de entero? Sugerencia: hay varias posibilidades,una es pensar en radianes y b = 2pi. $

Problema 4.12. El programa tablaseno1 (pg. 148) produce una tabla del senopara ngulos expresados en grados. Tanto el ngulo inicial, el ngulo final comoel incremento, son entrados por el usuario.

a) Observar el uso de const por constante para dar un valor aproximadode pi, anterior a la declaracin de variables. Observar tambin que no sehace una asignacin a pi , sino que se usa el signo =. El uso de const haceque no se puedan hacer asignaciones a pi pues no es una variable (es unaconstante): tratar de hacer una asignacin a pi y observar qu pasa.- Podemos pensar que al momento de compilar, la instruccin const a

= b hace que se reemplace cada ocurrencia de a en el programa fuentepor el valor b. Como no se puede hacer una asignacin a un valor (notiene sentido poner 1 := 2), no se pueden hacer asignaciones a a.

b) Antes o despus de ejecutar el programa, verificar que se obtienen los mismosresultados de una prueba de escritorio (como en el problema 4.11, ahora conlas variables inicial , final , incremento, grados y radianes).

c) Algunos compiladores Pascal tienen pre-definida la constante pi , pero no esestndar. Verificar si el compilador usado est en esta categora comentandoel rengln donde se define pi , i.e., encerrando el rengln entre (* y *).

d) En vez de poner manualmente un valor aproximado de pi, es comn usar laigualdad pi = 4 arctan 1.i) Cambiar el valor 3.14159265 dado a pi en el programa original, reempla-

zndolo por 4 * arctan(1). En general los compiladores no aceptaneste cambio, pues el estndar Pascal no lo permite.

ii) Eliminar el rengln donde se define a pi como una constante y definir encambio pi como una variable de tipo real, y en el cuerpo del programahacer la asignacin de la igualdad anterior. Comparar con los resultadosobtenidos originalmente.- Podra usarse otro valor similar para pi, como 2arccos 0 o 2arcsen 1,

pero arctan (el arco tangente) es la nica funcin trigonomtrica in-versa definida en el estndar Pascal.

e) Qu pasa si el valor de incremento es cero? Y si el valor de incrementoes positivo pero el de final es menor que el de inicial?

f ) Modificar el programa tablaseno1 para producir en cambio una tabla delogaritmos en base 10, donde los valores inicial , final e incremento son detipo real. Sugerencia: en Pascal est definido lnx = loge x, y para cualquiera, b y x razonables, loga x = logb x/ logb a. $

Otro uso muy comn de los lazos (while, repeat o for) es el clculo desumas o productos de muchos trminos. En forma similar al contador k delproblema 4.11.f ), si el resultado se va a guardar en la variable resultado, sta seinicializa a 0 en el caso de la suma o a 1 en el caso del producto antes del lazo,y en ste se van sumando o multiplicando los trminos deseados modificandoresultado. Ilustramos esta tcnica en el siguiente problema:

Problema 4.13 (Suma de Gauss). Para n N consideremos la suma

sn = 1 + 2 + 3 + + n =ni=1

i,


que, segn la frmula de Gauss, es

sn =n (n+ 1)

2.

Segn se dice, Karl Friederich Gauss (17771855) tena 8 aos cuando elmaestro de la escuela le dio como tarea sumar los nmeros de 1 a 100 paramantenerlo ocupado (y que no molestara). Sin embargo, hizo la suma muyrpidamente al observar que la suma era 50 101.

Las contribuciones de Gauss van mucho ms all de esta ancdota, sustrabajos son tan profundos y en tantas ramas de las matemticas que le valieronel apodo de prncipe de los matemticos. Para algunos, fue el ms grandematemtico de todos los tiempos.

El programa gauss (pg. 149) calcula sn sumando los trminos (y no usandola frmula de Gauss).

a) Cul es el valor de n al final del lazo? Sugerencia: hacer una prueba deescritorio.

b) Qu pasa si se ingresa n 0?c) La variable suma est declarada como de tipo real. Si se declarara como de

tipo entero, cul sera el mximo n para el cual se podra calcular sn (i.e.,para el cual sn maxint)?

d) Cuntas asignaciones se realizan (en trminos de n) dentro del lazo?e) Modificar el programa de modo que a la salida exprese tambin el valor ori-

ginal de n (algo como La suma de 1 a 100 es 5050 cuando n = 100).f ) Modificar el lazo while para que se sume al derecho, i.e., primero los

trminos ms chicos. $

Problema 4.14.

a) Modificar el programa gauss para obtener, dado n N, su factorial, deno-tado por n! y definido como

n! = 1 2 n.Sugerencia: recordar lo dicho antes del problema 4.13 sobre el clculo desumas y productos de varios trminos.

b) Hay alguna diferencia entre los resultados multiplicando al derecho (demenor a mayor) y al revs (de mayor a menor)?- Es posible que s cuando n es grande, debido a errores numricos.

c) Determinar cuntos ceros hay al final de la expresin decimal de 30!, y com-parar 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 q

Documents

Libro Pascal