Resolucion De Problemas Y Algoritmos.pdf

Resoluci¶on de problemas y algoritmos Ejercitaci¶on y algunas consideraciones te¶oricas Mg. Carlos Iv¶an Ches~nevar

Bah¶³a Blanca, febrero de 1997 (2da. Edici¶o n)

Prohibida su reproducci¶on sin autorizaci¶on del autor (Ley 11.723 de Propiedad Intelectual)

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

Prefacio de la Segunda Edici¶ on El presente texto constituye la segunda versi¶on del presentado originariamente en febrero de 1995. Las principales modi¯caciones incluidas en esta segunda edici¶on son las siguientes: ² Se corrigieron distintos ejercicios en los cuales aparec¶³an errores tipogr¶a¯cos, principalmente en los cap¶³tulos 1, 2 y 3. ² Se incluy¶o un ¶³ndice anal¶³tico para facilitar la b¶usqueda de un concepto determinado dentro del texto. ² Se agregaron ejercicios referidos a la traza de bloques de acciones. Mi agradecimiento para aquellos alumnos que me han comunicado errores tipogr¶a¯cos a corregir, y me han hecho llegar comentarios y opiniones sobre distintos aspectos que parec¶³an suceptibles de ser mejorados. Naturalmente, este proceso de correcci¶on y depuraci¶on de un texto es constante, por lo que son bienvenidos los comentarios, cr¶³ticas y sugerencias que permitan mejorar esta segunda edici¶on.

Mg. Carlos Iv¶an Ches~nevar Bah¶³a Blanca, febrero de 1997

{iii{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

¶Indice General 1 A modo de introducci¶ on

1

2 Resoluci¶ on de problemas: ejercitaci¶ on

7

2.1 Motivaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.2 Problemas varios (enunciados) . . . . . . . . . . . . . . . . . . . . . . . . . .

8

2.3 Respuesta a los problemas planteados . . . . . . . . . . . . . . . . . . . . . .

11

2.4 Problemas adicionales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

3 Uso de condiciones en algoritmos: generalidades

27

3.1 >Qu¶e es una condici¶on? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

3.2 Operadores l¶ogicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

3.2.1

Operador l¶ogico \y" (conjunci¶on) . . . . . . . . . . . . . . . . . . . .

29

3.2.2

Operador l¶ogico \o" (disyunci¶on) . . . . . . . . . . . . . . . . . . . .

30

3.2.3

Operador l¶ogico \no" (negaci¶on) . . . . . . . . . . . . . . . . . . . . .

31

3.3 Condiciones m¶as complejas . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

3.4 Datos booleanos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

3.5 Uso de condiciones: aspectos m¶as avanzados . . . . . . . . . . . . . . . . . .

36

3.5.1

Datos booleanos y la resoluci¶on de problemas complejos . . . . . . . .

36

3.5.2

Propiedades de los operadores l¶ogicos . . . . . . . . . . . . . . . . . .

37

3.5.3

Bloques de acciones y condiciones . . . . . . . . . . . . . . . . . . . .

38

3.5.4

Otras propiedades interesantes . . . . . . . . . . . . . . . . . . . . . .

39

4 Algoritmos en Lenguaje de Dise~ no - Ejercicios

41

5 De algoritmos en lenguaje de dise~ no a programas en Pascal

67

5.1 Introducci¶on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

67

5.2 >Qu¶e es la sintaxis? La notaci¶on bnf . . . . . . . . . . . . . . . . . . . . . .

67

5.3 La sintaxis de Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

69

5.3.1

Declaraci¶on de constantes . . . . . . . . . . . . . . . . . . . . . . . .

69

5.3.2

Declaraci¶on de tipos . . . . . . . . . . . . . . . . . . . . . . . . . . .

69

5.3.3

Declaraci¶on de variables . . . . . . . . . . . . . . . . . . . . . . . . .

70

5.3.4

De¯nici¶on de procedimientos y funciones . . . . . . . . . . . . . . . .

70

{v{

¶INDICE GENERAL

5.3.5

Bloque de sentencias . . . . . . . . . . . . . . . . . . . . . . . . . . .

71

5.4 Procedimientos y Funciones . . . . . . . . . . . . . . . . . . . . . . . . . . .

77

5.4.1

Principales diferencias entre procedimientos y funciones . . . . . . . .

77

5.4.2

Procedimientos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

77

5.4.3

Funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

79

6 Sugerencias para la impresi¶ on de dibujos en Pascal

83

7 Consideraciones para manejo de Turbo Pascal 7.0

93

7.1 Introducci¶on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

93

7.2 C¶omo empezar a trabajar en Turbo Pascal . . . . . . . . . . . . . . . . .

93

7.3 El men¶ u de opciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

94

7.3.1

File (Archivo) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

94

7.3.2

Edit (editar) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

95

7.3.3

Search (b¶usqueda) . . . . . . . . . . . . . . . . . . . . . . . . . . . .

96

7.3.4

Run . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

97

7.3.5

Compile (compilar) . . . . . . . . . . . . . . . . . . . . . . . . . . . .

98

7.3.6

Debug (depurar) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

98

7.3.7

Options . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

7.3.8

Window (Ventana) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

7.3.9

Help . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

7.4 Teclas utilizadas en Turbo Pascal . . . . . . . . . . . . . . . . . . . . . . 102 7.4.1

Teclas fundamentales . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

7.4.2

Teclas m¶as utilizadas dentro del editor . . . . . . . . . . . . . . . . . 103

7.5 Glosario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 8 Ap¶ endice: el ingl¶ es en computaci¶ on y su incidencia en nuestro idioma

109

8.1 Palabras cuestionables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 8.2 Otros problemas comunes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 9 Niklaus Wirth: el creador de Pascal Indice de materias

115 127

{vi{

Hombre que sangra Sangro sangre de letras y papeles en la entrega total de cada d¶³a, lloro llanto de p¶a ginas y frases, muero muertes de espacios y de l¶³neas. Conmover el gran muro de silencio e incomunicaci¶on que nos aisla, es la ambici¶on que pongo en cada gota de sangre blanca y l¶agrima de tinta. Transmitir es crear en largo y ancho, un mensaje de amor que abrace y llegue a¶ u n despu¶es de expirar el propio canto. Cumplir¶e en esa ley todas las leyes, sin saber hasta cuando ir¶e sangrando con mi sangre de letras y papeles. Julio Nicol¶as de Vedia

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

1

A modo de introducci¶ on

Ä Ubung macht den Meister (\La pr¶a ctica hace al maestro"; refr¶an alem¶an)

El presente texto constituye una compilaci¶on de distintos apuntes y material complementario de ejercitaci¶on elaborados para el dictado de la materia \Introducci¶on a la Inform¶atica", 1, en la cual me he desempe~nado como asistente de docencia en el per¶³odo 1993{ 1995, y como profesor desde 1996. El objetivo perseguido a trav¶es de este material es simplemente potenciar el aprovechamiento de las clases pr¶acticas, que resultan indispensables para una formaci¶on acabada en cualquier disciplina, y muy en especial en las Ciencias de la Computaci¶on. Como es sabido, al asistente de docencia le cabe la responsabilidad de guiar las clases pr¶acticas, coordinando el trabajo de los ayudantes, y conforme las pautas asignadas por el profesor de la materia. La preparaci¶on de ejercicios y presentaci¶on de temas complementarios a las clases te¶oricas dio como resultado la elaboraci¶on de los distintos textos y apuntes complementarios aqu¶³ presentados, a ¯nes de apuntalar muchos de los conceptos vertidos originalmente a trav¶es de explicaciones en el pizarr¶on. Es importante resaltar que la contribuci¶on que pretende aportar gran parte del material presentado se enmarca dentro de una metodolog¶³a elaborada conjuntamente por los profesores Ing. Silvia Castro, Lic. Sonia Rueda y Lic. Marcelo Zanconi, y utilizada para el dictado de la primer materia espec¶³¯ca de la carrera de Lic. en Ciencias de la Computaci¶on en la Universidad Nacional del Sur. Dicha metodolog¶³a comprende un desarrollo integral de distintos temas tratados puntual o separadamente en textos sobre programaci¶on y resoluci¶on de problemas, y ha sido volcada en un texto elaborado por los docentes antes mencionados [11].

Estructuraci¶ on El texto est¶a estructurado en distintas secciones, independientes entre s¶³. Cada una de las secciones involucra un tema espec¶³¯co, vinculado con ejercitaci¶on o bien con consideraciones te¶oricas adicionales referidas a la resoluci¶on de ejercicios. La n¶omina de los temas tratados, junto con una sucinta descripci¶on de ellas, es la siguiente: 1. Resoluci¶ on de Problemas: ejercitaci¶ on Esta secci¶on comprende la presentaci¶on de distintos ejercicios resueltos, detall¶andose brevemente el enfoque aplicado en cada caso, el cual ya ha sido presentado formalmente en las clases te¶oricas. Se incluyen asimismo algunos conceptos ¶utiles para resoluci¶on de problemas, tales como espacio de b¶usqueda y an¶alisis de mundos posibles. Este u¶ltimo enfoque {cuyos fundamentos provienen del ¶ambito de la Inteligencia Arti¯cial{ permite modelar adecuadamente distintos problemas de l¶ogica, haciendo que su resoluci¶on sea m¶as sencilla y ordenada. 1

Actualmente sus contenidos corresponden a la asignatura \Resoluci¶on de problemas y algoritmos".

{1{

¶ 1 A MODO DE INTRODUCCION

2. Uso de condicionales Aqu¶³ se hace un an¶alisis descriptivo del uso de las condiciones en el lenguaje de dise~ no presentado a nivel te¶orico. Se comentan, entre otros temas, el signi¯cado de las condiciones compuestas, el uso de variables booleanas y las leyes de De Morgan. 3. Algoritmos en lenguaje de dise~ no: ejercicios resueltos Se incluyen aqu¶³ diferentes tipos de ejercicios que involucran plantear algoritmos en lenguaje de dise~ no. Se incluye la resoluci¶on de dichos ejercicios, detall¶andose en algunos casos la estrategia de resoluci¶on empleada. Se intent¶o escoger ejercicios que evidencien situaciones caracter¶³sticas al momento de plantear un algoritmo, tales como uso de banderas, condiciones booleanas compuestas, ventajas de una modularizaci¶on adecuada, creaci¶on de primitivas ad hoc para resolver un problema dado, etc. 4. De Algoritmos a Pascal En esta secci¶on se hace una breve descripci¶on de la equivalencia entre distintos conceptos presentados en lenguaje de dise~ no y su adecuaci¶on a la sintaxis del lenguaje Pascal. Se mencionan entre otras cosas el uso de la notaci¶on bnf y las diferencias esenciales entre procedimientos y funciones. 5. Sugerencias para realizar ¯guras en pantalla La realizaci¶on de ¯guras en la pantalla utilizando d¶³gitos o caracteres especiales permite lograr una r¶apida familiarizaci¶on con conceptos tales como modularizaci¶on, anidamiento de bucles y de¯nici¶on de variables en funci¶on de otras. Esta secci¶on incluye distintas sugerencias y ejercicios resueltos que involucran ¯guras en pantalla. 6. Consideraciones sobre manejo de TURBO PASCAL 7.0. Aqu¶³ se presenta una gu¶³a sucinta de las principales caracter¶³sticas de Turbo Pascal 7.0.2 La inclusi¶on de la misma obedece a que ¶esta es una de las versiones de Pascal m¶as difundidas en el ¶ambito de las computadoras personales, a las cuales suelen tener acceso los alumnos. Se incluye asimismo un breve glosario de t¶erminos inform¶aticos {cuyo signi¯cado es obviamente nuevo para la gran mayor¶³a de los ingresantes{ a ¯n de facilitar un aprendizaje gradual de los mismos. 7. El ingl¶es en computaci¶ on y su incidencia en nuestro idioma Se analizan distintos giros, t¶erminos y convenciones tipogr¶a¯cas derivados del ingl¶es que se usan a menudo en computaci¶on, y cuyo signi¯cado puede ser confuso o ambiguo. 8. Niklaus Wirth: el creador de Pascal Se incluye un breve ap¶endice con datos sobre el creador del lenguaje Pascal, Niklaus Wirth. Se presenta el texto de la conferencia que ofreci¶o cuando le fue concedida la Turing Award Lecture 1984. 2

Turbo Pascal es una marca registrada por Borland Inc.

{2{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

Recomendaciones generales sobre las clases pr¶ acticas La ¯nalidad de las clases pr¶acticas es permitir que el alumno internalice los conceptos dados en las clases te¶oricas, a trav¶es de la resoluci¶on de ejercicios. Para cada tema te¶orico se proponen distintos ejercicios, enunciados en uno o varios Trabajos Pr¶acticos. Los docentes en las clases pr¶acticas cumplen esencialmente una funci¶on orientadora. El asistente y los ayudantes brindan sugerencias y consejos acerca de c¶omo encarar las distintas clases de ejercicios. Ocasionalmente, se desarrollar¶an en el pizarr¶on ejercicios que caracterizan una \clase" de problemas, as¶³ como aquellos ejercicios en los que una gran parte de los alumnos haya tenido di¯cultades. Si bien no existe una ¶unica metodolog¶³a de trabajo que resulte en un aprendizaje e¯caz, debe tenerse en cuenta que el esfuerzo propio y la ejercitaci¶ on realizada por el alumno son los ingredientes esenciales para aprobar los ex¶ amenes parciales. Debe evitarse la tentaci¶on de recurrir a los docentes para que ¶estos desarrollen para el alumno la soluci¶on de los \ejercicios dif¶³ciles". Es preferible acudir a ellos con preguntas concretas acerca de c¶omo superar las di¯cultades que impiden resolver dichos ejercicios. Encontrar obst¶aculos y adquirir la capacidad de superaralos es parte esencial del proceso de aprendizaje. No es lo mismo entender el desarrollo de un problema realizado por otra persona que ser uno mismo quien resuelve dicho problema.

Recomendaciones acerca del uso de ejercicios resueltos Advertencia importante: Las soluciones para los distintos ejercicios que se incluyen en todo material auxiliar utilizado para las clases pr¶acticas son de caracter tentativo. Las soluciones presentadas en este texto pretenden brindar una referencia para el alumno en lo que respecta a vocabulario t¶ecnico, secuencia l¶ogica y ordenamiento de los pasos a seguir. En muchos casos, junto con la soluci¶on tentativa de un ejercicio, se explica un m¶etodo o t¶ecnica que permite resolver toda una \clase" de ejercicios similares. El alumno debe determinar cu¶ando es conveniente aplicar dichos m¶etodos y t¶ecnicas para resolver un ejercicio dado. Algunas de las razones que motivaron la inclusi¶on de ejercicios resueltos como material auxiliar para las clases pr¶acticas son las siguientes: ² Agilizar el funcionamiento de las clases pr¶ acticas: Por diversas razones, es frecuente que muchos alumnos concurran a las clases pr¶acticas con el ¶unico ¯n de constatar si se explicar¶a el desarrollo de alg¶un ejercicio dif¶³cil del pr¶actico; otros desean solamente veri¯car si la soluci¶on encontrada para un ejercicio particular fue la correcta. Dado que el n¶ umero de ayudantes suele ser escaso para la proporci¶on de alumnos de la materia, el ritmo con que se atienden las dudas de los alumnos tiende a ser bajo; en ciertos casos, hay alumnos que deben esperar a que el ayudante se \desocupe" para poder resolver una pregunta simple. Disponer de la soluci¶on para los ejercicios puede ayudar a resolver dudas y preguntas sencillas, y brinda un mecanismo de control para las respuestas obtenidas. {3{

¶ 1 A MODO DE INTRODUCCION

² Estimular la capacidad de autoaprendizaje: Contar con un enunciado para un problema y disponer de una respuesta tentativa para el mismo en otra hoja brinda un est¶³mulo adicional para atacar ese ejercicio, pues se tiene la posibilidad de corroborar si el resultado alcanzado es correcto, o si el m¶etodo de resoluci¶on empleado es el adecuado. Por otro lado, trabajar de esta manera incentiva la madurez del alumno, ya que no se trata de resolver el ejercicio con el mero ¯n de \tenerlo hecho"; la motivaci¶on para encarar el ejercicio es descubrir c¶ omo resolverlo, y constatar que la soluci¶on obtenida es correcta. ² Brindar un elemento de referencia: El aprendizaje \por analog¶³a" consiste en analizar e imitar los m¶etodos y estrategias utilizados por personas experimentadas para resolver problemas en cierto ¶ambito, para aplicarlos luego a la soluci¶on de problemas nuevos. As¶³, por ejemplo, al aprender a programar, suele ser conveniente ver programas hechos por otras personas. Un programa bien escrito puede ense~ nar un truco o una t¶ecnica novedosa para encarar un problema, y esa t¶ecnica puede generalizarse luego a otros problemas. ² Optimizar tiempo en las clases pr¶ acticas: Es corriente que, durante las clases pr¶acticas, se desarrollen ejercicios en el pizarr¶on, a ¯n de orientar a los alumnos acerca de su soluci¶on. Disponer de las respuestas tentativas para los ejercicios no reemplaza el papel del ayudante o asistente, pero si evita desaprovechar tiempo en preguntas o dudas cuya respuesta pueden estar dadas por escrito de antemano. . . Asimismo, contar con una resoluci¶on modelo de ciertos ejercicios alienta a los alumnos a plantear preguntas y dudas m¶as complejas acerca de la resoluci¶on de dichos ejercicios (ej: otras formas de resolver un mismo problema; uso de estrategias alternativas, etc.)

Lo que no hay que hacer. . . \El que no sabe lo que busca, no entiende lo que encuentra" (Alberto Salamanco)

Si el alumno se limita a leer pasivamente las respuestas dadas, sin encarar por s¶³ mismo primero los ejercicios propuestos, las consecuencias de tal actitud son profundamente negativas. En primer lugar, estar¶a perdiendo la oportunidad de aprender de la manera m¶as efectiva: haciendo. La programaci¶on, por ejemplo, es algo que se aprende esencialmente a trav¶es de la pr¶actica; no es posible memorizar algoritmos hechos por otras personas, pues las variantes son in¯nitas. La capacidad de programar bien es algo que se incorpora gradualmente; no es algo mec¶anico, pues cada ejercicio demanda un enfoque diferente. La mera lectura o copia de algoritmos ajenos no ense~na a programar. Es fundamental ser consciente que \entender" un algoritmo no es lo mismo que saber hacerlo. {4{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

El intentar resolver un ejercicio, aun cuando no se llegue a su soluci¶on, ense~na algo. Muestra aquellos aspectos del problema que uno fue capaz de develar, y {lo m¶as importante{ qu¶e aspectos no pudieron ser resueltos. La experiencia obtenida en la resoluci¶ on de un ejercicio es intransferible. Aqu¶³ {como en la mayor¶³a de los procesos de aprendizaje-, la experiencia es el mejor maestro, pero tambi¶en el m¶as caro. . . Es normal que se deban invertir varios d¶³as de estudio para adquirir habilidades de resoluci¶on de problemas y de desarrollo de algoritmos.

Uso de las resoluciones tentativas como herramienta de aprendizaje Es conveniente que se intente resolver cada uno de los ejercicios propuestos. Si no se llega a una soluci¶on satisfactoria, pueden utilizarse las resoluciones dadas como un elemento de ayuda. Debe tenerse presente que la resoluci¶on que se adjunta al enunciado del ejercicio es una soluci¶on posible. Siempre es recomendable intentar ensayar soluciones alternativas a la dada, si ¶estas existen. Si se llega a una soluci¶on que se considera correcta, y la resoluci¶on que se adjunta no resulta ¶util para confrontarla con ¶esta, se sugiere recurrir a los docentes de la C¶atedra y consultarlos acerca del enfoque utilizado para resolver el problema. Debe tenerse presente que un elemento fundamental en computaci¶on es la creatividad; si la soluci¶on a la que se arrib¶o di¯ere de la resoluci¶on dada, esto no implica que dicha soluci¶on no es correcta; la soluci¶on que se encuentre puede que sea correcta, pero quiz¶as sea m¶as larga, m¶as complicada, basada en otras estrategias, o simplemente m¶as ingeniosa.

Agradecimientos Cabe agradecer a los profesores Marcelo Zanconi y Silvia Castro la correcci¶on y revisi¶on de distintos aspectos en la redacci¶on y estructuraci¶on del material presentado. Asimismo, mi agradecimiento a la Prof. Sonia Rueda por varios comentarios, recomendaciones y sugerencias aportados durante el tiempo en que me desempe~nara como ayudante en la asignatura \Inform¶atica A". Mg. Carlos Iv¶an Ches~nevar Bah¶³a Blanca, febrero de 1997 Nota: este texto no constituye una publicaci¶o n o¯cial del Departamento de Ciencias de la Computaci¶o n de la Universidad Nacional del Sur. Cualquier equ¶³voco u omisi¶on involuntaria es exclusiva responsabilidad del autor.

{5{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

2

Resoluci¶ on de problemas: ejercitaci¶ on

2.1

Motivaciones

En esta secci¶on se presentan diferentes tipos de problemas, para cuya resoluci¶on deben emplearse diferentes estrategias y metodolog¶³as. Varios de los enunciados presentados (antecedidos con un asterisco) han sido reproducidos del Trabajo Pr¶actico N± 1 utilizado en la materia \Introducci¶on a la Inform¶atica" durante los a~nos 1992, 1993 y 1994. 3 Otros enunciados fueron tomados y adaptados de los libros \Matem¶aticas Recreativas" [10], \Acertijos Fant¶asticos" [9], y de diversas revistas de pasatiempos y entretenimientos matem¶aticos. En las respuestas desarrolladas se incluyen sugerencias que pretenden dilucidar ciertos \puntos d¶ebiles" en la mayor¶³a de los alumnos ingresantes, tales como el planteo adecuado de ecuaciones, formalizaci¶on de hip¶otesis asociadas a un problema dado, y la mec¶anica utilizada para la obtenci¶on de conclusiones \por el absurdo". Se incluyen asimismo explicaciones acerca de dos estrategias de resoluci¶on de problemas que permiten atacar una amplia gama de situaciones: \b¶ usqueda espacio-estado" (aplicable a problemas que involucran hallar \cu¶al es el camino" que lleva a la soluci¶on del problema) y \an¶alisis de mundos posibles" (aplicable a problemas de l¶ogica).

Algunas sugerencias. . . Al desarrollar la resoluci¶on de un ejercicio, es conveniente tener en cuenta los siguientes puntos: ² Expresar claramente toda suposici¶on que se realice acerca del enunciado. No dudar en abundar en explicaciones cuando se lo estime necesario. Para analizar la claridad en el desarrollo de un ejercicio, suele resultar ¶util situarse imaginariamente en la posici¶on de aquella persona que analizar¶a o corregir¶a luego el desarrollo realizado. ² Identi¯car claramente los elementos que ayudaron a resolver el problema, expres¶andolos en un lenguaje preciso. Despojar dichos elementos de toda caracter¶³stica adicional que no contribuya a solucionar el problema en s¶³. ² Veri¯car no haber hecho uso de justi¯caciones ambiguas o confusas para obtener conclusiones relevantes a la soluci¶on de un problema. Llegar a una conclusi¶on correcta a partir de premisas equivocadas suele carecer de valor al momento de evaluar cu¶an correctamente se resolvi¶o un ejercicio. 3

El autor del presente texto se remiti¶o a transcribir dichos enunciados, redactando las soluciones y acercamientos para los mismos que se muestran posteriormente.

{7{

¶ DE PROBLEMAS: EJERCITACION ¶ 2 RESOLUCI ON

2.2

Problemas varios (enunciados)

Ejercicio 2.1 (*) Hallar tres n¶umeros consecutivos cuya suma sea 69. Ejercicio 2.2 (*) Una persona tiene 50 a~ nos, y su hijo 20. >Dentro de cu¶antos a~nos la edad del padre ser¶a el doble que la de su hijo? Ejercicio 2.3 (*) En un corral hay conejos y gallinas. Se cuentan 140 patas y 50 cabezas. >Cu¶antos conejos hay? Ejercicio 2.4 (*) >Cu¶anto tiempo tarda un tren de 200 metros de largo que marcha a una velocidad de 15 m/s en atravesar un t¶ unel de 1600 metros de largo? Ejercicio 2.5 (*) >Qu¶e edad tendr¶a Juan en el a~no 2000, sabiendo que esa edad ser¶a igual a la suma de las cifras de su a~ no de nacimiento? Ejercicio 2.6 (*) Se desea disponer los alumnos de una escuela en forma de cuadrado. En el primer intento se forma un cuadrado de x alumnos de lado, y sobran 25 ni~nos. Se realiza un nuevo ensayo, agregando un alumno m¶as por ¯la y por columna, y faltan 46. >Cu¶antos alumnos tiene la escuela? Ejercicio 2.7 (*) Un autom¶ovil pasa frente a un moj¶on que tiene la numeraci¶on AB km; una hora m¶as tarde pasa por otro que tiene la numeraci¶on BA km; y una hora despu¶es pasa por el moj¶on A0B km. >Qu¶e n¶ umeros tienen los mojones y cu¶al es la velocidad del autom¶ovil? Ejercicio 2.8 (*) 42 personas toman parte de un baile. Durante la ¯esta una dama bail¶o con 7 caballeros, una segunda dama con 8, una tercera con 9, y as¶³ sucesivamente hasta que la u¶ltima bail¶o con todos los hombres. >Cu¶antas damas hab¶³a en el baile? Ejercicio 2.9 (*) Una canilla puede llenar un tanque en 15 minutos, otra lo puede llenar en 20 minutos, y una tercera en 30 minutos. >Cu¶anto se tardar¶a en llenar el tanque si las tres canillas funcionan simult¶aneamente? Ejercicio 2.10 (*) Pipo y Nino son gemelos. Uno de ellos siempre dice la verdad, el otro siempre miente. Le pregunto a uno: >Pipo es quien siempre miente?, y me responde que s¶³. >Con cu¶al de los dos gemelos habl¶e? Ejercicio 2.11 (*) Un campesino debe extraer 6 litros de agua de r¶³o, pero al hacerlo se da cuenta de que solo tiene 2 recipientes de capacidad 9 y 4 litros. >Podr¶a llevar a cabo su tarea? >C¶omo? {8{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

Ejercicio 2.12 (*) Una isla est¶a habitada por dos tribus. Los miembros de una tribu siempre dicen la verdad, los de la otra mienten siempre. Un misionero encontr¶o a dos de estos nativos: uno alto y el otro petiso. \Eres de los veraces" pregunt¶o al m¶as alto. \Upf", respondi¶o el nativo. El misionero reconoci¶o que esta era una palabra tribal que correspond¶³a a \s¶³" o \no", pero no recordaba exactamente a qu¶e. El nativo petiso hablaba espa~nol, de modo que el misionero le pregunt¶o por lo que hab¶³a dicho su compa~nero. \El dijo s¶³", contest¶o el petiso, \pero el ser un gran mentiroso", agreg¶o. >A qu¶e tribu perte nec¶³a cada nativo? Ejercicio 2.13 (*) En la orilla de un r¶³o se encuentran un lobo, un repollo, y una oveja al cuidado de un pastor, quien debe trasladarlos a la otra orilla del r¶³o. Para esto dispone de solamente un bote con capacidad para dos pasajeros, uno de los cuales deber¶a ser necesariamente el propio pastor. El pasajero restante ser¶a el lobo, la oveja o el repollo. En ning¶ un momento el pastor debe dejar solos (en alguna de las orillas) al lobo y la oveja (pues el lobo se comer¶³a a la oveja), o a la oveja y el repollo (pues la oveja se comer¶³a el repollo). Indique c¶omo debe el pastor realizar los traslados para cumplir su objetivo exitosamente. Ejercicio 2.14 Dos obreros, uno viejo y otro joven, viven en un mismo apartamento y trabajan en la misma f¶abrica. El joven va desde casa a la f¶abrica en 20 minutos; el viejo, en 30 minutos. >En cu¶antos minutos alcanzar¶a el joven al viejo si ¶este sale de casa 5 minutos antes que el joven? Ejercicio 2.15 >Cu¶antos a~ nos ten¶es?, le preguntaron a Iv¶an. El respondi¶o: Tomad tres veces los a~nos que tendr¶e dentro de tres a~nos, restadle tres veces los a~nos que ten¶³a hace tres a~nos, y resultar¶a exactamente los a~nos que tengo ahora. >Cu¶antos a~ nos tiene Iv¶an? Ejercicio 2.16 El hijo le dice al padre: \Qu¶e edad tiene el padre? >qu¶e edad tiene el hijo? Ejercicio 2.17 En una ¯esta hay estudiantes de computaci¶on y estudiantes de medicina. Los estudiantes de computaci¶on siempre dicen la verdad, y los de medicina siempre mienten. En una mesa hay cuatro estudiantes sentados. Al acercarnos, nos dicen al un¶³sono: \Aqu¶³, en esta mesa, hay estudiantes de medicina y hay estudiantes de computaci¶on". >A qu¶e carrera pertenecen esos cuatro estudiantes? Ejercicio 2.18 En una f¶abrica, se utiliza jugo de naranja y soda para producir una gaseosa. Para fabricar la gaseosa, se cuenta con un aparato que consta de dos canillas y un recipiente. Una de las canillas vierte 10 litros por minuto de jugo de naranja, y la otra 7 litros por minuto de soda. El l¶³quido vertido por las canillas cae en el recipiente, el cual tiene 1000 litros de capacidad. Juan, estudiante de computaci¶on, es el encargado de manejar este aparato. {9{

¶ DE PROBLEMAS: EJERCITACION ¶ 2 RESOLUCI ON

Inicialmente, el recipiente est¶a vac¶³o. A las 10:00, Juan abre la canilla de donde sale jugo de naranja, el cual comienza a caer en el recipiente. A las 10:10, Juan recuerda que tambi¶en deb¶³a abrir la otra canilla, por lo que abre la canilla de donde sale la soda. Pasado cierto tiempo, Juan cierra ambas canillas: en ese instante, el recipiente conten¶³a el doble de jugo que de soda. >A qu¶e hora Juan cerr¶o ambas canillas? Ejercicio 2.19 \>Cu¶antos a~nos tiene Jos¶e?", dijo Pedro con voz inquieta. "Hace 18 a~nos, recuerdo que era exactamente tres veces m¶as viejo que su hijo", le contesto. \Seg¶un me dijeron," a~ nade Julio, \Jos¶e es ahora dos veces m¶as viejo que su hijo". >Cu¶antos a~nos tiene Jos¶e? Ejercicio 2.20 \Cu¶antas? 4 Ejercicio 2.22 Lul¶ u, mi vecina, busca marido, y no sabe como decidirse entre sus tres pretendientes. Durante toda la semana escuch¶e sus suspiros y cavilaciones, mientras hablaba en voz alta acerca de qui¶en podr¶³a ser su futuro esposo. El lunes dijo: \>Con qui¶en me caso? >Con el que vive en Cnel.Pringles, con el empresario o con el ganadero?". El martes dijo: \>Con qui¶en me caso? >Con el que tiene un Alfa Romeo, el que tiene un Mercedes o el viudo?". El mi¶ercoles dijo: \>Con qui¶en me caso? >Con el estudiante de computaci¶on, el que vive en Nueva York o el que tiene yate?". El jueves dijo: \>Con qui¶en me caso? >Con el que vive en Cnel.Pringles, el viudo o el que 4

Las relaciones entre las distintas unidades monetarias son totalmente ¯cticias, y no se corresponden con aquellas v¶alidas actualmente.

{10{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

vive en Nueva York?". El viernes dijo: \>Con qui¶en me caso? >Con el ganadero, el que tiene un Mercedes o el estudiante de computaci¶on?". El s¶abado ya hab¶³a elegido. Tras una llamada telef¶onica, el estudiante de computaci¶on vino a buscarla en su Alfa Romeo. Indique cu¶ales todas las caracter¶³sticas de cada uno de los tres pretendientes de Lul¶ u.

2.3

Respuesta a los problemas planteados

Ejercicio 2.1 Si x es el primero de los tres n¶umeros, los dos restantes son x + 1 y x + 2. Puede entonces plantearse la siguiente ecuaci¶on de primer grado: x + (x + 1) + (x + 2) = 69. Simpli¯cando, de ah¶³ se deduce que 3x + 3 = 69 ¡! 3x = 66 ¡! x = 22. Obs.: cabe recordar que una ecuaci¶on de grado n, de la forma cn xn + cn¡1xn¡1 + ¢ ¢ ¢+c1x1 + c0 tiene n soluciones posibles. En el caso anterior, n = 1.

Ejercicio 2.2 Sea x la cantidad de a~nos que deben transcurrir para que la edad del hijo sea el doble que la del padre. Dado que el tiempo transcurre igualmente para ambos, puede plantearse la siguiente ecuaci¶on: (50 + x) = 2(20 + x) (esto es, en x a~ nos a partir de ahora, la edad del hijo ser¶a 20 + x, y la del padre 50 + x; la ecuaci¶on re°eja la condici¶on de que la edad del hijo sea el doble que la del padre). Simpli¯cando la ecuaci¶on planteada, resulta 50 + x = 40 + 2x ¡! x = 10. Luego, dentro de 10 a~nos, la edad del hijo ser¶a el doble que la del padre. Ejercicio 2.3 Se sabe que un conejo tiene 4 patas y 1 cabeza, y una gallina tiene 2 patas y 1 cabeza. Sea x = nro. de conejos, e y = nro. de gallinas, entonces el valor de x e y corresponde a la soluci¶on del par de ecuaciones 4x+2y = 140 y x+ y = 50. Aplicando alguno de los m¶etodos conocidos para resoluci¶on de ecuaciones (ej: sustituci¶on), resulta x = 20 e y = 30. Luego hay 20 conejos y 30 gallinas. Ejercicio 2.4 Para que el tren atraviese totalmente el t¶unel, es necesario que lo recorra de punta a punta, y que el u¶ltimo vag¶on del tren abandone el t¶unel. Luego la distancia a recorrer es 1600 metros + 200 metros = 1800 metros. Aplicando la f¶ormula de velocidad = distancia/tiempo, resulta: Tiempo =

distancia velocidad

=

1800m 15m=s

= 120 segs. = 2 minutos

{11{

¶ DE PROBLEMAS: EJERCITACION ¶ 2 RESOLUCI ON

Ejercicio 2.5 Puede asumirse que Juan naci¶o en el siglo XX, ya que de haber nacido en el siglo XIX, para el a~no 2000 tendr¶³a m¶as de 100 a~nos, y es imposible que la suma de 4 d¶³gitos (esto es, 1 + 8 + x + y) sea mayor que 100. Luego, de aqu¶³ se deduce que Juan naci¶o en el a~ no \19xy", donde x e y son d¶³gitos. 5 Deben determinarse ahora los valores de las decenas y las unidades. El a~ no \19xy" puede expresarse por su descomposici¶on en base 10 como el n¶umero 1:103 + 9:102 + x:101 + y:100 = 1900 + 10x + y Por lo tanto, seg¶un los datos del enunciado, se sabe que 1 + 9 + x + y = 2000¡ \19xy", es decir 10 + x + y = 2000 ¡ (1900 + 10x + y). Simpli¯cando, resulta 11x + 2y = 90 (1) Esta es una ecuaci¶on a dos variables, y tiene como tal in¯nitas soluciones en los n¶umeros reales. Sin embargo, se sabe tambi¶en que x e y son d¶³gitos, es decir, 0 · x · 9, 0 · y · 9. Esto restringe considerablemente la cantidad de casos a analizar. No obstante, aun sabiendo que x e y son digitos, habr¶³a 100 combinaciones distintas de x e y que deber¶³an ensayarse para averiguar qu¶e valores satisfacen la ecuaci¶on (1). Se emplear¶a un mecanismo \por tanteo" para estimar que valores de x e y resultan ser aceptables. Se sabe que 2y · 18, para cualquier d¶³gito y. Luego debe buscarse un valor de x que, sumado a un n¶ umero que es menor o igual a 18, permita \llegar" a 90. Los ¶unicos valores posibles son x = 7 y x = 8. Luego x es 7, o bien x es 8. Si x = 7, entonces despejando resulta y = 6; 5 (absurdo, pues y debe ser un d¶³gito). Luego necesariamente x = 8, y despejando resulta y = 1. Juan naci¶o entonces en 1981. Ejercicio 2.6 Sea T la cantidad total de ni~nos de la escuela, y sea x la cantidad de alumnos que forman el lado del cuadrado que se hace inicialmente en el patio. Seg¶un el enunciado, sobran 25 ni~ nos para que el cuadrado de x ni~ nos de lado quede formado. Esto es x2 = T ¡25. Si se a~ nade un ni~ no al cuadrado, ¶este pasa a tener x+ 1 ni~nos de lado. En este caso, faltan 46 ni~nos. Puede plantearse la ecuaci¶on (x + 1)2 = T + 46. Despejando T en ambas ecuaciones, resulta la igualdad x2 + 25 = x2 + 2x + 1 ¡ 46 25 = 2x ¡ 45 x = 35

Luego el cuadrado formado inicialmente ten¶³a 35 ni~nos de lado, y la escuela tiene 352 + 25 = 1250 ni~ nos. 5

Las comillas en \19xy" fueron usadas para diferenciar el n¶umero de a~no formado por los d¶³gitos 1, 9, x e y del producto 19:x:y

{12{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

Ejercicio 2.7 Primeramente, es conveniente realizar una representaci¶on gr¶a¯ca del problema: AB BA A0B |---------|--------| 1 h 1 h

Puede asumirse que la velocidad del auto es constante. Luego la distancia entre \AB" y \BA" es la misma que entre \BA" y \A0B". Esto es: distancia(\AB",\BA") = distancia(\BA",\A0B") (1) >C¶omo expresar la distancia entre mojones? El n¶umero que tiene un moj¶on puede indicarse num¶ericamente como en el caso del problema 2.5. As¶³, el moj¶on \AB" tiene asociado el n¶ umero 10A + B. Luego, (1) puede expresarse como (10B + A) ¡ (10A + B) = (100A + B) ¡ (10B + A) Simpli¯cando, resulta: ¡9A + 9B = 99A ¡ 9B 0 = 108A ¡ 18B; donde 0 · A · 9; y 0 · B · 9 Puede hacerse luego un an¶alisis similar al ejercicio 2.5: es claro que A = 1, ya que ² si A = 0, entonces B = 0, y los tres mojones en cuesti¶on ser¶³an 00, 00 y 000, lo que no tiene sentido. 6 ² si A > 1 (p.ej: A = 2), se obtiene la ecuaci¶on 0 = 216 ¡ 18:B, y es claro que no existe ning¶un d¶³gito B que permita satisfacer esta ecuaci¶on (lo mismo vale para valores A = 3, 4, etc.) Luego necesariamente A = 1. Resulta entonces 0 = 108 ¡18:B ¡! B = 108=18 = 6. Los n¶umeros de los tres mojones eran entonces 16, 61 y 106. La velocidad del autom¶ovil puede calcularse a partir de la diferencia de distancia entre dos mojones consecutivos cualesquiera, p.ej. (61-16) = 45 km/h. Ejercicio 2.8 Se sabe que cada dama bail¶o con un n¶ umero distinto de caballeros, es decir: 1ra. dama bail¶o con 7 caballeros. 2da. dama bail¶o con 8 caballeros. 3ra. dama bail¶o con 9 caballeros. 6

Esto de hecho ser¶³a una soluci¶on v¶a lida, asumiendo que el autom¶o vil se quedo parado todo el tiempo frente al mismo moj¶o n. En tal caso, su velocidad ser¶³a cero.

{13{

¶ DE PROBLEMAS: EJERCITACION ¶ 2 RESOLUCI ON

De aqu¶³ se deduce que n-¶esima dama bail¶o con n + 6 caballeros. Si la n-¶esima dama es la ¶ ultima dama presente en el baile, esto quiere decir que ella bail¶o con todos los caballeros (seg¶un lo expuesto en el enunciado). Se sabe asimismo que nro.damas + nro.caballeros = 42. Pero precisamente, si la u¶ltima dama en bailar es la n¶ umero n, el valor n representa tambi¶en la cantidad de damas presentes en el baile. La dama n-¶esima bail¶o con n + 6 caballeros. Luego n + (n + 6) = 42 ¡! n=18. Resulta entonces que la cantidad de damas en el baile era 18. Ejercicio 2.9 Sea T la capacidad del tanque, y sean C1,C2 y C3 las tres canillas disponibles. Calculemos ahora el n¶ umero de litros que vierte cada canilla en un minuto. As¶³, para C1 resulta por regla de tres simple: 15 min. 1 min.

|{ |{

T litros x litros

De aqu¶³ resulta que x = T =15 litros. An¶alogamente, se tiene T=20 y T =30 litros para las canillas C 2 y C3 respectivamente. Luego, si se abren las tres canillas simult¶aneamente, en un minuto se vertir¶an (T =15) + (T =20) + (T =30) litros, es decir (T =15) + (T =20) + (T =30) = (9=60)T . Aplicando regla de tres nuevamente, se tiene: 1 minuto |{ x minutos |{

9/60 T T

De aqu¶³ resulta x = 9TT = 609 = 6; 66 minutos = 6' 40". Este es el tiempo que demorar¶a 60 en llenarse el tanque abriendo las tres canillas simult¶aneamente. Ejercicio 2.10 Un problema de este tipo puede resolverse \al tanteo", o bien empleando alguna metodolog¶³a que ordene la informaci¶on con la que se cuenta. Una estrategia aplicable para este tipo de enunciados es el denominado \an¶alisis de mundos posibles". An¶alisis de mundos posibles Se distingue por un lado la informaci¶on de la \realidad". Esta informaci¶on corresponde a aquellos datos que indudablemente sabemos que son ciertos. En este caso, la \realidad" est¶a dada por el hecho de que le pregunt¶e a un gemelo \>Pipo es el que miente?" y responde \s¶³". Por otro lado, se distinguen distintos \mundos posibles". Cada mundo posible es una alternativa diferente a partir de los datos dados en el enunciado. En nuestro caso, tenemos los siguientes cuatro mundos posibles (cuatro alternativas diferentes), excluyentes entre s¶³: 1. Habl¶e con Pipo. Pipo es veraz; Nino miente. 2. Habl¶e con Pipo. Pipo miente; Nino es veraz. 3. Habl¶e con Nino. Pipo es veraz; Nino miente. 4. Habl¶e con Nino. Pipo miente; Nino es veraz. {14{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

Esquem¶aticamente, esto puede representarse como: 8 > > > > > > < > > > > > > :

Habl¶e con Pipo

(

Pipo es veraz, Nino miente (1) Pipo miente, Nino es veraz (2)

Habl¶e con Nino

(

Nino es veraz, Pipo miente (3) Nino miente, Pipo es veraz (4)

El paso siguiente es analizar cada uno de los \mundos posibles", descartando aquellos mundos que sean \absurdos" o \imposibles" (p.ej: un mundo en el que una persona veraz dice \Yo soy mentiroso" es un mundo imposible). Los mundos \sobrantes" son posibles soluciones para el problema a considerar. A continuaci¶on se muestra un an¶alisis de mundos posibles para el caso anterior: 1. Imposible. Si Pipo es veraz, nunca va a responder que s¶³ a la pregunta \>Pipo miente?" 2. Imposible. Si Pipo miente, nunca va a responder que s¶³ a la pregunta \>Pipo miente?" pues <estar¶³a diciendo la verdad!) Luego la ¶unica situaci¶on posible es la 3 o la 4. Pero en cualquiera de esos casos resulta ser que he hablado con Nino, y el enunciado del problema precisamente pide determinar con qui¶en habl¶e. Por el an¶alisis anterior, necesariamente el gemelo con quien se habl¶o fue Nino. Ejercicio 2.11 Este problema puede resolverse bastante f¶acilmente por medio de una t¶ecnica gr¶a¯ca llamada \b¶ usqueda espacio-estado". B¶ usqueda espacio-estado Un \estado" S es una situaci¶on posible de las cosas a partir de los datos del enunciado. La idea consiste en pasar de un estado inicial S a otros alternativos S1, S2 , . . . Sn, a partir de las restricciones dadas por el enunciado del problema. Para cada uno de esos estados alternativos, puede pasarse a su vez a otros, y as¶³ sucesivamente, hasta llegar a un estado meta M , el cual constituye la soluci¶on del problema. El camino de¯nido por la secuencia de estados existente entre S y M es la secuencia de pasos que permite arribar a la soluci¶on. Estos conceptos pueden verse m¶as claramente en el caso concreto del enunciado a resolver. Primeramente, debe establecerse una representaci¶on adecuada para un estado posible. En nuestro caso, se representar¶an los dos recipientes del campesino con un par de n¶umeros A; B, donde A representa el contenido del recipiente de 9 litros de capacidad y B el de 4 litros de capacidad. El estado inicial es 0; 0 (ambos recipientes vac¶³os). >Cu¶ales son todos los nuevos estados a los cuales se puede acceder a partir del estado 0; 0? El campesino puede llenar el recipiente de 4, llenar el recipiente de 9, o bien llenar los dos recipientes. Esto se expresar¶a dicendo que a partir del estado 0; 0, puede pasarse al estado 0; 4, 9; 0 y 9; 4. Gr¶a¯camente:

/ 0 4

0 0 | 9 0

\ 9 4

{15{

¶ DE PROBLEMAS: EJERCITACION ¶ 2 RESOLUCI ON

Luego, a partir de cada nuevo estado obtenido, se intentar¶a pasar a su vez a nuevos estados alternativos. Por ejemplo, a partir del estado 0; 4, se tienen las siguientes alternativas: ² Puede vaciarse el recipiente de 4 (no es una alternativa v¶alida, pues se vuelve al estado inicial de donde se comenz¶o). ² Puede llenarse el recipiente de 9 (no sirve: es lo mismo que llenar ambos recipientes a la vez, y <ese estado se lo puede alcanzar directamente a partir del estado inicial 0,0 !). ² Puede volcarse el recipiente de 4 lts. en el de 9 lts., pasando al estado 4,0. A partir de 4,0 la ¶unica nueva alternativa es pasar a 4,4, y a partir de ah¶³ no puede pasarse a ning¶un otro nuevo estado. Por lo tanto, a partir de este an¶alisis puede asegurarse que si el campesino llena primero el recipiente de 4 lts., <jam¶as llegar¶a a tener 6 lts!. Se marca entonces con una X al llegar al estado 4,4, indicando con esto que por ese camino no puede encontrarse una soluci¶on. Un an¶alisis similar vale para el estado 9,4. Luego, la ¶unica alternativa restante es 9,0. Se ensayan entonces los estados posibles a partir de 9,0, hasta conseguir un estado x; y en el que tenga 6 litros. El \camino" desde el estado 0,0 al 6,4 es una soluci¶on para el problema planteado. A continuaci¶on se muestra el desarrollo completo del problema, utilizando esta t¶ecnica:

/ 0 4 / 4 0 | 4 4 X

0 0 | 9 0 | 5 4 | 5 0 | 1 4 | 1 0 | 0 1 | 9 1 | 6 4

\ 9 4 X

> solucion: se tiene un recipiente con 6 lts.

Ejercicio 2.12 Puede plantearse la soluci¶on de manera an¶aloga al problema de Pipo y Nino. En la \realidad", se tiene: ² Le pregunt¶e a un 1er. nativo \>Eres de los veraces?" y responde \Upf". {16{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

² \Upf" signi¯ca \s¶³" o \no". ² Le pregunt¶e a un 2do. nativo qu¶e hab¶³a dicho el 1er. nativo, y responde \Dijo que s¶³ y ¶el es un gran mentiroso". Los \mundos posibles" pueden esquematizarse como sigue: 8 > > > > > > > > > > > > > > > > > > > > > <

Upf signi¯ca > > > > > > > > > > > > > > > > > > > > > :

8 > > > > > > <

S¶³ > > > > > > :

8 > > > > > > <

No > > > > > > :

1er. nativo veraz

(

(

2do. nativo veraz (3) 2do. nativo miente (4)

(

2do. nativo veraz (5) 2do. nativo miente (6)

1er. nativo miente

1er. nativo veraz

2do. nativo veraz (1) 2do. nativo miente (2)

1er. nativo miente

(

2do. nativo veraz (7) 2do. nativo miente (8)

A continuaci¶on, se har¶a un an¶alisis de dichos mundos posibles: 1 Imposible. Si el 1er. y 2do. nativos son veraces, el 2do. nativo no podr¶³a nunca decir \¶el es un mentiroso", pues estar¶³a mintiendo (absurdo). 2 Imposible. Si se asume que \Upf" signi¯ca \s¶³", dado que el 2do. nativo miente, nunca podr¶³a decir \El dijo que s¶³" (pues el 2do. nativo estar¶³a diciendo la verdad). 3 Es posible. 4 Imposible por raz¶on id¶entica a 2). 5,6,7,8 Imposible. Ante la pregunta \Eres de los veraces?", un veraz dice \s¶³" (dice la verdad) y un mentiroso dice \s¶³" (miente). Luego \Upf" signi¯ca necesariamente \s¶³". Luego los mundos posibles 5,6,7 y 8 quedas descartados. En consecuencia, el ¶unico mundo posible es 3. Luego, \Upf" signi¯ca \s¶³", el 1er. nativo miente y el 2do. dice la verdad. Ejercicio 2.13 Puede plantearse en forma an¶aloga al ejercicio del campesino. Los estados posibles se representar¶an con A j B, queriendo decir con esto que A son aquellas cosas que est¶an en la orilla izquierda y B las que est¶an en la orilla derecha. Sea P = pastor; R = repollo; O = oveja; L = lobo. El estado inicial es P LRO j vac¶{o. Los estados marcados con X representan caminos que no conducen a soluci¶on, ya que resulta ser que \alguien se come a otro". Puede verse que hay dos soluciones, las cuales pueden obtenerse a partir del gr¶a¯co de b¶usqueda que se detalla m¶as abajo. {17{

¶ DE PROBLEMAS: EJERCITACION ¶ 2 RESOLUCI ON

² P LRO j vac¶{o , LR j P O, P LR j O, L j P RO, P LO j R, O j P LR, P O j LR, vac¶{o j P LRO. ² P LRO j vac¶{o , LR j P O, P LR j O, R j P LO, P OR j L, O j P LR, P O j LR, vac¶{o j P LRO. PLRO|nada / | \ \ LO|PR OR|PL LR|PO LRO|P X X | X (*) | PLR|O / | \ / | \ _____R|PLO L|PRO LR|PO / / | X / / | POR|L PR|LO PLO|R / X | / | O|PLR O|PLR | | PO|LR PO|LR | | vacio|PLOR vacio|PLOR

Ejercicio 2.14 Este problema puede resolverse por diversos procedimientos. Intuitivamente, puede pensarse que, para recorrer todo el camino, el obrero viejo emplea 10 minutos m¶as que el joven. Si el viejo saliera 10 minutos antes que el joven, ambos llegar¶³an a la f¶abrica a la vez. Si el viejo ha salido s¶olo 5 minutos antes, el joven debe alcanzarle precisamente a mitad de camino; es decir, 10 minutos despu¶es (el joven recorre todo el camino en 20 minutos). Una soluci¶on m¶as formal ser¶³a la siguiente: se sabe que velocidad es igual a la distancia recorrida dividido el tiempo empleado en recorrerla, esto es, v = d=t (1). Sea dc la distancia del camino que recorren ambos obreros. La velocidad del obrero joven ser¶a v1 = dc=20; la del obrero viejo, ser¶a v2 = dc=30. Sea x el tiempo transcurrido desde que el obrero joven se pone en marcha hasta que alcanza al obrero viejo. Se sabe que, en el momento del encuentro, las distancias recorridas por ambos ser¶an las mismas. A partir de la ecuaci¶on (1), se sabe tambi¶en que d = vt. Luego puede plantearse la igualdad:

(d=20)x min: = (d=30)(x min: + 5 min:) (1=20)x min: = (1=30)(x min: + 5 min:) {18{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

(3=2)x min: = x min + 5 min: x = 10 min: Ejercicio 2.15 Sea x la edad actual de Iv¶an. Cuando ¶el dice tomad tres veces la edad que tendr¶e dentro de tres a~nos, eso equivale a 3(x + 3). De igual manera, la edad que ten¶³a hace tres a~ nos ser¶a 3(x ¡ 3). De la a¯rmaci¶on de Iv¶an, puede plantearse la ecuaci¶on: 3(x + 3) ¡ 3(x ¡ 3) = x de donde resulta x = 18. Luego, la edad actual de Iv¶an es 18 a~nos. Ejercicio 2.16 Es claro que obteniendo la edad del padre, autom¶aticamente se tiene la del hijo (invirtiendo los d¶³gitos de la edad del padre). Asumamos que el hijo tiene \xy00 a~nos. Luego el padre tiene \yx00 a~ nos. Para poder manipular los d¶³gitos de dichas edades, deber¶an expresarse en su descomposici¶on decimal. As¶³, \xy 00 es equivalente a 10x + y, con x e y d¶³gitos. Cuando el padre cumpla a~ nos, pasa a tener \yx00 + 1 a~ nos, y en ese momento, su edad 00 ser¶a el doble que la del hijo, esto es, 2\xy . Puede plantearse entonces la siguiente ecuaci¶on: \yx00 + 1 = 2\xy 00 A partir de la descomposici¶on decimal de los n¶umeros \yx00 y \xy00 , lo anterior puede expresarse como: 10y + x + 1 = 20x + 2y de donde se deduce y = (19x ¡ 1)=8.

Se sabe que x e y deben ser d¶³gitos. Para que esto suceda, x debe necesariamente ser un d¶³gito impar (para que y sea entero en la ecuaci¶on anterior). Luego x puede ser 1,3,5,7 ¶o 9. De todas estas alternativas, la ¶unica aceptable es x = 3. Reemplazando, resulta y = 7. Luego el hijo tiene 37 a~ nos, y el padre tiene 73. Ejercicio 2.17 Denominemos con M al estudiante de medicina, y con C al de computaci¶on. En la mesa hay cuatro estudiantes sentados, y no sabemos qui¶enes son M y quienes son C. Hay 6 casos posibles: 1. Todos los estudiantes son M: es posible. 2. Hay un estudiante C, y los dem¶as son M : imposible, pues los estudiantes M estar¶³an diciendo la verdad (\hay estudiantes de computaci¶on"). 3. Hay dos estudiantes C, y dos M : imposible (idem razonamiento en el caso 2). {19{

¶ DE PROBLEMAS: EJERCITACION ¶ 2 RESOLUCI ON

4. Hay tres estudiantes C , y uno M : imposible (idem razonamiento en el caso 2). 5. Todos los estudiantes son C: imposible. Todos ellos siempre dicen la verdad, y ser¶³a mentira decir que \. . . hay estudiantes de medicina". El u¶nico caso posible es el primero: todos los estudiantes mienten. Luego todos los estudiantes sentados a la mesa son de medicina. Ejercicio 2.18 Llamemos C j a la canilla de jugo, y Cs a la de soda. El hecho de que el recipiente tenga 1000 litros no es relevante a la soluci¶on del problema. Nuestros datos son los siguientes:7 ² La canilla Cj vierte 10 lit./min, y la canilla Cs vierte 7 lit./min. ² La canilla Cs se abre 10 minutos despu¶es que la canilla Cj . ² En el momento de cerrar ambas canillas, el recipiente contiene el doble de soda que de jugo (es decir, el volumen de l¶³quido vertido por Cj es la mitad que el de Cs . La canilla Cj est¶a abierta 10 minutos. En ese tiempo, vertir¶a 10 lit./min * 10 min = 100 litros. A partir de ese momento, se abre la canilla Cs , que vertir¶a 7 lit./min. A partir de aqu¶³, transcurridos x minutos, se cierran ambas canillas, y en ese momento el volumen de jugo es el doble que el de soda. En x minutos, la canilla Cj vierte 100 + 10x litros. La canilla Cs vierte 7x litros. Seg¶ un el enunciado, sabemos que transcurridos esos x minutos, se cumple que Cj arroj¶o el doble que Cs , es decir: 100 + 10x = 2(7x) Despejando, resulta 100 + 10x 100 + 10x 100 x

= = = =

2(7x) 14x 4x 25

Luego Juan cerr¶o ambas canillas a los 25 minutos de que abriera Cs . Como Cs se abri¶o a las 10:10, las canillas fueron cerradas 25 minutos m¶as tarde, esto es, 10:35. 7

En la soluci¶o n de este ejercicio hab¶³a errores tipogr¶a ¯cos que fueron detectados por el alumno Pablo Santiago en 1997.

{20{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

Ejercicio 2.19 Este problema puede resolverse por medio de una ecuaci¶on de una inc¶ognita. Supongamos que el hijo tiene ahora x a~nos. Seg¶un lo dicho por Julio, el padre tiene 2x a~nos. Hace 18 a~ nos, cada uno ten¶³a 18 a~ nos menos, y resultaba ser que Jos¶e era tres veces m¶as viejo que su hijo. Puede entonces plantearse la igualdad 3(x ¡ 18) = 2x ¡ 18 Despejando la inc¶ognita, resulta que x = 36. Luego el hijo tiene 36 a~nos, y Jos¶e tiene 72. Ejercicio 2.20 Sea \abc" el n¶umero de tres cifras que se ha escrito. Sea r el resultado obtenido al hacer la resta. El n¶umero \abc" puede expresarse como: 100a + 10b + c Si se le resta la suma de sus d¶³gitos, se tiene r = 100a + 10b + c ¡ (a + b + c) Simpli¯cando la expresi¶on anterior: r = 100a + 10b + c ¡ a ¡ b ¡ c r = 99a + 9b r = 9(11a + b) Luego r es un producto donde 9 es un factor. Es claro entonces que r sea divisible por 9. Ejercicio 2.21 Sea a = valor de un peso, b = valor de una corona sueca, c = valor de un marco alem¶an y d = valor de un yen. A partir de las a¯rmaciones del cajero, se sabe que: a+b = c a = b+d 2c = 3d

Para saber cu¶antas b recibo a cambio de 10a, debo averiguar la relaci¶on existente entre a y b. De lo anterior, puede deducirse c d 2(a + b) 2a + 2b 5b

= = = = =

a +b a¡b 3(a ¡ b) 3a ¡ 3b a

Luego 1 peso es equivalente a 5 coronas suecas. Consecuentemente, mis 10 pesos equivaldr¶an a 50 coronas suecas. {21{

¶ DE PROBLEMAS: EJERCITACION ¶ 2 RESOLUCI ON

Ejercicio 2.22 Primeramente, identi¯quemos los datos relevantes en el problema. Es claro que el hecho de que las a¯rmaciones hechas por Lul¶u hayan sido hechas en distintos d¶³as de la semana no tiene mayor signi¯cado para la pregunta ¯nal. En cada a¯rmaci¶on, Lul¶ u nos indica tres caracter¶³sticas de los tres pretendientes. Por la forma en que est¶an hechas dichas a¯rmaciones, se sabe que cada caracter¶³stica corresponde a uno de los pretendientes (y no a los dem¶as). Las a¯rmaciones de Lul¶u podr¶³an reformularse como sigue: 1. Un pretendiente \vive en Cnel.Pringles", otro \es empresario", y otro \es ganadero". 2. Un pretendiente \tiene Alfa Romeo", otro \tiene un Mercedes", y otro \es viudo". 3. Un pretendiente \es estudiante", otro \vive en N.York", y otro \tiene yate". 4. Un pretendiente \vive en Cnel.Pringles", otro \es viudo", y otro \vive en N.York". 5. Un pretendiente \es ganadero", otro \tiene un Mercedes", y otro \es estudiante". 6. El pretendiente que \es estudiante" es el mismo que \tiene un Alfa Romeo" Podemos construir el cuadro que se muestra a continuaci¶on, volcando en ¶el la informaci¶on disponible sobre cada pretendiente. En principio, se sabe que el estudiante tiene un Alfa Romeo, y que los pretendientes son un estudiante, un ganadero y un empresario. A partir de la a¯rmaci¶on 1, se deduce que el estudiante es quien vive en Cnel.Pringles. Pretendiente 1 Pretendiente 2 Pretendiente 3

Profesi¶o n estudiante ganadero empresario

Veh¶³culo Alfa Romeo

Otra informaci¶on vive en Cnel.Pringles

A partir de la a¯rmaci¶on 5, se deduce que quien tiene un Mercedes es el empresario. Pretendiente 1 Pretendiente 2 Pretendiente 3

Profesi¶o n estudiante ganadero empresario

Veh¶³culo Alfa Romeo

Otra informaci¶on vive en Cnel.Pringles

Mercedes

A partir de la a¯rmaci¶on 2, se deduce que el viudo es necesariamente el ganadero. Pretendiente 1 Pretendiente 2 Pretendiente 3

Profesi¶o n estudiante ganadero empresario

Veh¶³culo Alfa Romeo

Otra informaci¶on vive en Cnel.Pringles es viudo

Mercedes

De la a¯rmaci¶on 4, resulta que quien vive en N.York no es ni el viudo ni el de Pringles; luego, se trata del empresario. Tambi¶en es claro entonces que es el ganadero quien posee el yate. Pretendiente 1 Pretendiente 2 Pretendiente 3

Profesi¶o n estudiante ganadero empresario

Veh¶³culo Alfa Romeo yate Mercedes

{22{

Otra informaci¶on vive en Cnel.Pringles es viudo vive en N.York

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

2.4

Problemas adicionales

Ejercicio 2.23 Al pobre de Don Nicanor le han robado los tomates de la huerta, y sospecha de tres vagos que pasaron por all¶³. Descubra al culpable sabiendo que: ² Ale no es canoso ni es el que pas¶o a pie. ² C¶esar pas¶o en bicicleta. ² El de la moto no es morocho. ² Guille y el rubio odian los tomates. Ejercicio 2.24 Nos enteramos de que, en la casa de Andrea (una vecina), se hizo una cena familiar. Cuando le preguntamos a ella que tal hab¶³a sali do la reuni¶on, dijo: "Mi abuelo se sent¶o a mi izquierda; entre ¶el y mi t¶³a, se sentaron dos hombres. Mi mami no se sent¶o al lado de mi t¶³a porque est¶an peleadas. Entre mi t¶³o y mi primo se sentaron dos mujeres. Mi primo se acomod¶o frente a mi papi, y entre mi mami y la abuela." >C¶omo se distribuyeron los 8 familiares alrededor de la mesa de la ¯gura? 1

2 3 \ | / 8___\|/___4 /|\ / | \ 7 6 5

Ejercicio 2.25 Un grupo de amigos renueva peri¶odicamente sus colecciones de revistas, cambiando algunas de las que tienen por otras. Las equivalencias de trueque son las siguientes: ² Dos revistas Somos se cambian por una Gente y dos Noticias. ² Una Noticias se cambia por una Gente y una Billiken. ² Una Somos se cambia por cuatro Billiken. >A cu¶antas Billiken equivale una Noticias? Ejercicio 2.26 Un chico y una chica est¶an sentados en las escaleras de su escuela. \Yo soy un chico" dice la persona morena. \Yo soy una chica" dice la persona pelirroja. Si al menos uno de los hablantes a mentido, >qui¶en es pelirrojo y quien moreno? {23{

¶ DE PROBLEMAS: EJERCITACION ¶ 2 RESOLUCI ON

Ejercicio 2.27 La isla de Pampum est¶a en un rinc¶on remoto de la Polinesia. Sus habitantes son brujos y zombies. Los brujos siempre dicen la verdad, y los zombies mienten siempre. Tanto brujos como zombies entienden el castellano, pero se niegan a hablar en otro idioma que no sea el suyo. Su idioma tiene s¶olo dos palabras: pum y pam. Una de estas palabras signi¯ca \s¶³" y la otra \no", pero no necesariamente en ese orden. Le preguntamos a un nativo de la isla: {>Pum signi¯ca s¶³? {Pum -contest¶o. Ahora bien: ese nativo >es brujo o zombie? Ejercicio 2.28 En una estaci¶on de trenes la familia Perez se despide de la familia Ruiz. Cada uno de los Perez saluda a cada uno de los Ruiz, como corresponde. Al saludarse dos varones se dan un apret¶on de manos, mientras que al saludarse un var¶on y una mujer, o dos mujeres, se dan un beso. Por supuesto, cada una de las dos familias tiene m¶as de un integrante. Un testigo circunstancial {que nunca falta en estos acertijos{ nos informa que el saldo contable de la despedida fue de 21 apretones de mano y 34 besos. >Cu¶antos hombres y cu¶antas mujeres estuvieron all¶³ despidi¶endose? Ejercicio 2.29 El campe¶on del Tenis Club \Bolas y Raquetas" apareci¶o muerto en la cancha central. La causa: un raquetazo. El inspector Fisgonetti, que conduce la investigaci¶on, llam¶o a declarar a los trillizos Pachinott pues, seg¶un testigos, dos de ellos hab¶³an jugado esa ma~nana con el infortunado campe¶on. A continuaci¶on se transcribe parte del interrogatorio: {Fisgonetti (a los tres) : >Jugaron ustedes hoy con el occiso? {Archibaldo: \Yo no" {Belisario : \Pues yo s¶³" {Celedonio : \Yo no" {Fisgonetti (a los tres) : >Mat¶o alguno de ustedes al campe¶on? {Archibaldo : \Yo no lo mat¶e!" {Belisario : \Fue Celedonio!" {Celedonio : \Fue Belisario!" El inspector {enterado de que uno de los hermanos miente siempre, mientras que los otros dos no lo hacen jam¶as{ detuvo inmediatamente a uno de ellos >A qui¶en? Ejercicio 2.30 Guiso de Piedra: El astronauta Mark lleg¶o a la excavaci¶on, y recogi¶o muestras de roca para llevar de regreso a los cient¶³¯cos terrestres. Meti¶o las rocas en tres bolsas negras: una para las rocas ¶³gneas, otra para las sedimentarias y otra para las metam¶or¯cas. En su mano ten¶³a tres etiquetas, una para cada bolsa. Pero estaba tan apurado para regresar al cohete antes de que se le terminara la provisi¶on de ox¶³geno, que puso mal las etiquetas de todas las bolsas. >Cu¶antas rocas tuvo que sacar de cu¶antas bolsas para averiguar que hab¶³a en cada una?

Respuestas Ejercicio 2.23 C¶esar rob¶o los tomates. {24{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

Ejercicio 2.24 Si se le asigna a Andrea el n¶umero 1, los dem¶as familiares {siguiendo el sentido de las agujas del reloj{ son los siguientes: 2=abuelo, 3=pap¶a, 4=t¶³o, 5=t¶³a, 6=abuela, 7=primo, 8=mam¶a. Ejercicio 2.25 Una Noticias equivale a tres Billiken. Ejercicio 2.26 Ambos mintieron. El muchacho es pelirrojo y la jovencita morena. Ejercicio 2.27 El nativo es un brujo. Ejercicio 2.28 Una familia tiene 5 miembros (3 hombres y 2 mujeres) y la otra tiene 11 miembros (7 hombres y 4 mujeres). Ejercicio 2.29 El inspector detuvo a Celedonio. Si el mentiroso fuese Belisario, los otros dos deber¶³an ser veraces, y entonces nadie hubiera jugado con el campe¶on. Pero se sabe que jugaron dos. Por lo tanto, Belisario debe ser veraz, y es cierta la acusaci¶on que hace contra Celedonio. Ejercicio 2.30 Una roca de una bolsa. Si abriera la bolsa etiquetada \¶³gnea", por ejemplo, y la roca que sacara fuera sedimentaria, entonces sabr¶³a que las otras dos bolsas no podr¶³an contener rocas sedimentarias: tendr¶³an rocas ¶³gneas o metam¶or¯cas en su interior. Pero como todas las bolsas tienen etiquetas err¶oneas, la que tiene la etiqueta \sedimentaria" tiene que contener rocas metam¶or¯cas y la que dice \metam¶or¯ca" debe contener rocas ¶³gneas. Este problema resalta la necesidad de prestar atenci¶on cuidadosa al lenguaje en el cual se expresa un problema, intentando hacer uso de toda la informaci¶on dada en el enunciado.

{25{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

3

Uso de condiciones en algoritmos: generalidades

3.1

>Qu¶ e es una condici¶ on?

En los diferentes algoritmos considerados en clase, han aparecido a menudo acciones bajo la forma: Si A es primo entonces .... sino ....

Repetir mientras (b< 4) ....

Todas estas situaciones tienen un elemento com¶ un: hay asociada a ellas una condici¶on. Las condiciones utilizadas en algoritmos son un tipo especial de proposiciones. En el lenguaje de la l¶ogica, se llama \proposici¶on" a aquella enunciaci¶on o sentencia que solo puede ser verdadera o falsa. Ejemplos de proposiciones son: \Juan tiene 20 a~nos", \3147 es primo", \Bah¶³a Blanca es una ciudad ubicada en la Provincia de Buenos Aires", etc. Asimismo, la pregunta \>Cu¶antos a~ nos ten¶es?" no es una proposici¶on, dado que no puede a¯rmarse nada en particular acerca de su veracidad o falsedad. Los t¶erminos \verdadero" y \falso" (en ingl¶es \true" y \false") constituyen el denominado valor de verdad asociado a una proposici¶on. Ejemplo: el valor de verdad asociado a la proposici¶on \2 es menor que 3" es \verdadero". Las condiciones constituyen proposiciones restringidas al uso de datos junto con ciertas relaciones y operaciones matem¶ aticas. Una condici¶on puede ser \verdadera" o \falsa". Cuando se determina el valor de verdad asociado a una condici¶on que tiene ciertos datos, se dice que se eval¶ua esa condici¶on. Ejemplo: \A < 3",\B > 4", \A + B ¡ (C ¤ D) > 0" son condiciones. Si el valor del dato A en un momento dado es 3, al evaluar la condici¶on \A < 3" el resultado es \falso". Para especi¯car una condici¶on en algoritmos que van a ser luego ejecutados por una computadora, suelen utilizarse ¶unicamente las relaciones < (menor), > (mayor), <= (menor o igual) >= (mayor o igual), = (igual) y 6= (distinto) 8 junto con distintas operaciones aritm¶eticas, como + (suma), - (resta), * (producto), / (divisi¶on entera), y // (resto de la divisi¶on entera). Los s¶³mbolos <, >, <=, >=, = y 6= se denominan operadores relacionales, mientras que los s¶³mbolos +, -, * y / son llamados operadores aritm¶eticos, y corresponden a las operaciones tradicionales del ¶algebra. Del mismo modo en que contamos con acciones primitivas cuyo dato de salida es un n¶umero, tambi¶en podremos de¯nir acciones primitivas que devuelvan un valor de verdad (esto es, verdadero o falso). Estas primitivas podr¶an combinarse con los operadores antes mencionados, para construir condiciones m¶as complejas. Ejemplo: puede considerarse una primitiva EsBisiesto, la cual recibe como dato de entrada un n¶umero de a~no, y devuelve \verdadero" si ese a~ no es bisiesto, y \falso" si no lo es. Esta primitiva puede ayudar en la elaboraci¶on de un algoritmo que cuente la cantidad de d¶³as transcurridos entre dos fechas determinadas. 8

Al traba jar en la computadora en lenguaje Pascal, se utilizar¶a el s¶³mbolo <> en lugar de 6=.

{27{

3 USO DE CONDICIONES EN ALGORITMOS: GENERALIDADES

Ejemplo: La primitiva EsPar, que permite determinar si un n¶umero es par o no, puede construirse como sigue: Algoritmo EsPar d.e.: N fnro. enterog d.s.: verdadero si N es par; falso si N no es par. Si (N // 2) = 0 entonces EsPar à verdadero sino EsPar à falso Esta primitiva puede usarse para construir una condici¶on en otro algoritmo (posiblemente m¶as complejo) indicando simplemente su nombre: ... Si EsPar(A*B)=verdadero entonces mostrar `El n¶ umero ' A*B `es par' ... Nota: Cuando se tiene que resolver un ejercicio y plantear un algoritmo, es usual indicar cu¶ales son las primitivas b¶asicas de las que se dispone. Al resolver un ejercicio dado, puede resultar conveniente contar con ciertas primitivas auxiliares, las que deber¶an ser de¯nidas a partir de las primitivas b¶asicas disponibles.

Se mencion¶o anteriormente que, a ¯n de elaborar algoritmos que posteriormente van a codi¯carse en un lenguaje de programaci¶on, se utilizar¶an condiciones, y no proposiciones. Esto es as¶³ en virtud de que los lenguajes de programaci¶on no tienen la su¯ciente \inteligencia" como para poder expresar relaciones complejas en un nivel adecuado para ser ejecutado por una computadora. Es por esto que ciertas veces aparecer¶a la necesidad de \reescribir" una proposici¶on, expres¶andola como una condici¶on, en un lenguaje m¶as cercano al de la computadora. Ejemplo: En lenguaje corriente Si Juan tiene 20 a~nos entonces ....

¡! ¡!

En un lenguaje algor¶³tmico Si EdadDeJuan = 20 entonces ....

Si el n¶ umero N es par entonces ....

¡!

Si EsPar(N)=verdadero entonces ....

Si A es menor que B entonces ....

¡!

Si A < B entonces ....

Si A2 es igual a B entonces . . .

¡!

Si A*A = B entonces . . .

Naturalmente, no todos los problemas que pueden plantearse intuitivamente en lenguaje corriente son expresables f¶acilmente a nivel algor¶³tmico. El an¶ alisis que se har¶ a en lo {28{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

sucesivo, se restringir¶ a al uso de condiciones formadas a partir de los operadores relacionales y aritm¶eticos antes mencionados, combinados eventualmente con primitivas que entreguen un valor \verdadero" o \falso".

3.2

Operadores l¶ ogicos

Las condiciones expresadas usando operadores relacionales, operadores aritm¶eticos y primitivas que devuelven \verdadero" o \falso", pueden combinarse utilizando los llamados operadores l¶ogicos y, o, y no (tambi¶en identi¯cados comunmente por las palabras en ingl¶es and, or y not, respectivamente). A continuaci¶on se detalla sucintamente cu¶al es el signi¯cado de cada uno de ellos. 3.2.1

Operador l¶ ogico \y" (conjunci¶ on)

Dadas dos condiciones C1 y C2, el operador \y" permite construir una nueva condici¶on \C1 y C 2". El valor de verdad de esa condici¶on ser¶a verdadero solo si C1 es verdadero \y" C2 es verdadero. 9 Para de¯nir el signi¯cado de un operador l¶ogico, suele recurrirse a las denominadas tablas de verdad. En una tabla de verdad se indican, para cada combinaci¶on posible de los valores de verdad de los operandos, cu¶al es el valor resultante de la operaci¶on. En el caso de la operaci¶on \y", la tabla de verdad asociada es la siguiente: C1 F F V V

C2 F V F V

C1 y C2 F F F V

Nota: es com¶un abreviar las palabras verdadero y falso con v y f, respectivamente. Ejemplo: Sean los datos x e y con valores 1 y 2, respectivamente. Entonces el valor de verdad de la condici¶on \(x = 1) y (y = 2)" es verdadero; \(x < 0) y (y = 2)" es falso; \(x < 0) y (y = 3)" es falso. Ejemplo: consid¶erese el siguiente trozo de algoritmo Si (a > 3) y (b < 4) entonces sino 9

En computaci¶on a menudo se simpli¯ca el lengua je utilizado en situaciones t¶³picas. As¶³, en lugar de enunciar \el valor de verdad resultante de evaluar la proposici¶o n C es verdadero", suele decirse simplemente \la condici¶o n C es verdadera". Este abuso del lengua je se considerar¶a l¶³cito en la medida en que no resulte ambiguo.

{29{

3 USO DE CONDICIONES EN ALGORITMOS: GENERALIDADES

El bloque i se ejecutar¶a solo si a > 3 y b < 4. El bloque ii se ejecutar¶a en el caso contrario, es decir: a > 3 es falso, o bien b < 4 es falso, o bien las dos condiciones son falsas. Esto ¶ultimo es an¶alogo a decir: el bloque ii se ejecutar¶a si a <= 3 o bien b >= 4. 3.2.2

Operador l¶ ogico \o" (disyunci¶ on)

Dadas dos condiciones C1 y C 2, el operador \o" permite construir una nueva condici¶on \C1 o C2 ". El valor de esta condici¶on ser¶a \verdadero" solo si C1 es verdadero \o" C 2 es verdadero, \o" tanto C1 como C2 son verdadero. Dicho en otras palabras: \C1 o C2" es falso solo si las dos condiciones C 1 y C2 son falsas; caso contrario, es verdadero. La tabla de verdad asociada al operador \o" es la siguiente: C1 F F V V

C2 F V F V

C1 o C2 F V V V

Ejemplo: Sean los datos x e y con valores 1 y 2, respectivamente. Entonces la condici¶on \(x = 1) o (y = 2)" es verdadero; \(x < 0) o (y = 2)" es verdadero; \(x < 0) o (y = 3)" es falso. Ejemplo: consid¶erese el siguiente trozo de algoritmo Si (a > 3) y (b < 4) entonces sino El bloque i se ejecutar¶a solo si a > 3, o b < 4, o se veri¯can ambas (esto es, vale que a > 3 y tambi¶en que b > 4). El bloque ii se ejecutar¶a en el caso contrario, es decir, si a > 3 es falso y b < 4 es falso. Ejemplo: Repetir mientras (a = 3) o (b = 4) El bloque A se ejecutar¶a mientras que a valga 3, o bien b valga 4, o bien se veri¯quen ambas (a valga 3 y b valga 4). Nota: Existe un operador l¶ogico denominado \o exclusivo" (en ingl¶es \exclusive or", o abreviadamente xor). Este operador no es usado usualmente en algoritmos en lenguaje de dise~ no, pero suele utilizarse en programaci¶on de bajo nivel (lenguaje ensamblador). Una condici¶on compuesta de la forma C1 xor C2 ser¶a verdadera solo si C 1 es verdadera o bien C2 es verdadera, y ser¶a falsa si C1 y C 2 son ambas verdaderas (o ambas falsas). La tabla de verdad asociada al operador \xor" es la siguiente: {30{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

C1 F F V V

3.2.3

C2 F V F V

C1 xor C2 F V V F

Operador l¶ ogico \no" (negaci¶ on)

Dada una condici¶on C, el operador \no" permite construir una nueva condici¶on \no C ". Esta condici¶on ser¶a \verdadero" solo si C es falsa, y ser¶a falsa solo si C es verdadero. Para el operador \no", la tabla de verdad asociada es la siguiente: C F V

no(C) V F

El operador \no" permite expresar cierto tipo de condiciones en una manera alternativa. Ejemplo: la condici¶on \A 6= B" es equivalente a \no (A = B)" la condici¶on \A > B" es equivalente a \no (A <= B)" Ejemplo: los siguientes trozos de c¶odigo son equivalentes: Si A 6= B entonces Bloque I sino Bloque II

Si no(A = B) entonces Bloque I sino Bloque II

Si no(A 6= B) entonces Bloque I sino Bloque II

Nota: por convenci¶on, las expresiones que usan operadores relacionales suelen escribirse entre par¶entesis cuando aparezcan asociadas a un operador l¶ogico dentro de un algoritmo. As¶³, en lugar de escribir \Si a > b y c > d entonces...", ¶o "repetir...hasta c = 3 o b = 4\, suele escribe "Si (a > b) y (c < d) entonces..."y \repetir...hasta (c = 3) o (b = 4)", respectivamente. Nota hist ¶ orica: Los operadores l¶ogicos y, o, y no se denominan tambi¶en \booleanos", en honor al matem¶atico y l¶ogico ingl¶es George Boole (1815-1864), quien los introdujera por primera vez en su libro \Las leyes del pensamiento". Boole estudi¶o las propiedades de estos operadores como una tem¶atica del ¶algebra y de la l¶ogica matem¶atica, sin sospechar que su aplicaci¶on pasar¶³a a ser, un siglo m¶as tarde, un concepto fundamental dentro de las Ciencias de la Computaci¶on.

{31{

3 USO DE CONDICIONES EN ALGORITMOS: GENERALIDADES

3.3

Condiciones m¶ as complejas

Por medio de los operadores l¶ogicos \y", \o" y \no", pueden construirse condiciones complejas a partir de otras m¶as sencillas. Ejemplo: Si los datos x, y, y z valen 1,2 y 3 respectivamente, se tiene que: la la la la

condici¶on condici¶on condici¶on condici¶on

\(x = 1) y (y = 2) y (z = 3)" es verdadera; \( (x = 1) o (x > 7) o (z < ¡10)) y (y = 1 + 1)" es verdadera; \( (x = 1) y (x = 2) y (z < ¡10)) o (y = 1 + 1)" es verdadera; \( (x 6= 1) o (x > 7) o (z = 10)) o (y < 2)" es falsa;

Los par¶entesis ayudan a expresar el orden en que se evaluar¶an las distintas condiciones. As¶³, no es lo mismo escribir \( (A > 3) y (B < 4) ) o (C = 3))" que \(A > 3) y ( (B < 4) ) o (C = 3) )". Si A vale 2, B vale 1 y C vale 3, el valor de verdad de la primera condici¶on es verdadero, mientras que el de la segunda es falso. Nota importante: En matem¶atica es frecuente escribir \Si a = 3 ¶o 4 ¶o 5 entonces....", \Si a > b > 1 entonces...", o \Si 8 <=promedio<= 10 entonces...". Algunas veces, esta notaci¶on puede dar lugar a dudas en su interpretaci¶on. Es com¶un entonces que, al escribir algoritmos, lo anterior se exprese como \Si (a = 3) o (a = 4) o (a = 5) entonces...", \Si (a > b) y (b > 1) entonces...", y \Si (8<=promedio) y (promedio<=10) entonces...", respectivamente.

3.4

Datos booleanos

A lo largo de distintos algoritmos, hemos visto la aplicaci¶on de datos en diferentes situaciones: para contar la cantidad de n¶umeros primos entre 1 y 1000, para calcular una sumatoria dada, etc. En todos esos casos, los datos han recibido valores num¶ericos. A un dato tambi¶en puede asign¶arsele un valor de verdad (\verdadero" o \falso"). Un dato de este tipo se denomina dato booleano. Se ver¶a ahora una situaci¶on que justi¯ca el uso de datos booleanos. Consid¶erese el siguiente enunciado: Escribir un algoritmo que, dado un n¶u mero natural N (N > 0) y un d¶³gito D, devuelva verdadero si D es un d¶³gito de N, y falso en caso contrario. Un primer acercamiento a este problema ser¶³a pensar en descomponer gradualmente al n¶ umero N (dividi¶endolo por 10), y analizar el resto resultante de dicha divisi¶on, compar¶andolo con el d¶³gito D. Es decir, un esbozo de nuestra estrategia ser¶³a la siguiente: Repetir mientras \haya d¶igitos en N por analizar" Resto à N // 10 Si D=Resto entonces \verdadero; D est¶a en N" N à N/10 fseguir buscandog sino {32{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

Sin embargo, ser¶³a conveniente que el ciclo repetir-mientras se cortase tan pronto como se encontrara que D est¶a en N >C¶omo expresar ese tan pronto como? Los datos booleanos brindan una soluci¶on para esto. La condici¶on \haya d¶³gitos en N para analizar" podr¶³a expresarse, en este caso, como \mientras N sea mayor que 0". El resto del algoritmo podr¶³a reescribirse como sigue: Algoritmo EstaDigitoPresente d.e.: D, N fD es un d¶³gito, N es un n¶umero naturalg d.s.: verdadero si D est¶a en N; falso en caso contrario. AunNoEncontreDigito à verdadero Repetir mientras N > 0 y AunNoEncontreDigito = verdadero Resto à N // 10 Si D=Resto entonces AunNoEncontreDigito à falso fEncontr¶e que D est¶a en Ng sino N à N/10 Si AunNoEncontreDigito=verdadero entonces EstaDigitoPresente à falso sino EstaDigitoPresente à verdadero Este algoritmo trabaja de la siguiente manera: se asume inicialmente que el d¶³gito no ha sido encontrado en el n¶umero N. Esto se indica asignando al dato AunNoEncontreDigito el valor \verdadero". Se analiza uno a uno los d¶³gitos que forman N, y si en alg¶un momento se encuentra que D es d¶³gito de N, el valor de AunNoEncontreDigito se hace falso. Con esto, el ciclo repetir mientras se corta (>por qu¶e?). Al abandonar ese ciclo, analizamos el valor de AunNoEncontreDigito: si es \verdadero", esto signi¯ca que nunca el d¶³gito D coincidi¶o con un d¶³gito de N; luego el algoritmo debe devolver \falso" (el d¶³gito no est¶a presente). En caso contrario, sabemos que el dato AunNoEncontreDigito vale falso; para que a este dato se le haya asignado este valor, necesariamente en alg¶ un momento el d¶³gito D coincidi¶o con un d¶³gito de N; luego el algoritmo debe devolver \verdadero". Consideremos otro ejemplo de aplicaci¶on de datos booleanos. Escribir un algoritmo que, dado un n¶umero natural N, determine si N es un n¶ u mero primo. Apelando a la de¯nici¶on de n¶ umero primo (aquel que tiene como divisores ¶unicamente al 1 y a s¶³ mismo), puede pensarse la siguiente estrategia: se asumir¶a inicialmente que el n¶umero N es primo, y se ensayar¶an todos los n¶umeros entre 2 y N ¡ 1 como potenciales divisores de N . Si alguno de esos n¶umeros divide exactamente a N , entonces el n¶ umero N no es primo; si, por el contrario, ning¶un n¶umero entre 2 y N ¡1 divide a N, puede asegurarse que N es primo. A partir de este an¶alsis, puede escribirse el siguiente algoritmo: Algoritmo EsPrimo

fversion inicialg {33{

3 USO DE CONDICIONES EN ALGORITMOS: GENERALIDADES

d.e.: N fentero positivog d.s.: Imprime mensaje \s¶³" en caso que el n¶ umero N es primo; \no" si no lo es. Cant de divs hallados à 0 div considerado à 2 finicialmente 2g Repetir mientras (div considerado < N) Si (N // div considerado = 0 entonces Cant de divs hallados à Cant de divs hallados + 1 div considerado à div considerado + 1 Si cant de divs hallados = 0 entonces Mostrar \S¶³, N es primo" sino Mostrar \No, N no es primo" El dato \div considerado" asume todos los valores posibles para un divisor de N (entre 2 y N ¡ 1 inclusive). El dato \Cant de divs hallados" cuenta la cantidad de divisores de N encontrados. Este dato se incrementa en 1 cuando N es divisible por div considerado. El algoritmo anterior, tal como est¶a planteado, no es u¶til desde el punto de vista de permitir construir primitivas para ser usadas para construir primitivas m¶as complejas, ya que solamente imprime un mensaje. Ser¶³a mucho m¶as conveniente que la salida del algoritmo estuviese dada en t¶erminos de datos. Para lograr esto, puede reescribirse la parte ¯nal del algoritmo como sigue: Si cant de divs hallados = 0 entonces EsPrimo à verdadero sino EsPrimo à falso Sin embargo, a¶un incluyendo esta modi¯caci¶on, el algoritmo tiene un defecto en cuanto a su e¯ciencia, ya que trabaja \en exceso". No se pretende saber cu¶antos divisores tiene N, sino que se desea conocer tan solo si existe al menos uno. De cumplirse esto ¶ultimo, ya puede asegurarse que N no es primo. Puede mejorarse este algoritmo reescribiendo la parte repetir mientras de la siguiente manera: Repetir mientras (div considerado < N) y (Cant de divs hallados = 0) Si (N // div considerado = 0 entonces Cant de divs hallados à Cant de divs hallados + 1 div considerado à div considerado + 1

De esta forma, tan pronto como el algoritmo encuentre un divisor para N, se incrementar¶a el valor de \Cant de divs hallados", y en consecuencia se detendr¶a el ciclo Repetir mientras. Los datos booleanos brindan una alternativa elegante para resolver el problema anterior. Se introducir¶a un dato \ElNroEsPrimo", que inicialmente ser¶a \verdadero". Se ensayar¶an {34{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

todos los divisores posibles, y si alguno de ellos divide a N , el dato \ElNroEsPrimo" tomar¶a valor \falso". Algoritmo EsPrimo fversion mejoradag d.e.: N d.s.: verdadero si N es primo; falso en caso contrario ElNroEsPrimo à verdadero Repetir mientras (ElNroEsPrimo = verdadero) y (div considerado < N) ElNroEsPrimo à (N // div considerado) 6= 0 div considerado à div considerado + 1 Si (ElNroEsPrimo = verdadero) entonces Es Primo à verdadero sino Es Primo à falso En este algoritmo, se asume primeramente que \ElNroEsPrimo" es verdadero. Si se encuentra alg¶un divisor para N, se hace que \ElNroEsPrimo" sea falso, y se abandona el ciclo repetir mientras. Los datos \booleanos" permiten escribir la parte ¯nal de este algoritmo de una manera a¶un m¶as simple. En lugar de escribir Si (ElNroEsPrimo = verdadero) entonces entonces Es Primo à verdadero sino Es Primo à falso simplemente puede escribirse Es Primo à ElNroEsPrimo Si se quiere aplicar al extremo el uso de datos booleanos, tambi¶en podr¶³a reescribirse la condici¶on \div considerado< N " utilizando un dato booleano. El algoritmo resultante ser¶³a el siguiente: debo probar mas numeros à verdadero ElNroEsPrimo à verdadero Repetir mientras (ElNroEsPrimo = verdadero) y (debo probar mas numeros = verdadero) ElNroEsPrimo à (N div considerado)*div considerado 6= N div considerado à div considerado + 1 debo probar mas numeros à (div considerado < N)

Aqu¶³ se aprecia que el ciclo repetir-mientras termina cuando \ElNroEsPrimo" es falso, o bien \debo probar mas numeros" es falso (es decir, ya se ensayaron todos los divisores posibles). Para escribir el algoritmo \EsPrimo", se ha recurrido a datos \booleanos" que asumen inicialmente un valor determinado, y lo cambian cuando se veri¯ca una condici¶on particular. Ejemplo: el dato \ElNroEsPrimo" es verdadero, y cambia de valor cuando se comprueba que existe un divisor para el n¶ umero considerado. En la jerga computacional, los datos {35{

3 USO DE CONDICIONES EN ALGORITMOS: GENERALIDADES

booleanos utilizadas de esta manera se denominan \banderas" (en ingl¶es \°ags"). Un dato \bandera" permite expresar ciertas condiciones de manera m¶as sint¶etica y clara al escribir un algoritmo. Los datos \bandera" no siempre son necesarios; la conveniencia de su utilizaci¶on es algo que fundamentalmente se aprende con la pr¶actica. Nota: Al elaborar algoritmos, es usual omitir las palabras \verdadero" y \falso" dentro de una condici¶ on. Ej: en lugar de escribir \Si DeboSeguir=verdadero entonces...", suele escribirse simplemente \Si DeboSeguir entonces...". An¶alogamente, en lugar de escribir \Si DeboSeguir=falso entonces...", suele escribirse \Si no(DeboSeguir) entonces....". Lo mismo puede aplicarse a la condici¶on asociada a una estructura repetir-mientras. Esta forma de expresar las condiciones permite muchas veces una lectura m¶as \¶agil" de los pasos asociados a un algoritmo.

3.5 3.5.1

Uso de condiciones: aspectos m¶ as avanzados Datos booleanos y la resoluci¶ on de problemas complejos

Supongamos que se quiere escribir un algoritmo que reconozca si una fecha expresada mediante tres datos d¶ ³a, mes y a~ no es una fecha v¶alida. As¶³, por ejemplo, la fecha 20-7-1969 10 (correspondiente a dia=20, mes=7 y a~ no =1969) es una fecha v¶alida. No ser¶an fechas v¶alidas 31-11-1987 (pues noviembre tiene 30 d¶³as) ni tampoco 14-13-1980 (ya que el n¶ umero del mes debe ser menor o igual a 12). Nota: los meses con 30 dias son el mes 4, 6, 9 y 11. Los dem¶as tienen 31 d¶³as, excepto el mes 2 que tiene 28 d¶³as. Se asume que el a~ no a considerar es un a~no v¶alido y que no es bisiesto. Para resolver el problema anterior, puede escribirse el siguiente algoritmo: Algoritmo EsFechaValida d.e.: dia, mes d.s.: verdadero si dia y mes corresponden a una fecha valida; falso en caso contrario fObs: no se consideran a~ nos bisiestos; incluir dicha consideraci¶on queda como ejercicio adicional para el lector.g Si (dia>=1) y (((dia<=31) y ( (mes=1) o (mes=3) o (mes=5) o (mes=6) o (mes=8) o (mes=11) o (mes=12) )) o ((dia<=30) y ( (mes=4) o (mes=7) o (mes=9) o (mes=10)) ) o ((dia<=28) y (mes=2))) entonces EsFechaValida à verdadero sino EsFechaValida à falso No cabe duda que lo anterior resulta engorroso, ya que es dif¶³cil determinar si la condici¶on asociada a la estructura si - entonces est¶a expresada correctamente. Por otro lado, 10

Este es el d¶³a en que el hombre lleg¶o por primera vez a la Luna.

{36{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

si alguien quisiera interpretar qu¶e signi¯ca la condici¶on anterior, deber¶a analizar cuidadosamente todas las expresiones en las que aparecen operadores \y" y \o"; es evidente que el signi¯cado de la condici¶on no salta a simple vista. A ¯n de expresar esta condici¶on de una manera m¶as clara y sencilla, podemos introducir datos booleanos (tambi¶en llamadas datos condicionales). Un dato booleano es aquel que puede almacenar el \resultado" de una condici¶on (esto es, verdadero o falso). As¶³, por ejemplo, puede escribirse la asignaci¶on: EsUnDiaValido à (dia>=1) y (dia<=31) Esto debe interpretarse de la siguiente manera: evaluar la condici¶on \(dia>=1) y (dia<=31)" y almacenar posteriormente el resultado de dicha evaluaci¶on en el dato EsUnDiaValido. En este caso, el dato EsUnDiaValido almacenar¶a el valor \verdadero" si la condici¶on \(dia>=1) y (dia<=31)" es verdadero; EsUnDiaValido almacenar¶a el valor falso si la condici¶on es falsa (es decir, en caso que el valor de \dia" sea menor que 1 o mayor que 31). Ahora se analizar¶a c¶omo puede reescribirse la condici¶on del algoritmo anterior con auxilio de datos booleanos. EsDiaValido à (dia>=1) y (dia<=31) EsMesDe31Dias à (mes=1) o (mes=3) o (mes=5) o (mes=7) o (mes=8) o (mes=11) o (mes=12) EsMesDe30Dias à (mes=4) o (mes=6) o (mes=9) o (mes=10) EsMesDe28Dias à (mes=2) EsFechaAceptable à EsDiaValido y ( ((dia<=31) y (EsMesDe31Dias)) o ((dia<=30) y (EsMesDe30Dias)) o ((dia<=28) y (EsMesDe28Dias)) ) EsFechaValida à EsFechaAceptable

Se mencion¶o anteriormente que una dato booleano puede almacenar el resultado de evaluar una condici¶on. En particular, al escribir algoritmos, puede asign¶arsele directamente a un dato booleano los valores \verdadero" o \falso". Estos valores pueden pensarse como si fueran condiciones \constantes". Ejemplo: \AÃ verdadero", \BÃ falso". Esto puede pensarse como algo equivalente a realizar asignaciones tales como \AÃ (2=2)" y \BÃ 16=1", respectivamente. La utilidad de realizar asignaciones del tipo \AÃ verdadero" se ver¶a m¶as adelante, en el inciso que trata el uso de datos booleanos como banderas. 3.5.2

Propiedades de los operadores l¶ ogicos

Sean C1 y C 2 dos condiciones. Pueden enunciarse las siguientes propiedades: a) \no(no C1 )" es equivalente a \C1" b) \C1 y C2" es equivalente a \no (no(C1) o no(C2 ))" c) \C1 o C2" es equivalente a \no (no(C1) y no(C2 ))" {37{

3 USO DE CONDICIONES EN ALGORITMOS: GENERALIDADES

Las propiedades b) y c) pueden expresarse tambi¶en como: b') \no(C 1 y C2)" es equivalente a \no(C1) o no(C2 )" c') \no(C 1 o C2 )" es equivalente a \no(C 1) y no(C2 )" Las propiedades b y c fueron postuladas por el matem¶atico Augusto de Morgan, por lo que suele denomin¶arselas \leyes de De Morgan". >Qu¶e utilidad tienen las propiedades anteriores? Por medio de ellas puede expresarse una condici¶on C en una forma alternativa C 0 . Eventualmente, puede resultar que C 0 sea m¶as sencilla de interpretar que C. Ejemplo: Usando las propiedades anteriores, se tiene que En lugar de escribir Si no(no A=3) entonces .... Si no(A=B y C=D) entonces .... Si no(A=B o C=D) entonces .... Si no( no(A=B) y no(C=D)) entonces .... 3.5.3

Puede escribirse: O tambi¶en Si (A=3) entonces Si (no(A=B) o no(C=D)) Si (A6= B) o (C6=D) entonces .... entonces .... Si (no(A=B) y no(C=D)) Si (A6= B) y (C6=D) entonces .... entonces .... Si (A=B) o (C=D) entonces ....

Bloques de acciones y condiciones

Si C es una condici¶on, y S1, S2 y S son acciones (o bloques de acciones) en un algoritmo, entonces las siguientes estructuras son equivalentes: Si C entonces S1 sino S2

()

Si no(C) entonces S2 sino S1

Repetir mientras C S

()

Si C entonces Repetir S Hasta no(C)

Repetir S Hasta C

()

S Repetir mientras no(C) S

Los ejemplos que siguen ilustran las equivalencias antes enunciadas. En cada caso, el trozo de algoritmo que ¯gura en el lado izquierdo es equivalente a al que ¯gura en el lado derecho. {38{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

Si A=3 Si no(A=3) entonces entonces mostrar \A vale 3" mostrar \A no vale 3" sino sino mostrar \A no vale 3" mostrar \A vale 3" CÃ1 CÃ1 Repetir mientras C< 10 Si C< 10 mostrar C entonces CÃC+1 Repetir mostrar C CÃC+1 Hasta no(C<10) CÃ1 CÃ1 Repetir mostrar C mostrar C CÃC+1 CÃC+1 Repetir mientras no(C=10) Hasta C=10 mostrar C CÃC+1 3.5.4

Otras propiedades interesantes

A continuaci¶on se analizar¶a una serie de propiedades de los operadores l¶ogicos, que pueden resultar de ayuda en el momento de veri¯car el comportamiento correcto de un algoritmo. Consid¶erese los siguientes trozos de c¶odigo: (a) Si (2=3) y C2 y C3 y C4 entonces Acci¶on A

(b) Si (2=2) o C2 o C3 o C4 entonces Acci¶on B

donde C1, C2, C3 y C4 son condiciones cualesquiera. En el caso (a), puede asegurarse que la acci¶on A no se ejecutar¶a, ya que (2=3) es \falso", por lo que {por la de¯nici¶on del operador \y"{ la condici¶on completa ser¶a \falso". En el caso (b), puede asegurarse que la acci¶on B se ejecutar¶a, ya que (2=2) es \verdadero", por lo que {por de¯nici¶on del operador \o"{ la condici¶on completa ser¶a \verdadero". Lo anterior puede expresarse {un poco m¶as formalmente{ como sigue: Si se tiene una condici¶on \C 1 y C2 y . . . y Cn", y se sabe que existe alg¶ un Ci que es siempre \falso", entonces la condici¶on \C1 y C2 y ... y C n" es siempre \falso". Si se tiene una condici¶on \C1 o C2 o . . . o Cn ", y se sabe que existe alg¶ un C i que es siempre \verdadero", entonces la condici¶on \C1 o C 2 o ... o Cn " es siempre \verdadero". Es claro que condiciones como las anteriores son, en cierto sentido, \redundantes". Si se sabe que algo siempre va a ser \verdadero" o \falso" >para qu¶e escribirlo en forma de una condici¶on? La \moraleja" de lo enunciado anteriormente es la siguiente: {39{

3 USO DE CONDICIONES EN ALGORITMOS: GENERALIDADES

Debe tenerse precauci¶on con aquellas condiciones que, independientemente de los valores de los datos que intervienen en ellas, tienen siempre un valor predeterminado (\verdadero" o \falso"). Este tipo de condiciones debe evitarse. Si bien resulta obvio que \2=2" siempre es verdadero, y que \2=3" es falso, hay casos m¶as sutiles y no tan f¶acilmente detectables. Ejemplo: en el siguiente trozo de algoritmo, la parte entonces... nunca se ejecutar¶a, ya que es imposible que un n¶umero sea primo y sea par (asumiendo que el n¶ umero es mayor que 2). Si EsPrimo(N) y EsPar(N) y C3 y C4 y ..... y Cn entonces . . . Seg¶un lo enunciado anteriormente, es claro que esto resulta ser independiente de si las condiciones C3,C4 , . . . Cn son verdaderas o falsas.

{40{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

4

Algoritmos en Lenguaje de Dise~ no - Ejercicios

Nota: la resoluci¶on para los ejercicios abajo listados ha sido confeccionada recientemente. Por esa raz¶on, es posible que exista alg¶un error tipogr¶a¯co en las soluciones. Si se llegara a detectar errores de ese tipo, se agradecer¶a que se lo comunique a la C¶atedra. Ejercicio 4.1 Realice una traza para los siguientes bloques de acciones. Indique claramente cu¶ales ser¶³an los valores ¯nales para cada uno de los datos en cada caso. Ejercicio a aÃ0 bÃ1 a à a+1 bÃa Ejercicio e aÃ1 a à a*a Si a>0 entonces b à a+1 b à b*b

Ejercicio b aÃ0 a à a+1 a à a+1 a à a+1 Ejercicio f aÃ0 b à a+1 Si a>b entonces b à a

Ejercicio i aÃ0 Repetir 4 veces a à a+1 b à a*2

Ejercicio j Repetir 3 veces a à a+1

Ejercicio m aÃ1 Repetir a à a+1 Hasta a=3

Ejercicio c a à b+1 bÃ0 Ejercicio g aÃ1 Si a 6=0 entonces bÃ1 sino bÃ2 Si b=2 entonces cÃ1 sino cÃ0

Ejercicio k aÃ3 iÃ1 Repetir mientras i<4 a à a*a i à i+1 Ejercicio n Ejercicio o iÃ0 iÃ0 Repetir mientras i<2 Repetir bÃ0 i à i+1 Repetir Hasta i=0 b à b+1 Hasta b=2 i à i+1

{41{

Ejercicio d aà 2 a à a*2 a à a*2 a à a*a Ejercicio h Si a à 0 entonces bÃ1 bÃ3 Si b=1+2 entonces aÃ1

Ejercicio l iÃ0 Repetir mientras i>0 i à i+1 aÃi Ejercicio p ià 1 Repetir jÃ1 Repetir j à j+1 Hasta j=2 i à i+1 Hasta i>2

~ - EJERCICIOS 4 ALGORITMOS EN LENGUAJE DE DISENO

Nota: Aseg¶urese de comprender claramente los conceptos de asignaci¶on (ej: a à b) y estructura de control condicional (ej: Si a=b entonces c à b) y estructura de control iterativa (ej: Repetir . . . Hasta) antes de abordar la elaboraci¶on de algoritmos m¶as complejos.

Ejercicio 4.2 Realice una traza para los siguientes bloques de acciones. Indique claramente cu¶ales ser¶³an los valores ¯nales para cada uno de los datos en cada caso. Ejercicio a aÃ0 bÃ1 Repetir mientras (a <3) y (b=0) a à a+1 b à b*b

Ejercicio b aÃ0 bÃ1 Repetir a*a veces a à a-1 b à b+1 a à a+1 Ejercicio c Ejercicio d aÃ0 aÃ0 bÃ0 bÃ0 Repetir mientras (a < 3) o (b=0) Repetir a à a+1 a à a*a b à b*b Hasta (a>3) y (b>5)

Ejercicio 4.3 Utilizando como primitivas las operaciones *, +, - y /, escriba algoritmos que implementen las siguientes primitivas: ² EsDivisiblePor: recibe dos n¶umeros enteros N y D, y devuelve verdadero si N es divisible por D, y falso en caso contrario. ² ValorAbsoluto: recibe un n¶umero entero N, y devuelve el valor absoluto de N. ² RaizCuadradaEntera: recibe un n¶ umero natural N, y devuelve la ra¶³z entera (sin decimales) de N. Ej: si N es 10, se devuelve 3. ² EsCuadradoPerfecto: recibe un n¶umero natural N, y devuelve verdadero si N es cuadrado perfecto; falso en caso contrario. ² Resto: recibe dos nros enteros N y D, y devuelve el resto de dividir N por D. ² Potencia: recibe una base real B y un exponente entero E, y devuelve B elevado a la E. ² CantidadDeCifras: recibe un n¶umero entero N, y devuelve la cantidad de d¶³gitos de N (ej: si N = 3421, devuelve 4) {42{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

² Iesimo Digito: recibe un n¶umero entero N, y un valor i, y devuelve el i¡esimo d¶³gito de N (contando desde la izquierda). Ejemplo: para N = 3478, i = 2, Iesimo Digito devuelve 7. Obs.: el operador \/" representa la divisi¶on. Cuando se lo aplica a dos enteros Z1 y Z2, Z1 / Z2 corresponde a la divisi¶on entera entre Z1 y Z2. Cuando se los aplica a reales R1 y R2, la divisi¶on R1 / R2 corresponde a la divisi¶on real. Ejercicio 4.4 Escriba un algoritmo para hallar y mostrar todos los numeros de la forma aabb, donde a y b son d¶³gitos, tal que aabb sea cuadrado perfecto. Obs.: a debe ser distinto de b.

Ejercicio 4.5 Escriba un algoritmo que reciba como entrada un n¶umero natural N y diga si es o no capic¶ua. Un n¶umero N formado por los d¶³gitos d1d2 : : : dk es capic¶ ua si el n¶ umero dk dk¡1 : : : d2d 1 es igual a N . Ejemplo: 1,7, 131, 212, 5005 son capic¶ uas. Ejercicio 4.6 Escriba un algoritmo que muestre todos los capic¶uas entre 0 y 1000. Ejercicio 4.7 Escriba un algoritmo que muestre todas las palabras de cuatro letras que se pueden armar con las letras c, e, p, y a. Obs.: se asume que una \palabra" es una secuencia cualquiera de las cuatro letras dadas, posiblemente repetidas. Ej: ecpa, ppca y eeee son algunas de las palabras que deben mostrarse.

Ejercicio 4.8 Escriba un algoritmo que indique si dos n¶ umeros a y b son \parientes". Se dice que a es \pariente" de b si la suma de los d¶³gitos de a2 es igual a b, y la suma de los d¶³gitos de b2 es igual a a. Ejemplo: 13 y 16 son parientes, ya que 132 = 169, y 1 +6 +9 = 16 y rec¶³procamente 162 = 256, y 2 + 5 + 6 = 13.

Ejercicio 4.9 Escriba algoritmos que permitan sumar los n primeros t¶erminos de las siguientes series: a) 1 + 3 + 5 + 7 + : : : + 2k + 1 + : : : b) 1 ¡ 3 + 5 ¡ 7 + : : : + (¡1)k2k + 1 + : : : Ejercicio 4.10 Escriba un algoritmo para que dadas dos fechas expresadas como d1; m1; a1 y d2; m2; a 2, se obtenga como dato de salida la cantidad de d¶³as transcurridos entre ambas fechas. Ejemplo: {43{

~ - EJERCICIOS 4 ALGORITMOS EN LENGUAJE DE DISENO

² Si d1 = 1, m1 = 1, a1 = 1991 y d2 = 1, m2 = 1, a2 = 1992 ¡! la cantidad de d¶³as trancurridos es 365. ² Si d 1 = 1, m ¡ 1 = 1, a 1 = 1992 y d2 = 1, m2 = 1, a 2 = 1993 ¡! la cantidad de d¶³as trancurridos es 366. Puede asumirse que las fechas dadas son posteriores al 1/1/1900, que la fecha d2 =m2=a2 es posterior a d1=m1=a1 , y que se dispone de la primitiva EsBisiesto, que indica si un a~ no es bisiesto o no. Ejercicio 4.11 Escriba un algoritmo que permita calcular un valor de la serie 1

1 ¡ x1! +

x2 2!

¡

x3 3!

+

x4 4!

¡

x5 5!

¢¢¢

para un valor de x cualquiera, con una \aproximaci¶on" de 0.001 en el resultado (es decir, si Sk es la suma de los primeros k t¶erminos, y Sk+1 es la suma de los primeros k + 1 t¶erminos, la diferencia en valor absoluto entre Sk y Sk+1 debe ser menor que 0.001). Ejercicio 4.12 Escriba un algoritmo que calcule el primer n¶umero primo de forma abc, donde a < b < c. Si no existe ningun primo de esa forma, el algoritmo deber¶a devolver 0 como dato de salida. Ejercicio 4.13 Dado un n¶ umero N, indique el primer M > N tal que M sea m¶ ultiplo de 3 o bien M sea m¶ultiplo de 5. Ejercicio 4.14 Escriba un algoritmo que permita hallar la suma S de todos los numeros primos p comprendidos entre dos enteros N y M , tales que N < p < M . Ejemplo: si N = 10 y M = 20, S = 11 + 13 + 17 + 19:

Ejercicio 4.15 (
Ejercicio 4.16 El Tercer Teorema de Fermat enuncia que no existen n¶umeros enteros x,y,z, tales que para un n¶umero natural n, n > 2, se veri¯que que xn + y n = z n . Sin embargo, el matem¶atico franc¶es Pierre Fermat (1601-1665) tan s¶olo enunci¶³o el teorema anterior, pero no pudo demostrarlo . . . (seg¶ un ¶el, porque la hoja que ten¶³a en ese momento no le alcanzaba). Quiz¶as el teorema sea falso. Para asegurar eso habr¶³a que encontrar un contraejemplo, esto {44{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

es, bastar¶³a encontrar tres n¶ umeros x; y; z y un valor n mayor que 2 tales que xn + yn = z n. Obs.: para n = 2, lo anterior puede satisfacerse; Ejemplo: 32 + 42 = 52 ). Escriba un algoritmo que determine si el Tercer Teorema de Fermat se cumple para cualquier entero entre 0 y 20, con n = 3 y n = 4. (Es decir, el algoritmo deber¶a devolver verdadero si no existen valores x; y; z comprendidos entre 0 y 20, tales que para n = 3 y n = 4, resulte xn + yn = z n). Ejercicio 4.17 Escriba un algoritmo que indique si dos n¶ umeros naturales N y M est¶an formados por los mismos d¶³gitos. Ejemplo: 321 y 213; 599 y 995; 45 y 554 est¶an formados por los mismos d¶³gitos. Ejercicio 4.18 Escriba un algoritmo que encuentre la mayor potencia de 2 que divide exactamente a 100!. Es decir, debe hallar el valor k m¶as grande posible tal que 100! es divisible por 2k. Pista: piense que 100! est¶a compuesto por factores que van desde 1 a 100, y cada factor a su vez puede \factorearse". . . Generalice el ejercicio anterior escribiendo un algoritmo que encuentre la mayor potencia de un n¶umero N que divida exactamente a un valor M !. Ejercicio 4.19 Escriba un algoritmo que dado un n¶ umero natural N, devuelva un nuevo n¶umero natural M , tal que M est¶e formado por los d¶³gitos de N ordenados de menor a mayor. Ejemplo: si N = 7124, entonces M ser¶a 1247; si N = 2231, entonces M ser¶a 1223.

Ejercicio 4.20 Escriba un algoritmo que dados dos n¶umeros naturales N y M , diga si M est¶a contenido en N. Un n¶ umero M se dice contenido en otro N si la secuencia de los d¶³gitos de M aparece consecutivamente dentro de la secuencia de los d¶³gitos de N. Ejemplo: 12 est¶a contenido en 2123 ; 12 no est¶a contenido en 2132; 103 est¶a contenido en 93103 ; 31 est¶a contenido en 93103. Atenci¶ on: Aseg¶ urese que el algoritmo que haya escrito funcione correctamente en casos como los siguientes: N = 321421 y M = 321; N = 32321 y M = 321.

Ejercicio 4.21 La conjetura de Goldbach expresa que todo n¶umero natural par puede expresarse como la suma de dos naturales primos. Ejemplo: 18 = 11 + 7, 20 = 17 + 3, 30 = 11 + 19. Por ser una \conjetura" y no un \teorema", el enunciado anterior podr¶³a llegar a ser falso. Es decir, nadie ha demostrado que lo anterior siempre se cumple, pero nadie tampoco ha encontrado un contraejemplo. Escriba un algoritmo que devuelva verdadero en caso de que la conjetura de Goldbach se veri¯que para todos los n¶ umeros pares entre 100 y 1000, y falso en caso contrario.

{45{

~ - EJERCICIOS 4 ALGORITMOS EN LENGUAJE DE DISENO

Resoluciones tentativas para los algoritmos propuestos Las resoluciones siguientes muestran una manera de resolver los enunciados anteriores; esto no implica que ¶esta sea la ¶unica forma de resolverlos. Ejercicio 4.1 a)

a 0 0 1 1

b ? 1 1 1

b) a 0 1 2 3

e)

a 1 1 1 1

b ? ? 2 4

f) a b 0 ? 0 1

i)

a 0 1 2 3 4

b ? 2 4 6 8

j) a ? ? ?

m)

a 1 2 3

n) b ? 0 1 2 2 0 1 2 2

c) a b ? ? ? 0

g) a 1 1 1

k)

i 0 0 0 0 1 1 1 1 2

d)

b ? 1 1

c ? ? 0

a 3 3 9 9 81 81 6561 6561

i ? 1 1 2 2 3 3 4

o) i 0 1 2 3 ...

a 2 4 8 64

h) a 0 0 0 0 1

b ? 1 1 3 3

l) i 0

p) i 1 1 2 2 2 2 3

j 1 2 2 2 1 2 2

N¶otese que en el caso o), el bloque de acciones se ejecuta un n¶ umero in¯nito de veces (este bloque de acciones no podr¶³a formar parte de un algoritmo, pues ¶este debe llevarse a cabo en un n¶umero ¯nito de pasos). {46{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

Ejercicio 4.2 a)

a b 0 ? 0 1

b) a 0 0 1

b ? 1 1

c)

a 0 0 1 1 2 2 3 3 4 ...

b ? 0 0 0 0 0 0 0 0 ...

d) a 0 0 1 2 ...

b ? 0 0 0 ...

N¶otese que en los casos a) y b), el ciclo repetitivo no se realiza en absoluto; los casos c) y d) el bloque de acciones se ejecuta un n¶ umero in¯nito de veces. Ejercicio 4.3 Nota: para muchos nombres de variables se utiliz¶o el caracter \ " (denominado \underscore" en ingl¶es). Este caracter se utiliza usualmente en computaci¶on para armar nombres de variables con varias palabras (Ejemplo: numero inicial, cant primos). Dado que dicho caracter se confunde en ciertos casos con el subrayado que aparece en el texto, en algunos casos se lo sustituy¶o por un gui¶on \-". (As¶³, en lugar de escribir por ejemplo Iesimo digito, aparece Iesimo-Digito). Otra alternativa utilizada fue crear un nombre de variable concatenando (esto es, ubicando consecutivamente) distintas palabras. Ejemplo: CantPrimosHallados, NumeroHallado, etc. En tales casos, se utilizaron letras may¶usculas en el comienzo de cada palabra para facilitar distinguirlas unas de otras. Algoritmo EsDivisiblePor d.e.: Nro, DivisorPosible d.s.: verdadero si Nro es divisible por DivisorPosible; falso en caso contrario Si DivisorPosible = 0 entonces ERROR ``Division por cero no esta definida'' sino Si (Nro / DivisorPosible)*DivisorPosible = Nro entonces EsDivisiblePor à VERDADERO sino EsDivisiblePor à FALSO {47{

~ - EJERCICIOS 4 ALGORITMOS EN LENGUAJE DE DISENO

Algoritmo ValorAbsoluto d.e.: Nro fcorresponde a un valor enterog d.s.: V fel valor absoluto de Nrog Si Nro>=0 entonces V à Nro sino V à -Nro Algoritmo RaizCuadradaEntera d.e.: Nro fNro es un n¶ u mero naturalg d.s.: Raiz fcorresponde a la ra¶ ³z cuadrada entera de Nrog i à 0 Repetir mientras i*i
fBase es entera; Exponente es naturalg {48{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

d.s.: Pot fResultado de calcular Base elevado a Exponenteg Ex à Exponente Ba à Base Si Exponente=0 entonces Pot à 1 sino Si Exponente<0 entonces fObs: si el exponente es negativo, se lo pasa a un valor positivo equiva Ex à -Exponente Ba à 1/Base ffin del sinog i à Ex Pot à 1 Repetir mientras (i>0) Pot à Pot*Ba fen Pot se almacena Pot*Bag i à i - 1 Algoritmo CantidadDeCifras d.e.: N fn¶ u mero natural mayor que 0g d.s.: Cant fcantidad de digitos de Ng i à 0 Nro à N Repetir mientras (Nro>0) Nro à Nro / 10 i à i + 1 Cant à i Algoritmo Iesimo-Digito d.e.: i, N d.s.: Digito fel d¶ ³gito que ocupa la posicion i-esima en N, contando desde la izquierda. Ej: para i=2, N=3478, Digito es 7g Divisor à Potencia(10,i-1) NroAuxiliar à N / Divisor Digito à Resto(NroAuxiliar, 10) Ejercicio 4.4 Algoritmo HallarAABB d.e.: ninguno d.s.: muestra todos los numeros de la forma aabb que son cuadrados perfectos {49{

~ - EJERCICIOS 4 ALGORITMOS EN LENGUAJE DE DISENO

a à 1 fa var¶ ³a entre 1 y 9g Repetir Mientras a<=9 b à 0 Repetir Mientras b<=9 fb var¶ ³a entre 0 y 9g Si a<>b entonces Numero à ArmarNumero(a,b) Si CuadradoPerfecto(Numero)=VERDADERO entonces mostrar Numero b à b + 1 a à a + 1 Algoritmo ArmarNumero d.e.: a y b fvalores enterosg d.s.: nro fde la forma aabbg Nro = a*1000 + a*100 + b*10 + b fObservacion:el algoritmo para CuadradoPerfecto figura en un ejercicio anteriorg

Ejercicio 4.5 Una estrategia a aplicar puede ser la siguiente: dado un n¶umero d k : : : d1, se asume primero que el n¶ umero es capic¶ ua, usando una variable EsCapicua a la que le asigna verdadero. Se calcula luego la posici¶on del primer y el ¶ultimo d¶³gito, y se las almacena en variables Izquierda y Derecha respectivamente. Se comparan los d¶³gitos que est¶an en esas posiciones. Si son iguales, se incrementa Derecha y se decrementa Izquierda, y se sigue comparando. Si son distintos, a EsCapicua se le asigna el valor falso. El proceso de comparar d¶³gitos se repite hasta que las variables Izquierda y Derecha se \crucen", o EsCapicua llegue a tener valor falso. Ejemplo: en un principio, EsCapicua = verdadero 199891 199891 199891

Izq = 6, Der = 1 , EsCapicua = (1=1) verdadero Izq = 5, Der = 2 , EsCapicua= (9=9) verdadero Izq = 4, Der = 3 , EsCapicua= (9=8) falso

y en este punto se corta el ciclo, ya que EsCapicua tiene valor falso. Algoritmo EsCapicua d.e.: N fn¶ u mero naturalg d.s.: verdadero si N es capic¶ u a; falso en caso contrario. {50{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

CantDigitos à CantidadDeCifras(N) Derecha à 1 Izquierda à CantDigitos EsNroCapicua à verdadero Repetir Mientras (Derecha>Izquierda) y (EsNroCapicua=verdadero) DigDer à Iesimo-Digito(Derecha,N) DigIzq à Iesimo-Digito(Izquierda,N) EsNroCapicua à (DigDer = DigIzq) Derecha à Derecha + 1 Izquierda à Izquierda -1 Si EsNroCapicua=verdadero entonces EsCapicua à VERDADERO sino EsCapicua à FALSO Ejercicio 4.6 Algoritmo Capicuas d.e.: ninguno d.s.: muestra todos los capic¶ u as entre 0 y 1000 NumeroEnCurso à 1 Repetir mientras (NumeroEnCurso<1000) Si EsCapicua(NumeroEnCurso)=verdadero entonces mostrar NumeroEnCurso NumeroEnCurso à NumeroEnCurso + 1 Ejercicio 4.7 Este ejercicio es an¶alogo a generar todos los n¶umeros posibles que pueden obtenerse a partir de 4 d¶³gitos distintos (p.ej: 1,2,3 y 4), considerando la posibilidad de que haya d¶³gitos repetidos. Habiendo hecho esto, necesitar¶³amos hacer corresponder cada d¶³gito con una de las letras dadas (c,e,p,a). Un algoritmo para generar los n¶ umeros anteriores ser¶³a: Algoritmo GenerarNumeros d.e.: ninguno d.s.: muestra todos los n¶ umeros de 4 d¶ ³gitos que pueden formarse a partir de 1,2,3 y 4. a à 1 Repetir mientras (a<=4)

{51{

~ - EJERCICIOS 4 ALGORITMOS EN LENGUAJE DE DISENO

b à 1 Repetir mientras (b<=4) c à 1 Repetir mientras (c<=4) d à 1 Repetir mientras (d<=4) Numero à ArmarNumero(a,b,c,d) (*) mostrar Numero (*) d à d+1 c à c + 1 b à b + 1 a à a + 1 Algoritmo ArmarNumero d.e.: a,b,c,d fdigitosg d.s.: Numero fformado por los digitos a,b,c,d,g Numero à a*1000 + b*100 + c*10 + d Para generar todas las palabras posibles con las letras dadas, simplemente debemos reemplazar la parte marcada con (*) por la llamada a primitiva MostrarPalabra(a,b,c,d). La primitiva MostrarPalabra puede escribirse como sigue: Algoritmo MostrarPalabra d.e.: a,b,c,d fvariables que contienen valores num¶ ericosg d.s.: muestra en pantalla una palabra de cuatro letras MostrarLetra(a) MostrarLetra(b) MostrarLetra(c) MostrarLetra(d)

Algoritmo MostrarLetra d.e.: N d.s.: muestra la letra 'c', 'e','p' o 'a', seg¶ un el valor de N Si N = 1 entonces mostrar 'c' sino

{52{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

Si N=2 entonces mostrar 'e' sino Si N=3 entonces mostrar 'p' sino Si N=4 entonces mostrar 'a' Ejercicio 4.8 Algoritmo NrosParientes d.e.: A,B fA,B 2 Naturales, inclu¶ ³do el 0g d.s.: verdadero si A es ``pariente'' de B; falso en caso contrario A2 à A*A B2 à B*B CantDigiA2 à CantidadDeCifras(A2) CantDigiB2 à CantidadDeCifras(B2) n1 à 1 SumaDigitosA2 à 0 Repetir mientras (n1<=CantDigiA2) Digitoi à Iesimo-Digito(A2,n1) SumaDigitosA2 à SumaDigitosA2 + Digitoi n1 à n1 + 1 n2 à 1 SumaDigitosB2 à 0 Repetir mientras (n2<=CantDigiB2) Digitoi à Iesimo-Digito(B2,n2) SumaDigitosB2 à SumaDigitosB2 + Digitoi n2 à n2 + 1 NrosParientes à (SumaDigitosA2 = SumaDigitosB2) (es decir, si la suma de los d¶³gitos de ambos n¶ umeros es igual, NrosParientes es verdadero; caso contrario es falso). Ejercicio 4.9 Inciso a: Algoritmo Serie {53{

~ - EJERCICIOS 4 ALGORITMOS EN LENGUAJE DE DISENO

d.e.: n fcantidad de t¶ erminos a sumarg d.s.: Suma fsuma de los n primeros t¶ erminosg Suma à 0 i à 1 Repetir mientras (i<=n) TerminoIesimo à Termino(i) Suma à Suma + TerminoIesimo i à i + 1 Algoritmo Termino d.e.: i d.s.: T fvalor del t¶ e rmino i-esimo de la serieg T à 2*i+1 Inciso b: Puede utilizarse el algoritmo Serie antes de¯nido. El algoritmo Termino deber¶a rede¯nirse como sigue: Algoritmo Termino d.e.: i d.s.: T ft¶ ermino i-esimo de la serieg Signo à Potencia(-1,i) factor à 2*i+1 T à signo*factor Moraleja: para sumar los n primeros t¶erminos de una serie, puede usarse por lo general un algoritmo b¶asico Serie, adaptando {seg¶un el caso{ la de¯nici¶on del algoritmo Termino. Ejercicio 4.10 Para calcular los d¶³as transcurridos entre d1/m1/a1 y d2/m2/a2, se va a hacer lo siguiente: primero, se calculan los d¶³as transcurridos entre d2/m2/a2 y 1/1/1900 (se llama a esto Cant2). Luego se calculan los d¶³as transcurridos entre d1/m1/a1 y 1/1/1900 (se llama a esto Cant1). Luego se calcula CantDias como el valor absoluto de Cant2 - Cant1. La fecha \base" (en este caso 1/1/1900) puede ser cualquiera. En este caso, el algoritmo sirve para cualquier fecha del siglo xx en adelante (lo que a ¯nes pr¶acticos es su¯ciente). Alternativamente, podr¶³a haberse elegido como fecha \base" cualquier primero de enero de un a~ no dado. Se de¯nir¶an los siguientes algoritmos auxiliares Algoritmo DiasDeA~ no d.e.: a~ no fnro. de a~ nog {54{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

d.s.: DiasA~ no fla cantidad de d¶ ³ as que tiene el a~ nog Si EsBisiesto(a~ no)=verdadero entonces DiasA~ no à 366 sino DiasA~ no à 365 Algoritmo DiasDeMes d.e.: mes, a~ no fnro. del mesg d.s.: DiasMes fcantidad de d¶ ³ as que tiene el mes en ese a~ nog Si Mes=2 entonces Si EsBisiesto(a~ no)=verdadero entonces DiasMes à 29 ffebrero tiene 29 d¶ ³asg sino DiasMes à 28 Si Mes=1 o Mes=3 o Mes=5 o Mes=7 o Mes=8 o Mes=10 o Mes=12 entonces DiasMes à 31 fes mes de 31 d¶ ³asg sino DiasMes à 30 fes mes de 30 d¶ ³asg Algoritmo DiasEnSigloXX fcalcula la cantidad de d¶ ³as entre una fecha y 1/1/1900g d.e.: d, m, a fd¶ ³a mes y a~ n og d.s.: CantDias fd¶ ³ as entre d,m,a y 1/1/1900g d1 à d fse almacena primero todo en variables auxiliaresg m1 à m a1 à a CantDias à 0; fse inicializa CantDias en 0g Repetir Mientras a1>1900 a1 à a1-1 fse cuentan d¶ ³ as de los a~ nos desde a1-1 hasta 1900g CantDias à CantDias + DiasDelAno(a1) fidem con los mesesg Repetir Mientras m1>1 m1 à m1-1 CantDias à CantDias + DiasDelMes(a1,m1) fidem con d¶ ³asg Repetir Mientras d1>1 d1 à d1-1 CantDias à CantDias + 1 Algoritmo DiasEntreFechas fCalcula la cantidad de d¶ ³as entre dos fechas dadas d1/m1/a1 y d2/m2/a2 g d.e.: d1,m1,a1 d2,m2,a2 flas dos fechasg d.s.: CantDias fcantidad de d¶ ³as transcurridosg {55{

~ - EJERCICIOS 4 ALGORITMOS EN LENGUAJE DE DISENO

CantDiasAux à DiasEnSigloXX(d2,m2,a2) - DiasEnSigloXX(d1,m1,a1) CantDias à ValorAbsoluto(CantDiasAux) Ejercicio 4.11 Se de¯nen primeramente los siguientes algoritmos auxiliares Algoritmo Factorial d.e.: n fn¶ u mero enterog d.s.: Fac fEl valor n!g Fac à 1 Naux à n Repetir Mientras Naux>1 Fac à Fac * Naux Naux à Naux - 1 Algoritmo Termino d.e.: Num,Den fnumerador,denominadorg d.s.: Cociente fel cociente entre numerador y denominadorg f...El cuerpo del algoritmo queda a cargo del lector ...g Algoritmo SumaSerie d.e.: x fvalor de x a utilizarg d.s.: Aprox fresultado de la serie para xg AproxActual à 1 fla primer aproximaci¶ on es 1g signo à -1 fel signo empieza siendo negativog i à 1 fi es el ¶ ³ndice para cada t¶ erminog EncontreAproximacion à falso fse asume que 1 no es la aprox. Repetir Numerador à Potencia(x,i) Denominador à Factorial(x,i) NuevoTermino à Termino(Numerador,Denominador) AproxNueva à AproxActual + Signo*NuevoTermino Signo à Signo * (-1) fSe cambia el signog i à i + 1 Epsilon à ValorAbsoluto(AproxNueva-AproxActual) Si Epsilon<0.001 entonces EncontreAproximacion à verdadero Hasta EncontreAproximacion=verdadero Aprox à AproxNueva

{56{

buscadag

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

Ejercicio 4.12 La estrategia ser¶a la siguiente: se va a suponer que no hay ning¶ un primo N de la forma pedida, es decir, N = 0. Se van a armar todos los numeros posibles entre 100 y 999, y si alguno de ellos es primo de la forma que se pide, ese ser¶a el valor de N . Los numeros entre 100 y 999 se ir¶an armando siempre y cuando N sea 0 (es decir, si todav¶³a no se encontr¶o el primo que se busca). Si se llega a encontrar el primo N, entonces debe detenerse la b¶usqueda. Algoritmo PrimoABC d.e.: ninguno d.s.: N fnro. primo de la forma abc seg¶ u n el enunciado, o 0 si no hay ning¶ un primo como el que se pideg N à 0 fse asume en principio que no existe un primo como el pedidog a à 1 fa son las centenasg Repetir b à a+1 fb son las decenas, que van de a + 1 hasta 9 g Repetir c à b+1 f c las unidades, que van de b + 1 hasta 9g Repetir Naux à a*100 + b*10 + c Si EsPrimo(Naux)=verdadero entonces fqueda como ejercicio escribir EsPrimog N à Naux sino c à c + 1 Hasta (c>9) o (EsPrimo(N)=verdadero) b à b + 1 Hasta (b>9) o (EsPrimo(N)=verdadero) a à a + 1 Hasta (a>9) o EsPrimo(N)=verdadero Obs.: la primitiva EsPrimo(N) deber¶³a devolver falso para N = 0, para que el algoritmo anterior funcione correctamente. Por razones de e¯ciencia (que se ver¶an m¶as adelante), resulta conveniente sustituir dicha condici¶on por N > 0 en el texto del algoritmo. Esta ¶ultima condici¶on es equivalente a EsPrimo(N) a los ¯nes del funcionamiento correcto del algoritmo. Ejercicio 4.13 Algoritmo PrimerM d.e.: n d.s.: m Maux à n {57{

~ - EJERCICIOS 4 ALGORITMOS EN LENGUAJE DE DISENO

TermineMul3 à falso fse asume que a¶ u n no se tiene un m¶ u ltiplo de 3g TermineMul5 à falso fni de 5g Repetir Maux à Maux + 1 Si EsMultiplo(Maux,3) entonces fqueda por escribir la primitiva EsMultiplog TermineMul3 à verdadero Si EsMultiplo(Maux,5) entonces TermineMul5 à verdadero Hasta (TermineMul3=verdadero) o (TermineMul5=verdadero) Mostrar Maux

Ejercicio 4.14 Se de¯ne primero el siguiente algoritmo auxiliar: Algoritmo ProximoPrimo fdevuelve el pr¶ o ximo primo mayor que ng d.e.: n fnro enterog d.s.: ProxPri f1er nro primo p > ng EncontrePrimo à falso Naux à n + 1 Repetir Si EsPrimo(Naux)=verdadero entonces ProxPri à Naux EncontrePrimo à verdadero sino Naux à Naux + 1 Hasta (EncontrePrimo = verdadero) Algoritmo SumaPrimos d.e.: n, m flos valores N y M del enunciadog d.s.: Suma fla suma de primos p tales que N < p < M g Suma à 0 Indice à n + 1 Repetir Mientras Indice<M NroPrimo à ProximoPrimo(Indice) fse busca el proximo primog Suma à Suma + NroPrimo fy se sigue buscando, a partirg Indice à NroPrimo fdel pr¶ oximo primo que se encontr¶ og Ejercicio 4.15 Los s¶³mbolos romanos a usar ser¶an I, V, X, L, C, D, y M. Puede establecerse la siguiente {58{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

relaci¶on de valor num¶erico entre los s¶³mbolos:

S¶³mbolo 1 I X C

S¶³mbolo 2 V L D

S¶³mbolo 3 X C M

Es decir, la relaci¶on entre I, V y X es la misma que se da entre X,L,C y C,D,M. Puede escribirse el siguiente algoritmo:

Algoritmo DigitoRomano d.e.: Dig, Simbolo1, Simbolo2, Simbolo3 d.s.: muestra Digito en nros. romanos usando los Simbolos anteriores Si (Dig>=5) y (Dig<9) entonces mostrar Simbolo2 Dig à Dig-5 Si (Dig>0) y (Dig<4) entonces ià 1 Repetir mientras (i<=Dig) Mostrar Simbolo1 Digà Dig-1 Si (Dig=4) entonces Mostrar Simbolo1,Simbolo2 Si (Dig=9) entonces Mostrar Simbolo1,Simbolo3

Algoritmo DescomponerNro d.e.: N fn¶ u mero naturalg d.s.: Centena, Decena, Unidad fdescomposici¶ o n en digitos de Ng Centena à n / 100 Decena à (n-Centena*100) / 10 Unidad à (n-Centena*100-Decena*10) Algoritmo ArmarNroRomano d.e.: N fn¶ u mero naturalg d.s.: muestra n¶ umero romano correspondiente a N DescomponerNro(N,Cen,Dec,Uni) {59{

~ - EJERCICIOS 4 ALGORITMOS EN LENGUAJE DE DISENO

DigitoRomano(Cen,'C','D','M') DigitoRomano(Dec,'X','L','C') DigitoRomano(Uni,'I','V','X') Ejercicio 4.16 Algoritmo Fermat d.e.: ninguno d.s.: VERDADERO si el teorema se cumple para los valores probados, FALSO en caso contrario. SeCumple à verdadero n à 3 Repetir mientras (N<5) y (SeCumple=verdadero) x à 0 Repetir mientras (x<20) y (SeCumple=verdadero) y à 0 Repetir mientras (y<20) y (SeCumple=verdadero) z à 0 Repetir mientras (z<20) y (SeCumple=verdadero) x-elev-n à Potencia(x,n) y-elev-n à Potencia(y,n) z-elev-n à Potencia(z,n) SeCumple à (x-elev-n + y-elev-n) <> (z-elev-n) z à z + 1 y à y + 1 x à x + 1 n à n + 1 Si SeCumple = FALSO entonces Fermat à FALSO sino Fermat à VERDADERO Ejercicio 4.17 Dados N y M , dos n¶ umeros naturales, se veri¯car¶a por doble inclusi¶on que los d¶³gitos de N son los mismos que los de M . Esto es: se ver¶a que los d¶³gitos de N est¶an contenidos en los d¶³gitos de M , y viceversa. La estrategia ser¶a la siguiente: Se supone al principio que N y M tienen los mismos d¶³gitos. Esto se lo representa con una variable booleana TienenLosMismosDigitos a la cual le asigna valor verdadero. Se toma N, y se veri¯ca que cada d¶³gito de N aparezca en M . Luego se toma M , y se veri¯ca que cada d¶³gito de M aparezca en N. Si en alg¶un punto llega a darse el caso que hay un d¶³gito de un n¶ umero que no aparece en el otro n¶umero, entonces a TienenLosMismosDigitos se le asigna falso. Algoritmo NumerosConDigitosIguales {60{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

d.e.: N, M d.s.: VERDADERO si d¶ ³gitos de N son los mismos que d¶ ³gitos de M FALSO en caso contrario TienenLosMismosDigitosà verdadero CantN à CantidadDeCifras(N) CantM à CantidadDeCifras(M) i à 1 Repetir mientras (i<=CantN) y (TienenLosMismosDigitos=verdadero) d à Iesimo Digito(N,i) Si (DigitoEnNumero(d,M)=falso) entonces TienenLosMismosDigitos=falso i à i + 1 i à 1 Repetir mientras (i<=CantM) y (TienenLosMismosDigitos=verdadero) dà Iesimo Digito(M,i) Si (DigitoEnNumero(d,N)=falso) entonces TienenLosMismosDigitos=falso i à i + 1 Si TienenLosMismosDigitos=verdadero entonces NumerosConDigitosIguales à VERDADERO sino NumerosConDigitosIguales à FALSO

El algoritmo auxiliar DigitoEnNumero de¯ne una primitiva que permite veri¯car si dado un d¶³gito D y un n¶umero N, el d¶³gito D est¶a presente entre los d¶³gitos de N. Algoritmo DigitoEnNumero d.e.: Digito, Numero d.s.: VERDADERO si Digito est¶ a en Numero; FALSO en caso contrario. DigitoPresente à falso fse supone primero que el d¶ ³ gito no est¶ a presente en el n¶ umerog Repetir Cociente à Numero / 10 Resto à Numero - Cociente*10 Si Resto = Digito entonces DigitoPresente à verdadero Hasta (Cociente=0) o (DigitoPresente=verdadero) Si DigitoPresente=verdadero entonces DigitoEnNumero à VERDADERO sino DigitoEnNumero à FALSO

{61{

~ - EJERCICIOS 4 ALGORITMOS EN LENGUAJE DE DISENO

Ejercicio 4.18 Recordemos que 100! es equivalente al producto de todos los naturales consecutivos desde 1 hasta 100, esto es 1:2:3:4: : : : 98:99:100. Para encontrar la mayor potencia de 2 que divide a 100!, debemos contar la cantidad de veces que el 2 aparece como factor en 100!. Para esto, debemos contar la cantidad de veces que 2 aparece como factor en la descomposici¶on de todos los naturales entre 1 y 100. Escribimos el siguiente algoritmo: Algoritmo MayorPotenciaDe2 d.e.: ninguno d.s.: exponente fexponente de la m¶ a xima potencia de 2 que divide a 100! nro à 2 fse empieza de 2 en adelanteg exponente à 0 Repetir mientras (nro<=100) CantApariciones à ContarAparicionDos(nro) exponente à exponente + CantApariciones

g

Algoritmo ContarAparicionDos d.e.: Nro d.s.: Cant fcantidad de veces que 2 aparece como factor en Nrog Aux à Nro Cant à 0 Repetir mientras (EsDivisible(Aux,2)=verdadero) y (Aux>0) Cant à Cant + 1 Aux à Aux / 2

La generalizaci¶on del algoritmo anterior es directa, y queda como ejercicio para el lector.

Ejercicio 4.19 La estrategia que podemos emplear es la siguiente: buscamos las apariciones de cada d¶³gito posible, desde el 9 hasta el 1 (el cero no lo consideramos pues no agrega nada al nuevo n¶umero a formar). Para cada d¶³gito D, contamos la cantidad K de veces que aparece en N, y D se agrega K veces a un nuevo n¶ umero Resultado en la posici¶on correspondiente. Ejemplo: si N = 13491, hacemos lo siguiente 13491 13491 ... 13491 13491 ... 13491

{buscamos d¶³gito 9, y contamos 1 aparici¶on ¡! {buscamos d¶³gito 8, y contamos 0 aparici¶on ¡!

Resultado=9 Resultado=9

{buscamos d¶³gito 4, y contamos 1 aparici¶on ¡! {buscamos d¶³gito 3, y contamos 1 aparici¶on ¡!

Resultado=49 Resultado=349

{buscamos d¶³gito 1, y contamos 2 apariciones ¡!

Resultado=11349

La posici¶on correspondiente para el nuevo n¶umero la llevamos en una variable Desplazamiento. {62{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

Algoritmo ObtenerNuevoNumero d.e.: N d.s.: M fn¶ umero formado a partir de los d¶ ³ gitos de N ordenados de menor a mayorg DigitoEnCurso à 9 Desplazamiento à 0 Resultado à 0 Repetir mientras (DigitoEnCurso>=1) VecesQueAparece à ContarAparicion(N,DigitoEnCurso) ià 1 Repetir mientras (i<=VecesQueAparece) Resultado à Resultado + DigitoEnCurso*Potencia(10,Desplazamiento) i à i+1 Desplazamiento à Desplazamiento + 1 DigitoEnCurso à DigitoEnCurso + 1 M à Resultado

Usamos el algoritmo auxiliar ContarAparicion, el cual recibe como entrada un n¶umero N y un d¶³gito D, y devuelve la cantidad de veces que el d¶³gito D aparece en N. Algoritmo ContarAparicion d.e.: Digito, Numero d.s.: Veces fcantidad veces Digito aparece en Numerog Cociente à Numero Veces à 0 Repetir Resto à Cociente // 10 Cociente à Cociente / 10 Si Resto = Digito entonces Veces à Veces + 1 Hasta (Cociente=0) Ejercicio 4.20 Algoritmo TerminaEnNumero d.e.: N, M d.s.: VERDADERO si el n¶ umero N ``termina'' en M; FALSO en caso contrario (ej: devuelve verdadero para 31234 y 234; 1431 y 31; 93413 y 3413, etc.) AuxN à N AuxM à M Termina à verdadero Repetir mientras (AuxM>0) y (Termina=verdadero)

{63{

~ - EJERCICIOS 4 ALGORITMOS EN LENGUAJE DE DISENO

DigN à Resto(AuxN,10) DigM à Resto(AuxM,10) Termina à (DigN = DigM) AuxN à AuxN / 10 AuxM à AuxM / 10 Si Termina=verdadero entonces TerminaEnNumeroà VERDADERO sino TerminaEnNumeroà FALSO Algoritmo EstaContenidoMenN d.e.: N, M d.s.: VERDADERO si M est¶ a contenido en N; FALSO en caso contrario AuxN à N EstaContenido à falso Repetir mientras (AuxN > M) y (EstaContenido=falso) Si TerminaEnNumero(AuxN,M)=verdadero entonces EstaContenido à verdadero AuxN à AuxN / 10 Si EstaContenido entonces EstaContenidoMenNà VERDADERO sino EstaContenidoMenNà FALSO Ejercicio 4.21 Algoritmo ConjeturaGoldbach d.e.: ninguno d.s.: VERDADERO si la conjetura de Goldbach se cumple para todos los n¶ umeros pares entre 100 y 1000; FALSO en caso contrario. Conjetura à Verdadero NroPar à 100 Repetir mientras (Conjetura=verdadero) y (NroPar<=1000) Conjetura à AplicarGoldbach(NroPar, Primo1 , Primo2) Si (Conjetura = verdadero) entonces mostrar `el numero' NroPar `puede escribirse como la suma de' Primo1 ` y ' Primo2 sino mostrar `La Conjetura de Goldbach es FALSA..!!!' NroPar à NroPar + 2 Si Conjetura=verdadero {64{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

entonces ConjeturaGoldbach à VERDADERO sino ConjeturaGoldbach à FALSO El algoritmo AplicarGoldbach prueba todas las sumas posibles entre dos primos i y j, tal que i+ j < NroP ar. Si en alg¶ un momento resulta que i +j = N roP ar, se han encontrado los dos primos buscados, y el \resultado" de la conjetura es verdadero. Si en ning¶un momento se encuentran los n¶umeros i y j en las condiciones pedidas, el \resultado" devuelto es falso. para probar todas las sumas posibles entre primos, se usar¶an dos estructuras repetir mientras anidadas de la siguiente manera: i à primer primo j à primer primo Repetir mientras (i+j) j à pr¶ oximo primo siguiente a j i à pr¶ oximo primo siguiente a i Algoritmo AplicarGoldbach d.e.: NroPar d.s.: Primo1, Primo2 fnros. primos que sumados dan NroParg Resultado fVERDADERO si se pudo encontrar dos primos que sumen NroPar; FALSO en caso contrariog i à 2 j à 2 Encontre à falso Repetir mientras ((i+j)
~ - EJERCICIOS 4 ALGORITMOS EN LENGUAJE DE DISENO

sino AplicarGoldbach à FALSO

Cabe se~ nalar que la primitiva ProximoPrimo es an¶aloga a la primitiva \Incrementar en 1", con excepci¶on de que cada incremento pasa al pr¶oximo natural primo, y no al pr¶oximo natural (como suced¶³a en el caso de \Incrementar en 1").

{66{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

5 5.1

De algoritmos en lenguaje de dise~ no a programas en Pascal Introducci¶ on

Ya se ha visto c¶omo resolver problemas mediante algoritmos, los cuales fueron expresados en un lenguaje de dise~ no. Ahora nos abocaremos a la tarea de trasladar dichos algoritmos en programas, utilizando el lenguaje de programaci¶on Pascal. La estructura general de los algoritmos permanecer¶a inalterada, exceptuando muchas de las palabras clave empleadas, las que deber¶an escribirse ahora en ingl¶es (ej: repetir mientras a>0 ser¶a escrito while a>0 do). En la elaboraci¶on de programas existe menos libertad que al trabajar con algoritmos, dado que los programas deben ser ejecutados sobre una computadora. La computadora es simplemente una m¶aquina capaz de ejecutar programas a gran velocidad. Sin embargo, debe indic¶arsele exactamente que se desea hacer mediante instrucciones dadas en un lenguaje de programaci¶on.

5.2

>Qu¶ e es la sintaxis? La notaci¶ on bnf

Un elemento com¶un entre los idiomas hablados por los seres humanos y los lenguajes de programaci¶on es la presencia de una sintaxis. La sintaxis es un conjunto de reglas que de¯ne cu¶ales son las sentencias v¶alidas de un lenguaje. La sem¶antica, por otra parte, establece cu¶al es el signi¯cado de una sentencia de un lenguaje. Ejemplo: en castellano, es incorrecto escribir \Yo ten¶³an hambre"; el verbo y el sujeto no concuerdan; se dice en tal caso que la oraci¶on es sint¶acticamente inv¶alida. La oraci¶on \Juan vuela debajo del agua" es sint¶acticamente v¶alida (verbo y sujeto concuerdan; debajo del agua es una expresi¶on correcta en castellano, etc.), pero es sem¶anticamente incorrecta, ya que no tiene sentido (esto es, no tiene un signi¯cado claro) hablar de \volar debajo del agua". Ser¶³a muy complicado de¯nir exactamente cu¶al es la sintaxis del castellano, ya que resulta pr¶acticamente imposible de¯nir formalmente todas las oraciones \v¶alidas" posibles; la cantidad de oraciones diferentes que podr¶³an construirse es enorme. Sin embargo, en los lenguajes de programaci¶on, el problema no es tan grave. Los lenguajes de programaci¶on suelen tener un conjunto restringido de sentencias posibles, facilit¶ando as¶³ al compilador la tarea de detectar si un programa es o no sint¶acticamente v¶alido. Para de¯nir la sintaxis de un lenguaje de programaci¶on, suele emplearse una notaci¶on conocida como forma Backus-Naur, abreviada como bnf. Esta notaci¶on permite caracterizar aquellas secuencias de caracteres que van a aceptarse como sentencias v¶alidas. La notaci¶on bnf hace uso de una serie de s¶³mbolos especiales. Veamos cu¶ales son estos s¶³mbolos:

{67{

~ A PROGRAMAS EN PASCAL 5 DE ALGORITMOS EN LENGUAJE DE DISENO S¶³mbolo j fg [] ::= termino

Signi¯cado Se utiliza para separar varias alternativas. Se utilizan para encerrar algo que se repite 0 o m¶a s veces. Se utilizan para indicar que algo es opcional. Se utiliza para indicar que lo que aparece a la izquierda de este s¶³mbolo est¶a de¯nido por lo que aparece a la derecha. los corchetes angulares se utilizan para indicar que t¶ermino est¶a de¯nido a partir de otros elementos. se utiliza para indicar que t¶ermino consiste exactamente de la secuencia de letras t, e, r, m, i, n y o.

Ejemplo: supongamos que queremos de¯nir un identi¯cador (esto es, el nombre asociado a un dato o una variable dentro de un programa) como una secuencia de letras y/o d¶³gitos, que debe comenzar necesariamente con una letra. Ejemplos de identi¯cadores v¶alidos ser¶³an Pepe, P1, Eje01, ab00cd. Veamos primeramente c¶omo de¯nir qu¶e es un d¶³gito. Un d¶³gito es simplemente: ::= 0j1j2j3j4j5j6j7j8j9 Esto es, un d¶³gito es o bien el caracter 0, o bien el caracter 1, o bien el caracter 2, etc. Un n¶ u mero natural est¶a formado por uno o m¶as d¶³gitos. Podemos de¯nirlo entonces como: ::= fg Una letra tambi¶en es f¶acil de de¯nir, de la siguiente manera ::= ajbjcjdjejfjgjhjijjjkjljmjnjojpjqjrjsjtjujvjwjxjyjz Un identi¯cador (ej: el nombre de una variable, o el nombre del programa) debe comenzar con una letra, y estar seguido luego de letras o d¶³gitos. Esto puede escribirse como: := fjg Esto es: un identi¯cador est¶a formado por una letra, seguido por 0 o m¶as s¶³mbolos, cada uno de los cuales puede ser una letra o un d¶³gito. Esta de¯nici¶on de identi¯cador es pr¶acticamente id¶entica a la que utiliza el lenguaje Pascal. 11 11

En los identi¯cadores de Pascal tambi¶en es posible utilizar como caracter intermedio el \ ", denominado en ingl¶es underscore. Ejemplo: en Pascal, son identi¯cadores v¶a lidos Es Nro Primo, Cantidad Digitos, etc.

{68{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

La sintaxis de Pascal

5.3

A continuaci¶on se analizar¶a cu¶al es la estructura general de un programa en Pascal, expres¶andola en notaci¶on bnf. Program (input,output) ; [ <declaracion-constantes> ] [ <declaracion-tipos> ] [ <declaracion-variables> ] [ <de¯nicion-procedimientos-y-funciones> ] Begin End. La parte de c¶odigo correspondiente a constituye lo que suele denominarse programa principal, para diferenciarlo de los procedimientos y funciones auxiliares que puedan utilizarse dentro del programa. Analizaremos ahora m¶as detalladamente cada uno de los elementos que pueden aparecen en un programa en Pascal. 5.3.1

Declaraci¶ on de constantes

Esta parte es opcional. A trav¶es de la misma, puede asociarse un valor constante a determinados identi¯cadores. La de¯nici¶on de <declaraci¶on-constantes> es: <declaracion-constantes>::= Const = f; = g Ejemplo: si en un programa P se incluye Const Pi = 3.14; Verdadero = True; Diez = 10;

entonces los identi¯cadores Pi, Verdadero y Diez tendr¶an asociados los valores constantes 3.14, True y 10, respectivamente. 5.3.2

Declaraci¶ on de tipos

Esta parte tambi¶en es opcional. En este punto, el programador tiene la alternativa de de¯nir nuevos tipos de dato, a partir de los tipos b¶asicos ya existentes provistos por Pascal. La de¯nici¶on de <declaraci¶on-tipos> en notaci¶on bnf es: <declaracion-tipos>::= Type =<de¯nicion-tipo> f; = <de¯nicion-tipo>g; {69{

~ A PROGRAMAS EN PASCAL 5 DE ALGORITMOS EN LENGUAJE DE DISENO

La especi¯caci¶on de <de¯nicion-tipo> es un tema importante, que ser¶a tratado en profundidad en materias m¶as avanzadas. Veamos algunos ejemplos de de¯nici¶on de tipos: Type Entero = integer; TipoDiaDeSemana = (lunes, martes, miercoles, jueves, viernes); TipoDigitos = 0..9;

En el primer caso, se est¶a de¯niendo un nuevo tipo Entero, que ser¶a id¶entico al tipo integer provisto por Pascal. Posteriormente, podr¶a declararse una variable de tipo Entero, y realizar sobre ella todas las operaciones que Pascalprovee para el tipo integer. En el segundo caso, se est¶a de¯niendo un tipo enumerado: una variable que sea de tipo TipoDiaDeSemana podr¶a tener asumir u¶nicamente lunes, martes, miercoles, jueves o viernes como valor. Si Dia es una variable TipoDiaDeSemana, podr¶an escribirse luego sentencias tales como If (Dia = lunes) or (Dia=martes) then writeln('Comienzo de semana...');

En el tercer caso, se est¶a de¯niendo un tipo subrango: una variable de tipo TipoDigito podr¶a asumir u¶nicamente valores que van de 0 a 9. Advertencia: La declaraci¶on de nuevos tipos es un tema que ser¶a tratado en detalle m¶as adelante; en este apunte se incluye el mismo s¶ olo a t¶³tulo informativo. 5.3.3

Declaraci¶ on de variables

Esta parte tambi¶en es opcional. En este punto, el programador debe declarar todas las variables que se utilizar¶an posteriormente en . Para declarar una variable, debe indicarse su nombre y su tipo. Si existe m¶as de una variable del mismo tipo, puede declar¶arselas separ¶andolas por una coma, e indicando luego el tipo asociado. M¶as formalmente, la declaraci¶on de variables puede de¯nirse de la siguiente manera: <declaracion-variables>::= Var f,g: f;f,g: g; Ejemplo: las siguientes son declaraciones v¶alidas de variables.

Var indice,n,i,k: integer; DeboSeguir,EncontreUnNumeroPrimo: boolean; RaizCuadradaDeN,RaizCubicaDeN: Real;

5.3.4

De¯nici¶ on de procedimientos y funciones

En este punto, el programador debe de¯nir los \cuerpos" de los procedimientos y funciones asociados al programa. Pueden de¯nirse tantos procedimientos y funciones como se desee;

{70{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

m¶as formalmente, puede caracterizarse la de¯nici¶on de procedimientos y funciones de la siguiente manera: <de¯nicion-procedimientos-y-funciones> ::= f <de¯nicion-procedimiento> j<de¯nicion-funcion> g Al ¯nal de este apunte, se detallar¶a en qu¶e consisten <de¯nicion-procedimiento> y <de¯nicion-funcion>. Debe tenerse presente que los procedimientos y funciones se corresponden con el concepto de \primitiva" visto en clase. Seg¶ un la cantidad de datos de salida que posea la primitiva, ser¶a conveniente utilizar procedimientos o funciones. 5.3.5

Bloque de sentencias

El bloque de programa est¶a formado por una o m¶as sentencias. Las sentencias est¶an separadas entre s¶³ por un punto y coma (;). ::= <sentencia>f;<sentencia>g Esto signi¯ca que un bloque tendr¶a la forma: <sentencia-1>; <sentencia-2>; ... <sentencia-n-1>; <sentencia-n> Existen distintos tipo de sentencias. Formalmente, <sentencia> puede de¯nirse como: <sentencia> ::= <sentencia <sentencia <sentencia <sentencia <sentencia <sentencia <sentencia <sentencia

While-Do> j Repeat-Until> j If-Then-Else> j de asignaci¶on> j de llamada a procedimiento> j de entrada o salida> j compuesta> j vacia>

Veamos en detalle en qu¶e consiste cada una de dichas alternativas: Sentencia While-Do: La sintaxis de esta sentencia es la siguiente: <sentencia While-Do> ::= While do <sentencia> La sentencia While-do corresponde a la estructura Repetir-mientras de nuestro lenguaje de dise~ no. Ejemplo: el trozo de algoritmo que se muestra a la izquierda es equivalente al c¶odigo Pascal que se muestra sobre la derecha: {71{

~ A PROGRAMAS EN PASCAL 5 DE ALGORITMOS EN LENGUAJE DE DISENO

Repetir mientras i > 0 i à i-5

While i>0 do i:=i-5;

Sentencia Repeat-Until: Su sintaxis es la siguiente: <sentencia Repeat-Until> ::= Repeat Until B¶asicamente, la sentencia Repeat-Until hace que se repita la ejecuci¶on de hasta que (until) sea verdadero. En ese punto, se corta la repetici¶on. Esta sentencia no se utiliz¶o generalmente en el lenguaje de dise~no, dado que siempre puede ser sustituida alternativamente por una versi¶on equivalente, escrita utilizando la sentencia Repetir-mientras (ver cap¶³tulo 3 sobre uso de condiciones en algoritmos). Consideremos un ejemplo de uso de la sentencia Repeat-Until: a:=10; Repeat writeln(a); a:=a-1; Until a=0;

Este trozo de c¶odigo muestra en pantalla los n¶ umeros de 10 hasta 1. Cuando a vale 0, se corta el ciclo Repeat-Until. Sentencia If-Then-Else: Su sintaxis es la siguiente: <sentencia If-Then-Else> ::= If Then <Sentencia1> [Else <Sentencia2>] La sentencia If-Then-Else se corresponde a la estructura Si-entonces-si no utilizada en lenguaje de dise~no. Consid¶erese el siguiente ejemplo: If (a=3) and (b>7) Then Begin writeln('Que suerte! a vale 3'); writeln('y b es mayor que 7...') End Else Begin writeln('Que desgracia! a no vale 3'); writeln('o bien b es menor o igual a 7...') End

Sentencia de asignaci¶ on: Su sintaxis es la siguiente: <sentencia asignaci¶on> ::= := <expresi¶on>

{72{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

Su uso es an¶alogo en lenguaje de dise~ no, con la excepci¶on de que se utiliz¶o el s¶³mbolo à en lugar de :=. Consid¶erese el siguiente ejemplo: a := 7; CuadradoDeN := N * N;

Sentencia vac¶³a: Es la sentencia que no contiene nada. Ejemplo: consid¶erese el siguiente trozo de programa en Pascal: Program P(input,output); Begin While 2=2 do; writeln('hola!'); end.

Si se corre este programa, se ver¶a que no termina nunca. En efecto, al ejecutarse la sentencia while do, se veri¯ca que 2 es igual a 2, y se ejecuta la sentencia vac¶³a. Se eval¶ ua nuevamente la condici¶on asociada al While, y se repite el proceso in¯nitamente, ya que la condici¶on siempre se mantiene v¶alida. Para terminar el programa, deber¶a abort¶arselo.12 Sentencia compuesta: La sentencia compuesta corresponde a un conjunto de sentencias, delimitadas por las palabras begin y end. M¶as formalmente: <sentencia compuesta>::= begin end En lenguaje de dise~ no, sol¶³amos escribir bloques de acciones utilizando un corchete sobre el lado izquierdo del algoritmo, que abarcaba todas las sentencias involucradas en una sentencia compuesta. Consid¶erese el siguiente ejemplo: While i>3 do begin writeln(i); writeln(i*i); i:=i-1 End

Repetir mientras i>0 mostrar i mostrar i*i i à i-1

Sentencia de entrada y salida: Todo equipo de c¶omputos posee asociados distintos dispositivos de entrada/salida (en ingl¶es, input/output devices). Los dispositivos de salida son aquellos en los que un programa puede \escribir" o grabar informaci¶on, como por ejemplo un disco, un diskette, una cinta, una impresora o la pantalla de la terminal. Los dispositivos de entrada son aquellos de los cuales un programa puede leer informaci¶on, como por ejemplo un disco, o un teclado. Ciertos dispositivos (ej: teclado) son ¶unicamente dispositivos de entrada; solamente puede leerse informaci¶on de ellos (en el teclado, la computadora \lee" 12 En

una computadora personal esto suele hacerse pulsando Ctrl+C.

{73{

~ A PROGRAMAS EN PASCAL 5 DE ALGORITMOS EN LENGUAJE DE DISENO

cu¶ales han sido las teclas pulsadas). Otros dispositivos son solamente dispositivos de salida (ej: impresora, o pantalla de una terminal). Otros pueden ser dispositivos tanto de entrada como de salida (ej: diskette), ya que puede leerse o escribirse informaci¶on en ellos. El lenguaje Pascal brinda dos tipos de \sentencias", write y read, que permiten ejecutar operaciones de salida y de entrada de datos, respectivamente. En Pascal no suele usarse el t¶ermino \sentencias de entrada y salida", pues la entrada y salida de datos est¶a provista a partir de procedimientos est¶andar provistos por el lenguaje. En t¶erminos rigurosos deber¶iamos referirnos entonces a \procedimiento est¶andar read" y \procedimiento est¶andar write". Abandonaremos de momento esta restricci¶on, para simpli¯car nuestra explicaci¶on. Adem¶as, debemos se~nalar que para los objetivos de esta materia la sentencia write se restringir¶a a \salida por pantalla", y la sentencia read se restringir¶a a \lectura desde el teclado". Posteriormente se ver¶a que ambas sentencias pueden utilizarse para operaciones de entrada y salida de datos a¶ un m¶as complejas. Sentencia Write: La sentencia Write permite mostrar informaci¶on por pantalla. Tiene la forma write (<expresion-write>f,<expresion-write>g) Una <expresi¶on-write> puede ser: ² Una expresi¶on aritm¶etica convencional, como por ejemplo a, a*a, a+(b*3), Cuadrado(3)*7+2. ² Una constante alfanum¶erica. Esto es una secuencia de caracteres, encerrada entre comillas simples ('). Ej: 'hola', 'que tal', etc. Ejemplos de uso de la sentencia write: write('La variable X vale ',X); write(a,' por ',a, ' es igual a ',a*a); write(b*b-c*(a+a),' es un numero');

La sentencia Writeln es similar a Write, excepto que pasa a la pr¶oxima l¶³nea tras realizar la impresi¶on en pantalla. Ejemplo: el trozo de c¶odigo writeln('Hola'); writeln('Que tal');

Imprimir¶a en pantalla Hola Que tal

¶n: write(e 1,e2 ,...e n); es equivalente a escribir Observacio

{74{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

write(e1); write(e2); ... write(en);

Asimismo, writeln(e1,e 2,...en ); es equivalente a escribir write(e1,e2 ,...en); writeln;

Sentencia Read: La sentencia read permite leer informaci¶on desde el teclado. Tiene la siguiente forma: read(f,g) Cuando la computadora debe ejecutar una sentencia read, se realiza la secuencia de acciones siguiente: 1. Espera que el usuario ingrese una secuencia de caracteres cualesquiera mediante el teclado. 2. Cuando pulse Enter, los valores ingresados por el teclado se almacenan en las variables asociadas a la sentencia read. 3. Si hay alg¶un error en los datos ingresados (ej: el read era para leer un n¶umero entero, y se ingres¶o una letra), el programa se abortar¶a autom¶aticamente, y aparecer¶a en pantalla un mensaje de error (en ingl¶es). Ejemplo: supongamos que el programa contiene declaradas dos variables enteras a y b, y la sentencia read(a,b);

Al ejecutarse esta sentencia, Pascal espera a que el usuario ingrese los valores correspondientes a dichas variables. Ejemplo: supongamos que el usuario ingresa 3 5 <Enter>

Al pulsar Enter, Pascal asociar¶a el 3 con la variable a, y el 5 como valor de la variable b. Si, por el contrario, se ingresara 4 xxdj <Enter>

se obtendr¶a un mensaje de error (por ejemplo, Data type mismatch, esto es, inconsistencia de tipo de dato), y el programa se abortar¶a. Esto es debido a que Pascal intent¶o asociar la secuencia xxdj a un n¶ umero entero. La sentencia Readln es similar a Read, excepto que tambi¶en se lee la tecla Enter ingresada por el usuario. Ejemplo: si se escribe

{75{

~ A PROGRAMAS EN PASCAL 5 DE ALGORITMOS EN LENGUAJE DE DISENO readln(a); readln(b);

para ingresar los valores asociados a estas variables, debe escribirse 5 <Enter> 3 <Enter>

¶n: es conveniente combinar Write y Readln cuando se pretende ingresar Recomendacio valores de variables en un programa, a ¯n de clari¯car a qu¶e variable se est¶a haciendo referencia. Siempre es recomendable que, al ingresar un valor, aparezca un cartel indicando cu¶al es la variable que est¶a siendo ingresada. Ejemplo: write('Ingrese el valor de a:'); readln(a); write('Ingrese el valor de b:'); readln(b);

Este trozo de c¶odigo, al ejecutarse, generar¶a la siguiente interacci¶on con el usuario: Ingrese el valor de a: Ingrese el valor de b:

3 <Enter> 5 <Enter>

¶n: read(var1 ,var2 ,...varn) es equivalente a escribir Observacio read(var1 ); read(var2 ); ... read(varn );

Asimismo, readln(var1 ,var2,...varn) es equivalente a escribir read(var1 ,var2,...varn); readln;

Sentencia de llamada a procedimiento: La forma de esta sentencia es la siguiente: <nombre del procedimiento>[(<lista-de-parametros-reales>)] La <lista-de-parametros-reales> est¶a formada por uno o m¶as par¶ametros reales, separados por comas. Cada par¶ametro real se corresponder¶a con un par¶ametro formal en la de¯nici¶on del procedimiento. Ejemplos de llamadas a procedimientos (se supone que los mismos fueron de¯nidos en alguna parte del programa): ImprimirDivisores(10); fMuestra en pantalla los divisores de 10g BorrarPantalla; fBorra la pantallag

Importante: una llamada a procedimiento es una sentencia de Pascal; una invocaci¶on a funci¶on, por el contrario, es parte de una expresi¶on .

{76{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

5.4

Procedimientos y Funciones

En lenguaje de dise~no, utilizamos la noci¶on de primitivas para construir algoritmos complejos. En el lenguaje Pascal existen dos maneras de de¯nir primitivas: los procedimientos y las funciones. 5.4.1

Principales diferencias entre procedimientos y funciones

² Una funci¶on tiene asociado un u ¶nico dato de salida; un procedimiento puede tener asociados m¶ as de un dato de salida, o ning¶ un dato de salida en especial (ej: puede escribirse un procedimiento para hacer que la computadora emita un sonido, o borre la pantalla). El hecho de si \emitir un sonido" es o no un dato de salida podr¶³a ser cuestionable, pero esta es una pregunta de ¶³ndole ¯los¶o¯ca. . . ² A un procedimiento se lo invoca mediante una llamada a procedimiento, la cual constituye una sentencia de Pascal. A una funci¶on se la invoca siempre desde dentro de una expresi¶ on. 5.4.2

Procedimientos

La sintaxis de de¯nici¶on de un procedimiento es la siguiente: <de¯nicion-procedimiento> ::= Procedure [ ( ) ] ; [ <declaracion-constantes> ] [ <declaracion-tipos> ] [ <declaracion-variables> ] [ <de¯nicion-procedimientos-y-funciones> ] Begin End; Como puede apreciarse, la estructura general de un procedimiento es an¶aloga a la de un programa. Un procedimiento P puede tener constantes, tipos y variables asociadas a ¶el, e incluso otros procedimientos y funciones internos al procedimiento P . La primer l¶³nea de la de¯nici¶on anterior corresponde a la cabecera del procedimiento. En la cabecera ¯guran el nombre del procedimiento, y los datos de entrada y datos de salida, encerrados entre par¶entesis (si existen). Cada dato de entrada se indica de manera an¶aloga a una declaraci¶on de variable, especi¯cando el nombre de una variable y su tipo. Los datos de salida se especi¯can de manera similar, pero anteponiendo la palabra Var. Los datos de entrada y salida que aparecen en la cabecera del procedimiento se denominan par¶ametros formales del procedimiento. Veamos algunos ejemplos de procedimientos: {77{

~ A PROGRAMAS EN PASCAL 5 DE ALGORITMOS EN LENGUAJE DE DISENO Procedure ImprimirDivisores(n:integer); fmuestra en pantalla todos los divisores de ng Var Divisor:integer; Begin Divisor:=2; While Divisor <= n div 2 do Begin If n mod Divisor = 0 then writeln(Divisor); Divisor:=Divisor + 1; End End; fprocedimientog Procedure ObtenerCocienteYResto(n,d:integer; VAR Cociente,Resto:integer); fdado un n¶ umero n, y un divisor d, devuelve cociente y resto de dividir n por dg Begin Cociente:=n div d; Resto:=n mod d; End; Procedure ImprimirSaludo; Begin writeln('Hola, que tal, como te va!'); End; Procedure ObtenerCuadrado(n:integer; VAR Cuadrado:integer); Begin Cuadrado:=n * n; End;

El algoritmo asociado a este ¶ultimo procedimiento puede expresarse m¶as claramente utilizando una funci¶on, dado que existe un ¶unico dato de salida. M¶as abajo se indica una versi¶on equivalente de este procedimiento, expresado como funci¶on. Invocaci¶ on de procedimientos Un procedimiento P puede ser invocado desde el programa principal; tambi¶en puede invoc¶arselo desde otro procedimiento (o funci¶on) ubicado al mismo nivel que P . 13 Para invocar a un procedimiento, se indica su nombre y sus par¶ametros reales,14 los que se corresponder¶an uno a uno con los par¶ametros formales. Veamos un ejemplo: supongamos un programa en el que X e Y son variables de tipo integer. Puede entonces incluirse en alg¶ un punto la invocaci¶on ... ObtenerCocienteYResto(7,2,X,Y); ... 13 14

Este concepto se puede analizar en detalle en un libro sobre lengua je Pascal. Llamados actual parameters en ingl¶es. La palabra actual en ingl¶es signi¯ca real o efectivo en castellano.

{78{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

Tras ejecutarse la sentencia de llamada al procedimiento ObtenerCocienteYResto, la variable X contendr¶a el cociente de dividir 7 por 2, y la variable Y contendr¶a el resto de dicha divisi¶on. Las variables X e Y constituyen par¶ametros reales; las variables Cociente y Resto, presentes en la cabecera de la de¯nici¶on de la funci¶on, constituyen par¶ametros formales. 5.4.3

Funciones

La sintaxis de de¯nici¶on de una funci¶on es la siguiente: <de¯nicion-funcion> ::= Function [()]:; [ <declaracion-constantes> ] [ <declaracion-tipos> ] [ <declaracion-variables> ] [ <de¯nicion-procedimientos-y-funciones> ] Begin End; La estructura de una funci¶on es similar a la de un procedimiento. La principal diferencia radica en la cabecera de la funci¶on: la funci¶on tiene (al igual que un procedimiento) cero (o m¶as) datos de entrada. El nombre de la funci¶on constituye el dato de salida de la funci¶on, y es de tipo . Veamos algunos ejemplos: Function Cuadrado(n:integer):integer; Begin ... End;

La funci¶on Cuadrado tiene un dato de entrada n de tipo integer, y el dato de salida (el nombre de la funci¶on) es tambi¶en de tipo integer. Function EsPar(n:integer):boolean; Begin If n mod 2 = 0 then EsPar:= true else EsPar:= false; End;

La funcion EsPar recibe como dato de entrada un entero n, y devuelve como dato de salida true si n es par, y false en caso contrario. Function Pi:real; Begin Pi:=3.14159; End;

{79{

~ A PROGRAMAS EN PASCAL 5 DE ALGORITMOS EN LENGUAJE DE DISENO

La funci¶on Pi no tiene ning¶un dato de entrada, y devuelve el valor constante Pi. A los ¯nes de un uso posterior, la funci¶on Pi se comporta exactamente igual a una de¯nici¶on de constante. Function Potencia(n,i:integer):integer; fDados dos naturales n e i, calcula n elevado a la ig Var p:integer; Begin p:=1; While i>0 do begin p:=p*n; i:=i-1; end; Potencia:=p; End;

La funci¶on Potencia tiene dos datos de entrada de tipo integer, y el dato de salida (nombre de la funci¶on) es de tipo integer. Muy importante 1: en toda funci¶on F, debe asign¶arsele en alg¶ un punto un valor al nombre de la funci¶on, el que se comporta como una variable convencional, de tipo . Si no se realiza ninguna asignaci¶on, el valor devuelto por la funci¶on F ser¶a inde¯nido. Muy importante 2: en toda funci¶on de nombre F, el nombre de la funci¶on podr¶a aparecer como una variable m¶as ¶unicamente del lado izquierdo de una asignaci¶on. >Por qu¶e? Consideremos el ejemplo anterior, en el cual podr¶³a aparentemente ahorrarse el uso de la variable p escribiendo lo siguiente: Function Potencia(n,i:integer):integer; fDados dos naturales n e i, calcula n elevado a la ig Begin Potencia:=1; While i>0 do Begin Potencia:=Potencia*n; i:=i-1; end; End;

Esta funci¶on no est¶a correctamente de¯nida; el compilador detectar¶a un error en la asignaci¶on, ya que asumir¶a que Potencia en el lado derecho corresponde a una invocaci¶on a la funci¶on Potencia, y no a una referencia a una variable. Es necesario en consecuencia utilizar una variable auxiliar p, como en el ejemplo anterior, para obtener el resultado de elevar n a la i, y luego asignar a Potencia el valor de dicha variable p. Invocaci¶ on de funciones

{80{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

A diferencia de las llamadas a procedimiento, las llamadas a funci¶on no constituyen una sentencia en si mismas. Las funciones deben ser invocadas desde dentro de una expresi¶on. Dicha expresi¶on puede aparecer t¶³picamente en las situaciones siguientes: ² A la izquierda dentro de una sentencia de asignaci¶on. ² Dentro de una sentencia Write o Writeln. ² Dentro de una condici¶on. Veamos algunos ejemplos de c¶omo invocar las funciones de¯nidas anteriormente: If (EsPar(n)=true) and (n>10) then writeln(n,' es un numero par mayor de 10'); ... Writeln(Pi,' es un numero irracional); ... write('Ingrese un numero:'); readln(n); write('Ingrese un exponente:'); readln(i); k:=Potencia(n,i); writeln(n,' elevado a la ',i,' es ',k);

Estas ¶ultimas dos sentencias podr¶³an haberse resumido en: writeln(n,' elevado a la ',i,' es ',Potencia(n,i));

{81{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

6

Sugerencias para la impresi¶ on de dibujos en Pascal

La impresi¶on de distintos dibujos en pantalla constituye una interesante motivaci¶on para ejercitar la programaci¶on en Pascal. A t¶³tulo de ejemplo, puede considerarse el siguiente enunciado: Escribir un programa en Pascal para realizar el siguiente dibujo: 1 121 12321 1234321 123454321 1234321 12321 121 1 A continuaci¶on se enumeran distintos elementos o pautas a tener en cuenta al momento de resolver un ejercicio de este tipo. Entre ellos, pueden mencionarse: 1. Analizar primeramente c¶omo est¶a compuesta cada l¶³nea del dibujo que se quiere realizar. Debe tenerse presente que una l¶³nea termina necesariamente con el caracter cr (¯n de l¶³nea), el cual puede imprimirse usando la sentencia Writeln. Analizar tambi¶en los caracteres correspondientes a espacios en blanco (' '), que aparecen entre el comienzo y el ¯nal de cada l¶³nea. A ¯n de poder visualizar todos los caracteres impresos en pantalla, se representar¶an los espacios en blanco como *, y el ¯n de l¶³nea con cr . El dibujo anterior podr¶³a conceptualizarse como se muestra a continuaci¶on: Nro. de L¶³nea 1 2 3 4 5 6 7 8 9

Texto a imprimir ****1 cr ***121 cr **12321 cr *1234321 cr 123454321 cr *1234321 cr **12321 cr ***121 cr ****1 cr

2. Luego puede analizarse qu¶e relaci¶on existe entre los caracteres que componen cada l¶³nea (el n¶umero marcado en it¶alica corresponde a la columna central del dibujo)

{83{

¶ DE DIBUJOS EN PASCAL 6 SUGERENCIAS PARA LA IMPRESION

Nro. de l¶³nea 1: 2: 3: 4: 5: 6: 7:

Debe imprimirse: 4 blancos, 1, cr 3 blancos, 1 2 1 cr 2 blancos, 1 2 3 2 1 cr 1 blanco, 1 2 3 4 3 2 1 cr 0 blanco, 1 2 3 4 5 4 3 2 1 cr 1 blanco, 1 2 3 4 3 2 1 cr etc.

De lo anterior, puede concluirse que: ² Para las primeras 5 l¶³neas, el n¶umero de columna central es un valor que se va incrementando en uno (1,2,3,4,5), y la cantidad de blancos se va decrementando en uno (4,3,2,1,0). Dicho en otros t¶erminos: cuando la columna central tiene asociado el d¶³gito i, hay 5 ¡ i blancos al principio de esa l¶³nea. ² Adem¶as, cuando el d¶³gito de la columna central es i, la l¶³nea asociada est¶a formada por { los n¶umeros de 1 hasta i, seguidos de { los n¶umeros de i ¡ 1 hasta 1. Luego, puede concluirse que dado un valor i, todo el contenido de la l¶³nea estar¶a en funci¶on de ¶el. Para la l¶³nea con columna central i, debe hacerse lo siguiente: ² ² ² ²

Imprimir 5 ¡ i blancos; imprimir los n¶umeros desde 1 hasta i; imprimir los n¶umeros desde i ¡ 1 hasta 1; imprimir cr

Esto vale para las l¶³neas que van de la 1 a la 5. Expresando esto en Pascal, resulta write('':5-i); (*1*) For k:=1 to i do write(k:1); For k:=i-1 downto 1 do write(k:1); writeln;

Para modularizar esto adecuadamente, podr¶³a de¯nirse un procedimiento Linea:

{84{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶oricas { Carlos I. Ches~ n evar

Procedure Linea(i:integer); Var k:integer; Begin write('':5-i); For k:=1 to i do write(k:1); For k:=i-1 downto 1 do write(k:1); writeln; End;

Pero esto vale para cada una de las 5 primeras l¶³neas de texto, y el n¶umero de la columna central es el mismo que el n¶umero de l¶³nea. Luego, para hacer las primeras 5 l¶³neas del dibujo puede escribirse For j := 1 to 5 do Linea(j);

Consideremos ahora las l¶³neas 6 a la 9: aqu¶³ la relaci¶on entre el n¶umero de la columna central y la cantidad de blancos se mantiene (an¶alogo al caso (*1*)). Pero ahora la columna central var¶³a entre 4 y 1. Como las l¶³neas que siguen se van a ubicar autom¶aticamente debajo de las que ya est¶an impresas, para hacerlas simplemente basta con escribir: For j:=4 downto 1 do Linea(j);

En s¶³ntesis, el programa de¯nitivo es el que se muestra a continuaci¶on: Program Dibujo(input,output); Var j:integer; Procedure Linea(i:integer); Var k: Begin write('':5-i); For k:=1 to i do write(k:1); For k:=i-1 downto 1 do write(k:1); writeln; {85{

¶ DE DIBUJOS EN PASCAL 6 SUGERENCIAS PARA LA IMPRESION

End; {Linea} Begin {ppal} For j := 1 to 5 {primer mitad} do Linea(j); For j := 4 downto 1 {segunda mitad} do Linea(j); End. {ppal}

Consideraremos ahora otro ejercicio a modo de ejemplo. La ¯gura a imprimir es ahora la siguiente: 1 2 2 3 3 4 4 5 5 6 6 5 5 4 4 3 3 2 2 1 Se analizar¶a primeramente c¶omo est¶an compuestas las l¶³neas del dibujo, en t¶erminos similares a los usados antes. Nro.L¶³nea 1 2 3 4 5 6 7 8 9 10 11

Debe imprimirse: *****1 cr ****2*2 cr ***3***3 cr **4*****4 cr *5*******5 cr 6*********6 cr *5*******5 cr **4*****4 cr ***3***3 cr ****2*2 cr *****1 cr

Es claro que, aplicando un criterio an¶alogo al anterior, la soluci¶on ideal consistir¶³a en poder de¯nir una l¶³nea gen¶erica del dibujo en funci¶on de alg¶un valor, y luego hacer el dibujo en dos partes, de la siguiente manera: {86{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

For j:=1 to 6 do Linea(...); For j:=5 downto 1 do Linea(...); Veamos c¶omo caracterizar la l¶³nea i¡¶esima. Puede decirse que cuando se genera la l¶³nea k, hay 6¡k espacios en blanco al comienzo de la misma. Considerando a partir de la segunda l¶³nea (pues la primer l¶³nea es un caso especial, ya que tiene un solo d¶³gito), la l¶³nea que tiene asociado el n¶ umero k tendr¶a la forma: write('':6-k); {blancos al comienzo de la linea} (*2*) write(k); {digito a la izquierda} ; write(k); {digito a la derecha} writeln; {escribir cr, y pasar a la proxima linea} Falta caracterizar la expresi¶on \cierta cantidad de espacios en blanco" >Cuantos son? Analic¶emoslo: Nro.L¶³nea

Blancos intermedios:

2 3 4 5 6

1 3 5 7 9

>Cu¶al es la relaci¶on entre el valor del n¶umero asociado a la l¶³nea y la cantidad de blancos intermedios? Puede apreciarse que la cantidad de blancos son impares consecutivos, pero ... >c¶omo asociarlos a un n¶umero dado? Si se considera que en cada una de las l¶³neas (desde la segunda en adelante) siempre aparece una columna central con un blanco, e igual cantidad de blancos a izquierda y derecha de dicha columna, lo anterior puede escribirse como: Nro. L¶³nea 2 3 4 5 6

Col.Izq. Col.Centro 0 1 1 1 2 1 3 1 4 1

Col.Dcha. 0 1 2 3 4

Ahora se aprecia m¶as claramente la relaci¶on entre el n¶ umero y los blancos intermedios. Cuando el n¶ umero es k, la cantidad de blancos intermedios es

{87{

¶ DE DIBUJOS EN PASCAL 6 SUGERENCIAS PARA LA IMPRESION

(k ¡ 2) + blancos a la izquierda de la columna del centro 1 + blanco ocupado por la columna del centro (k ¡ 2) blancos a la derecha de la columna del centro

Realizando la suma algebraica de las expresiones anteriores, esto es equivalente a 2k ¡ 3. En s¶³ntesis: cuando el n¶umero que aparece en la l¶³nea es k, hay 2k ¡ 3 blancos intermedios. Luego el c¶odigo (*2*) puede completarse, y escribirse un un procedimiento L¶ ³nea. Agregamos tambi¶en el caso de que la l¶³nea sea la n¶umero 1, ya que es un \caso especial": simplemente debe imprimirse el d¶³gito 1 con un desplazamiento de 6 ¡ 1 = 5 blancos. Resulta entonces: Procedure Linea(k:integer); Begin If k=1 {si se trata de la linea con numero 1} then Begin Write('':6-k); write(1); end else begin write('':6-k); {blancos al comienzo} write(k); {digito a la izq} write('':2*k-3); {blancos intermedios} write(k); {digito a la derecha} end; writeln; {pasar a la proxima linea} end; {procedure linea} y el programa principal ser¶a: Program Dibujo2(ouput); Var j:integer; Procedure Linea ...(aqui aparece el texto del linea)... Begin For j:=1 to 6 do Linea(j); For j:=5 downto 1 do Linea(j); End. Este ejemplo muestra que no siempre es sencillo encontrar la relaci¶on existente entre los distintos caracteres que componen una l¶³nea. En el caso de los blancos intermedios, la {88{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

relaci¶on entre la cantidad de blancos y el n¶umero no salta a la vista. Haber distinguido entre columna izquierda, central y derecha ayud¶o a visualizar esta relaci¶on. Obs.: no siempre hay una relaci¶on entre los caracteres que componen las l¶³neas. Ejemplo: en el dibujo 1 253 342 no hay una relaci¶on particular entre los blancos y los n¶umeros. (Sin embargo, normalmente las ¯guras que deber¶an representarse en los ejercicios propuestos tienen alguna relaci¶on entre sus caracteres, de modo que se puedan aplicar los conceptos antes vistos) Por u¶ltimo, se analizar¶a un tercer ejemplo. El ejercicio consiste ahora en escribir un procedimiento DibujarFigura, que reciba como par¶ametro un valor K, y que dibuje un \¶arbol" compuesto por K tri¶angulos, de la siguiente manera: 1 121 1 121 12321 ....... 1 121 12321 1234321 ... ... 123..K..321 Ejemplo: si se llama a DibujarFigura con K = 2, deber¶a imprimirse: 1 121 1 121 12321 Deben dibujarse K tri¶angulos, donde {si se analiza el dibujo{ se tiene que:

{89{

¶ DE DIBUJOS EN PASCAL 6 SUGERENCIAS PARA LA IMPRESION

² El primer tri¶angulo tiene 2 l¶³neas ² El segundo tri¶angulo tiene 3 l¶³neas ... ² El K-¶esimo tri¶angulo tiene K + 1 l¶³neas

Adem¶as, todos los tri¶angulos siguen el mismo patr¶on (lo que var¶³a es el n¶umero de l¶³neas de cada uno de ellos). Luego puede escribirse: Procedure DibujarFigura(K:integer); Var NroTri:integer; Begin For NroTri := 1 to K do DibujarTriangulo(NroTri+1); End; El procedimiento DibujarTriangulo recibe como par¶ametro la cantidad de l¶³neas del tri¶angulo. Resulta entonces: Procedure DibujarTriangulo(CantLineas:integer); Var i,j:integer; Begin For i:=1 to CantLineas do Begin write('':9-i); For j:=1 to CantLineas do write(j); For j:=CantLineas-1 downto 1 do write(j); writeln; End; {For} End; {DibujarTriangulo} Obs.: cuando se dibuja la primer l¶³nea, el segundo bucle es equivalente a ejecutar For j:=0 downto 1, y por lo tanto la sentencia write asociada a ¶el no se lleva a cabo. Sugerencias varias La siguiente es una enumeraci¶on de las pautas m¶as relevantes a tener en cuenta cuando se resuelven ejercicios asociados a dibujar ¯guras en pantalla. ² Observar con atenci¶on qu¶e regla de formaci¶on sigue cada l¶³nea del dibujo. Determinar que elementos var¶³an de una l¶³nea a la otra. ² Determinar que elementos est¶an en funci¶on de otros. Ejemplo: en el primer ejemplo, si el n¶umero de la columna central era i, la cantidad de blancos era 5 ¡ i. Analizar cu¶antas variables entran en juego para de¯nir una l¶³nea (en el ejemplo, con una sola variable se de¯n¶³a toda la estructura de la l¶³nea). {90{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

² Determinar cuando un valor crece desde un valor inicial hasta un tope dado, y cuando decrece. El primer caso corresponde a un bucle for..to (en el ejemplo, la primer mitad del dibujo). En el segundo caso, corresponde a un bucle for..downto. ² Analizar si el dibujo tiene partes sim¶etricas. En tal caso, generalmente puede hacerse la primer mitad con un bucle, y la segunda mitad con el mismo bucle pero \en sentido inverso". Tener en cuenta que algunos dibujos poseen una parte \central" (la l¶³nea del medio) que se imprime una sola vez. Ejemplo: en la primer mitad del primer ejemplo, el bucle va de 1 a 5; la segunda mitad es de 4 a 1 (si por el contrario la segunda mitad fuese tambi¶en de 5 a 1, el segundo bucle imprimir¶³a 2 veces la l¶³nea central). Finalmente, algunos ejemplos de dibujos con partes sim¶etricas:

1 1 12 21 123321 12 21 1 1

1 2 2 3 3 2 2 1

1 12 123 1234 123 12 1

5 4 3

/----\ / xx \ / xx \ / xxx xxx \ \ xxx xxx / \ xx / \ xx / \----/ 5

4 3 2 2 1 2 2 3 3 4 4 5 5

1 212 32 23 43 34 32 23 212 1

{91{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

Consideraciones para manejo de Turbo Pascal 7.0

7 7.1

Introducci¶ on

Turbo Pascal 15 es un entorno de programaci¶on para lenguaje Pascal desarrollado para trabajar en cualquier computadora personal (pc) compatible con una IBM Pc.16 El hecho de que Turbo Pascal sea un entorno de programaci¶on signi¯ca que incluye una serie de facilidades que hacen m¶as f¶acil la elaboraci¶on, compilaci¶on y ejecuci¶on de programas en Pascal. En la actualidad, Turbo Pascal es una de los softwares m¶as difundidos para programaci¶on en lenguaje Pascal. Entre las caracter¶³sticas del entorno Turbo Pascal, podemos mencionar las siguientes: ² Facilidades de manejo de pantalla para programar en Pascal. Turbo Pascal incluye un editor de textos, que permite elaborar, compilar y ejecutar programas de manera interactiva. Como ventaja adicional, todas las palabras reservadas de lenguaje Pascal aparecen resaltadas, de manera que pueden distinguirse f¶acilmente del resto del texto. ² Facilidades para desarrollar proyectos de programaci¶on complejos en lenguaje Pascal. Turbo Pascal permite crear m¶odulos (denominados units), que agrupen a varios algoritmos (procedimientos) que se utilizan para un ¯n determinado. Dichos m¶odulos pueden compilarse y almacenarse por separado (ej: un m¶odulo que contenga todos los algoritmos fundamentales para trabajar con fechas), facilitando la elaboraci¶on de programas m¶as complejos. ² Turbo Pascal incluye un depurador (debugger), que permite ejecutar un programa en Pascal paso a paso (sentencia por sentencia), indicando en cada momento cuanto valen las distintas variables, constantes, etc. Esta facilidad permite encontrar r¶apidamente errores l¶ogicos de programaci¶on. Turbo Pascal 7.0 brinda un sistema de ventanas, que facilita considerablemente el desarrollo y ejecuci¶on de programas. El usuario escribe su programa en una ventana de edici¶on (asociada al editor de textos). El programa, al ser ejecutado, muestra sus resultados en la ventana del usuario. El usuario puede alternar entre varias ventanas, ejecutando el programa desde la ventana de edici¶on, y pasar a la ventana del usuario para visualizar los resultados.

7.2

C¶ omo empezar a trabajar en Turbo Pascal

Primeramente, deber¶a cargarse Turbo Pascal, escribiendo la palabra TURBO y pulsando luego la tecla ENTER. Tras un mensaje que indica que Turbo Pascal est¶a siendo cargado, 15 16

Turbo Pascal es marca registrada de Borland, Inc. IBM es la sigla de International Business Machines.

{93{

7 CONSIDERACIONES PARA MANEJO DE TURBO PASCAL 7.0

en la pantalla aparecer¶a una \ventana" (la ventana de edici¶on) con distintos comandos en la parte superior. La primer letra de cada comando estar¶a en video intenso, 17 si se tiene un monitor monocromo; en un monitor color, la primer letra de cada comando aparecer¶a en un color distinto al de las letras restantes. Pulsando la tecla esc, el cursor aparecer¶a autom¶aticamente en la pantalla. En ese momento, puede comenzar a usarse Turbo Pascal como un editor de textos para escribir programas en Pascal. Con la tecla F10, puede pasarse del editor de textos al men¶u de opciones. principal, y retornarse al editor pulsando nuevamente esc. Estando en el editor, puede procederse a escribir un programa en Pascal. Para editar programas en Pascal, Turbo Pascal ofrece adem¶as una serie de comandos para manipular el texto del programa. Los comandos m¶as usados se detallan al ¯nal de este apunte.

7.3

El men¶ u de opciones

Seguidamente se analizar¶an las opciones m¶as importantes que brinda el men¶u de opciones de Turbo Pascal. Se dar¶a especial ¶enfasis a aquellas opciones que son necesarias para desarrollar programas en Pascal, dentro de los requerimientos de la materia \Resoluci¶on de Problemas y Algoritmos". Al lado de cada opci¶on, se detalla su signi¯cado en castellano, as¶³ como la secuencia de teclas que constituye un \atajo" para llegar a dicha opci¶on (si es que dicha secuencia existe). 7.3.1

File (Archivo)

Para acceder a esta opci¶on, debe pulsarse Alt+F 18 desde el editor. Esta opci¶on hace aparecer en pantalla un peque~no men¶u de opciones, en el que se ofrecen distintas alternativas para manipular archivos, tales como cargar archivos ya existentes, crear nuevos archivos, y grabar archivos. Cuando se carga un archivo, ¶este es editado autom¶aticamente. Cuando se termina de escribir un archivo, puede grab¶arselo en cualquier directorio y con cualquier nombre. Algunas opciones del men¶u \File" (y lo mismo vale para otros men¶ues), tienen a su lado el nombre de una tecla. Ej: load tiene asociado F3. Esta tecla constituye un \atajo" para dicho comando (ver glosario). Las principales opciones del menu \File" son: ² Load (cargar; atajo: F3) Permite cargar un archivo cualquiera, indicando su nombre y extensi¶on (ej: PEPE.PAS). Alternativamente, puede escribirse una \m¶ascara" (ej:*.PAS), y en pantalla 17 En

una pantalla de computadora monocrom¶a tica, el texto puede aparecer escrito en video normal, video inverso o video intenso. El video inverso es id¶entico al normal, excepto que se intercambian los colores de fondo y el color de las letras; en video intenso, las letras aparecen en un tono resaltado. 18 ALT+F debe interpretarse como \pulsar simult¶a neamente la tecla ALT y la tecla F". Cabe se~nalar que es conveniente pulsar primero la tecla ALT, y, manteni¶endola pulsada, presionar la tecla F. Las teclas ALT, CTRL y SHIFT son denominadas teclas \mudas", ya que por s¶³ solas no tienen ning¶ u n efecto.

{94{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

se visualizar¶an todos los programas con extensi¶on PAS. Usando las teclas del cursor, puede seleccionarse un programa cualquiera en particular, y pulsando Enter, puede cargarse dicho programa, edit¶andose autom¶aticamente. ² Save (grabar; atajo: F2) Permite grabar en disco r¶³gido o diskette el programa en Pascal que est¶a siendo editado. Si el archivo a¶un no tiene nombre, Turbo Pascal le asigna por defecto el nombre NONAME.PAS. Si se quiere grabar un archivo que a¶un no tiene nombre (es decir, el archivo acaba de ser creado mediante el editor de textos), Turbo Pascal pedir¶a primero que se indique el nombre que se le dar¶a al archivo, y luego proceder¶a a grabarlo. ² New (nuevo) Esta opci¶on borra todo archivo preexistente en el editor de Turbo Pascal, y permite comenzar a escribir un archivo nuevo que a¶un no tiene nombre. Turbo Pascal asigna por defecto el nombre NONAME.PAS al archivo asociado al texto. Cuando se desee grabar el archivo (opci¶on \Save"), Turbo Pascal permitir¶a que el usuario le de al archivo el nombre que desee. ² Save As (grabar como) Permite escribir el archivo que est¶a siendo editado con un nuevo nombre. Ej: si se est¶a usando el archivo PEPE.PAS, puede crearse una \copia" id¶entica de ¶el con nombre JUAN.PAS usando Save As: Turbo Pascal solicitar¶a simplemente el nombre nuevo que se quiere usar (en este caso JUAN.PAS), y grabar¶a el archivo que est¶a en edici¶on bajo dicho nombre. ² Save All (grabar todo) Graba en diskette (o disco r¶³gido) todos los archivos que hayan sido modi¯cados utilizando el editor de textos. Es conveniente utilizar siempre esta opci¶on antes de salir de Turbo Pascal. ² Print (imprimir) Lista por impresora el texto correspondiente al archivo que est¶a siendo editado. ² Dos Shell (pasar al sistema operativo DOS) Permite pasar al Sistema Operativo de la PC, sin que Turbo Pascal se retire de la memoria de la computadora; se puede retornar a Turbo escribiendo exit desde el sistema operativo. ² Exit (salir; atajo: Alt+X) Permite salir de Turbo Pascal, devolviendo el control al sistema operativo. 7.3.2

Edit (editar)

Para acceder a esta opci¶on, debe pulsarse Alt+E. Las principales alternativas que se presentan son: {95{

7 CONSIDERACIONES PARA MANEJO DE TURBO PASCAL 7.0

² Undo (deshacer; atajo: Alt+Backspace): Esta opci¶on permite \retroceder en el tiempo", deshaciendo las acciones de los u¶ltimas teclas pulsadas al usar el editor. ² Redo (rehacer): Rehace la operaci¶on previamente deshecha usando \undo". ² Cut (cortar; atajo: Shift+Delete): Corta el bloque de texto (si existe), el cual desaparece del archivo de texto, y pasa al portapapeles (clipboard). ² Copy (copiar; atajo: Ctrl+Insert) Copia el bloque de texto (si existe) al portapapeles. ² Paste (pegar; atajo: Shift+Insert) Copia el contenido del portapapeles en la posici¶on que ocupa el cursor, dentro del archivo de texto que est¶a siendo editado. ² Clear (borrar; atajo: Ctrl+Delete) Corta el bloque de texto (si existe), el cual desaparece de¯nitivamente del archivo de texto. ² Show Clipboard (mostrar portapapeles) Muestra el contenido del portapapeles. Para retornar al editor de textos, debe pulsarse Alt+F3. 7.3.3

Search (b¶ usqueda)

² Find (hallar; atajo: Ctrl+Q F19) Permite buscar una cadena de caracteres particular dentro del archivo de texto que est¶a siendo editado. Una vez que se accede a esta opci¶on, aparece una caja de di¶alogo, que permite seleccionar diversos par¶ametros, tales como: { Case sensitive (sensitividad a tipo de letra): activando esta opci¶on, en la b¶usqueda se distinguir¶a entre may¶usculas y min¶ usculas. { Whole words only (solo palabras completas): activando esta opci¶on, la b¶usqueda se realizar¶a para palabras completas, y no para subcadenas. { Forward/Backward (hacia adelante/hacia atr¶as): permite seleccionar la direcci¶on en la que se har¶a la b¶ usqueda del texto, dentro del archivo de texto que est¶a siendo editado. ² Replace (reemplazar; atajo Ctrl+Q A) Permite reemplazar una cadena de texto por otra. Esta opci¶on tiene asociada una caja de di¶alogo similar a Find. 19

Esto debe interpretarse como pulsar la combinaci¶o n Ctrl+Q, y luego pulsar la tecla F

{96{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

² Search Again (buscar nuevamente) Permite repetir la ¶ultima operaci¶on efectuada con Find o Replace. 7.3.4

Run

Esta opci¶on permite ejecutar un programa en Pascal, brindando distintas alternativas. Para acceder a ella, debe pulsarse Alt+R desde el editor. Esta opci¶on hace aparecer en pantalla otro men¶u de opciones. Las opciones son: ² Run (correr o ejectuar; atajo: Ctrl+F9) Si no se ha compilado el archivo presente en la ventana de edici¶on, o si el archivo editado ha sido modi¯cado desde la ¶ultima compilaci¶on, esta opci¶on invoca autom¶aticamente al compilador. Luego pasa a ejecutar el programa correspondiente al archivo que est¶a siendo editado. Cuando se ejecuta un programa en Pascal, Turbo Pascal abandona la ventana de edici¶on, y realiza operaciones de entrada/salida (Write/ln o read/ln) sobre una ventana \del usuario". Terminada la ejecuci¶on, Turbo Pascal retorna a la ventana de edici¶on. Nota: si el programa en Pascal ejecutado no incluye ninguna sentencia Readln o Read que obligue al usuario a hacer una entrada de datos, la ejecuci¶on del programa puede ser tan veloz que el usuario tendr¶a la impresi¶on de que <no pas¶o nada! Para solucionar esto se dispone de la combinaci¶on Alt+F5: pulsando estas teclas, puede pasarse de la ventana de edici¶on a la ventana del usuario, y viceversa. ² Program Reset (anulaci¶on de programa; atajo: Ctrl+F2) Esta opci¶on debe utilizarse si se quiere ejecutar un programa, habi¶endose usado previamente el depurador (\debugger"). Esta opci¶on libera la memoria adicional utilizada por el depurador de Turbo Pascal. ² Go to cursor (atajo: F4) El uso de esta opci¶on va m¶as all¶a del alcance de la asignatura. ² Trace into (trazar; atajo: F7) Ejecuta el programa que est¶a siendo editado l¶³nea por l¶³nea. En cada paso, la l¶³nea que est¶a siendo ejecutada aparecer¶a resaltada (en video inverso). Si el usuario quiere ver los resultados parciales de la ejecuci¶on del programa, puede hacerlo utilizando Alt+F5, alternando entre la ventana de edici¶on y la ventana del usuario. Si en el programa ejecutado hay una llamada a procedimiento, se muestran las l¶³neas de c¶odigo del procedimiento a medida que van siendo ejectuadas. ² Step Over (saltar por encima; atajo: F8) Idem a la opci¶on Trace Into, pero con la diferencia que, en caso de ejecutarse una llamada a procedimiento, se la realiza sin mostrar la ejecuci¶on de cada una de las l¶³neas que componen el procedimiento. Permite \saltear" la ejecuci¶on paso a paso de un procedimiento. Esta opci¶on resulta ¶util cuando se quiere evitar seguir paso a paso la ejecuci¶on de un procedimiento cuyo correcto funcionamiento ya ha sido veri¯cado. {97{

7 CONSIDERACIONES PARA MANEJO DE TURBO PASCAL 7.0

7.3.5

Compile (compilar)

Para acceder a esta opci¶on, pulsar Alt+C desde la ventana de edici¶on. Esta opci¶on hace aparecer en pantalla un men¶u con las siguientes opciones. ² Compile (compilar; atajo: Alt+F9) Compila el programa que est¶a en la ventana de edici¶on. Si no hubo errores, aparecer¶a un cartel indicando la cantidad de l¶³neas compiladas y las palabras \Compile successful" (compilaci¶on exitosa). Si hubo al menos un error, Turbo Pascal har¶a que el cursor se posicione en el lugar en que ocurri¶o ese error en el c¶odigo del programa en Pascal. Debe destacarse que, a diferencia de otros compiladores de Pascal, el entorno Turbo Pascal, ni bien encuentra un error en el programa, da por terminada la compilaci¶on, esperando que el usuario corrija el error, y vuelva a compilar. ² Make (atajo: F9) El uso de esta opci¶on va m¶as all¶a del alcance del curso. ² Build El uso de esta opci¶on va m¶as all¶a del alcance del curso. ² Destination (Disk/Memory) (destino disco o memoria) Con esta opci¶on, puede seleccionarse si al compilar debe generarse un c¶odigo ejecutable en el disco (opci¶on Disk), o bien no se desea generar c¶odigo ejecutable, manteniendose dicho c¶odigo en la memoria principal, sin crear ning¶ un archivo de extensi¶on .EXE (opci¶on Memory). Para alternar entre Disk y Memory, debe pulsarse la tecla Enter. Si se est¶a editando un archivo llamado PEPE.PAS, al compilarlo con la opci¶on Compile/Destination Disk, Turbo Pascal generar¶a un archivo PEPE.EXE, el cual podr¶a ejecutarse directamente desde el sistema operativo, sin necesidad de cargar previamente el entorno Turbo Pascal. Si, por el contrario, se utilizara la opci¶on Compile/Destination Memory, el c¶odigo ejecutable permanecer¶a en la memoria principal; cuando se abandone Turbo Pascal, se perder¶a la posibilidad de ejecutar el programa PEPE.PAS desde fuera de Turbo Pascal. ² Primary File El uso de esta opci¶on va m¶as all¶a del alcance del curso. ² Information (informaci¶on) Brinda distintas informaciones sobre el archivo que est¶a en la ventana de edici¶on. 7.3.6

Debug (depurar)

Esta opci¶on tiene asociadas varias opciones adicionales, todas ellas para facilitar la depuraci¶on de programas. Para acceder, debe pulsarse Alt+D desde la ventana de edici¶on. Esta opci¶on hace aparecer en pantalla un men¶ u con distintas opciones.

{98{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

² User Screen (pantalla del usuario; atajo: Alt+F5) Pulsando Alt+F5, puede alternarse entre la pantalla de Turbo Pascal (ventana de edici¶on) y la ventana del usuario (la pantalla en la que se realiza la ejecuci¶on). ² Output (salida) Permite abrir una ventana, en la cual se muestran los contenidos de la ventana del usuario. Esta opci¶on es sumamente conveniente para ver la ejecuci¶on de un programa, sin abandonar Turbo Pascal. ² Call Stack (pila de invocaciones; atajo: Ctrl+F3) Permite abrir una ventana en la cual se muestran los nombres de las funciones y procedimientos que han sido invocados hasta el momento, y que a¶un no han sido conclu¶³dos. Para los conceptos siguientes, es conveniente analizar primero el signi¯cado y utilidad de ciertas expresiones. >Qu¶ e es un \watch"? En Turbo Pascal, se llama \watch" a un indicador de alg¶un estado del programa, comunmente una variable. Un \watch" act¶ ua como un visor, que nos va a permitir ver el contenido de cualquier variable. Los \watchs" son creados por el usuario. A medida que van siendo creados, van a aparecer en la parte inferior de la pantalla, en una ventana peque~ na que tiene el t¶³tulo \Watch". El usuario puede pasar de la ventana de edici¶on a la ventana \Watch" y viceversa usando la tecla F6. Los \watchs" le permiten al usuario hacer una traza din¶amica del programa, pudiendo verse en pantalla los valores de las variables que uno desee a medida que el programa va siendo ejecutado. Normalmente, la ejecuci¶on del programa se har¶a combinando Step Over y Trace Into. >Que es un \breakpoint"? Adem¶as de watches, Turbo Pascal incorpora el concepto de breakpoint para facilitar la depuraci¶on y seguimiento de programas. Un breakpoint es una l¶³nea cualquiera de programa (ej: una una asignaci¶on, un \write"; no se permite que sea una llamada a procedimiento o funci¶on). Marcar un breakpoint es sencillo: se posiciona el cursor sobre la l¶³nea deseada, y se pulsa Ctrl+F8. La l¶³nea se iluminar¶a en video intenso. Si se pulsa Ctrl+F8 de nuevo, la l¶³nea volver¶a a estar en video normal, anul¶andose el breakpoint. Cuando una l¶³nea est¶a \iluminada", es un breakpoint. Esto signi¯ca lo siguiente: cuando se ejecute el programa, se ejecutar¶a todo el c¶odigo hasta llegar al breakpoint. En ese punto, Turbo Pascal se detendr¶a, permitiendo que el usuario {si lo desea{ contin¶ ue la ejecuci¶on usando Step Over o Trace Into. En particular, si el usuario pulsa Ctrl+F9 (Run), el programa continuar¶a su ejecuci¶on normal hasta llegar al pr¶oximo breakpoint. En s¶³ntesis, puede decirse que al llegar a un breakpoint, el usuario puede continuar la ejecuci¶on del programa haciendo Step Over (se ejecuta la pr¶oxima l¶³nea, sin \entrar" al c¶odigo de los procedimientos), Trace Into (ejecuta la pr¶oxima l¶³nea, inclu¶³do el c¶odigo asociado a los procedimientos) o Run (Ctrl+F9) (se ejecuta hasta el proximo breakpoint, y Turbo Pascal vuelve a detenerse). Los breakpoints tienen sentido u¶til s¶olo si se los usa combinados con watchs, para ver los valores que toman las variables. Ahora ya puede analizarse en detalle el signi¯cado de otras opciones en el men¶ u Debug. {99{

7 CONSIDERACIONES PARA MANEJO DE TURBO PASCAL 7.0

² Breakpoints (puntos de corte): Muestra una caja de di¶alogo, a trav¶es de la cual pueden visualizarse todos los breakpoints activos, pudi¶endoselos borrar, modi¯car, etc. ² Watch (punto de observaci¶on o vigilancia): Abre una ventana de watches. En la parte inferior de la pantalla, aparecen distintos comandos para agregar, borrar y visualizar watches. Dicha ventana puede anularse con Alt+F3. ² Add Watch (a~ nadir watch; atajo: Ctrl+F7) Permite a~ nadir un nuevo watch, el cual pasar¶a a incorporarse a la ventana de watches. 7.3.7

Options

Esta opci¶on incluye distintas caracter¶³sticas de Turbo Pascal que pueden ser de¯nidas por el usuario. Para acceder, pulsar Alt+O desde la ventana de edici¶on. Las principales opciones que aparecen son: ² Compiler (compilador) Permite de¯nir caracter¶³sticas del compilador. Ej: Chequeo de rangos, evaluaci¶on booleana con corto circuito,etc. ² Environment (entorno) Permite de¯nir caracter¶³sticas del entorno de trabajo Turbo Pascal. Ej: si hay archivos de resguardo (back-up ¯les), cu¶al es el tama~no del tabulador, etc. ² Directories (directorios) Permite de¯nir directorios por separado para casos particulares. Ej: cu¶al es el directorio donde se guardar¶an los archivos .EXE generados a partir de la compilaci¶on,etc. ² Save Options (grabar opciones) Permite grabar todas las caracter¶³sticas que el usuario de¯ne en el men¶ u \Options" bajo un nombre de archivo. Ej: TURBO.TP. ² Retrieve Options (recuperar opciones) Permite cargar un archivo de caracter¶³sticas de¯nido previamente que se haya grabado con la opci¶on Save Options. Esta opci¶on con¯gura a Turbo Pascal con las caracter¶³sticas de¯nidas en dicho archivo. 7.3.8

Window (Ventana)

Todos los conceptos que se han mencionado anteriormente tienen un elemento com¶un: se he hecho referencia a la ventana de edici¶on, ventana del usuario, ventana de watches, etc. El hecho de que Turbo Pascal 7.0 sea un entorno basado en ventanas facilita mucho su manejo, ya que este concepto uni¯ca muchos aspectos de trabajo. B¶asicamente, la opci¶on {100{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

Window brinda al usuario distintos comandos para manipular ventanas: abrir, cerrar o mover ventanas, pasar a otra ventana, listar las ventanas abiertas, etc. Dos teclas particularmente importantes son F6 (pasa a la pr¶oxima ventana), y Alt+F3 (cierra la ventana en curso). ² Tile (azulejar): Muestra todas las ventanas abiertas en pantalla, en estilo \tile" (azulejo). Las ventanas se muestran como si fuesen azulejos colocados sobre una pared. ² Cascade (cascada): Idem Tile, pero utilizando el estilo \cascade" (cascada). Las ventanas se muestran de manera tal que se ve la parte superior de todas las ventanas, mostr¶andose ¶unicamente en su totalidad la ¶ultima ventana activa. ² Close All (cerrar todo): Cierra todas las ventanas abiertas. ² Size/Move (tama~ no/mover; atajo: Ctrl+F5) Permite cambiar el tama~ no de la ventana activa, utilizando las teclas del cursor. ² Zoom (ampliaci¶on; atajo: F5): Agranda el tama~no de la ventana activa. ² Next (pr¶oximo; atajo: F6): Muestra la pr¶oxima ventana, de aquellas ventanas que hayan sido abiertas. ² Previous (previo; atajo: Ctrl+F6): Idem Next, pero para la ventana previa. ² Close (cerrar; atajo: Alt+F3): Cierra la ventana en curso. ² List (listar): Lista todas las ventanas abiertas. 7.3.9

Help

Esta opci¶on brinda ayuda sobre distintos t¶opicos de Turbo Pascal. Cabe destacar que, al escribir un programa, puede solicitarse ayuda sobre el lenguaje Pascal, pulsando Ctrl+F1. Ej: posicion¶andose sobre la palabra IF, y pulsando Ctrl+F1, aparecer¶a en pantalla una explicaci¶on de la sentencia If-Then-Else. El texto de ayuda aparece en idioma ingl¶es.

{101{

7 CONSIDERACIONES PARA MANEJO DE TURBO PASCAL 7.0

7.4 7.4.1

Teclas utilizadas en Turbo Pascal Teclas fundamentales

a) Parte central del teclado ² ESC: permite cancelar cualquier opci¶on de un men¶u. Pulsando esta tecla se abandona el men¶ u principal, y se pasa al editor de textos. ² SHIFT: (identi¯cada a veces con una °echa hacia arriba). Hay dos teclas SHIFT, una a cada lado del teclado. Esta tecla es similar a la tecla de may¶ usculas en una m¶aquina de escribir. Permite obtener letras may¶ usuclas. Combinada con otras teclas especiales (ej: F1, Delete, etc.), produce distintos resultados. ² CAPS LOCK: Pulsando esta tecla, todo texto que se escriba de ah¶³ en adelante aparecer¶a en may¶usculas. Para desactivar las may¶usuclas, basta pulsar CAPS LOCK nuevamente. ² CTRL: Hay dos teclas CTRL, una a cada lado del teclado. Esta tecla no cumple ninguna funci¶on en s¶³ misma, sino que es de utilidad cuando se la combina con otras teclas especiales. ² ALT: Idem CTRL. ² ENTER: (tambi¶en llamada RETURN) Esta tecla est¶a situada sobre la derecha del teclado, y suele ser la de mayor tama~no. Se utiliza para pasar a la pr¶oxima l¶³nea, al escribir un texto, o tambi¶en para con¯rmar la ejecuci¶on de una opci¶on de un men¶u. ² BACKSPACE: (caracterizada con una °echa hacia la izquierda). Esta tecla desplaza el cursor un lugar a la izquierda, borrando el caracter sobre el cual se hallaba ubicado el cursor. ² F1..F12: estas teclas suelen denominarse \teclas de funci¶on". En Turbo Pascal, algunas de ellas tienen asignado un ¯n espec¶³¯co (ej: F1 permite obtener ayuda). A veces puede utiliz¶arselas en combinaci¶on con CTRL o ALT para obtener nuevos comandos. b) Parte lateral del teclado ² TECLAS DEL CURSOR: Caracterizadas por cuatro °echas, en cuatro direcciones distintas: arriba, abajo, derecha e izquierda. Permiten desplazar el cursor en la pantalla en cualquiera de esas cuatro direcciones, pulsando la tecla respectiva.

{102{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

² INSERT (o insertar): permite pasar de modo \insertar" a modo \sobreescribir" al utilizar el editor de textos de Turbo Pascal. En el modo \insertar", cada caracter escrito desplaza a los caracteres situados a derecha del cursor; en el modo \sobreescritura", cada caracter escrito tapa a los caracteres a la derecha del cursor. ² DELETE (o suprimir): permite borrar el caracter sobre el cual se encuentra posicionado el cursor, sin desplazarlo. ² HOME (o inicio): Dentro del editor de textos, desplaza el cursor al comienzo de la l¶³nea en curso. ² END (o ¯n): Dentro del editor de textos, desplaza al cursor al ¯nal de la l¶³nea en curso. ² PAGE UP (o ReP¶ag): Dentro del editor de textos, desplaza el texto que se muestra en pantalla cierto n¶ umero de l¶³neas hacia \arriba", permitiendo desplazarse hacia el principio del texto. ² PAGE DOWN (o AvP¶ag): Idem PAGE UP, pero permitiendo desplazarse hacia el ¯nal del texto. 7.4.2

Teclas m¶ as utilizadas dentro del editor

A continuaci¶on se describen las combinaciones de teclas m¶as usadas para trabajar con el editor incorporado a Turbo Pascal. Se recomienda a los alumnos familiarizarse con el uso de dichas teclas, para facilitar la elaboraci¶on de programas en la computadora. Comandos de inserci¶on/borrado Modo Insert on/o® Ctrl+V o Insert Insertar nueva l¶³nea Ctrl+N Borrar l¶³nea en la que se halla el cursor Ctrl+Y Borrar hasta ¯n l¶³nea Ctrl+Q Y Borrar caracter a izquierda del cursor Ctrl+H o Backspace Borrar caracter en posici¶on cursor Ctrl+G o Delete Borrar palabra a derecha del cursor Ctrl+T Borrar bloque de texto Ctrl+K Y

{103{

7 CONSIDERACIONES PARA MANEJO DE TURBO PASCAL 7.0

Comandos de manejo de bloques Marcar comienzo bloque Marcar ¯n de bloque Copiar bloque Mover bloque Borrar bloque Leer bloque de disco Escribir bloque a disco Esconder/mostrar bloque Imprimir bloque Indententar bloque Desindentar bloque

Ctrl+K Ctrl+K Ctrl+K Ctrl+K Ctrl+K Ctrl+K Ctrl+K Ctrl+K Ctrl+K Ctrl+K Ctrl+K

B K C V Y R W H P I U

Comandos para hallar y reemplazar palabras Hallar Ctrl+Q F Hallar y reemplazar Ctrl+Q A Repetir hallar o reemplazar Ctrl+L

7.5

Glosario

A continuaci¶on se detalla el signi¯cado de algunos de los t¶erminos m¶as usuales en computaci¶on, utilizados en la materia \Resoluci¶on de Problemas y Algoritmos". Cabe se~ nalar que las descripciones que se dan pueden no ser absolutamente precisas; se pretende, con ellas, brindar un panorama general a aquellos alumnos que han tenido una experiencia escasa o nula con el manejo de computadoras. Algunos t¶erminos referidos a sistemas multiusuarios (ej: terminal, etc.) se presentan de manera simpli¯cada, para facilitar su comprensi¶on para el alumno. Abortar (ingl¶es \abort"): anular la ejecuci¶on normal de un programa, ya sea presionando ciertas teclas, o bien ingresando un comando particular. Aceptar: ant¶onimo de cancelar. Suele con¯rmarse la aceptaci¶on de una opci¶on utilizando la tecla ENTER. Archivo (ingl¶es \¯le"): Uno de los conceptos m¶as importantes en las ciencias de la computaci¶on. Un archivo es, b¶asicamente, un conjunto de datos identi¯cados por un nombre. Los archivos se guardan en dispositivos de almacenamiento, tales como diskettes, discos, etc. Para una computadora, un programa en Pascal, una carta, etc. son archivos. Los archivos m¶as comunes que se manejar¶an durante la materia ser¶an los programas en Pascal que uno mismo realiza. A ¯n de poder guardar un programa en diskette (o disco r¶³gido), deber¶a \grab¶arselo" como un archivo. Las acciones b¶asicas que se hacen sobre los archivos son grabar (save), borrar (delete), cargar (load) y modi¯car. Archivo de texto (ingl¶es \text ¯le"): se llama as¶³ a todo archivo formado por secuencias de letras (o m¶as gen¶ericamente, de caracteres) que forman un texto en la pantalla de la com{104{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

putadora. Un programa en Pascal, al grabarse en un medio de almacenamiento secundario (disco o diskette) se graba como un archivo de texto. Atajos (ingl¶es \shortcuts"; tambi¶en \hot keys"): Un atajo para un comando es una tecla particular (o secuencia de teclas), que evita tener que utilizar otra secuencia m¶as larga (que involucra m¶as teclas) para ejecutar dicho comando. Ej: para cargar un archivo en Turbo Pascal, debe hacerse ALT+F, y luego ir a la opci¶on \Load", y pulsar Enter. Todos estos pasos pueden resumirse con pulsar solamente la tecla F3. Dicho de otra manera, F3 es un atajo para la opci¶on \Load". Bloque de texto: se llama as¶³ a cualquier porci¶on del texto de un archivo de texto. El usuario es quien de¯ne d¶onde comienza y d¶onde termina un bloque de texto. En Turbo Pascal, s¶olo puede existir un ¶unico bloque de texto activo. Un bloque de texto puede abarcar una o m¶as l¶³neas. Para de¯nir un bloque de texto, Turbo Pascal cuenta con dos comandos: CTRL+K y B (comienza bloque) y CTRL+K E (¯naliza bloque). Tras marcar el comienzo y ¯n de un bloque de texto, dicho bloque aparecer¶a resaltado en la pantalla. Posteriormente, el editor de Turbo Pascal brinda distintos comandos que permiten manipular dicho bloque de texto (copiar, borrar, etc). Sobre un bloque de texto, pueden efectuarse distintas operaciones, tales como: ² Cortar y Pegar (ingl¶es \cut" y \paste"): estos t¶erminos son usuales en computaci¶on para describir operaciones sobre archivos de texto. Al \cortar" un bloque (o trozo) de texto, el bloque en cuesti¶on desaparece del archivo de texto que est¶a siendo editado, y se almacena en un ¶area especial llamada \portapapeles" (clipboard). Al \pegar" un bloque de texto, el editor toma el contenido del portapapeles, y lo agrega al archivo de texto, en el lugar en que se encuentre posicionado el cursor. ² \Copiar" y \Borrar" (ingl¶es \copy" y \clear"): copiar un bloque de texto es una acci¶on similar a \pegar": el bloque de texto pasa al portapapeles, pero no desaparece del archivo de texto editado. Borrar un bloque de texto es una acci¶on similar a \cortar": el bloque de texto desaparece del archivo de texto, pero no se almacena en el portapapeles. Al borrar un bloque de texto, su contenido se pierde de¯nitivamente. ² \Mover" un bloque de texto: se denomina as¶³ a la acci¶on de trasladar un bloque de texto de un lugar a otro, dentro de un mismo archivo. Para mover un bloque de texto en Turbo Pascal, debe primeramente delimitarse el comienzo y ¯n del bloque (utilizando Ctrl+K B y Ctrl+K K), posicionar luego el cursor en el punto al cual se desea trasladar el bloque de texto, y pulsar Ctrl+K V. Borrar (en ingl¶es \delete"): Borrar un archivo del diskette (o disco r¶³gido). Un archivo que ha sido borrado desaparece del medio de almacenamiento que lo conten¶³a, y no podr¶a ser cargado en el futuro. Cadena (ingl¶es \string"): secuencia de caracteres. Caja de di¶alogo (ingl¶es \dialog box"): se llama as¶³ a un peque~ no recuadro que aparece en pantalla, que permite seleccionar par¶ametros adicionales para una opci¶on determinada. {105{

7 CONSIDERACIONES PARA MANEJO DE TURBO PASCAL 7.0

Ej: al usar la opci¶on Edit/Find, aparece una caja de di¶alogo, en la que puede indicarse par¶ametros tales como direcci¶on de la b¶ usqueda (hacia atr¶as o hacia adelante), punto de comienzo de la b¶usqueda, etc. Las cajas de di¶alogo son comunes en los programas que tienen sistema de ventanas. Cancelar (ingl¶es \cancel"): decidir que no quiere ejecutarse una opci¶on particular de un men¶u. Ej: si en un programa aparece la pregunta \>Quiere seguir? (s/n)", pulsando la tecla \n" se cancela dicha opci¶on. Cargar (en ingl¶es \load"): Recuperar un archivo del diskette (o disco r¶³gido), y pasarlo a la memoria principal de la computadora. C¶ odigo ejecutable: secuencia de sentencias que pueden ser entendidas directamente por la computadora. El c¶odigo ejectuable es el resultado de la compilaci¶on de un programa. Compilador (ingl¶es \compiler"): programa que recibe como dato de entrada un programa escrito en un lenguaje de programaci¶on (ej: Pascal o Fortran), y devuelve un c¶odigo ejecutable, que puede ser ejecutado por una computadora. Cuenta: los sistemas multiusuarios constan de una computadora central y varias terminales. Para que un usuario pueda utilizar el sistema, debe disponer de una cuenta. Este concepto es similar en cierto sentido al concepto de cuenta bancaria. Una cuenta consiste simplemente en un espacio reservado por la computadora para el usuario, a ¯n de que ¶este pueda utilizar el sistema, almacenar y ejecutar sus propios programas, etc. Las cuentas son administradas (creadas, destruidas, etc) por personal especializado del C¶entro de C¶omputos. Un usuario puede acceder a su cuenta desde cualquier terminal. Para acceder a una cuenta, el usuario debe indicar el nombre de su cuenta (o login), y una palabra clave (password), que solamente ¶el conoce. Esto ¶ultimo impide que cualquiera pueda acceder a los datos de una cuenta particular, a excepci¶on del usuario mismo. Directorio (ingl¶es \directory"): Un medio de almacenamiento como el diskette o disco r¶³gido puede organizarse en directorios, para llevar un mejor control de d¶onde se encuentra cada archivo. Si se piensa a un diskette como un armario (que guarda informaci¶on a trav¶es de archivos), un directorio constituye un caj¶on dentro de ese armario. La idea es que un directorio es una \divisi¶on", en la que se agrupan varios archivos que tienen alg¶un elemento en com¶ un. Ej: si en un diskette hay varios cientos de archivos, y algunos de ellos son cartas, otros programas en Pascal y otros juegos, ser¶³a conveniente contar con tres directorios: CARTAS, PROGPAS y JUEGOS. editar (ingl¶es \edit"): este verbo se utiliza con el signi¯cado de "cargar un archivo de texto mediante un editor de textos". Cuando se edita un archivo, se est¶a en condiciones de modi¯carlo desde el editor de textos, a trav¶es del teclado. Editor de textos: nombre gen¶erico que se da a un programa utilitario que permite escribir textos en la computadora, y grabarlos como archivos de texto. Asimismo, un editor permite cargar archivos de texto ya existentes, modi¯carlos y grabarlos nuevamente. Un editor de textos es indispensable para poder escribir adecuadamente programas en Pascal, ya que ¶estos u¶ltimos se almacenan como archivos de texto. Grabar (o Salvar) (en ingl¶es \save"): Almacenar un archivo en diskette o disco r¶³gido. {106{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

Login: nombre de la cuenta que corresponde a un usuario. Ver Cuenta. Tambi¶en se llama as¶³ a la acci¶on de acceder a una cuenta. Logout: acci¶on de abandonar la cuenta. Normalmente, un usuario puede hacer un \logout" utilizando la palabra exit. Memoria: la memoria de la computadora es el lugar donde se almacena informaci¶on. La memoria principal (o memoria RAM) es aquella en la que la computadora almacena los programas que est¶an siendo ejecutados. La memoria secundaria corresponde a medios de almacenamiento como diskettes o disco r¶³gido. Men¶ u: conjunto de opciones que aparecen en un programa, y entre las que el usuario puede optar. MS-DOS: acr¶onimo de \Microsoft Disk Operating System". Uno de los sistemas operativos monousuarios m¶as difundidos para uso en computadoras personales (PCs). Nombre de archivo (ingl¶es \¯lename"): el nombre completo de un archivo suele estar formado por dos partes: una secuencia de hasta 8 letras (tambi¶en llamado simplemente \nombre") y otra secuencia de hasta 3 letras (o \extensi¶on"), separadas entre s¶³ por un punto (\."). La extensi¶on suele caracterizar el tipo o clase de archivo al cual est¶a asociado el \nombre". Ej: PAS corresponde a archivos en Pascal; BAS corresponde a archivos en lenguaje Basic. Ej: nombres de archivo v¶alidos son EJEM.PAS, RULETA.BAS, etc. Por defecto (ingl¶es \by default"): Esta expresi¶on signi¯ca ante la falta de mayor informaci¶on". Muchas opciones de Turbo Pascal requieren que el usuario brinde cierta informaci¶on (ej: al grabar un programa, ser¶³a natural que se indique que nombre se quiere dar a dicho programa). Sin embargo, la ausencia de dicha informaci¶on hace que Turbo Pascal asuma que el nombre con que se grabar¶a el programa es NONAME.PAS. Decimos entonces que, por defecto, el nombre de un programa es NONAME.PAS (es decir, el nombre ser¶a NONAME.PAS a menos que el usuario indique lo contrario). Password: palabra clave, conocida u¶nicamente por un usuario particular, que le permite acceder al uso de una cuenta (en un sistema multiusuario). \Salir" de un programa (ingl¶es \exit"): est¶a acci¶on consiste en abandonar el programa que ha sido cargado en la memoria principal de la computadora, y retornar el control al sistema operativo. Sistema monousuario: se llama as¶³ a todo equipo de c¶omputos que permite ¶unicamente el trabajo de una persona por vez. El concepto opuesto es sistema multiusuario. Una computadora personal (PC) es un ejemplo t¶³pico de un sistema monousuario. Sistema multiusuario: se llama as¶³ a todo equipo de c¶omputos que permite trabajar simult¶aneamente a varias personas, mediante terminales. Sistema Operativo (ingl¶es \operating system"): conjunto de programas encargados de controlar y administrar las funciones b¶asicas de la computadora, tales como: detectar que teclas est¶an siendo pulsadas, cargar programas desde diskettera o disco r¶³gido, etc. Una de las principales acciones que puede ejecutar el sistema operativo es cargar un programa cualquiera en la memoria principal de la computadora, y proceder a ejecutarlo. Para esto, {107{

7 CONSIDERACIONES PARA MANEJO DE TURBO PASCAL 7.0

suele ser su¯ciente indicar el nombre del programa que se desea ejecutar. Ej: al encender una PC, el sistema operativo tiene el control. Al escribir TURBO, el sistema operativo est¶a recibiendo la instrucci¶on de cargar Turbo Pascal, y ejecutarlo. Subcadena: parte de una cadena, que constituye una cadena en s¶³ misma. Ej: \as" es una subcadena de \casa". Terminal: conjunto de teclado y monitor, que puede conectarse a una computadora central. A diferencia de una PC, una terminal no es una computadora en s¶³ misma. Simplemente, permite acceder a una computadora central, la cual permanece invisible al usuario. UNIX20: nombre de un sistema operativo multiusuario, de uso ampliamente difundido. Usuario (ingl¶es \user"): persona que trabaja con la computadora. Ventana (ingl¶es \window"): se llama as¶³ a un recuadro en la pantalla de la computadora, que cumple la funci¶on de una mini-pantalla. Las ventanas se popularizaron a trav¶es del sistema operativo Windows,21 el cual se basa totalmente en uso de ventanas. Cuando se \abre" una ventana, pasa a existir una peque~ na pantalla virtual dentro del monitor. De esta manera, teniendo a su disposici¶on varias ventanas, el usuario puede trabajar con distintos programas o archivos simult¶aneamente con un ¶unico monitor. Las ventanas que no desean utilizarse pueden \cerrarse". Las ventanas tienen una longitud y altura que pueden ser modi¯cadas por el usuario. Windows 95: sistema operativo para computadoras personales, que actualmente prevalece por sobre el sistema operativo MS-DOS. Surgido en 1995, este sistema operativo constituye una evoluci¶on de su predecesor Windows 3.1.

20 21

UNIX es marca reservada de Bell Laboratories, Inc. Windows es una marca reservada de Microsoft Corporation

{108{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

8

Ap¶ endice: el ingl¶ es en computaci¶ on y su incidencia en nuestro idioma

Es indudable que el idioma ingl¶es juega hoy en d¶³a un rol fundamental en diversos ¶ambitos, y quiz¶as las ciencias de la computaci¶on sean el ¶area en la cual se hace evidente su supremac¶³a como veh¶³culo com¶un de comunicaci¶on. El ingl¶es est¶a presente en pr¶acticamente todos los lenguajes de programaci¶on, en gran cantidad de t¶erminos t¶ecnicos, en libros de texto y revistas especializadas, y en la terminolog¶³a cient¶³¯ca de vanguardia utilizada en ¶areas tales como inteligencia arti¯cial, redes y teleprocesamiento, etc. Sin embargo, tambi¶en es innegable que, en calidad de hispanohablantes, los profesionales argentinos del ¶area de ciencias de la computaci¶on debemos comunicarnos mayormente con distintos tipos de usuarios, muchos de ellos con conocimiento escaso o nulo acerca de t¶erminos t¶ecnicos o de programaci¶on, pero con un denominador com¶un: la capacidad de comprender el idioma castellano. En tal sentido, el manejo de literatura t¶ecnica casi exclusivamente en ingl¶es provoca una suerte de \deformaci¶on profesional": muchos t¶erminos en ingl¶es se adaptan literalmente al castellano, en una versi¶on supuestamente equivalente. Por desgracia, esa equivalencia a menudo no existe; ciertas palabras en ingl¶es se escriben de manera id¶entica en castellano, pero con distinto signi¯cado (ej.: los adjetivos en ingl¶es actual y eventual). En consecuencia, muchas veces llegan a elaborarse frases en castellano utilizando palabras que resultan equ¶³vocas o ambiguas, ya que para interpretarlas correctamente debe conocerse su signi¯cado en ingl¶es. Lo dicho anteriormente no pretende constituir un argumento para sustituir cada t¶ermino en ingl¶es por uno equivalente en castellano, suprimiendo la jerga t¶ecnica utilizada comunmente. No obstante, es preocupante observar la pereza con la que se trata ciertas veces el uso correcto del castellano, como si acaso todos aquellos errores idiom¶aticos que se semejan a pautas de redacci¶on en ingl¶es constituyesen una mera \cuesti¶on de estilo", o resultasen m¶as \tolerables". A modo de ejemplo, puede mencionarse el gran n¶ umero de veces en que se obvian acentos, o no se utilizan los dos s¶³mbolos de interrogaci¶on o de admiraci¶on. Sin intenci¶on de ponti¯car al respecto, ni adoptar una postura xen¶ofoba, entendemos que el idioma castellano debe preservarse y cultivarse como tal, ya que constituye nuestra herramienta b¶asica de comunicaci¶on. Es imprescindible educar y desarrollar la capacidad de redacci¶on de textos en castellano; el estilo utilizado podr¶a adaptarse seg¶un las circunstancias, pero no debe deformarse al punto que se torne ininteligible \a menos que se lo interprete en ingl¶es". A trav¶es de estas p¶aginas se intenta dar una modesta contribuci¶on al problema antes mencionado. En primer lugar, se menciona una serie de palabras cuestionables, utilizadas muchas veces en libros de texto o a nivel coloquial como traducci¶on de ciertos t¶erminos en ingl¶es, pero cuyo signi¯cado es ambiguo, incorrecto estil¶³sticamente o equivocado. En cada caso se menciona la palabra cuestionable en castellano, el t¶ermino en ingl¶es a partir del cual fue traducida o derivada dicha palabra, el problema asociado a la traducci¶on, sugiri¶endose ¯nalmente algunas traducciones posibles. Se mencionan tambi¶en ciertas cuestiones {109{

¶ ¶ EN COMPUTACION ¶ Y SU INCIDENCIA EN NUESTRO 8 APENDICE: EL INGLES IDIOMA

estil¶³sticas y referentes a la tipograf¶³a en castellano, que suelen ser muchas veces confundidas con aquellas empleadas en textos en ingl¶es. En el texto que sigue, en aquellos casos en que se considere necesario destacarlo, las palabras en ingl¶es estar¶an en tipograf¶³a it¶alica, y las palabras en castellano aparecer¶an en tipograf¶³a sans-serif.

8.1

Palabras cuestionables

Palabra cuestionable en castellano: actual T¶ ermino original en ingl¶ es: actual Problema: En ingl¶es, actual signi¯ca \efectivo", \concreto", \que existe como un hecho real". Ej: There is a big di®erence between the opinion polls and the actual election results (Hay una gran diferencia entre las encuestas de opini¶on y los resultados concretos de la elecci¶on); We must consider both potential and actual problems (Debemos considerar tanto los problemas potenciales como los problemas realmente existentes). Traducci¶ on sugerida: efectivo, real, concreto. Palabra cuestionable en castellano: actualmente T¶ ermino original en ingl¶ es: actually Problema: El adverbio actually signi¯ca \en realidad" o \de hecho". Ej: She says it's a good ¯lm, though she hasn't actually seen it (Ella dice que la pel¶³cula es buena, aunque en realidad ella no la vio). En conversaciones, actually se usa para dar un tono amable a una correcci¶on hecha a otra persona, o bien para expresar disconformidad. Ej: una persona le dice a otra Happy Birthday!, y la otra contesta Well, actually my birthday was yesterday. Traducci¶ on sugerida: en realidad, de hecho, en rigor de verdad. Palabra cuestionable en castellano: aplicar T¶ ermino original en ingl¶ es: to apply Problema: El verbo ingl¶es to apply signi¯ca, entre otras cosas, \solicitar algo, especialmente de manera o¯cial y por escrito". Ej: I've applied for a scholarship (He pedido/solicitado una beca). El verbo espa~nol \aplicar" no posee este signi¯cado. Otra expresi¶on derivada de to apply es application form, es decir, una \solicitud" (A qu¶e equipo de f¶utbol apoya? o, m¶as informalmente, >De qu¶e cuadro sos?. La oraci¶on My theory is supported by this theorem

{110{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

puede interpretarse como mi teor¶³a se sustenta en este teorema. Traducci¶ on sugerida: Entre otros, pueden considerarse apoyar(se), ¯nanciar, alentar, sustentar(se) en, y basarse en. Palabra cuestionable en castellano: eventual , eventualmente T¶ ermino original en ingl¶ es: eventual, eventually Problema: En castellano, la palabra \eventual" signi¯ca \sujeto a cualquier evento o contingencia". En ingl¶es, el signi¯cado es totalmente distinto: eventual signi¯ca \que ocurre a la larga como resultado ¯nal". Ej: The new computer is expensive, but the eventual savings it will bring are very signi¯cant (La nueva computadora es cara, pero, a la larga, representar¶a un ahorro muy signi¯cativo). Algo similar ocurre con \eventualmente", que en castellano signi¯ca \incierta o casualmente"; en ingl¶es, eventually se corresponde con expresiones tales como at last, in the end (es decir, \a la larga"). Ej: After many attempts she eventually managed to pass the exam (Despu¶es de muchos intentos, ella pudo ¯nalmente aprobar el examen). Traducci¶ on sugerida: a la larga; ¯nalmente Palabra cuestionable en castellano: procedural T¶ ermino original en ingl¶ es: procedural Problema: La palabra \procedural" no existe en castellano, ni est¶a asociada en modo alguno a la idea de \procedimiento". El adjetivo procedural deriva de procedure; en castellano, la derivaci¶o n resultante a partir de \procedimiento" ser¶³a, en todo caso, \procedimental". Traducci¶ on sugerida: procedimental. Palabra cuestionable en castellano: discutir T¶ ermino original en ingl¶ es: to discuss Problema: En ingl¶es, to discuss signi¯ca \considerar algo, ya sea en forma hablada o por escrito, desde distintos puntos de vista". Ej: This chapter discusses di®erent approaches to the treatment of diseases; Discuss the following theorem. En castellano, si bien \discutir" tambi¶en posee una acepci¶o n similar, es m¶as saludable utilizar como equivalente \analizar", \considerar", etc. Ej: en la ¶ultima frase mencionada, una traducci¶on m¶a s acorde que \Discuta el siguiente teorema" ser¶³a \Analice/considere el siguiente teorema". Traducci¶ on sugerida: En ciertos contextos, se sugiere utilizar analizar o considerar. Palabra cuestionable en castellano: sino T¶ ermino original en ingl¶ es: else Problema: La palabra \sino" equivale a la palabra but, pero no a la palabra else. Ej: This is not only...but also... (Esto no solo es..., sino tambi¶en....). La palabra else, tal como se la usa en lenguajes de programaci¶on, equivale a otherwise o if not, por lo que se corresponde en castellano a \si no", o \en caso contrario". Ej: You must pay $100 or else go to prison (Debe pagar $100, o si no ir¶a a la c¶arcel). Traducci¶ on sugerida: Al escribir sentencias condicionales (if-then-else), se podr¶³a escribir \si no" para poner en claro que la palabra utilizada no es la misma que \sino". De mantenerse la palabra \sino", debe aclararse que se est¶a abusando del lenguaje por razones pr¶acticas o de comodidad, y que no se la est¶a utilizando correctamente.

{111{

¶ ¶ EN COMPUTACION ¶ Y SU INCIDENCIA EN NUESTRO 8 APENDICE: EL INGLES IDIOMA Palabra cuestionable en castellano: ocurrir , ocurrencia T¶ ermino original en ingl¶ es: to occur, occurrence Problema: En ingl¶es, el sustantivo occurrence est¶a asociado al verbo to occur (suceder, ocurrir, tener lugar). Ej: How many times does the letter 'a' occur in this line of text?; The number of occurrences of 'a's in the text is . .. En castellano no existe tal asociaci¶o n. Una \ocurrencia" tiene el ¶unico signi¯cado de \una observaci¶on o comentario chistoso, gracioso o ir¶o nico". Por otro lado, en situaciones como la anterior, en castellano es usual utilizar el verbo \aparecer". Ej: >Cu¶antas veces aparece la letra 'a' en esta l¶³nea de texto?; La cantidad de apariciones de la letra 'a' en el texto es . . . . Traducci¶ on sugerida: En contextos como el mencionado, puede usarse aparecer, y su forma sustantivada aparici¶on. Palabra cuestionable en castellano: refrasear T¶ ermino original en ingl¶ es: to rephrase Problema: La palabra \refrasear" no existe en castellano. El verbo to rephrase signi¯ca \expresar algo con otras palabras, especialmente para hacer m¶as claro su signi¯cado". Ej: We have to rephrase the last two paragraphs. Traducci¶ on sugerida: reescribir, revisar. Palabra cuestionable en castellano: sustituir a por b T¶ ermino original en ingl¶ es: substitute a for b Problema: En ingl¶es, decir we substituted Xs for Ys signi¯ca we put Xs in place of Ys. En castellano, por el contrario, decir \sustituir Xs por Ys" signi¯ca \poner Ys en lugar de Xs". Traducci¶ on sugerida: No hay ning¶un inconveniente en utilizar el verbo sustituir, siempre y cuando se advierta que los roles que juegan Xs e Ys en el ejemplo anterior se invierten.

8.2

Otros problemas comunes

² El uso de acentos y signos de puntuaci¶on correctos es un aspecto importante en lo que respecta a la calidad de presentaci¶o n de un trabajo. Es com¶ u n observar que s¶olo se utilice el signo de interrogaci¶on o admiraci¶on ¯nal (esto es, ? o !). En castellano, es obligatorio el uso de los dos s¶³mbolos correspondientes en cada caso: >, ?, < y !. Cabe se~nalar que, en ingl¶es, la estructura de las oraciones interrogativas permite \predecir" que las mismas est¶an asociadas a preguntas, ya que el verbo se coloca en primer lugar. Ej: consid¶erense las preguntas Is there any sugar left?, o Do you know what time it is?. En castellano no existe tal situaci¶on, por lo que la presencia de dos signos de interrogaci¶o n hace m¶as f¶acil la identi¯caci¶on de una pregunta, lo que resulta particularmente importante al momento de leerla en voz alta. Ej: >Es importante diferenciar todos los aspectos antes mencionados?. En esta frase, de haberse colocado solamente un u¶ nico signo de interrogaci¶o n al ¯nal, el lector reconocer¶³a que se trata de una oraci¶o n interrogativa u¶nicamente cuando llega al ¯nal de la misma... ² Es com¶ u n leer t¶³tulos tales como \Evitando ciclos en la programaci¶on en Pascal", como traducci¶on de Avoiding Loops in Pascal Programming. Debe se~nalarse que el gerundio en

{112{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

ingl¶es tiene un uso mucho m¶as frecuente que en castellano. En particular, en ingl¶es es com¶un especi¯car t¶³tulos o encabezamientos utilizando verbos en gerundio. Ej: \Preparing to Take the TOEFL Test", \Getting started", \Changing the Margins", etc. Para comprobar esta a¯rmaci¶on, basta tomar el ¶³ndice de un libro en ingl¶es, y analizar el gran n¶ u mero de cap¶³tulos y secciones, cuyo encabezamiento tiene un verbo en gerundio. En castellano, por el contrario, el uso del gerundio es m¶as restringido. El gerundio que aparece en t¶³tulos en ingl¶es puede sustituirse por preguntas indirectas o por verbos sustantivados. As¶³, los t¶³tulos anteriores podr¶³an escribirse como \C¶omo evitar ciclos en la programaci¶o n en Pascal", \C¶omo prepararse para rendir el examen TOEFL", \C¶omo empezar", y \C¶omo cambiar los m¶argenes". ² En ingl¶es es obligatorio utilizar letras may¶usculas en muchas situaciones especiales, como por ejemplo: a) en los sustantivos y adjetivos que aparecen en el t¶³tulo de una obra literaria, o en un encabezamiento (ej: \How to Live with no Money", \How to Program in Pascal"); b) en gentilicios y adjetivos derivados de nombres de personas (ej: Newtonian laws, an American author); c) en los nombres de religiones, grupos ¶etnicos y raciales, etc. (ej: Buddhism, Democrats and Republicans); d) en los nombres de los meses y de los d¶³as (ej: Monday, June). En castellano, como regla general, no se utilizan may¶ usculas en ninguno de estos casos. As¶³, por ejemplo, el t¶³tulo de un libro o art¶³culo se escribe con su primer letra en may¶ uscula (y las dem¶as en min¶ uscula), o bien todas en may¶uscula. Ej: \C¶omo programar en Pascal", o \COMO PROGRAMAR EN PASCAL". Los adjetivos asociados a nombres de personas, as¶³ como los gentilicios, se escriben en min¶uscula. Ej: leyes newtonianas, regla bayesiana.

{113{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

9

Niklaus Wirth: el creador de Pascal

Niklaus Wirth fue quien introdujo por primera vez la programaci¶on estructurada y la descomposici¶on modular como metodolog¶³a de trabajo para desarrollar algoritmos. Su aporte a las ciencias de la computaci¶on fue muy signi¯cativo. Fue ¶el quien introdujo una serie de lenguajes de programaci¶on innovadores en muchos sentidos, tales como Euler, Algol-W, Modula y Pascal. Este ¶ultimo es quiz¶as el m¶as famoso y difundido de todos ellos. Pascal, desarrollado hacia 1972, adquiri¶o una gran signi¯caci¶on por su aplicaci¶on a la ense~nanza de la programaci¶on. Los conceptos establecidos por Wirth a trav¶es de este lenguaje sentaron las bases de investigaciones futuras en ¶areas tales como lenguajes de programaci¶on, arquitectura de computadoras y an¶alisis de sistemas. Los elementos m¶as sobresalientes de Pascal son su simplicidad y su potencialidad como herramienta para desarrollar sistemas complejos. Pascal, comparado con los lenguajes existentes en la ¶epoca en que fue creado, result¶o ser un lenguaje cuya notaci¶on era una extensi¶on natural del pensamiento algor¶³tmico, sin recurrir a ning¶un formalismo adicional. En abril de 1971, Wirth public¶o un art¶³culo en la revista "Communications of the ACM", donde introdujo los conceptos de \re¯namiento paso a paso" y \modularizaci¶on", ejempli¯c¶andolos en la soluci¶on del famoso problema de ubicar 8 reinas en un tablero de ajedrez sin que se ataquen entre s¶³. El trabajo de Wirth despert¶o, pocos a~nos m¶as tarde, una ola de furor en el mundo de la computaci¶on, dando lugar al nacimiento de la \programaci¶on estructurada". Las pautas que planteara Wirth en aquel trabajo de 1971 siguen a¶un vigentes hoy como estrategias de programaci¶on y de resoluci¶on de problemas. Posteriormente, Wirth desarroll¶o un lenguaje m¶as poderoso que Pascal en el manejo de estructuras de datos, al que denomin¶o Modula. Variantes posteriores de dicho lenguaje fueron Modula-2 y Modula-3. Wirth recibi¶o el t¶³tulo de Ph.D. (doctor) de la Universidad de California, en Berkeley, en 1963. Fue profesor asistente de la Universidad de Stanford hasta 1967. Desde 1968, se desempe~na como profesor del Instituto Tecnol¶ogico Federal de Suiza (ETH). En 1984, recibi¶o el premio Turing (Turing Award) por parte de la Association for Computing Machinery (ACM), en honor a su trayectoria y sus valiosos aportes a las ciencias de la computaci¶on. Lo que sigue es la parte principal del texto de la conferencia dada por Niklaus Wirth, al recibir el premio Turing (Turing Award) 1984. Dicho premio se entrega anualmente a aquellos que han realizado contribuciones importantes a las ciencias de la computaci¶on. En dicha conferencia (llevada a cabo en 1985), Wirth relat¶o sus experiencias profesionales m¶as relevantes, y resulta sumamente interesante releerlas para analizar {a la luz de nuestros conocimientos actuales{ las motivaciones que sustentaron la contribuci¶on de N. Wirth a las Ciencias de la Computaci¶on. El original de dicha conferencia ¯gura en la revista Communications of the ACM, Vol.28, No.2, Feb.1985.

{115{

9 NIKLAUS WIRTH: EL CREADOR DE PASCAL

Del dise~ n o de un lenguaje de programaci¶o n a la construcci¶on de una computadora Turing Award Lecture 1984 por Niklaus Wirth [...] Por cierto, cuando ingres¶e al campo de la computaci¶on en 1960, ¶esta no era el centro de la atenci¶on p¶ ublica, ni en lo comercial ni en lo acad¶emico, como lo es hoy. Durante mis estudios en el Instituto Federal Suizo de Tecnolog¶³a (ETH), la ¶unica mencion que escuch¶e acerca de computadoras fue en un curso optativo dado por Ambros P.Speiser (quien m¶as tarde resultara ser electo presidente del IFIP). Speiser hab¶³a desarrollado una computadora llamada ERMETH, la cual era de dif¶³cil acceso para los estudiantes de computaci¶on, raz¶on por la cual mi iniciaci¶on en la computaci¶on fue postergada hasta que tom¶e un curso de an¶alisis num¶erico en la Universidad de Laval, en Canad¶a. Pero la m¶aquina con que contabamos all¶³ era una Alvac III E, la cual ten¶³a problemas la mayor parte del tiempo, por lo que nuestros ejercicios de programaci¶on sol¶³an quedar en papel, en la forma de meras secuencias de d¶³gitos hexadecimales... Mi siguiente intento fue ya m¶as exitoso: en Berkeley (California), me pusieron ante la \m¶aquina mascota" de Harry Huskey: la Bendix G-15. Aunque la Bendix G-15 prove¶³a cierta sensaci¶on de ¶exito (pues produc¶³a resultados), la esencia del arte de programar parec¶³a radicar en c¶omo ordenar inteligentemente las instrucciones de los programas en el \tambor" (drum) de almacenamiento de la m¶aquina. Si uno ignoraba ese arte, los programas pod¶³an llegar a correr cien veces m¶as lentos. Pero hab¶³a una ventaja educacional: uno no pod¶³a dejar de lado ni siquiera el menor detalle. No hab¶³a forma de resolver errores de dise~no con simplemente \poner m¶as memoria". Vi¶endolo desde la ¶optica de hoy en d¶³a, el aspecto m¶as atractivo de esta m¶aquina era que cada detalle era visible, y pod¶³a ser comprendido. No hab¶³a nada escondido en una circuiter¶³a compleja, o en un sistema operativo m¶agico. Por otra parte, era obvio que las computadoras del futuro ten¶³an que ser programables m¶as efectivamente. Por esa raz¶on, abandon¶e la idea de estudiar c¶omo dise~nar hardware, y me dediqu¶e a estudiar c¶omo usar el que hab¶³a disponible m¶as elegantemente. Fui afortunado en unirme a un equipo de investigaci¶on que estaba trabajando en el desarrollo (o m¶as bien, una mejora) de un compilador para correr en la IBM 704. El lenguaje se llamaba NELIAC, y era un dialecto de ALGOL 58. Los bene¯cios de este \lenguaje" eran bastante obvios, y la tarea de traducir autom¶aticamente programas en c¶odigo m¶aquina planteaba problemas considerables. Esto es precisamente lo que uno quiere encontrar cuando est¶a buscando un doctorado. El compilador para NELIAC, que estaba escrito tambi¶en en NELIAC, era un l¶³o bastante intrincado. El tema parec¶³a consistir de un uno por ciento de ciencia, y noventa y nueve por ciento de magia, y esto hab¶³a que cambiarlo. Evidentemente, los programas ten¶³an que dise~ narse siguiendo los mismos principios que los circuitos electr¶onicos, es decir, dividirlos claramente en subpartes con solamente unos pocos cables saliendo de cada una de ellas. Solamente si uno era capaz de entender cada parte por separado, exist¶³a la esperanza de entender ¯nalmente el todo. Este intento recibi¶o un impulso vigoroso con la aparici¶on del informe t¶ecnico sobre Algol 60. Algol 60 era el primer lenguaje dise~nado con claridad; su sintaxis estaba especi¯cada in{116{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

cluso en un formalismo riguroso. La lecci¶on era que una especi¯caci¶on clara es una condici¶on su¯ciente, pero no necesaria, para lograr una implementaci¶on efectiva y con¯able. El contacto con Aadrian van Wijngaarden, uno de los codise~nadores de Algol, dio como resultado un tema que resultar¶³a central: >Ser¶³a posible condensar y cristalizar m¶as a¶ un los principios del Algol? As¶³ empezaron mis aventuras con los lenguajes de programaci¶on. Mi primer experimento llev¶o a un trabajo de tesis y al desarrollo del lenguaje Euler (un viaje con un machete dentro de la jungla de lenguajes existentes). El resultado fue de elegancia acad¶emica, pero no de mucha utilidad pr¶actica (casi la ant¶³tesis de los lenguajes de programaci¶on estructurados y basados en tipo de dato). Pero Euler cre¶o una base para el dise~no sistem¶atico de compiladores que (esa era la idea), pod¶³a extenderse sin perder claridad, a ¯n de incluir nuevas caracter¶³sticas. Euler atrajo la atenci¶on del Grupo de Trabajo IFIP, que estaba involucrado en el desarrollo de un nuevo Algol. El lenguaje Algol 60, dise~nado por y para matem¶aticos num¶ericos, ten¶³a una estructura sistem¶atica y una de¯nici¶on concisa, que fueron apreciados por gente entrenada matem¶aticamente; sin embargo, Algol carec¶³a de compiladores y apoyo en la industria. Para ganar aceptaci¶on, deb¶³a ampliarse su rango de aplicaciones. El Grupo de Trabajo IFIP asumi¶o la tarea de desarrollar un sucesor, y pronto este trabajo se dividi¶o en dos campos: en uno estaban los \ambiciosos", los que quer¶³an sentar un monolito dentro del dise~no de lenguajes; en el otro estaban los que sent¶³an que el tiempo apremiaba, y que ampliar Algol 60 adecuadamente ser¶³a una tarea productiva. Yo estaba en este segundo grupo, y enviamos una propuesta que perdi¶o en la votaci¶on. A partir de ah¶³, la propuesta fue mejorada con contribuciones de Tony Hoare (miembro del mismo grupo) e implementada en la primer IBM 360 de la Univ. de Stanford. El lenguaje resultante lleg¶o a ser conocido como Algol W, y fue usado en varias universidades para ense~ nanza. Vale la pena mencionar un peque~ no interludio en todos estos esfuerzos de implementaci¶on. La nueva IBM 360 s¶olo ofrec¶³a c¶odigo ensamblador, y, por supuesto, lenguaje Fortran. Ninguna de estas alternativas eran miradas con cari~no (ni por m¶³ ni por mis estudiantes) como una herramienta para construir un compilador. Fue as¶³ que encontr¶e el coraje su¯ciente para de¯nir \otro lenguaje m¶as" para poder describir el compilador Algol: deb¶³a ser un compromiso entre Algol, y las facilidades ofrecidas por lenguaje ensamblador; deb¶³a ser un lenguaje m¶aquina pero con estructuras de sentencias y declaraciones tipo Algol. Incre¶³blemente, de¯nir este lenguaje llev¶o un par de semanas. Despu¶es escrib¶³ el compilador en una Burroughs B-5000 en cuatro meses, y un \estudiante aplicado" se encarg¶o de adaptarlo para la IBM 360 en otros cuatro meses. Este interludio preparativo ayud¶o a acelerar los trabajos en Algol en gran medida. El lenguaje \intermedio" dise~nado (PL360) estaba pensado para servir a nuestros prop¶ositos, y luego para descartarlo. No obstante, r¶apidamente adquiri¶o \su propio lugar": PL360 se convirti¶o en una herramienta efectiva en muchos lugares, e inspir¶o el desarrollo de aplicaciones similares para otras m¶aquinas. Ir¶onicamente, el ¶exito de PL360 fue tambi¶en un indicador del fracaso de Algol W. El rango de aplicaciones de Algol hab¶³a aumentado, pero como herramienta para la programaci¶on de sistemas, segu¶³a teniendo sus de¯ciencias. Hab¶³a surgido la di¯cultad de resolver muchas demandas con un u¶nico lenguaje: la meta de desarrollar \un ¶unico lenguaje" pas¶o a ser {117{

9 NIKLAUS WIRTH: EL CREADOR DE PASCAL

cuestionable. PL/1, un lenguaje lanzado hacia esos a~nos, parec¶³a apoyar m¶as a¶un esta suposici¶on. PL/1 segu¶³a la idea de \Swiss army knife", la navaja multiuso, que serv¶³a para todo prop¶osito; esto ten¶³a sus m¶eritos, pero tambi¶en sus desventajas. El compilador de Algol W, por su parte, creci¶o m¶as all¶a de los l¶³mites en los que uno pod¶³a descansar tranquilo, sabiendo que ten¶³a una \idea", una visi¶on de todo el programa. El deseo de lograr un formalismo m¶as conciso y m¶as apropiado para programaci¶on de sistemas a¶ un no se hab¶³a visto concretado. La programaci¶on de sistemas requiere un compilador e¯ciente, que genere c¶odigo e¯ciente, y que opera sin una gran cantidad de rutinas run-time (que deb¶³an estar residentes). Este objetivo no hab¶³a sido alcanzado ni por Algol W ni por PL/1; en ambos casos, el problema era que los lenguajes eran demasiados complejos, y las m¶aquinas en las que corr¶³an eran inadecuadas. En el oto~no de 1967, volv¶³ a Suiza. Un a~no m¶as tarde, pude establecer un equipo con tres asistentes, para implementar un lenguaje que m¶as adelante se denomin¶o Pascal. Ya estaba liberado de las presiones y restricciones de un comit¶e (como el que rigi¶o el desarrollo de Algol), y pude concentrarme en incluir aquellas cosas que ve¶³a esenciales, y sacar aquellas que a la larga no traer¶³an bene¯cio. Muchas veces, tambi¶en suele ser una ventaja contar con una cantidad limitada de colaboradores para desarrollar un lenguaje (como era mi caso). Ocasionalmente se ha dicho que Pascal fue dise~ nado como un lenguaje para ense~ nanza. Esto es correcto, pero su uso en la ense~ nanza no era su ¶unico ¯n. De hecho, no creo en eso de usar herramientas y formalmismos en la ense~nanza que en realidad son inadecuados para las tareas pr¶acticas. Con los est¶andares de hoy, Pascal tiene de¯ciencias obvias con los grandes sistemas de programaci¶on, pero hace 15 a~nos, represent¶o un compromiso adecuado entre lo que era deseable y lo que era efectivo. En el ETH, comenzamos a introducir Pascal en las clases de programaci¶on en 1972, luchando contra una oposici¶on considerable. Al ¯nal, Pascal result¶o ser un ¶exito, porque le permit¶³a al profesor concentrarse m¶as en las estructuras y conceptos que en los rasgos secundarios de un programa; es decir, pod¶³a concentrarse m¶as en los principios que en las t¶ecnicas. Nuestro primer compilador Pascal fue implementado para la familia de computadoras CDC 6000, y estaba escrito en Pascal. No hizo falta el PL360, y yo vi a esto como un paso sustancial. Sin embargo, el c¶odigo generado era muy inferior al que generaban los compiladores Fortran, para programas equivalentes. La velocidad es un criterio esencial, y f¶acilmente medible, y cre¶³amos que la validez del concepto de \lenguaje de alto nivel" s¶olo ser¶³a aceptada en la industria si el costo a pagar en perfomance pod¶³a desaparecer, o al menos disminuir. Con esta idea en mente, nos lanzamos a producir un compilador de alta calidad, si bien el resultado alcanzado fue b¶asicamente la tarea de un u¶nico profesional. En 1974, Urs Ammann desarroll¶o un compilador que fuera distribuido ampliamente, y que a¶ un hoy se usa en muchas universidades e industrias. El precio fue alto; el esfuerzo por generar buen c¶odigo es proporcional a las diferencias que existen entre la m¶aquina y el lenguaje, y la CDC 6000 no estaba dise~nada para correr sobre ella lenguajes de alto nivel... Una vez m¶as, ir¶onicamente, el principal bene¯cio apareci¶o por donde menos se lo esperaba. Despu¶es de que la existencia de Pascal se hizo conocida, mucha gente comenz¶o a pedirnos que la asistieramos en implementar Pascal en otras m¶aquinas, enfatizando que pensaban usarlo para ense~ nanza, y que la velocidad no era tan importante. Con esto fue que {118{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

nos decidimos a escribir un compilador que generar¶³a c¶odigo para una m¶aquina de nuestro propio dise~no. Este c¶odigo ser¶³a conocido luego como c¶odigo-P. El la versi¶on de c¶odigo-P era f¶acil de construir, porque el nuevo compilador estaba dise~nado como un gran ejercicio de programaci¶on estructurada, donde hab¶³a que usar re¯namiento paso a paso. Pascal-P result¶o ser tremendamente exitoso, extendiendo el uso del lenguaje entre muchos usuarios. Si hubiesemos tenido la visi¶on su¯ciente como para poder preveer los alcances de este lenguaje, hubiesemos puesto mayor cuidado en el desarrollo, dise~no y documentaci¶on del c¶odigo-P. Sin embargo, as¶³ como qued¶o, fue algo que vali¶o la pena. Esto muestra que a¶un con las mejores intenciones en mente, uno puede elegir sus propias metas equivocadamente. Pero Pascal reci¶en gan¶o un reconocimiento verdadero cuando Ken Bowles, en San Diego, reconoci¶o que el sistema Pascal-P pod¶³a implementarse en las microcomputadoras, que acababan de aparecer. Sus esfuerzos en lograr un entorno adecuado, con un compilador, editor y depurador integrados, causaron sensaci¶on: Pascal pas¶o a estar disponible a miles de nuevos usuarios, que ya no ten¶³an sobre sus espaldas el peso de h¶abitos adquiridos de programaci¶on, y no estaban urgidos por mantener compatibilidad con el software del pasado. Mientras tanto, termin¶e de trabajar con Pascal, y me decid¶³ a investigar un ¶area nueva: multiprogramaci¶on. Aqu¶³, Hoare ya hab¶³a sentado bases s¶olidas, y Brinch Hansen hab¶³a marcado el camino con su Pascal concurrente. El intento de \destilar" reglas concretas para una disciplina de multiprogramaci¶on me llev¶o r¶apidamente a formularlas en t¶erminos de un peque~no conjunto de facilidades para programar. A ¯n de someter estas reglas a alg¶ un tipo de test, las puse en un lenguaje semicompleto, al que le puse un nombre que re°ejara mi meta principal: modularidad en programaci¶on. El m¶odulo result¶o ser m¶as adelante la principal caracter¶³stica de este lenguaje. A trav¶es de este concepto, el concepto abstracto de ocultamiento de la informaci¶on (necesario en programaci¶on de sistemas) tomaba una forma concreta, e incorporaba un m¶etodo que resultaba signi¯cativo tanto para multiprogramaci¶on como para la programaci¶on tradicional. El lenguaje, llamado Modula, ten¶³a facilidades para expresar procesos concurrentes y su sincronizaci¶on. Hacia 1976, ya me hab¶³a cansado un poco de los lenguajes de programaci¶on, y de la tarea frustrante de construir buenos compiladores para las computadoras existentes, las que estaban dise~nadas para ser codi¯cadas \a mano", a la usanza antigua. Por fortuna, tuve la posibilidad de pasar un a~no sab¶atico en el laboratorio de investigaci¶on de Xerox Corp, en Palo Alto (California), donde se hab¶³a originado y puesto en pr¶actica el concepto de una \workstation" personal y poderosa. En lugar de compartir una computadora monol¶³tica, gigantesca, con varios usuarios, peleando por recibir atenci¶on de un sistema con 3KHz de ancho de banda, ahora yo contaba con mi propio sistema, debajo de mi escritorio, con un canal de m¶as de 15KHz. La capacidad de trabajo se hab¶³a incrementado 5000 veces. La sensaci¶on m¶as particular fue que despu¶es de estar 16 a~nos trabajando con computadoras, reci¶en ah¶³ la computadora parec¶³a estar trabajando para m¶³. Por primera vez empec¶e a usar una computadora para escirbir reportes y manejar mi correspondencia, en lugar de ponerme a plani¯car nuevos lenguajes, compiladores y cosas por el estilo. Otra revelaci¶on para m¶³ fue la posibilidad de fabricar un compilador para el lenguaje Mesa, cuya complejidad era mucho mayor que la de uno para Pascal; un compilador para Mesa pod¶³a implementarse en una workstation como la que pose¶³a. Estas nuevas condiciones de trabajo ten¶³an tantos ¶ordenes {119{

9 NIKLAUS WIRTH: EL CREADOR DE PASCAL

de magnitud por encima de lo que estaba acostumbrado, me llevaron a pensar en desarrollar un entorno para este tipo de m¶aquinas. Finalmente, decid¶³ empezar a explorar primero el dise~no de hardware. Esta decisi¶on estuvo reforzada por mi antiguo disgusto con las arquitecturas de computadoras existentes, las que hac¶³an miserable la vida de un dise~nador de compiladores que quer¶³a simpli¯car las cosas sistem¶aticamente. La idea de dise~ nar y construir un sistema computacional completo, consistente de hardware, microc¶odigo, compilador, sistema oparativo, y utilitarios, fue tomando forma en mi imaginaci¶on: lograr un dise~no que estuviese liberado de cualquier restricci¶on de ser compatible con PDP-11, IBM 360, o Fortran, Pascal, Unix, o cualquiera fuese el est¶andar que un comit¶e podr¶³a llegar a querer imponer. Pero una sensaci¶on de liberacion no basta para tener ¶exito en un proyecto t¶ecnico. El trabajo duro, la determinaci¶on, una sensibilidad de lo que es esencial y lo que es ef¶³mero, y una cuota de buena suerte, son indispensables. El primer accidente afortunado fue una llamada telef¶onica de un dise~nador de hardware que quer¶³a informarse acerca de las posibilidades de venir a nuestra universidad, y aprender acerca de t¶ecnicas de software y adquirir un t¶³tulo de Ph.D. >Por qu¶e no ense~narle software, mientras que ¶el a nosotros nos ense~ naba hardware? No llev¶o mucho tiempo para que los dos formasemos un equipo activo. La persona a que hago referencia era Richard Ohran. Pronto estuvo tan excitado con el asunto de dise~nar un nuevo hardware que se olvid¶o todo respecto al software y a su Ph.D. Eso no me molestaba demasiado, ya que yo estaba muy ocupado con la especi¯caci¶on de micro- y macroc¶odigo (y con la programaci¶on de un int¶erprete para este ¶ultimo), con la plani¯caci¶on de un sistema de sofware integrado, y en particular, con la programaci¶on de un editor de textos y un editor de diagramas. Estos u¶ltimos hac¶³an uso de un nuevo tipo de monitor, de alta resoluci¶on y con mapeo de bits, y de un peque~no milagro llamado \mouse" como dispositivo auxiliar. Esta ejercitaci¶on en desarrollar programas utilitarios altamente interactivos requer¶³a el estudio y la aplicaci¶on de t¶ecnicas bastante extra~ nas para alguien que hab¶³a trabajado en el dise~ no convencional de sistemas operativos y compiladores. El proyecto en su conjunto era tan diversi¯cado y complejo que parec¶³a irresponsable comenzarlo, particularmente teniendo en cuenta del escaso n¶umero de colaboradores con semi-dedicaci¶on que nos ayudaban (unos siete). La mayor amenaza consist¶³a en que era dif¶³cil que nosotros dos nos mantuviesemos su¯cientemente entusiastas hasta que el resto de la gente tambi¶en fuese igualmente entusiasta (los dem¶as no hab¶³an experimentado lo su¯ciente con la potencia de una workstation). Para que el proyecto se mantuviese dentro de dimensiones razonables, me adher¶³ a tres dogmas: apuntar a una computadora con un u¶nico procesador, que ser¶³a operada por un ¶unico usuario, y programada en un ¶unico lenguaje. Notablemente, estos tres elementos eran diametralmente opuestos a las tendencias de ese momento, que estaban a favor de investigar con¯guraciones con multiprocesadores, sistemas operativos multiusuario con tiempo compartido, y tantos lenguajes de programaci¶on como fuera posible. Bajo las restricciones de \un ¶unico lenguaje", encar¶e una elecci¶on di¯cil, cuyos efectos ser¶³an duraderos: >qu¶e lenguaje elegir? De los lenguajes existentes, ninguno parec¶³a atractivo. Ninguno satisfac¶³a todos los requerimientos que ten¶³a en mente, ni era particularmente llamativo para el dise~ nador de compiladores, quien sabe que la tarea propuesta ten¶³a que {120{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

realizarse en un tiempo razonable. En particular, el lenguaje deb¶³a adaptarse a nuestros deseos en cuanto a contar con estructuras (ten¶³amos 10 a~ nos de experiencia con Pascal), y poder manejar problemas que hasta ese momento s¶olo pod¶³an ser resueltos usando lenguaje ensamblador. Para resumir: la elecci¶on fue dise~nar un hijo de Pascal {que ya hab¶³a sido probado lo su¯ciente{ y del Modula experimental en el que hab¶³a estado trabajando anteriormente. El lenguaje resultante lo llamamos Modula-2. El m¶odulo es la clave para poner bajo un mismo techo los requerimientos contradictorios que imponen, por un lado, la abstracci¶on de alto nivel, y por otro, facilidades de bajo nivel para permitir explotar las caracter¶³sticas individuales de una computadora particular. El m¶odulo le permite al programador encapsular el uso de facilidades de bajo nivel en peque~nas partes del sistema, protegi¶endolo de esta manera de caer en alguna rutina a bajo nivel en lugares inesperados. El proyecto Lilith demostr¶o que no solo es posible, sino tambi¶en ventajoso, dise~nar un sistema basado en un u¶nico lenguaje. Todo, desde los manejadores de dispositivos hasta los editores gr¶a¯cos y de texto, estaban escritos en el mismo lenguaje. No hay distinci¶on entre los m¶odulos que pertenecen al sistema operativo, y los m¶odulos que pertenecen al programa del usuario. De hecho, esta distinci¶on casi desaparece, y con ello se evita el peso de un bloque de c¶odigo residente pesado y mastod¶ontico, que nadie quiere pero que todos se ven obligados a aceptar. Adem¶as, el proyecto Lilith demostr¶o los bene¯cios de formar una buena pareja entre el dise~ no de software y hardware. Estos bene¯cios pueden medirse en t¶erminos de velocidad: las comparaciones de tiempos de ejecuci¶on de programas en M¶odula, revelaron que Lilith era un sistema a menudo superior a una VAX 750, cuya complejidad y costo eran superiores a los de Lilith. Las comparaciones entre sistemas pueden tambi¶en medirse en t¶erminos de espacio: el c¶odigo de programas Modula para Lilith es m¶as corto que el c¶odigo para PDP-11, VAX o 68000, en factores que van entre 2 y 3, y m¶as corto que el c¶odigo del NS 32000 en un factor de 1.5 a 2. Adem¶as, las partes de un compilador encargadas de generaci¶on de c¶odigo para estos procesadores son mucho m¶as intrincadas que las de Lilith, ya que las instrucciones a nivel de lenguaje m¶aquina no se correspond¶³an con el lenguaje a alto nivel. Esto, de alguna manera, arroja una sombra oscura sobre la \adaptabilidad" de muchos lenguajes de alto nivel, que han recibido mucha publicidad, para su uso en modernos microprocesadores, pero que en vista de estas comparaciones antes mencionadas resulta ser exagerada. La idea de que, adem¶as, estos dise~ nos de procesador ser¶an reproducidos millones de veces, es algo bastante deprimente. Por ser mayor¶³a, esos microprocesadores se impondr¶an como est¶andar. Por desgracia, los avances en tecnolog¶³a de semiconductores han sido tan veloces que los avances en arquitectura han quedado opacados, y han pasado a ser menos relevantes. La competencia fuerza a que los fabricantes armen nuevos dise~nos de chips antes de que ¶estos hayan probado realmente su e¯cacia. Y mientras que el software, por lo menos, puede modi¯carse y reemplazarse, la complejidad mayor hoy d¶³a ha descendido a los mismos chips. Y hay poca esperanza que dominemos mejor la complejidad cuando la aplicamos al hardware, pero no en la misma medida al software. Sin embargo, mirando las dos caras de la moneda, la complejidad tiene y ha mantenido una fuerte fascinaci¶on para mucha gente. Es cierto que vivimos en un mundo complejo, y nos esforzamos para resolver problemas inherentemente complejos. No obstante, estno no deber¶³a disminuir nuestro deseo de buscar soluciones elegantes, las cuales nos convenzan por {121{

9 NIKLAUS WIRTH: EL CREADOR DE PASCAL

su claridad y efectividad. Las soluciones simples, elegantes, son m¶as efectivas, pero son m¶as dif¶³ciles de hallar que las complejas, y requieren m¶as tiempo, cosa que a menudo la consideramos insoportable. Antes de terminar, quisiera rescatar algunas de las caracter¶³sticas comunes de los proyectos que se han mencionado. Una t¶ecnica muy importante, y que rara vez se usa tan efectivamente como en ciencias de la computaci¶on, es el bootstrap. Nosotros lo usamos casi en todos nuestros proyectos. Al desarrollar una herramienta, sea un lenguaje de programaci¶on, un compilador, o una computadora, los dise~ n¶e de tal manera que resultara bene¯cioso para el paso siguiente: PL360 fue desarrollado para implementar Algol W; Pascal fue desarrollado para implementar Pascal; Modula-2, para implementar todo el software de una workstation; y Lilith, para proveer un entorno adecuado para todo nuestr trabajo futuro, desde la programaci¶on al desarrollo y documentaci¶on de circuitos, desde la preparaci¶on de reportes al dise~ no de tipos de letra (fonts). El bootstraping es la forma m¶as efectiva de sacar provecho de los esfuerzos de uno, as¶³ como tambi¶en de sufrir los errores que uno mismo comete. Esto hace que sea importante distinguir a tiempo entre lo que es esencial, y lo que es ef¶³mero. Siempre intent¶e identi¯car y puntualizar lo que es esencial, y da bene¯cios incuestionables. Por ejemplo, la inclusi¶on de un esquema consistente y coherente de declaraciones de tipo de dato en un lenguaje de programaci¶on es, para m¶³, un aspecto esencial, mientras que los detalles de qu¶e tipo de sentencias FOR van a estar disponibles, o si el compilador va a distinguir entre may¶ usculas y min¶ usculas, son cuestiones ef¶³meras. En dise~no de computadoras, considero que la elecci¶on de los modos de direccionamiento, y la provisi¶on de un conjunto consistente y completo de instrucciones aritm¶eticas (incluyendo llamadas al sistema, manejo de over°ow, etc) son esenciales; en contraste, los detalles de un mecanismo de interrupci¶on prioritizada son m¶as bien perif¶ericos. A¶ un m¶as importante es asegurarse que lo ef¶³mero nunca se impregne en el dise~no estructurado y sistem¶atico de las facilidades centrales de un sistema; es mejor que aquello que es ef¶³mero sea a~ nadido posteriormente a un marco preexistene, perfectamente bien estructurado. A veces, es dif¶³cil rechazar las presiones de incluir todas aquellas facilidades que \ser¶³a lindo tener". El peligro es que los deseos de complacer tales pedidos chocan contra el objetivo ¯nal de lograr un dise~no consistente. Yo siempre he intentado pesar las ganancias versus los costos. Por ejemplo, al considerar la inclusi¶on de alguna caracter¶³stica especial a un lenguaje, o alg¶ un tratamiento especial a alguna construcci¶on o sentencia por parte del compilador, uno debe ponderar los bene¯cios frente a los costos agregados de su implementaci¶on y su mera presencia, que van a ocasionar que el sistema sea mucho m¶as grande. Los que dise~nan lenguajes a menudo fallan en este sentido. Yo admito con cierto placer que ciertas caracter¶³sticas de Ada que no est¶an en Modula-2 ser¶³an \lindas de tener", pero, al mismo tiempo, me pregunto si tenerlas valdr¶³a la pena por el costo que implican. Y este costo es considerable. Pensemos que, aunque el dise~ no de ambos lenguajes comenz¶o en 1977, los compiladores de Ada s¶olo comenzaron a aparecer hacia 1985, mientras que hemos estado usando Modula-2 desde 1979. En segundo lugar, se rumorea que los compiladores de Ada son programas gigantescos, que consisten de varios cientos de miles de l¶³neas de c¶odigo, mientras que nuestro ¶ultimo compilador de Modula tiene s¶olo unas cinco mil l¶³neas de c¶odigo. Yo {122{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

con¯eso que este compilador de Modula est¶a ya en los l¶³mites de una complejidad comprensible, y que yo mismo me sentir¶³a incapaz de construir un buen compilador para Ada. Pero a¶un si se ignora el esfuerzo de construir sistemas innecesariamente grandes, y el costo en memoria para contener su c¶odigo, el costo real est¶a oculto en los esfuerzos (que nadie ve) de los inumerables programadoses que intentan desesperadamente entender estos compiladores para usarlos efectivamente. Otra caracter¶³stica com¶ un de los proyectos presentados anteriormente fue la elecci¶on de herramientas. Creo que una herramienta debe estar a tono con el producto; debe ser tan simple como sea posible, pero no m¶as simple que eso. Una herramienta es de hecho contraproducente cuando lograr una gran parte de un proyecto est¶a sujeto a ser un experto en usar dicha herramienta. En los proyectos Euler, Algol-W y PL360, muchas de las consideraciones estuvieron puestas en el desarrollo de t¶ecnicas de an¶alisis sint¶actico bottom-up, guiadas por tablas. M¶as adelante, volv¶³ al m¶etodo top-down recursivo descendente, que es f¶acilmente comprensible y sin lugar a dudas su¯cientemente poderoso, si la sintaxis del lenguaje est¶a elegida de una manera inteligente. En el desarrollo del hardware de Lilith, nos restringimos a un buen osciloscopio; solo una que otra vez necesitamos un analizador de estados l¶ogicos. Esto fue posible debido a conceptos sistem¶aticos y sin trucos utilizados en el procesador. Cada proyecto en s¶³ mismo fue, principalmente, una experiencia de aprendizaje. Uno aprende m¶as cuando inventa. Solamente haciendo un proyecto de desarrollo uno puede ganar su¯ciente familiaridad con las di¯cultades intr¶³nsecas, y su¯ciente con¯anza para dominar los detalles inherentes al mismo. Yo nunca pude separar el dise~ no de un lenguaje de su implementaci¶on, ya que una de¯nci¶on r¶³gida sin la retroalimentaci¶on de la construcci¶on de su compilador, me parecer¶³a algo presuntuoso y poco profesional. De esta manera, particip¶e en la construcci¶on de compiladores, dise~no de circuitos, e incluso en la conexi¶on de cableado. Esto puede parecer extra~no, pero simplemente me gusta la experiencia real, \hands-on", mucho m¶as que el manejo de un equipo. Tambi¶en he aprendido que los investigadores aceptan el liderazgo de un miembro del equipo que \se ensucie las manos", mucho m¶as f¶acilmente que de un experto de organizaci¶on, sea ¶este un manager de la industria, o un profesor universitario. Yo intento tener en mente que el ense~ nar dando un buen ejemplo es uno de los m¶etodos m¶as efectivos, y a veces, el u¶nico disponible. Finalmente, cada uno de estos proyectos fue llevado a cabo con el entusiasmo y el deseo de triunfar, sabiendo que el desaf¶³o val¶³a la pena. Esto quiz¶as sea el prerequisito esencial, pero tambi¶en el m¶as sutil y dif¶³cil de explicar. Tuve la suerte de tener miembros en mi equipo que se dejaron \infectar" con entusiasmo, y en esta conferencia tengo la oportunidad de dar gracias a todos elllos por su valiosa contribuci¶on. Mi sincero agradecimiento va tambi¶en a todos aquellos que participaron, en forma directa, trabajando en el equipo, o bien indirecta, testeando nuestros resultados y contribuyendo con ideas a trav¶es de cr¶³ticas y palabras de aliento, as¶³ como tambi¶en aquellos que formaron sociedades de usuarios. Sin ellos, ni Algol W, ni Pascal, ni Modula-2, ni Lilith habr¶³an llegado a ser lo que son. Este premio Turing tambi¶en honra sus contribuciones. Niklaus Wirth

{123{

Resoluci¶o n de Problemas y Algoritmos { Ejercitac. y algunas consideraciones te¶o ricas { Carlos I. Ches~ n evar

Referencias [1] Diccionario Enciclop¶edico Abreviado Espasa-Calpe. Ed.Espasa-Calpe, Madrid, Espa~na, 1972. [2] Trabajo Pr¶actico Nro. 1 (Tema: resoluci¶on de problemas). C¶atedra de \Introducci¶on a la Inform¶atica" (a~nos 1992, 1993 y 1994). Universidad Nacional del Sur, Bah¶³a Blanca. [3] Ches~ nevar, C. I. Gu¶³a Informativa para el estudiante de la U.N.S. en Licenciatura en Ciencias de la Computaci¶on. Bah¶³a Blanca, febrero de 1994. [4] Ches~ nevar, C. I. \Some problems about English-Spanish translations in computer science literature". En Special Interest Group on Computer Science Education (SIGCSE) Bulletin, de la Association for Computing Machinery, septiembre de 1994. [5] Ches~ nevar, C. I. \Syntactic diagrams as a tool for solving text-processing problems". En Special Interest Group on Computer Science Education (SIGCSE) Bulletin, de la Association for Computing Machinery, diciembre de 1994. [6] Jenkins-Murphy, A. Grammar Review for the TOEFL. HBJ Publishers, New York, 1982. [7] Jensen, K. y Wirth, N. PASCAL. User Manual and Report (2nd.Ed.) SpringerVerlag, New York, 1975. [8] Longman Dictionary of Contemporary English. Longman Group, England, 1987. [9] Mandell, M. Acertijos Fant¶asticos. Ed. Juegos & Co. { Zugarto Ediciones, 1995. [10] Perelman, Y.I. Matem¶aticas Recreativas. Ed. en Lenguas Extranjeras, URSS, 1959. [11] Rueda, S., Castro, S. y Zanconi, M. Resoluci¶on de problemas y algoritmos (notas de curso). Universidad Nacional del Sur, Bah¶³a Blanca, 1990.

{125{

¶Indice de Materias Pascal Wirth: El creador de, 114 Turbo Pascal Opci¶on de Archivo (File), 94 Opci¶on de Ayuda (Help), 101 Opci¶on de B¶usqueda (Search), 96 Opci¶on de Compilaci¶on (Compile), 98 Opci¶on de Depuraci¶on (Debug), 98 Opci¶on de Edici¶on (Edit), 95 Opci¶on de Ejecuci¶on de programas (Run), 97 Opci¶on de Ventana (Window), 100 Opciones varias (Options), 100 Teclas utilizadas en, 102 Teclas utilizadas en editor, 103 Consideraciones para manejo, 93 Men¶u de opciones de, 94 Unix, 108

Compilador, 106 Condici¶on Qu¶e es una, 30 Condiciones Aspectos avanzados, 39 Bloques de acciones y su relaci¶on con, 41 Situaciones redundantes en, 42 Conjunci¶on Operador l¶ogico de, 32 Constantes Declaraci¶on de, 71 Cortar y Pegar, 105 Datos booleanos, 35 Aplicaci¶on de, 36 De Morgan, Leyes de, 41 Directorio, 106 Disyunci¶on Operador l¶ogico de, 33

Abortar, 104 Algorimtos con fechas, 46 Algoritmo para conjetura de Goldbach, 48 para n¶umeros romanos, 47 Teorema de Fermat, 47 Algoritmos para series, 46 Archivo, 104 Archivo de texto, 105

Editar, 106 Editor de Textos, 106 Ejercicios de trazas, 44 sobre algoritmos sencillos, 45 Estado inicial, 19 meta, 19 Estados, 19

B¶ usqueda espacio-estado, 19 Bloque de texto, 105 Boole, George, 34 Breakpoint en Turbo Pascal, 99

Funciones, 81 De¯nici¶on de, 72 Invocaci¶on de, 82

C¶odigo ejecutable, 106 Cadena, 105 Camino, 19 Cancelar, 106 Cargar, 106

Identi¯cador, 70 Invocaci¶on a procedimientos, 78

Glosario de t¶erminos de computaci¶on, 104 Grabar, 106

Lenguaje de programaci¶on, 69 Login, 106 127

¶INDICE DE MATERIAS

Logout, 107

Sentencia Repeat-Until, 74 Sentencia While-Do, 73 Sentencia Write, 76 Sentencias de entrada y salida, 75 Sintaxis, 69 de Pascal, 71 Sistema monousuario, 107 multiusuario, 107 operativo, 107 Sugerencias para dibujos en Pascal, 84 para resoluci¶on de problemas, 11

Memoria, 107 Men¶u, 107 Mover (bloque texto), 105 MS-DOS, 107 Mundos posibles, 18 en problemas de l¶ogica, 20 N¶umeros aabb, 45 N¶umeros capic¶ uas, 45 N¶umeros contenidos, 48 N¶umeros parientes, 46 Negaci¶on Operador l¶ogico de, 34 Notaci¶on bnf, 69

Terminal, 108 Tipos Declaraci¶on de, 71 Traducci¶on ingl¶es-castellano Palabras cuestionables, 110 Problemas comunes, 112

Operador l¶ogico \no", 34 Operador l¶ogico \o", 33 Operador l¶ogico \y", 32 Operadores l¶ogicos, 32 Condiciones complejas usando, 35 Propiedades de los, 40

Uso de ingl¶es en computaci¶on, 109

Password, 107 Procedimiento est¶andar Read, 77 Procedimiento est¶andar Write, 76 Procedimiento y funciones Diferencias entre, 79 Procedimientos, 79 De¯nici¶on de, 72 Invocaci¶on de, 80 Procedimientos y funciones, 79 Programas en Pascal, 69

Variables Declaraci¶on de, 72 Watch en Turbo Pascal, 99 Windows 95, 108 Wirth Niklaus, 114

Recomendaciones sobre clases pr¶acticas, 8 sobre ejercicios resueltos, 8 Sem¶antica, 69 Sentencia compuesta, 75 Sentencia de asignaci¶on, 74 Sentencia vac¶³a, 75 Sentencia If-Then-Else, 74 Sentencia Read, 77 {128{