1 Programación II 3-4 de marzo de 2009Diseño descendente Programación II 3-4 de marzo de 2009

2 Descomposición funcionalDescomponer un programa en funciones más sencillas Cada función resuelve una sola tarea Cada tarea es claramente diferenciada de las otras tareas Ayuda en la comprensión del programa Facilita la reutilización de código

3 Diseño descendente Empezar por el problema a resolverDiseñar una solución intuitiva sin especificar detalles Esta solución representa el primer nivel de abstracción Complementar detalles con funciones de segundo nivel (descender un nivel) Continuar hasta llenar todos los detalles

4 Secuencia Estructura de datos secuencial Funciones:LeerPrimerElemento(L, e); LeerSiguienteElemento(L, e); UltimoElemento(L); InicializarSecuencia(L); EscribirElemento(L, e);

5 Ejercicio Contar el número de veces que aparece la primera palabra en un texto acabado en punto “lo que sabemos es una gota de agua; lo que ignoramos es el océano.” (Isaac Newton)  “lo” aparece 2 veces Suponer que el texto está representado por una secuencia de caracteres

6 Problema de las ocho reinasSituar ocho reinas en un tablero de ajedrez sin que se amenacen entre sí

7 Idea Idea: para cada columna, encontrar la primera fila no amenazadaSituar una reina allí Continuar con la próxima columna Si encontramos una columna sin posibilidades, dar vuelta atrás (backtrack) Probar la siguiente fila posible

8 Ejemplo

9 Algoritmo accion OchoReinas() pos:vector (dim 8) de natural;Situar(1, pos); faccion pos: posición de la reina en cada columna

10 Segundo nivel accion Situar(col:natural, pos:vector de natural)variable fila:natural; si (col > 8) entonces Mostrar(pos); sino fila  ProximaFila(0, col, pos); mientras (fila ≤ 8) hacer pos[col]  fila; Situar(col + 1, pos); fila  ProximaFila(fila, col, pos); fmientras fsi faccion

11 Tercer nivel accion Mostrar(pos:vector de natural) variable i:natural;para i  1 hasta 8 hacer Mostrar(pos[i]); fpara Mostrar(‘\n’); faccion

12 Tercer nivel funcion ProximaFila(fila,col:natural,pos:vector de natural) devuelve natural fila  fila + 1; mientras (fila ≤ 8 y Amenazado(fila,col,pos)) hacer fmientras devuelve fila; ffuncion

13 Detectar amenazas

14 Cuarto nivel funcion Amenazado(fila,col:natural,pos:vector de natural) devuelve booleano variable i:natural; para i  1 hasta (col-1) hacer si ((pos[col-i] = fila-i) o (pos[col-i] = fila) o (pos[col-i] = fila+i)) entonces devuelve cierto; devuelve falso; faccion

15 Diseño descendente OchoReinas Situar Mostrar ProximaFila Amenazado

16 Pista de Carreras Estructura del código de la práctica 33023 líneas de código 51 funciones 19 archivos

17 main (p2Main.c) Leer los parámetros de la línea de comandaLlamar a la función StartGame con la pista y las estrategias Mostrar el ganador

18 StartGame (p2Game.c) Crear e inicializar las estructuras de datosCrear la matriz de adyacencia Repetir hasta finalizar el juego: Seleccionar el movimiento de un jugador Mostrar la pista Comprobar si el juego ha finalizado Liberar la memoria

19 CreateAdjacencyMatrixDiseño descendente main StartGame FreeMatrix ReadMatrix DisplayRaceTrack CreateAdjacencyMatrix MoveCar IsGameOver

20 Resumen Algoritmos de búsqueda y de ordenación Recurrencia ComplejidadDiseño descendente