Gua

UNIVERSIDAD DE LA CAADA

Primer rimer concurso de programacin Gua

2011

M. C. Silviana Jurez Chalini M. C. Beatriz Adriana Sabino Moxo M. C. Jos Alberto Mrquez Domnguez

Carretera Teotitln - San Antonio Nanahuatipn Km 1.7 s/n. Paraje Titlacuatitla. Teotitln de Flores Magn, Oax. Mxico, C.P. 68540

CONTENIDO

INTRODUCCIN.................................................................................................................................. 4 FASES PARA LA RESOLUCIN DE PROBLEMAS............................................................................................. 5 Anlisis del Problema ................................................................................................................. 5 Diseo del Algoritmo.................................................................................................................. 7 KAREL.............................................................................................................................................. 8 El mundo de Karel ...................................................................................................................... 8 Instrucciones Bsicas de Karel .................................................................................................... 8 NIVEL 1: BSICO ................................................................................................................................ 9 Ejercicios Resueltos .................................................................................................................... 9 Ejercicios Propuestos ............................................................................................................... 28 NIVEL 3: AVANZADO ......................................................................................................................... 35 Ejercicios Resueltos .................................................................................................................. 35 Ejercicios Propuestos ............................................................................................................... 48 BIBLIOGRAFA .................................................................................................................................. 52

INTRODUCCIN
Karel es un lenguaje de programacin muy reducido que fue inventado por el Prof. Richard Patis del Departamento de Ciencias de la Computacin, en la Universidad de Carnegie Mellon, USA. A diferencia de muchos lenguajes de programacin, Karel no se enfoca al clculo de complejas expresiones, asignacin de valores a variables o creacin de poderosas aplicaciones. Ms bien es un lenguaje orientado a la resolucin de tareas en un ambiente simulado por medio de la manipulacin de un robot llamado Karel. En el ambiente simulado vive un robot de nombre Karel (el cual le da el nombre al lenguaje de programacin), que recibe su nombre del escritor checo Karel Capek, el primero en la historia en usar el trmino robot en uno de sus libros. Este lenguaje ha resultado ser un excelente mtodo para introducir a los jvenes a la programacin de computadoras. Al limitar el repertorio del lenguaje del estudiante, y por medio del empleo de refuerzos visuales de las consecuencias de los comandos ms comnmente utilizados, el concepto de Karel rpidamente introduce a los estudiantes a los conceptos de procedimiento y estructuras de control.

FASES PARA LA RESOLUCIN DE PROBLEMAS

Las fases o etapas constituyen el ciclo de vida del software, ayudarn en el proceso de resolucin de un problema, estas consisten en: 1. 2. 3. 4. 5. 6. 7. 8. Anlisis del problema. Diseo del algoritmo. Codificacin (Implementacin). Compilacin y ejecucin. Verificacin Depuracin. Mantenimiento. Documentacin.

Las dos primeras etapas conducen a un diseo detallado escrito de forma de algoritmo1. Durante la tercera etapa (Codificacin) se implementa el algoritmo en un cdigo escrito en un lenguaje de programacin reflejando las ideas desarrolladas en las fases de anlisis y diseo [Joyanes, 2003]. La Compilacin, Ejecucin y Verificacin realiza la traduccin y ejecucin del programa, se comprueba rigurosamente y se eliminan todos los errores que pueda tener. Si existen errores es necesario modificarlo y actualzalo de manera que cumplan todas las necesidades de cambio de sus usuarios, para ello se usan las etapas de Verificacin y Depuracin. Finalmente se debe usar la fase de Documentacin, es decir, es la escritura de las diferentes fases del ciclo de vida del software, esencialmente el anlisis, diseo y codificacin, unidos a manuales de usuario y de referencia, as como normas para el mantenimiento. En este concurso se pondrn a prueba las cuatro primeras fases, aunque se recomienda realizar las fases faltantes para terminar con el ciclo de vida del software.

Anlisis del Problema

En esta fase se requiere una clara definicin del problema, para poder hacer esto es conveniente realizar las siguientes preguntas: 1. Qu entradas se requieren? (tipo y cantidad) 2. Cul es la salida deseada? (tipo y cantidad) 3. Qu mtodo produce la salida deseada? Con dichas preguntas se determina qu necesita el programa para resolver el problema. La solucin puede llevarse a cabo mediante varios algoritmos [Joyanes, 2004]. Un algoritmo dado correctamente resuelve un problema definido y determinado. El algoritmo debe cumplir diferentes propiedades: 1. Especificacin precisa de la entrada. Se debe dejar claro el nmero y tipo de valores de entrada y las condiciones iniciales que deben cumplir dichos valores.

Definido como un conjunto de instrucciones utilizadas para resolver un problema especfico.

2. Especificacin precisa de cada instruccin. No debe haber ambigedad sobre las acciones que se deben ejecutar en cada momento. 3. Exactitud, correccin. Si debe mostrar que el algoritmo resuelva el problema. 4. Etapas bien definidas y concretas. Concreto quiere decir que la accin descrita por esa etapa est totalmente comprendida por la persona o mquina que debe ejecutar el algoritmo. Cada etapa debe ser ejecutable en una cantidad finita de tiempo. 5. Nmero finito de pasos. Un algoritmo se debe componer de un nmero finito de pasos. 6. Un algoritmo debe terminar. En otras palabras, no debe entrar en un ciclo infinito. 7. Descripcin del resultado o efecto. Debe estar claro cul es la tarea que el algoritmo debe ejecutar. La mayora de las veces, esta condicin se expresa con la produccin de un valor como resultado que tenga ciertas propiedades. Ejemplo 1 Es un algoritmo la siguiente instruccin? Problema: Escribir una lista de todos los enteros positivos Solucin: Es imposible ejecutar la instruccin anterior dado que hay infinitos enteros positivos. Ejemplo 2 Problema: Calcular la paga neta de un trabajador conociendo el nmero de horas trabajadas, la tarifa horaria y la tasa de impuestos. Solucin: Debemos definir el problema. 1. Qu datos de entrada se requieren? Nmero de horas trabajadas Tarifa Impuestos 2. Cul es la salida deseada? Paga Neta 3. Cul es el mtodo a usar? (Algoritmo) Inicio Leer Nmero de horas trabajadas Leer Tarifa Leer Impuestos Calcular Paga Bruta = Nmero de horas trabajadas * Tarifa Calcular Impuestos = Paga Bruta * Tasa Calcular Pago Neta = Paga Bruta Impuestos Visualizar Paga Bruta Visualizar Impuestos Visualizar Pago Neta Fin

Diseo del Algoritmo

En esta fase, como se ha mencionado anteriormente, se determina cmo hace el programa la tarea solicitada. Los mtodos ms eficaces para el proceso de diseo se basan en el conocido divide y vencers, esto es dividiendo el problema en subproblemas y a continuacin dividir estos subproblemas en otros de nivel ms bajo hasta que pueda ser implementada la solucin. Existen diferentes herramientas de programacin, las ms utilizadas para disear algoritmos son: 1. Diagramas de flujo: Es una representacin grfica de un algoritmo. Los smbolos normalizados por el Instituto Norteamericano de Normalizacin (ANSI) y los ms frecuentes empleados se muestran a continuacin.

2. Pseudocdigo: Es una herramienta de programacin en la que las instrucciones se escriben en palabras similares en ingls o espaol, que facilitan tanto la escritura como la lectura de programas.

KAREL
El mundo de Karel
Karel es un robot que podemos controlar por medio de un programa para que realice cierto trabajo. El mundo de Karel consta de los siguientes elementos: Calles (horizontales) y avenidas (verticales) que se cruzan en esquinas. Paredes impenetrables colocadas entre dos esquinas. Zumbadores removibles colocados en las esquinas que emiten un sonido (su grosor es irrelevante). Bolsa de zumbadores que Karel lleva consigo.

Karel siempre est en una esquina y mirando al norte, sur, este u oeste. A travs de tres cmaras puede ver si se encuentra una pared entre l y las esquinas ms cercanas (enfrente, a su derecha y a su izquierda). Su odo le permite detectar el sonido de beepers en la esquina donde se encuentra. La manera de comunicarse con Karel es por medio de un programa. El problema principal es que lo nico que Karel puede hacer es seguir lo que le indiquemos "al pi de la letra". Karel no piensa y no puede darse cuenta de lo que queremos que haga si no sabemos cmo decrselo, para eso es necesario aprender su lenguaje.

Instrucciones Bsicas de Karel

Realizar un trabajo o tarea especfica con Karel consiste en llevarlo de una situacin original a una final a travs de la ejecucin de instrucciones avanza. Hace un paso en la direccin que est apuntando (puede causar error si hay una pared enfrente). gira-izquierda. Gira a su izquierda 90 (siempre se puede). coge-zumbador. Recoge un zumbador de la esquina donde est parado (puede causar error si no hay ningn zumbador en la esquina). deja-zumbador: Deposita un zumbador en la esquina (puede causar error si la bolsa de zumbadores de Karel est vaca). Apgate. Es el comando que finaliza y apaga a Karel.

Nota: Las nuevas funciones deben tener diferentes nombres y NO llamarse igual a una de las funciones bsicas.

NIVEL 1: BSICO

Ejercicios Resueltos
Problema 1. Karel se encuentra en su casa (posicin 1,1 viendo hacia el este), se ha dado cuenta que es hora de ir a recoger a su hermana a su escuela (posicin 8,3), su misin es ir por ella y regresar juntos a casa.

Estado inicial, Karel tiene 0 zumbadores Programa iniciar-programa inicia-ejecucion avanza; avanza; avanza; avanza; avanza; avanza; avanza; gira-izquierda; avanza; avanza; coge-zumbador; gira-izquierda; avanza; avanza; avanza; avanza; avanza; avanza; avanza; gira-izquierda; avanza; 9

Estado final, Karel tiene 1 zumbador y en la posicin inicial

avanza; apagate; termina-ejecucion finalizar-programa Problema 2. En un da de compras, Karel sale de su casa (posicin 1,1) y se dirige a obtener los siguientes productos: leche, pan, huevo y carne, cada uno en diferentes establecimientos, al final regresa a casa con todas sus compras En el mundo de Karel los establecimientos donde venden esos productos estn en las siguientes posiciones: o Leche: posicin (5, 5). o Pan: posicin (9, 11). o Huevo: posicin (16, 6). o Carne: posicin (8, 3).

Estado inicial, Karel tiene 0 zumbadores Programa iniciar-programa inicia-ejecucion avanza; avanza; avanza; avanza; gira-izquierda; avanza; avanza; avanza; avanza; coge-zumbador; gira-izquierda; gira-izquierda; gira-izquierda; avanza; avanza; 10

Estado final, Karel tiene 4 zumbadores y en la posicin inicial

avanza; gira-izquierda; gira-izquierda; gira-izquierda; avanza; avanza; coge-zumbador; gira-izquierda; avanza; gira-izquierda; avanza; avanza; avanza; avanza; avanza; avanza; avanza; avanza; coge-zumbador; gira-izquierda; gira-izquierda; gira-izquierda; avanza; avanza; avanza; avanza; avanza; avanza; avanza; gira-izquierda; gira-izquierda; gira-izquierda; avanza; avanza; avanza; avanza; avanza; coge-zumbador; avanza; avanza; avanza; avanza; avanza; gira-izquierda; gira-izquierda; gira-izquierda; avanza; avanza; 11

avanza; avanza; avanza; avanza; avanza; avanza; avanza; avanza; avanza; avanza; avanza; avanza; avanza; deja-zumbador; deja-zumbador; deja-zumbador; deja-zumbador; apagate; termina-ejecucion finalizar-programa

Problema 3. Es el da de compras, Karel tiene que ir por los productos de siempre, sin embargo algunas calles estn cerradas, por lo que tiene que tomar vas alternas. Los establecimientos estn en las mismas posiciones.

Estado inicial, Karel tiene 0 zumbadores Programa iniciar-programa inicia-ejecucion avanza; avanza; avanza; gira-izquierda; 12

Estado final, Karel tiene 4 zumbadores y en la posicin inicial

avanza; avanza; avanza; avanza; gira-izquierda; gira-izquierda; gira-izquierda; avanza; coge-zumbador; avanza; gira-izquierda; gira-izquierda; gira-izquierda; avanza; avanza; gira-izquierda; avanza; avanza; coge-zumbador; gira-izquierda; avanza; avanza; avanza; avanza; avanza; avanza; avanza; avanza; gira-izquierda; gira-izquierda; gira-izquierda; avanza; coge-zumbador; avanza; avanza; gira-izquierda; gira-izquierda; gira-izquierda; avanza; avanza; avanza; avanza; avanza; gira-izquierda; avanza; avanza; avanza; avanza; 13

avanza; coge-zumbador; gira-izquierda; gira-izquierda; gira-izquierda; avanza; avanza; avanza; avanza; avanza; gira-izquierda; gira-izquierda; gira-izquierda; avanza; avanza; avanza; avanza; avanza; avanza; avanza; avanza; avanza; avanza; avanza; avanza; avanza; avanza; avanza; deja-zumbador; deja-zumbador; deja-zumbador; deja-zumbador; apagate; termina-ejecucion finalizar-programa

Problema 4. Karel tiene una mascota que se le ha escapado en varias ocasiones, preocupado porque la ltima vez le cost mucho trabajo encontrarlo, decidi encerrarlo (utilizando 8 zumbadores) para que no se volviera a escapar.

14

Estado inicial Programa iniciar-programa inicia-ejecucion gira-izquierda; gira-izquierda; avanza; avanza; avanza; deja-zumbador; gira-izquierda; avanza; deja-zumbador; gira-izquierda; gira-izquierda; gira-izquierda; avanza; deja-zumbador; avanza; deja-zumbador; gira-izquierda; gira-izquierda; gira-izquierda; avanza; deja-zumbador; avanza; deja-zumbador; gira-izquierda; gira-izquierda; gira-izquierda; avanza; deja-zumbador; avanza; deja-zumbador; avanza; 15

Estado final

apagate; termina-ejecucion finalizar-programa Problema 5. Karel tiene una mascota que se le ha escapado en varias ocasiones, preocupado porque la ltima vez le cost mucho trabajo encontrarlo, decidi encerrarlo (utilizando 8 zumbadores) para que no se volviera a escapar, esta vez el perro estar en el jardn trasero de su casa y para llegar hasta all tiene que pasar por varios obstculos.

Estado inicial Programa iniciar-programa inicia-ejecucion gira-izquierda; gira-izquierda; avanza; gira-izquierda; gira-izquierda; gira-izquierda; avanza; avanza; gira-izquierda; gira-izquierda; gira-izquierda; avanza; gira-izquierda; avanza; avanza; gira-izquierda; avanza; gira-izquierda; gira-izquierda; 16

Estado final

gira-izquierda; avanza; gira-izquierda; avanza; avanza; gira-izquierda; gira-izquierda; gira-izquierda; avanza; deja-zumbador; gira-izquierda; avanza; deja-zumbador; gira-izquierda; gira-izquierda; gira-izquierda; avanza; deja-zumbador; avanza; deja-zumbador; gira-izquierda; gira-izquierda; gira-izquierda; avanza; deja-zumbador; avanza; deja-zumbador; gira-izquierda; gira-izquierda; gira-izquierda; avanza; deja-zumbador; avanza; deja-zumbador; apagate; termina-ejecucion finalizar-programa Problema 6. Karel tiene una mascota que se le ha escapado en varias ocasiones, esta vez lo volvi a hacer, un vecino le avis que su mascota estaba en el parque de la ciudad, la misin de Karel es ir por l , regresarlo a su casa y encerrarlo para que no se vuelva a escapar. La casa de Karel es rectangular delimitado por paredes. Karel inicia apuntando hacia el este en la esquina inferior izquierda de su casa.

17

Estado inicial Programa iniciar-programa inicia-ejecucion avanza; gira-izquierda; avanza; avanza; avanza; gira-izquierda; gira-izquierda; gira-izquierda; avanza; avanza; gira-izquierda; avanza; gira-izquierda; gira-izquierda; gira-izquierda; avanza; avanza; gira-izquierda; avanza; gira-izquierda; gira-izquierda; gira-izquierda; avanza; avanza; gira-izquierda; avanza; avanza; avanza; coge-zumbador; gira-izquierda; 18

Estado final

gira-izquierda; avanza; avanza; avanza; gira-izquierda; gira-izquierda; gira-izquierda; avanza; avanza; gira-izquierda; gira-izquierda; gira-izquierda; avanza; avanza; avanza; avanza; gira-izquierda; avanza; avanza; avanza; avanza; gira-izquierda; avanza; avanza; avanza; avanza; avanza; avanza; avanza; avanza; avanza; gira-izquierda; gira-izquierda; gira-izquierda; avanza; avanza; gira-izquierda; gira-izquierda; gira-izquierda; avanza; avanza; gira-izquierda; gira-izquierda; gira-izquierda; avanza; gira-izquierda; avanza; avanza; 19

gira-izquierda; avanza; gira-izquierda; gira-izquierda; gira-izquierda; avanza; gira-izquierda; avanza; avanza; gira-izquierda; gira-izquierda; gira-izquierda; avanza; avanza; deja-zumbador; gira-izquierda; gira-izquierda; avanza; deja-zumbador; gira-izquierda; gira-izquierda; gira-izquierda; avanza; deja-zumbador; gira-izquierda; gira-izquierda; gira-izquierda; avanza; deja-zumbador; avanza; deja-zumbador; gira-izquierda; gira-izquierda; gira-izquierda; avanza; deja-zumbador; avanza; deja-zumbador; gira-izquierda; gira-izquierda; gira-izquierda; avanza; deja-zumbador; avanza; deja-zumbador; apagate; termina-ejecucion finalizar-programa 20

Problema 7. Karel debe recoger los 5 zumbadores que se encuentran en la calle 1 del mundo.

Estado inicial, Karel tiene 0 zumbadores Programa iniciar-programa inicia-ejecucion gira-izquierda; gira-izquierda; gira-izquierda; avanza; coge-zumbador; avanza; coge-zumbador; avanza; coge-zumbador; avanza; coge-zumbador; avanza; coge-zumbador; apagate; termina-ejecucion finalizar-programa

Estado final, Karel tiene 5 zumbadores

Problema 8. Karel se encuentra en alguna esquina de su mundo, con 8 o ms zumbadores en su bolsa, se necesita que deje las chicharras en las esquinas de su alrededor.

Estado inicial, Karel tiene 0 zumbadores

Estado final, Karel tiene 0 zumbadores, todas ellas puestas alrededor en la posicin (8,1)

21

Programa iniciar-programa inicia-ejecucion gira-izquierda; gira-izquierda; gira-izquierda; avanza; coge-zumbador; avanza; coge-zumbador; avanza; coge-zumbador; avanza; coge-zumbador; avanza; coge-zumbador; avanza; coge-zumbador; avanza; coge-zumbador; avanza; coge-zumbador; gira-izquierda; avanza; deja-zumbador; avanza; deja-zumbador; gira-izquierda; avanza; deja-zumbador; avanza; deja-zumbador; gira-izquierda; avanza; deja-zumbador; avanza; gira-izquierda; avanza; gira-izquierda; avanza; apagate; termina-ejecucion finalizar-programa

22

Problema 9. Karel se encuentra frente a una montaa, debe conquistar el punto ms alto y dejar una bandera. La bandera estar representada por un zumbador.

Estado inicial, Karel debe dejar un zumbador

Estado final, Karel ha dejado su bandera y se encuentra en la posicin (10,1)

Programa iniciar-programa inicia-ejecucion gira-izquierda; gira-izquierda; gira-izquierda; avanza; gira-izquierda; avanza; gira-izquierda; gira-izquierda; gira-izquierda; avanza; gira-izquierda; avanza; gira-izquierda; gira-izquierda; gira-izquierda; avanza; avanza; gira-izquierda; avanza; avanza; avanza; avanza; gira-izquierda; gira-izquierda; gira-izquierda; avanza; deja-zumbador; avanza; gira-izquierda; 23

gira-izquierda; gira-izquierda; avanza; avanza; gira-izquierda; avanza; gira-izquierda; gira-izquierda; gira-izquierda; avanza; avanza; avanza; gira-izquierda; avanza; avanza; gira-izquierda; gira-izquierda; gira-izquierda; avanza; apagate; termina-ejecucion finalizar-programa Problema 10. Karel se encuentra en el origen mirando hacia el este, en el mundo hay montaas escalonadas que parten del lmite horizontal del mundo, y alcanzan una altura de 6 calles, las dos montaas estn separadas por una calle, debe recoger los zumbadores que se encuentran en su mundo.

Estado inicial, Karel tiene 0 zumbadores

Estado final, Karel tiene 20 zumbadores y regreso a su posicin inicial

Programa iniciar-programa inicia-ejecucion avanza; gira-izquierda; gira-izquierda; gira-izquierda; avanza; coge-zumbador; gira-izquierda; avanza; 24

gira-izquierda; gira-izquierda; gira-izquierda; avanza; coge-zumbador; gira-izquierda; avanza; gira-izquierda; gira-izquierda; gira-izquierda; avanza; coge-zumbador; avanza; gira-izquierda; gira-izquierda; gira-izquierda; avanza; coge-zumbador; apagate; termina-ejecucion finalizar-programa Problema 11. Karel se encuentra en alguna calle de la avenida 2. Al frente de l hay un muro de dos calles de altura y una calle ms adelante hay otro muro igual. A la izquierda del segundo muro, hay un zumbador que Karel debe recoger.

Estado inicial, Karel tiene 0 zumbadores Programa iniciar-programa inicia-ejecucion gira-izquierda; avanza; avanza; gira-izquierda; gira-izquierda; gira-izquierda; avanza; gira-izquierda; gira-izquierda; 25

Estado final, Karel tiene 1 zumbador

gira-izquierda; avanza; avanza; coge-zumbador; gira-izquierda; gira-izquierda; avanza; avanza; gira-izquierda; gira-izquierda; gira-izquierda; avanza; gira-izquierda; gira-izquierda; gira-izquierda; avanza; avanza; apagate; termina-ejecucion finalizar-programa

Problema 12. La siguiente figura se conoce como escalergonos, Karel debe poner zumbadores por toda la orilla, un zumbador en cada lugar.

Estado inicial, Karel tiene 4 zumbadores. Programa iniciar-programa inicia-ejecucion gira-izquierda; gira-izquierda; gira-izquierda; avanza; avanza; gira-izquierda; avanza; 26

Estado Final, Karel tiene 0 zumbadores y est en la posicin (3,3)

deja-zumbador; avanza; gira-izquierda; avanza; deja-zumbador; gira-izquierda; gira-izquierda; avanza; avanza; deja-zumbador; gira-izquierda; gira-izquierda; avanza; gira-izquierda; gira-izquierda; gira-izquierda; avanza; deja-zumbador; gira-izquierda; gira-izquierda; avanza; apagate; termina-ejecucion finalizar-programa

27

Ejercicios Propuestos
Problema 1. Una vez ms la mascota de Karel escap, pero en esta ocasin se meti a un laberinto, la misin de Karel es sacarlo y regresarlo a su casa (posicin 1, 1).

Problema 2. En un da de compras, Karel sale de su casa (posicin 1,1) y se dirige a obtener los siguientes productos: leche, pan, huevo, carne y verduras, cada uno en diferentes establecimientos, al final regresa a casa con todas sus compras. Para agilizarlas Karel debe recorrer los establecimientos utilizando el camino ms corto entre ellos. Mundo Inicial

28

Problema 3. En un da de compras, Karel tiene que ir por los productos de siempre, sin embargo se da cuenta que algunas calles estn cerradas por lo que necesita tomar vas alternas para llegar a los diferentes establecimientos y realizar sus compras. Mundo Inicial

Problema 4. Karel consigui un nuevo empleo en la tienda que renta pelculas, en este caso estas se entregan a domicilio y cada vez que Karel va por ellas Mundo Inicial

Problema 5. Se define el mundo de Karel, quien debe formar tres torres del mismo tamao en las avenidas rodeadas por muros.

29

Mundo Inicial

Problema 6. Karel se encuentra en la siguiente situacin, y debe llenar el cuarto de zumbadores. Mundo Inicio

Problema 7. Karel se encuentra en la siguiente situacin, y debe llenar el cuarto de zumbadores como se ilustra.

30

Mundo final

Problema 8. Karel debe recoger el zumbador y finalizar en la misma posicin que inicio. Mundo final

Problema 9. Karel debe recoger el zumbador y finalizar en la misma posicin que inicio. Mundo final

31

Problema 10. Karel trabaja en una librera y debe colocar todos los libros en los cuatro anaqueles de la biblioteca, en cada anaquel caben hasta dos libros; Karel debe guardarlos. Mundo inicial

Mundo final

Problema 10. Karel tiene un criadero de conejos formado por cuatro corrales. Todos los das saca los conejos de su corral y los pone frente a la entrada para que coman. En cada corral puede haber 3 conejos. Karel debe sacar los conejos de cada corral y ponerlos frente a la entrada, Karel parte mirando al norte y debe finalizar mirando al este. Mundo inicial

32

Mundo final

Problema 11. Karel debe poner zumbadores por toda la orilla del siguiente escalergono.

Mundo inicial

Mundo final

Problema 12. Karel y su hermanita Gretel fueron a la feria, y a los dos hermanos se les ocurri entrar al juego del laberinto. Primero entr Gretel, a quien se le ocurri dejar un zumbador a cada paso que daba al internarse en el laberinto para que Karel pudiera encontrarla. Al entrar Karel y encontrar los zumbadores, decidi buscarla siguiendo el camino de zumbadores que Gretel haba dejado. Karel debe terminar en el otro extremo del laberinto y haber recogido todos los zumbadores que lo conforman.

33

Mundo inicial

Mundo final

34

NIVEL 3: AVANZADO
Ejercicios Resueltos Problema 1. Karel deber contar cuantas esquinas hay desde la esquina (1,1) hasta topar con una
pared, que deber haber en la calle 1. Karel deber poner la cantidad de zumbadores igual a la cantidad de esquinas de distancia, los deber poner en la esquina (1,1). Como se muestra en las figuras siguientes:

Estado inicial. Programa iniciar-programa define-nueva-instruccion cuenta como inicio si frente-libre entonces inicio avanza; cuenta; deja-zumbador; fin sino inicio gira-izquierda; gira-izquierda; mientras frente-libre hacer avanza; fin; fin; inicia-ejecucion cuenta; deja-zumbador; 35

Estado final Karel.

apagate; termina-ejecucion finalizar-programa

Problema 2:Karel debe dejar 10 zumbadores a lo largo de la calle (Obviamente debe tener los 10
zumbadores en su mochila).

Estado inicial. Programa iniciar-programa define-nueva-instruccion dejalos(num) como inicio si no si-es-cero(num) entonces inicio deja-zumbador; avanza; dejalos(precede(num)); fin; fin; inicia-ejecucion dejalos(10); apagate; termina-ejecucion finalizar-programa

Estado final Karel.

Problema 3: Karel deber recoger todos los zumbadores que se encuentren junto de l, y llevarlos
hasta que se encuentre con una pared frente de l. Tendr INFINITO zumbadores en la mochila al iniciar el programa.

36

Estado inicial. Programa iniciar-programa define-nueva-instruccion deja(m) como inicio si no si-es-cero(m) entonces inicio deja-zumbador; deja(precede(m)); fin; fin; define-nueva-instruccion cuenta(n) como inicio si junto-a-zumbador entonces inicio coge-zumbador; cuenta(sucede(n)); fin sino inicio mientras frente-libre hacer avanza; deja(n); fin; fin; inicia-ejecucion cuenta(0); apagate; termina-ejecucion finalizar-programa

Estado final Karel.

Problema 4: Karel debe colocar ab zumbadores en la casilla (1, 3), Karel se encuentra en la casilla
(1,1) orientado al norte, en la casilla (1,1) hay a zumbadores, en la casilla (1, 2) hay b zumbadores, Karel tiene infinitos zumbadores en la mochila y no hay muros en el interior del mundo. 37

Programa iniciar-programa define-nueva-instruccion agarra-b(a) como inicio si junto-a-zumbador entonces inicio coge-zumbador; agarra-b(a); repetir a veces deja-zumbador; fin sino inicio avanza; fin; fin; define-nueva-instruccion agarra-a(a) como inicio si junto-a-zumbador entonces inicio coge-zumbador; agarra-a(sucede(a)); fin sino inicio avanza; agarra-b(a); fin; fin; inicia-ejecucion agarra-a(0); apagate; termina-ejecucion finalizar-programa

Problema 5: Karel deber recoger todos los zumbadores que se encuentren junto de l, y llevarlos hasta que se encuentre con una pared frente de l. Tendr INFINITO zumbadores en la mochila al iniciar el programa.

38

Estado inicial. Programa iniciar-programa define-nueva-instruccion gira-derecha como inicio gira-izquierda; gira-izquierda; gira-izquierda; fin; define-nueva-instruccion toma-zumbador como inicio si junto-a-zumbador entonces inicio coge-zumbador; gira-izquierda; avanza; fin sino inicio gira-izquierda; avanza; fin; fin; inicia-ejecucion gira-derecha; avanza; toma-zumbador; gira-derecha; avanza; toma-zumbador; gira-derecha; avanza; toma-zumbador; gira-derecha; avanza; toma-zumbador; apagate; 39

Estado final Karel.

termina-ejecucion finalizar-programa Problema 6: Karel debe medir la distancia entre su posicin inicial y la pared. Como resultado, deber dejar en la esquina inferior izquierda del mundo una cantidad de zumbadores igual a la distancia requerida.

Estado inicial. Programa iniciar-programa define-nueva-instruccion camina(n) como inicio si frente-libre entonces inicio avanza; camina(sucede(n)); fin sino inicio repetir n veces deja-zumbador; fin; fin; inicia-ejecucion mientras frente-libre hacer inicio avanza; fin; gira-izquierda; gira-izquierda; camina(1); apagate; termina-ejecucion finalizar-programa

Estado final Karel.

40

Problema 7: Karel est jugando con un amigo, tienen juguetes y se los van a repartir. Karel deber recogerlos y repartirlos, los juguetes de Karel en la esquina izquierda y los de su amigo en la esquina derecha.

Estado inicial. Programa iniciar-programa define-nueva-instruccion orientadoEste como inicio mientras no-orientado-al-este hacer inicio gira-izquierda; fin; fin; define-nueva-instruccion camina como inicio mientras frente-libre hacer inicio avanza; fin; fin; define-nueva-instruccion cogeZumbador como inicio mientras junto-a-zumbador hacer inicio coge-zumbador; fin; fin; define-nueva-instruccion orientadoOeste como inicio mientras no-orientado-al-oeste hacer inicio gira-izquierda; fin; fin; define-nueva-instruccion dejaLosZumbadores como inicio mientras algun-zumbador-en-la-mochila hacer inicio deja-zumbador; fin; fin;

Estado final Karel.

41

define-nueva-instruccion recogeLosZumbador como inicio si junto-a-zumbador entonces inicio coge-zumbador; si junto-a-zumbador entonces inicio coge-zumbador; recogeLosZumbador; deja-zumbador; fin sino inicio orientadoEste; camina; fin; fin sino inicio orientadoEste; camina; fin; fin; inicia-ejecucion recogeLosZumbador; orientadoOeste; camina; dejaLosZumbadores; apagate; termina-ejecucion finalizar-programa Problema 8 Karel y su amigo terminaron de jugar, ahora tiene que recoger sus torres y dejarlas en la caja de juguetes.

Estado inicial. Programa 42

Estado final Karel.

iniciar-programa define-nueva-instruccion orientadoEste como inicio mientras no-orientado-al-este hacer inicio gira-izquierda; fin; fin; define-nueva-instruccion orientadoOeste como inicio mientras no-orientado-al-oeste hacer inicio gira-izquierda; fin; fin; define-nueva-instruccion orientadoNorte como inicio mientras no-orientado-al-norte hacer inicio gira-izquierda; fin; fin; define-nueva-instruccion orientadoSur como inicio mientras no-orientado-al-sur hacer inicio gira-izquierda; fin; fin; define-nueva-instruccion camina como inicio mientras frente-libre hacer inicio avanza; fin; fin; define-nueva-instruccion orientadoOeste como inicio mientras no-orientado-al-oeste hacer inicio gira-izquierda; fin; fin; define-nueva-instruccion dejaLosZumbadores como inicio mientras algun-zumbador-en-la-mochila hacer inicio deja-zumbador; fin; fin; define-nueva-instruccion recogeTorre como inicio orientadoNorte; mientras junto-a-zumbador hacer inicio coge-zumbador; avanza; 43

fin; orientadoSur; camina; fin; define-nueva-instruccion recogeTorreIzq como inicio orientadoOeste; camina; recogeTorre; fin; define-nueva-instruccion encuentraMitad como inicio si frente-libre entonces inicio avanza; si frente-libre entonces inicio avanza; encuentraMitad; avanza; fin; fin sino inicio orientadoOeste; fin; fin; inicia-ejecucion recogeTorre; recogeTorreIzq; orientadoEste; encuentraMitad; dejaLosZumbadores; apagate; termina-ejecucion finalizar-programa

Problema 9: Karel se encuentra en una competencia de carrera. Es necesario que recorra un camino que tiene vallas (obstculos) hasta llegar al final donde se encuentra un zumbador.

Estado Inicial

44

Estado inicial.

Programa iniciar-programa define-nueva-instruccion camina como inicio mientras no-junto-a-zumbador y frente-libre hacer inicio avanza; fin; fin; define-nueva-instruccion girar (n) como inicio repetir n veces inicio gira-izquierda; fin; fin; define-nueva-instruccion brincar como inicio si no-junto-a-zumbador entonces inicio girar (1); avanza; girar (3); avanza; girar (3); avanza; girar (1); fin; fin; inicia-ejecucion mientras no-junto-a-zumbador hacer inicio camina; brincar; fin; apagate; 45

termina-ejecucion finalizar-programa

Problema 10: Hay varios zumbadores tirados en el cuarto, en varias posiciones del mismo. Debes
hacer un programa que haga que Karel recorra todo el cuarto y recoja todos los zumbadores que encuentre. Una vez que tenga todos los zumbadores deber depositarlos en la esquina inferior izquierda del cuarto y apagarse.

Estado inicial. Programa iniciar-programa define-nueva-instruccion caminaAvanza como inicio mientras junto-a-zumbador hacer inicio coge-zumbador; fin; mientras frente-libre hacer inicio avanza; mientras junto-a-zumbador hacer inicio coge-zumbador; fin; fin; fin; define-nueva-instruccion GirarAvanzar como inicio mientras no-orientado-al-este hacer inicio caminaAvanza; si derecha-libre entonces inicio 46

Estado final Karel.

gira-izquierda; gira-izquierda; gira-izquierda; avanza; gira-izquierda; gira-izquierda; gira-izquierda; caminaAvanza; si izquierda-libre entonces inicio gira-izquierda; avanza; gira-izquierda; fin sino inicio gira-izquierda; fin; fin sino inicio gira-izquierda; gira-izquierda; gira-izquierda; fin; fin; fin; define-nueva-instruccion regresa como inicio gira-izquierda; gira-izquierda; mientras frente-libre hacer inicio avanza; fin; gira-izquierda; mientras frente-libre hacer inicio avanza; fin; fin; define-nueva-instruccion dejarZumbadores como inicio mientras algun-zumbador-en-la-mochila hacer inicio deja-zumbador; fin; fin; inicia-ejecucion GirarAvanzar; regresa; dejarZumbadores; apagate; 47

termina-ejecucion finalizar-programa

Ejercicios Propuestos

Problema 1: La tarea de Karel es dejar zumbadores a lo largo de una pista de carreras. Un ejemplo de dicha pista es la de la siguiente imagen. Karel debe dar una vuelta completa y depositar un zumbador en cada esquina a lo largo del camino. Guarda el programa con el nombre karel7.kp. Tu solucin debe usar sentencias mientras/hacer. Construye el mundo inicial de la siguiente imagen con el nombre pistaCarreras.km. Asegurar de poner dentro de la mochila suficientes zumbadores para todas las esquinas. El ejemplo requiere 22 zumbadores. Karel debe empezar en cualquier interseccin de la pista.

Mundo Final

Problema 2: Escribe un programa que ayude a Karel a escapar de un laberinto que no contiene islas (cuadrados aislados). La salida del laberinto est marcada ubicando un zumbador en la primera esquina que est fuera del laberinto, al lado del muro de la derecha. Una forma de resolver este problema es hacer que Karel avance a lo largo del laberinto siguiendo el muro de su derecha (imagina que est tocando el muro y que nunca puede despegar su mano de l). En la siguiente imagen hay un ejemplo de un laberinto del cual debera ser capaz de salir (no olvides que tu programa debera funcionar en todos los laberintos, no solo en el de la imagen). La lnea roja muestra el camino que debera seguir Karel para este mundo. Recordar que no sabris de antemano donde estarn los muros..

Mundo Final

48

Problema 3: Ayuda a Karel a encontrar a Aldo y resctalo (rodalo con zumbadores). Mundo Final

Problema 4: Karel consigui trabajo como demoledor de edificios en la ciudad y su primer trabajo es tumbar la torre ms alta de la ciudad.

Problema 5: Karel se encuentra frente a una calle, la cual deber indicar con zumbadores, la lnea divisoria.

49

Problema 6: Karel se encuentra en la parte inferior de un cactus. Deber colocar, es su base, todas las pencas representadas por zumbadores. Utilice bsqueda en profundidad sin hacer un barrido completo.

Problema 7: Karel deber 'estirar' el gusano donde se encuentra, la posicin inicial ser la orilla cargada a la izquierda. El gusano estirado deber colocarse en la parte inferior del cuadriltero.

Problema 8: Karel deber 'cargar' el montn de zumbador al montn de la derecha si este, el segundo, es mayor; y 'traer' si el montn donde se encuentra Karel es mayor. La jerarqua se rige de izquierda a derecha, y de abajo a arriba; y es acumulable.

50

Problema 9: Karel deber 'taponear' las orillas de las tuberas que contienen zumbadores malignos, mediante 'tapones' representados por montones de tres zumbadores. Los zumbadores malignos se agrupan en montones de dos. Puede haber conjuntos de tuberas benignas. Karel se encuentra en un cuadriltero rodeado por paredes.

Problema 10: Karel deber fumigar los cuartos que existen en el mundo donde vive.

51

BIBLIOGRAFA
Luis Joyanes Aguilar. Fundamentos de Programacin, Algoritmos, estructuras de datos y objetos. Tercera Edicin. McGrawHill. 2003. Luis Joyanes Aguilar, Ignacio Zahonero Martnez. Algoritmos y Estructura de datos, una perspectiva en C. Primera Edicin. McGrawHill. 2004. Glenn Brookshear. Introduccin a las Ciencias de la Computacin. Cuarta Edicin. Addison Wesley Iberoamericana. 1995. Jos J. Garca-Badell. Turbo C++3 Programacin y manejo de Archivos. Primera Edicin. Addison Wesley Iberoamericana. 1994. Jordi Batallar Mascarrell, Rafael Magdalena Benedito. Programacin en C. Primera Edicin. Alfa Omega. 2001.

52