Diseño descendente

Programación II

24-25 de febrero de 2009

Algunas citas

• “El tiempo que un ser humano necesita para entender un programa aumenta exponencialmente con su longitud”

Edsger Dijkstra

• “Dividir cada dificultad que se examina en tantos fragmentos como sea posible y que se requieren para mejorar la solución”

René Descartes

Organización de programas

• Normalmente un programa lleva miles de líneas de código

• Podría poner todo dentro de una función

• Sin embargo, hay algunas normas de implementación para mejorar la calidad

• En particular, es buena práctica aplicar diseño descendente y descomposición funcional

Programación spaghetti

• Lo que uno quiere evitar:– funciones muy largas que cada una realiza

varias tareas– programas difíciles a entender para otros

programadores– código que no se puede reutilizar con

facilidad

Descomposición funcional

• Descomponer 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

Diseño descendente

• Empezar por el problema a resolver

• Diseñ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

Ejemplo: QuickSortaccion QuickSort(V: vector de natural,

i,d: natural)

variable x,y,temp: natural;

si (i < d) entonces

x i; temp V[x];y d – 1; V[x] V[d];mientras (x < y) hacer V[d] temp;

mientras (V[x] < V[d]) hacer QuickSort(V, i, x-1);

x x + 1; QuickSort(V, x, d);

fmientras fsi

mientras (V[y] ≥ V[d]) hacer faccion

y y - 1;fmientras

si (x < y) entonces

temp V[x];V[x] V[y];V[y] temp;

fsi

fmientras

Ejemplo: QuickSortaccion QuickSort(V: vector de natural, i,d: natural)

variable p: natural;si (i < d) entonces

p Particionar(V, i, d);QuickSort(V, i, p-1);QuickSort(V, p, d);

fsifaccion

Segundo nivelfuncion Particionar(V: vector de natural, i,d: natural) devuelve natural

variable x,y: natural;x i;y d – 1;mientras (x < y) hacer

mientras (V[x] < V[d]) hacerx x + 1;

fmientrasmientras (V[y] ≥ V[d]) hacer

y y - 1;fmientrassi (x < y) entonces

Intercambiar(V, x, y);fsi

fmientrasIntercambiar(V, x, d);devuelve x;

ffuncion

Tercer nivelaccion Intercambiar(V: vector de natural,

x,y: natural)

variable temp: natural;

temp V[x];V[x] V[y];V[y] temp;

faccion

Diseño descendente

QuickSort

Particionar

Intercambiar

Ejemplo

• Escribir un programa que juega a Tres-en-Raya

Idea

• Probar todas las posibilidades

Idea

• Cada jugador intenta maximizar su resultado

• Por lo tanto, escoge el mejor movimiento desde su perspectiva

• El tablero es suficientemente pequeño para probar todas las posibilidades

Representación

• Representar el tablero por un vector de nueve números naturales

• 0: casilla vacía

• 1, 2: este jugador ha jugado en la casilla

1 2 34 5 67 8 9

Acción principalaccion TresEnRaya()

variable jugador,ganador:natural; T,R:vector de natural;

jugador 1;ganador 0;T InicializarTablero();MostrarTablero(T);mientras (ganador = 0) hacer

R Mover(jugador,T);T[R[1]] jugador;MostrarTablero(T);jugador 3 – jugador;ganador DetectarGanador(T);

fmientrasMostrarGanador(ganador);

faccion

Segundo nivelfuncion InicializarTablero() devuelve vector de natural

variable i:natural; T:vector de natural;

para i 1 hasta 9 hacerT[i] = 0;

fparadevuelve T;

ffuncion

accion MostrarGanador(ganador:natural)si (ganador < 3) entonces

Mostrar(“Ha ganado el jugador ” + ganador);sino

Mostrar(“Ha sido un empate”);fsi

faccion

Segundo nivelaccion MostrarTablero(T:vector de natural)

variable i,j:natural;para i 1 hasta 3 hacer

para j 1 hasta 3 hacerMostrar(Simbolo(T[3*i + j]));

fparaMostrar(‘\n’);

fpara faccion

funcion Simbolo(jugador:natural) devuelve caractersi (jugador = 1) entonces

devuelve ‘X’;sino si (jugador = 2) entonces

devuelve ‘O’;sino

devuelve ‘ ’;fsi ffuncion

Segundo nivelfuncion DetectarGanador(T:vector de natural) devuelve natural

variable ganador:natural;ganador AnalizarFilas(T);ganador Maximo(ganador, AnalizarColumnas(T));ganador Maximo(ganador, AnalizarDiagonales(T));si (ganador > 0) entonces

devuelve ganador;sino si (TableroLleno(T)) entonces

devuelve 3;sino

devuelve 0;fsi

ffuncion

Tercer nivelfuncion AnalizarFilas(T:vector de natural) devuelve natural

variable i:natural;para i 1 hasta 3 hacer

si (Iguales(T[3*i-2], T[3*i-1], T[3*i]) y T[3*i] > 0)devuelve T[3*i];

fsifparadevuelve 0;

ffuncion

funcion Iguales(a,b,c:natural) devuelve booleanosi (a = b y a = c) entonces

devuelve cierto;sino

devuelve falso;fsi

ffuncion

Tercer nivelfuncion AnalizarColumnas(T:vector de natural) devuelve natural

variable i:natural;para i 1 hasta 3 hacer

si (Iguales(T[i], T[i+3], T[i+6]) y T[i] > 0) entoncesdevuelve T[i];

fsifparadevuelve 0;

ffuncion

funcion AnalizarDiagonales(T:vector de natural) devuelve naturalsi (Iguales(T[1], T[5], T[9]) y T[1] > 0) entonces

devuelve T[1];sino si (Iguales(T[3], T[5], T[7]) y T[3] > 0) entonces

devuelve T[3];fsidevuelve 0;

ffuncion

Tercer nivelfuncion TableroLleno(T:vector de natural) devuelve booleano

variable i:natural;para i 1 hasta 9 hacer

si (T[i] = 0) entoncesdevuelve falso;

fsifparadevuelve cierto;

ffuncion

funcion Maximo(a,b:natural) devuelve naturalsi (a > b) entonces

devuelve a;sino

devuelve b;fsi

ffuncion

La función Moverfuncion Mover(jugador:natural, T:vector de natural) devuelve vector de natural

variable i,ganador:natural; res, R:vector de natural;

ganador DetectarGanador(T);si (ganador > 0) entonces

devuelve [0, ganador];fsires [0, 0];para i 1 hasta 9 hacer

si (T[i] = 0) entoncesT[i] jugador;R Mover(3 – jugador, T);T[i] 0;si (R[2] = jugador) entonces

devuelve [i, jugador];sino si (R[2] = 3 o res[1] = 0) entonces

res [i, R[2]];fsi fsi fpara

devuelve res;ffuncion

Diseño descendenteTresEnRaya

MostrarTablero

Mover

DetectarGanador

InicializarTablero

MostrarGanador

TableroLleno

AnalizarDiagonalesAnalizarColumnasAnalizarFilas

Simbolo

Iguales

Maximo