Curso Pre-ingreso 2011 Carrera Ingeniera en Computacin - Facultad de Informtica Facultad de Ingeniera
Captulo 6
Programacin Estructurada
Objetivo
Este captulo introduce una metodologa que permitir facilitar la resolucin de problemas. La propuesta radica en descomponer las tareas a realizar en subtareas ms sencillas de manera de no tener que escribir un programa como un todo. Los problemas del mundo real, en general, resultan ser complejos y extensos. Si se pretende seguir con la forma de trabajo hasta aqu utilizada, se ver que resulta difcil cubrir todos los aspectos de la solucin. Por ejemplo, supongamos que se pide que el robot recorra todas las avenidas de la ciudad juntando flores y papeles e informe la cantidad de flores por avenida y el total de papeles durante todo el recorrido, seguramente nos resultar ms natural y sencillo pensar en trminos de tareas. Por ejemplo, recorrer una avenida contando flores y papeles, informar cantidad de flores de la avenida, posicionarse en la avenida siguiente, poner la cantidad de flores en cero, y al finalizar el recorrido informar la cantidad de papeles. Esta forma de trabajo es lo que se formalizar a partir de este captulo y se presentarn sus beneficios.
Temas a tratar
Descomposicin de problemas en partes Programacin modular Conclusiones Ejercitacin
U. N. L. P.
Introduccin a la Informtica
6.1 Descomposicin de problemas en partes
Una de las herramientas ms tiles en la resolucin de problemas con computadora es la descomposicin de los problemas a resolver en subproblemas ms simples. Esta descomposicin, que se basa en el paradigma Divide y Vencers", persigue un objetivo: cada problema es dividido en un nmero de subproblemas ms pequeos, cada uno de los cuales a su vez, puede dividirse en un conjunto de subproblemas ms pequeos an, y as siguiendo. Cada uno de estos subproblemas debiera resultar entonces ms simple de resolver. Una metodologa de resolucin con estas caractersticas se conoce como diseo Top -Down. La figura 6.1 muestra la representacin en forma de rbol de una descomposicin Top-Down.
Figura 6.1: Diseo Top-Down El nivel de descomposicin al que se llega depende de los conocimientos de quien va a implementar la solucin (obviamente, el nivel de detalle al que puede arribar un experto no es el mismo que al que llegar un novato). Es decir, que con esta metodologa, resolver el problema original se reduce a resolver una serie de problemas ms simples o subproblemas. En cada paso del proceso de resolucin, cada subproblema es refinado hasta llegar a un punto en que est compuesto de acciones tan simples que ya no tiene sentido seguir refinando. Cuando se realiza esta descomposicin debe tenerse en cuenta que los subproblemas que se encuentran a un mismo nivel de detalle pueden resolverse independientemente de los dems y que las soluciones de estos subproblemas deben combinarse para resolver el problema original De la figura 6.1 podemos inducir que la resolucin de los subproblemas C.1, C.2 y C.3 implica resolver el problema C. A su vez la resolucin de los subproblemas A, B, C y D permitirn obtener la resolucin del problema original. Es importante destacar que los subproblemas pueden ser resueltos de manera independiente entre s y desarrollado por diferentes grupos de trabajo.
U. N. L. P.
Programacin estructurada
6.2 Programacin modular
La metodologa descripta en la seccin anterior puede aplicarse al diseo de programas. Un buen diseo nos permitir dividir nuestra solucin en un nmero de piezas manejables llamadas mdulos, cada uno de los cuales, tiene una tarea perfectamente definida. Esta metodologa, conocida como modularizacin diseo Top Down, es una de las tcnicas ms importantes para lograr un buen diseo de programa. La programacin modular es uno de los mtodos de diseo ms flexibles y potentes para mejorar la productividad de un programa. La descomposicin de un programa en mdulos independientes ms simples se conoce tambin como el mtodo de divide y vencers". Se disea cada mdulo con independencia de los dems y, siguiendo un mtodo descendente, se llega hasta la descomposicin final del problema en mdulos en forma jerrquica. En consecuencia, el programa se divide en mdulos (partes independientes), cada uno de los cuales ejecuta una nica actividad o tarea especfica. Dichos mdulos se analizan, codifican y ponen a punto por separado. Si la tarea asignada a cada mdulo es demasiado compleja, este deber descomponerse en otros mdulos ms pequeos. El proceso sucesivo de subdivisin contina hasta que cada mdulo tenga slo una tarea especfica que ejecutar. Esta metodologa de trabajo ofrece numerosas ventajas entre las que se pueden mencionar: Independencia entre los mdulos: Dado que los mdulos son independientes, diferentes programadores pueden trabajar simultneamente en distintas partes de un mismo programa. Esto reduce el tiempo de diseo y codificacin del algoritmo. Revisemos el siguiente ejemplo: El robot debe acomodar las esquinas de la ciudad de manera que en cada una quede la misma cantidad de flores que de papeles. Para hacerlo, recoger lo que sobra. Por ejemplo, si en una esquina hay 10 flores y 14 papeles, se llevar 4 papeles para dejar 10 de cada uno. Las esquinas vacas sern consideradas equilibradas por lo que quedarn as. Puede verse que el procesamiento de una esquina en particular es independiente del resto del programa. Podra encargarse su diseo e implementacin a otra persona. Se denominar a esta persona Programador A. Como resultado de la tarea del programador A se obtendr un mdulo que iguala la cantidad de flores y de papeles haciendo que el robot se lleve lo que sobra. El programador B ser el encargado de usar este mdulo en la resolucin de este problema. Es importante notar que al programador B no le interesa cmo hizo el programador A para igualar la cantidad de elementos de la esquina. Por su parte, el programador A desconoce como se utilizar el mdulo que est implementando. Esto hace que ambos programadores
U. N. L. P.
Introduccin a la Informtica
trabajen con subproblemas ms simples que el problema original. El programador A slo se dedica al procesamiento de una esquina y el programador B slo se preocupa porque el robot recorra todas las esquinas de la ciudad, dando por hecho el procesamiento de cada esquina. Modificacin de los mdulos Cada mdulo tiene una tarea especfica que debe llevar a cabo. En su interior slo se definen acciones relacionadas con este fin. Por tal motivo, la modificacin interna de un mdulo no afectar al resto. Volviendo al ejemplo anterior, suponga que debe modificarse el procesamiento de cada esquina de manera que el robot iguale la cantidad de elementos intentando depositar primero (igualar hacia el nmero superior) y si no tiene, recin entonces se llevar lo que sobra. Al tener el comportamiento de la esquina encerrado en un mdulo, bastar con realizar all las modificaciones para que todos los programas que lo utilicen se vean actualizados SIN necesidad de cambiar nada.
Reusabilidad de cdigo
El desarrollo de un mdulo es independiente del problema original que se desea resolver. Por ejemplo, podra definirse un mdulo que permita al robot girar a la izquierda. Cuando est implementado, podr ser aplicado en mltiples recorridos. El concepto de reusabilidad hace hincapi en la ventaja de utilizar cada mdulo directamente sin necesidad de volver a pensarlo nuevamente. No importa cmo hace para quedar posicionado hacia la izquierda, lo que importa es que el mdulo cumple con la funcin especificada. En otras palabras, para poder utilizar un mdulo no interesa saber cmo est implementado internamente sino que alcanza con saber qu es lo que hace. Obviamente el hacedor o implementador del mdulo deber ocuparse de que ese mdulo cumpla la funcin de la mejor manera posible. Es por ello que los que luego lo utilizarn pueden desentenderse del cmo lo hace y concentrarse en qu hace Mantenimiento del cdigo Una vez que el programa es puesto en marcha resulta comn que aparezcan errores de diseo, ya sea porque no se interpretaron correctamente los requerimientos del usuario o porque han cambiado las especificaciones. Cuando se desea realizar modificaciones, el uso de mdulos es muy beneficioso ya que cada tarea se encuentra concentrada en un lugar del programa y basta con cambiar esta parte para llevar a cabo la actualizacin. Es ms fcil encontrar dentro del programa, el lugar dnde deben efectuarse las modificaciones. Por ejemplo, inicialmente el mdulo encargado de hacer girar al robot a la izquierda podra utilizar siete giros a derecha pero luego de verlo funcionar, se ve la conveniencia de realizar solo tres giros. Resulta claro ver que hay que ir al mdulo que hace girar al robot y efectuar los cambios all. Si no se utilizara un mdulo con estas caractersticas, seguramente habra varios lugares dentro del programa donde habra que hacer modificaciones, aumentando as la posibilidad de error.
U. N. L. P.
Programacin estructurada
En general, en las soluciones modularizadas, un programa es un mdulo en s mismo denominado programa principal que controla todo lo que sucede y es el encargado de transferir el control a los submdulos de modo que ellos puedan ejecutar sus funciones y resolver el problema. Cada uno de los submdulos al finalizar su tarea, devuelve el control al mdulo que lo llam. Un mdulo puede transferir temporalmente el control a otro mdulo; en cuyo caso, el mdulo llamado devolver el control al mdulo que lo llam, al finalizar su tarea. A continuacin se presenta la sintaxis a utilizar para la definicin de mdulos en el Visual Da Vinci:
proceso nombre del mdulo comenzar fin
{ acciones a realizar dentro del mdulo }
El esquema general de un programa que utilice mdulos y variables es el siguiente:
programa nombre del programa procesos proceso nombre del proceso comenzar fin variables
{indicar aqu TODOS los procesos a utilizar} { acciones a realizar dentro del proceso } { declarar aqu las variables del programa } { acciones del programa principal }
comenzar fin
Ejemplo 6.1: Se desea programar al robot para que recoja todas las flores de la esquina (1,1) y de la esquina (1,2).
Solucin sin modularizar programa Cap5Ejemplo5.1.1 comenzar iniciar mientras HayFlorEnLaEsquina tomarFlor mover mientras HayFlorEnLaEsquina tomarFlor fin Solucin modularizada programa Cap5Ejemplo5.1.2 procesos proceso JuntarFlores comenzar mientras HayFlorEnLaEsquina tomarFlor fin comenzar iniciar JuntarFlores (2) mover JuntarFlores fin U. N. L. P. (3)
(1)
(4) (5) (6)
Introduccin a la Informtica
En la solucin sin modularizar, nos vemos obligados a escribir dos veces el mismo cdigo debido a que la tarea a realizar en las dos esquinas es la misma. En la solucin modularizada, en cambio, nos alcanza con invocar al mdulo JuntarFlores cada vez que se quiera recoger flores en una esquina cualquiera. En este caso particular ser necesario invocar a dicho mdulo dos veces. La ejecucin del programa Cap6Ejemplo6.1.2 (solucin modularizada) comienza por la lnea (1). A continuacin, la instruccin (2) realiza la llamada o invocacin al proceso JuntarFlores. Esto hace que se suspenda la ejecucin del programa principal y el control pase a la lnea (3) donde se encuentra el inicio del proceso. Cuando este termina su ejecucin, el robot habr recogido todas las flores de la esquina y el control volver a la lnea siguiente a la que hizo la invocacin (4). El robot avanzar a la esquina (1,2) y en la lnea (5) se llamar al mismo proceso nuevamente, lo que produce que se vuelva a ejecutar desde (3) nuevamente. Cuando este proceso haya finalizado, el control volver a la lnea (6) y el robot se detendr llevando en su bolsa las flores de las esquinas (1,1) y (1,2). Ejemplo 6.2: Se desea programar al robot para que recorra la avenida 1 juntando todas las flores y los papeles que encuentre. Esto puede simplificarse si se utiliza la metodologa Top-Down ya descripta. Este programa se puede descomponer en mdulos, de modo que exista un mdulo principal y diferentes submdulos como se muestra en la figura 6.2.
Figura 6.2: Diseo Top-Down del ejemplo 6.2 El programa principal sera de la siguiente forma: programa principal Realizar una avenida {Juntar todas las flores de la esquina} {Juntar todos los papeles de la esquina} {Avanzar a la prxima esquina} El programa quedara entonces de la siguiente manera:
U. N. L. P.
Programacin estructurada
programa Cap6Ejemplo6.2 procesos proceso JuntarFlores comenzar mientras HayFlorEnLaEsquina tomarFlor fin proceso JuntarPapeles comenzar mientras HayPapelEnLaEsquina tomarPapel fin comenzar iniciar repetir 99 JuntarFlores JuntarPapeles mover
{Falta juntar las flores y papeles de la ltima esquina}
JuntarFlores JuntarPapeles
fin
Ejemplo 6.3: Se desea programar al robot para que recorra las primeras 10 avenidas juntando todas las flores y los papeles que encuentre.
Figura 6.3: Diseo Top-Down del ejemplo 6.3
U. N. L. P.
Introduccin a la Informtica
Solucin 1 programa Cap6Ejemplo6.3.1 procesos proceso JuntarFlores comenzar mientras HayFlorEnLaEsquina tomarFlor fin proceso JuntarPapeles comenzar mientras HayPapelEnLaEsquina tomarPapel fin comenzar iniciar repetir 10 repetir 99 JuntarFlores JuntarPapeles mover
Solucin 2 programa Cap6Ejemplo6.3.2 procesos proceso JuntarFlores comenzar mientras HayFlorEnLaEsquina tomarFlor fin proceso JuntarPapeles comenzar mientras HayPapelEnLaEsquina tomarPapel fin proceso Avenida comenzar repetir 99 JuntarFlores JuntarPapeles mover
{ltima esquina}
JuntarFlores JuntarPapeles fin comenzar iniciar repetir 10 Avenida Pos (PosAv+1,1) fin
{ltima esquina}
JuntarFlores JuntarPapeles Pos (PosAv+1,1)
fin
Como podemos observar, ambas soluciones resuelven el problema. Sin embargo en la solucin 2, el programa principal resulta ms legible debido a la utilizacin del mdulo Avenida. Por otra parte, hay que destacar que en la solucin 2, desde el mdulo Avenida se est invocando a los mdulos JuntarFlores y JuntarPapeles. Para que el mdulo Avenida pueda invocar correctamente a los mdulos JuntarFlores y JuntarPapeles, estos deben estar previamente declarados. Analice el programa anterior realizando un seguimiento de la invocacin de los procesos involucrados.
U. N. L. P.
Programacin estructurada
Ejemplo 6.4: Se desea programar al robot para que recorra las primeras 50 avenidas juntando las flores de las avenidas pares y los papeles de las avenidas impares. Al finalizar cada avenida debe depositar todos los elementos recogidos. Considere que inicialmente la bolsa est vaca. Al igual que en los ejemplos anteriores, este programa se puede descomponer en mdulos y submdulos. programa principal Recorrido de Avenidas {Realizar avenida impar} {Realizar avenida par} {Posicionamiento para la prxima avenida} Notemos que la complejidad de los mdulos no es la misma. En particular, el ltimo mdulo slo implica reubicar al robot en otra esquina, por lo cual, su refinamiento no es necesario. Si lo consideramos necesario, podemos continuar refinando los mdulos que procesan las avenidas de la siguiente manera: Mdulo Realizar avenida impar {Recorrer la avenida impar juntando papeles} {Depositar los papeles encontrados al finalizar la avenida impar} Mdulo Realizar avenida par {Recorrer la avenida par juntando flores} {Depositar las flores encontradas al finalizar el recorrido} En un nivel ms de refinamiento, estos mdulos pueden volver a descomponerse de la siguiente forma: Submdulo Recorrer la avenida impar juntando papeles {para cada esquina de la avenida impar} { recoger todos los papeles de la esquina} { avanzar una cuadra sobre la avenida impar}
Submdulo Recorrer la avenida par juntando flores {para cada esquina de la avenida par} {recoger todas las flores de la esquina} {avanzar una cuadra sobre la avenida par}
U. N. L. P.
Introduccin a la Informtica
Figura 6.4: Diseo Top-Down del Ejemplo 6.4
La representacin grfica se muestra en la figura 6.4. Puede verse que a nivel de mdulo se considera como elemento de trabajo a la avenida mientras que a nivel de submdulo se hace sobre las esquinas de cada avenida. Recordemos que la descomposicin Top-Down parte del problema general descomponindolo en tareas cada vez ms especficas y el concentrarse en una tarea en particular es ms simple que resolver el problema completo. En el ejemplo, es ms simple resolver una nica avenida par que intentar resolver las 26 avenidas pares en forma conjunta. Lo mismo ocurre con las impares. En la resolucin de este problema pueden utilizarse los procesos JuntarFlores y JuntarPapeles definidos anteriormente. Adems se necesitarn algunos otros mdulos: DejarPapeles, DejarFlores, RealizarAvenidaImpar y RealizarAvenidaPar. A continuacin se presenta el programa completo que resuelve el ejemplo 6.4.
U. N. L. P.
Programacin estructurada
programaCap6Ejemplo4 procesos proceso DejarPapeles comenzar mientras HayPapelEnLaBolsa depositarPapel fin proceso DejarFlores comenzar mientras HayFlorEnLaBolsa depositarFlor fin proceso JuntarFlores comenzar mientras HayFlorEnLaEsquina tomarFlor fin proceso JuntarPapeles comenzar mientras HayPapelEnLaEsquina tomarPapel fin proceso RealizarAvenidaPar comenzar repetir 99 JuntarPapeles mover DejarPapeles fin proceso RealizarAvenidaImpar comenzar repetir 99 JuntarFlores mover DejarFlores fin comenzar repetir 99 JuntarFlores JuntarPapeles mover
{ltima esquina}
JuntarFlores JuntarPapeles fin
U. N. L. P.
Introduccin a la Informtica
comenzar iniciar repetir 26 {En cada pasada recorre dos avenidas: una impar y una par} RecorrerAvenidaImpar Pos(PosAv + 1, 1) RecorrerAvenidaPar Pos(PosAv + 1, 1) fin
{programa principal del ejemplo6.4}
Sobre el ejemplo anterior pueden analizarse los siguientes aspectos: Se han reusado los procesos JuntarFlores y JuntarPapeles evitando de esta manera el tener que volver a pensar e implementar la recoleccin de cada tipo de elemento dentro de una esquina especfica.
Si en el ejemplo 6.2 se hubiera escrito un nico proceso que juntara todos los elementos de la esquina, no hubiera sido posible el reuso mencionado anteriormente. Esto lleva a tratar de escribir mdulos lo suficientemente generales como para que puedan ser aplicados en distintas soluciones. Podemos notar que no todos los submdulos de la figura 6.4 se han convertido en procesos. Esto se debe a que algunos de ellos son lo suficientemente simples como para traducirse en una instruccin del robot. Por ejemplo, Avanzar impar" se traduce en la instruccin mover.
Ejemplo 6.5: Programe al robot para que recorra el permetro del cuadrado determinado por (1,1) y (2,2). Al terminar debe informar cuntos de los vrtices estaban vacos. Para resolverlo es conveniente comenzar a analizar las distintas partes que componen el problema: Programa principal {Analizar el vrtice y registrar si esta vaco} {Avanzar 1 cuadra} {Girar a la izquierda} {Informar lo pedido} Las primeras tres acciones se repiten cuatro veces para poder dar vuelta al cuadrado y la ltima se realiza cuando el robot ha terminado de recorrer el permetro. Note que la descomposicin en mdulos del problema no busca representar flujo de control del programa. En otras palabras, las estructuras de control no se encuentran reflejadas en la metodologa Top-Down. Slo se indican las partes necesarias para resolverlo, de manera de dividir el trabajo en tareas ms sencillas. La unin de estos
U. N. L. P.
Programacin estructurada
mdulos, para hallar la solucin, es una tarea posterior. Por este motivo, tampoco se repiten los mdulos dentro de la descomposicin planteada. Todas las tareas indicadas en la descomposicin anterior son lo suficientemente simples como para ser implementadas directamente. Una solucin al problema podra ser la siguiente:
programa Cap6Ejemplo6.5 variables vacias : numero comenzar iniciar derecha vacias := 0 repetir 4 {Analizar el vrtice y registrar si esta vaco} si ~ HayFlorEnLaEsquina & ~HayPapelEnLaEsquina vacias := vacias + 1 mover {Girar a la izquierda} repetir 3 derecha Informar (vacias) fin
Sin embargo, sera importante contar con un proceso que permitiera indicar al robot girar izquierda con la misma facilidad con que se indica que gire a derecha. Esto hara ms legible los programas ya que el programa anterior podra escribirse de la siguiente forma:
programa Cap6Ejemplo6.5 procesos variables vacias : numero comenzar iniciar derecha vacias := 0 repetir 4
{Inserte aqu la definicin del proceso izquierda}
si ~HayFlorEnLaEsquina & ~HayPapelEnLaEsquina vacias := vacias + 1 mover izquierda Informar (vacias) fin
{Analizar el vrtice y registrar si est vaco}
U. N. L. P.
Introduccin a la Informtica
Queda como ejercicio para el lector la definicin del proceso izquierda. Una vez que haya incorporado a la solucin anterior el proceso izquierda, indique la cantidad de veces que el robot gira a la derecha para completar el recorrido.
Ejemplo 6.6: Dados los recorridos de la figura 6.6 Cul es el mdulo que sera conveniente tener definido?
Figura 6.6: Recorridos Como podemos observar todos los cuadrados tienen lado 2, entonces convendra tener definido un mdulo que permita realizar un cuadrado de lado 2 ya que puede utilizarse en los cuatro recorridos. Como muestra la figura 6.6 cada recorrido consiste en realizar varios cuadrados de lado 2 con el robot posicionado en lugares diferentes. El mdulo a utilizar puede escribirse de la siguiente forma:
proceso cuadrado {encabezado del proceso} comenzar repetir 4 {el cuadrado tiene 4 lados} repetir 2 mover derecha fin
En este momento puede apreciarse una de las principales ventajas de la modularizacin. Esta implementacin del proceso cuadrado es independiente del recorrido en el cual ser utilizado. Es ms, este proceso puede ser verificado de manera totalmente independiente de la aplicacin final.
U. N. L. P.
Programacin estructurada
El programador encargado de su desarrollo podra escribir el siguiente programa para verificar su funcionamiento:
programa prueba procesos proceso cuadrado comenzar repetir 4 repetir 2 mover derecha fin comenzar iniciar Pos(2,1) cuadrado fin
Una vez que se ha verificado que el funcionamiento del proceso cuadrado es correcto, su
programador lo ubicar en un lugar comn donde todos aquellos que lo requieran lo puedan acceder. Ahora, los usuarios del proceso cuadrado no slo no tendrn la necesidad de implementar este recorrido sino que adems cuentan con un proceso que funciona correctamente porque ya fue verificado previamente. En este sentido, el Visual Da Vinci presenta algunas limitaciones ya que los interesados en el mdulo debern insertarlo dentro de su programa. Sin embargo, esto no es as en la mayora de los lenguajes y este aspecto no debera invalidar las ventajas de la modularizacin. Los siguientes programas resuelven el recorrido a) de la figura 6.5:
programa RecorridoA- version1 procesos proceso cuadrado comenzar repetir 4 repetir 2 mover derecha fin comenzar iniciar Pos(2,1) cuadrado Pos(5,1) cuadrado Pos(8,1) cuadrado programa RecorridoA-version2 procesos proceso cuadrado comenzar repetir 4 repetir 2 mover derecha fin comenzar iniciar Pos(2,1) repetir 3 cuadrado Pos(PosAv+3,1) fin
fin
U. N. L. P.
Introduccin a la Informtica
Una de las diferencias entre estas soluciones es que el programa RecorridoA-version1 utiliza solo la secuencia mientras que RecorridoA version2 utiliza la estructura de control repetir. En ambos casos aparecen tres invocaciones al proceso cuadrado con el robot ubicado en una esquina distinta. El mdulo Cuadrado tiene las siguientes caractersticas: 1. El cuadrado tiene como vrtice inferior izquierdo la esquina donde el robot esta posicionado al momento de la invocacin. 2. Una vez terminado el cuadrado, el robot vuelve a quedar parado en la misma esquina y orientado en el mismo sentido que cuando se comenz la ejecucin del mdulo. Justifique las siguientes afirmaciones: Para que el programa RecorridoA-version1 funcione correctamente slo es preciso conocer la primera de estas caractersticas. En cambio, para que el programa RecorridoA-version2 funcione correctamente se requieren las dos.
A continuacin se presentan dos soluciones para el recorrido de la figura 6.6 b), una de ellas utiliza el modulo cuadrado y la otra no.
programa RecorridoB version1 procesos comenzar { proceso cuadrado} iniciar repetir 3 cuadrado Pos(PosAv+1, PosCa+2) fin
programa RecorridoB version2 comenzar iniciar repetir 3 {aqu comienza el cuadrado} repetir 4 mover mover derecha Pos(PosAv+1,PosCa+2) fin
El programa RecorridoB version1 utiliza el proceso que realiza el cuadrado de lado 2, mientras que el programa RecorridoB version2 ha sido implementado igual que los ejercicios de los captulos anteriores, es decir, sin utilizar ningn proceso. Estos dos programas muestran algunos aspectos importantes: 1. El uso de la modularizacin no es obligatorio. En los captulos anteriores se han resuelto problemas similares al del recorrido b) sin utilizar procesos. La metodologa
U. N. L. P.
Programacin estructurada
Top-Down no pretende afirmar que aquellas soluciones fueron incorrectas. Slo muestra una forma alternativa que debera facilitar el diseo y desarrollo de los programas. 2. Si se presta atencin al programa RecorridoB version1, puede verse que su implementacin slo se preocupa por posicionar al robot para formar el recorrido pedido. Mientras tanto, el programa RecorridoB version2 debe resolver ambos problemas: posicionar al robot y hacer el cuadrado. 3. Al proceso RecorridoB version1 no le preocupa cmo se hace el cuadrado. Da lo mismo que lo haga girando en el sentido de las agujas del reloj o girando en sentido contrario. En cambio el otro programa debe indicar claramente cmo hacer todo el recorrido. 4. Si en el futuro el robot contara con nuevas habilidades que le permitieran hacer el cuadrado de forma ms eficiente (por ejemplo, algn da podra aprender a correr) los programas que utilizan el mdulo cuadrado slo tendrn que hacer referencia a la nueva implementacin. Mientras tanto, los programas que hayan implementado explcitamente, en su interior, el recorrido para hacer el cuadrado de lado 2 debern ser modificados uno por uno. Quedan a cargo del lector las implementaciones de los programas que permitan al robot realizar los recorridos c y d. Ejemplo 6.7: Programe al robot para realizar el recorrido de la figura 6.7. Como puede apreciarse en el dibujo, el problema consiste en programar al robot para que de la vuelta a cada una de las manzanas indicadas. Como se explic anteriormente, el uso de la metodologa Top-Down no es obligatorio pero, si se opta por no utilizarla, habr que enfrentar la solucin del problema como un todo y el recorrido a realizar ya no es tan simple.
Figura 6.7: Recorrido del Ejemplo 6.7
U. N. L. P.
Introduccin a la Informtica
Si se descompone el problema puede pensarse en cinco torres de cinco cuadrados cada una. Si se logra resolver una de las torres, luego solo habr que repetir el proceso cinco veces. La figura 6.7 muestra la descomposicin Top-Down del problema.
Figura 6.7: Descomposicin Top-Down del Ejemplo 6.5 Si HacerTorre es el proceso que realiza una secuencia de cinco cuadrados como los de la figura 6.7, el programa principal podra escribirse de la siguiente forma:
programa Cap6Ejemplo6.7 procesos
comenzar iniciar repetir 5 HacerTorre {sucesin de cuadrados de la avenida } Pos(PosAv+2, 1) {posicin de inicio de la prox. torre} fin
{Insertar aqu el proceso Torre}
Para implementar cada torre de cinco cuadrados puede aplicar la misma metodologa de descomposicin del problema. Cada torre no es ms que llamar cinco veces a un proceso que realice un cuadrado de lado 1. El cdigo podra ser el siguiente:
proceso Torre comenzar repetir 5 HacerCuadrado Pos(PosAv, PosCa+2) fin U. N. L. P.
Programacin estructurada
Como puede verse en el cdigo anterior, el proceso HacerTorre realiza los cinco cuadrados a partir de la posicin donde el robot se encuentra parado. Cada cuadrado de lado 1 tendr su esquina inferior izquierda apoyada sobre la misma avenida. Notemos que para usar el proceso HacerCuadrado slo importa saber que se realiza tomando como esquina inferior izquierda del cuadrado de lado 1, la esquina donde el robot est parado al momento de la invocacin. A continuacin se muestra el programa implementado en Visual Da Vinci:
programa Cap6Ejemplo6.7 procesos proceso HacerCuadrado comenzar repetir 4 mover derecha fin proceso HacerTorre comenzar repetir 5 HacerCuadrado Pos(PosAv, PosCa+2) fin comenzar iniciar repetir 5 HacerTorre Pos(PosAv+2,1) fin
(3)
(1) (2)
Es importante destacar que la ejecucin del algoritmo comienza en el punto indicado con el nmero (1). Cuando el control llega a la invocacin del proceso HacerTorre, indicada por (2), el algoritmo contina ejecutndose en dicho proceso. Cuando llega al punto (3), es decir la invocacin de HacerCuadrado, se suspende la ejecucin del proceso HacerTorre y se realiza la primera vuelta a la manzana a partir de (1,1). Luego retorna a la instruccin siguiente de (3), posicionndose en la esquina (1,3), listo para hacer el prximo cuadrado. Esto se repite cinco veces. Una vez terminada la torre, el robot queda parado en (1,11). En ese momento el proceso HacerTorre termina y retorna a la instruccin siguiente de (2), posicionndose en la prxima avenida impar, listo para comenzar la segunda torre. Esto se repite cuatro veces ms y el recorrido finaliza.
Dnde queda parado el robot al final del recorrido?
Ejemplo 6.8: Escriba el proceso Evaluar para que el robot recoja todos los papeles y las flores de la esquina donde se encuentra y deje una flor en caso de haber ms flores que papeles; un papel, si hay ms papeles que flores uno de cada uno en caso contrario.
U. N. L. P.
Introduccin a la Informtica
Los pasos a seguir para implementar este proceso son los siguientes:
proceso Evaluar
{contar la cantidad de flores} { contar la cantidad de papeles} si {hay ms flores que papeles} {depositar una flor (si es que hay en la bolsa)}
sino si {la cantidad de flores y papeles es la misma } sino
{depositar uno de cada uno (si es que hay en la bolsa)} {depositar una flor (si es que hay en la bolsa)}
La implementacin del proceso Evaluar en Visual Da Vinci ser: proceso Evaluar variables CantF: numero CantP: numero comenzar
{cuenta las flores}
CantF := 0 mientras HayFlorEnLaEsquina tomarFlor CantF := CantF + 1
{cuenta los papeles} CantP := 0 mientras HayPapelEnLaEsquina tomarPapel CantP := CantP + 1 si CantF > CantP si HayFlorEnLaBolsa depositarFlor sino si cantF = cantP si HayFlorEnLaBolsa & HayPapelEnLaBolsa depositarPapel depositarFlor sino si HayPapelEnLaBolsa depositarPapel fin
{decide que depositar}
Como se puede observar en el ejemplo planteado, el mdulo Evaluar utiliza dos variables propias para representar la cantidad de flores y papeles que hay en una esquina de la ciudad.
U. N. L. P.
Programacin estructurada
Los valores de estas variables permiten tomar posteriormente una decisin. Es importante destacar que estas variables slo son tiles para el mdulo y no son conocidas fuera del mismo. Analice el comportamiento del proceso Evaluar cuando se trata de una esquina vaca Cules son las proposiciones atmicas que se evalan? Qu pasa si en la bolsa slo tiene papeles?
Ejemplo 6.9: Programe al robot para que aplique el proceso Evaluar a cada una de las esquinas de la ciudad. Tengamos en cuenta que para recorrer cada una de las esquinas de la ciudad, basta con recorrer todas las calles todas las avenidas. Cualquiera de estos recorridos nos asegura que el robot pasa por todas las esquinas de la ciudad. El diseo Top-Down para la solucin de este problema puede ser:
Figura 6.8: Descomposicin Top-Down del Ejemplo 6.9
programa Cap6Ejemplo6.9 procesos {Inserte aqu el proceso evaluar definido anteriormente} Proceso RecorrerCalle comenzar repetir 99 Evaluar mover Evaluar {esquina 100} fin comenzar iniciar derecha repetir 99 RecorrerCalle Pos(1, PosCa+1) {ltima calle} RecorrerCalle Fin U. N. L. P.
Introduccin a la Informtica
Esta solucin recorre cada calle usando el mdulo RecorrerCalle. Para cada calle se recorren todas sus esquinas ejecutando el mdulo Evaluar. Notemos que en el mdulo RecorrerCalle no se hace ninguna referencia a las variables usadas en el mdulo Evaluar, como as tampoco en el cuerpo del programa principal.
6.3 Conclusiones
En este captulo se ha presentado una metodologa que ayuda a disear soluciones a problemas ms complejos basada en la descomposicin del problema original en subproblemas ms sencillos. En particular se han ejemplificado las siguientes ventajas: La descomposicin realizada facilita la implementacin del programa ya que las partes a desarrollar son mucho ms simples que el todo. El programa principal, encargado de invocar los mdulos, es ms fcil de leer e interpretar. La existencia de procesos permite reusar cdigo escrito anteriormente. Esto tiene la ventaja no slo de no tener que volver a analizarlo y reescribirlo sino que se asegura que su funcionamiento ser el adecuado.
U. N. L. P.
Programacin estructurada
Ejercitacin
1. Escriba un proceso que le permita al robot realizar un cuadrado de lado 2 girando en la direccin de las agujas del reloj. 2. Utilice el proceso desarrollado en 1. para realizar un programa para cada uno de los recorridos de la figura 6.9.
Figura 6.9: Recorridos usando cuadrados de lado 2
3. Escriba un proceso que le permita al robot realizar un rectngulo de base 5 y altura 3 girando en la direccin de las agujas del reloj a partir de la posicin (1,1). 4. Programe al Robot para que realice los recorridos de la figura 6.10 utilizando el proceso desarrollado en 3.
Figura 6.10: Recorridos usando rectngulos de 5x3.
U. N. L. P.
Introduccin a la Informtica
5. Rehacer el recorrido del ejercicio 4.c) trasladando los papeles de cada esquina correspondientes a un lado del rectngulo al vrtice siguiente en el recorrido. Por ejemplo, para el rectngulo con vrtice en (1,1), los papeles de (1,2) y (1,3) deben ser trasladados a (1,4); los de la calle 4 entre las avenidas 2 y 5 deben ser reubicados en (6,4); y as siguiendo. 6. (a) Escriba un proceso que le permita al robot realizar un rectngulo de base 5 y altura 3 girando en la direccin contraria a la de las agujas del reloj. (b) Indique si se produce alguna modificacin en los procesos de los ejercicios 4 y 5 si se reemplaza el mdulo realizado en 3 por el implementado en 6.a. 7. Realice un programa que le permita al robot recorrer las calles pares de la ciudad. Al finalizar cada calle debe informar si la calle tuvo ms papeles que flores. LAS ESQUINAS NO DEBEN SE MODIFICADAS. MODULARICE. 8. (a) Escriba el proceso LimpiarEsquina que le permita al robot recoger todas las flores y todos los papeles de la esquina donde se encuentra parado. (b) Escriba un programa que le permita al robot recoger todas las flores y papeles de la avenida 56, utilizando los procesos implementados en 7a). (c) Modifique el proceso 6.a) para que el robot realice el rectngulo indicado dejando a su paso todas las esquinas vacas. Para hacerlo debe utilizar el proceso LimpiarEsquina. (e) Rehacer el recorrido 4.b) utilizando el proceso definido en 7.c) [Link] al robot para que recorra la ciudad de la siguiente manera: primero debe recorrer la avenida 1 juntando todas las flores que encuentre, luego debe recorrer la calle 1 juntando todos los papeles que encuentre. Luego recorre la avenida 2 y la calle 2 de la misma manera y as siguiendo. Implemente un mdulo para recorrer la avenida y otro mdulo para recorrer la calle. 10. Realice un programa que le permita al robot recorrer todas las avenidas pares de la ciudad. Cada avenida debe recorrerse hasta juntar 27 flores, que pueden no existir, adems cuando se termina de recorrer cada avenida debe informarse la cantidad de papeles juntados en el recorrido de la misma. MODULARICE.
U. N. L. P.
