Download 1. Desarrollo de Programas iterativos usando invariante

4. Desarrollo de Programas: enfoques
Top-down y Bottom-up
Idea
• Objetivos:
• Facilitar el proceso de solución de un problema
• Orden y Claridad del código
• Distribución de tareas entre programadores
• Estrategia bottom-up: “partir” un problema en subproblemas, solucionar los sub-problemas desarrollando
código “encapsulado” y luego escribir el programa principal
usando el código encapsulado
• Estrategia top-down: Escribir el código del programa principal
en forma gruesa, dejando para después la solución de subproblemas. Luego se desarrollan los sub-problemas.
• Distribución del trabajo: para distribuir el trabajo es necesario
establecer claramente como se usarán y cual será el
comportamiento del código encapsulado
Ejemplo
Problema: desarrollar el programa que implementa el siguiente
diálogo con el usuario:
Suma, resta de 2 tiempos
Primer tiempo (HHMMSS) ? 013040
Segundo tiempo (HHMMSS) ? 104530
Suma = 12:16:10
Resta = 09:14:50
Mayor = 10:45:30
Menor = 01:30:40
Solución sin estrategia:
import java.util.*;
class T {
public static void main(String[] args) {
Scanner C = new Scanner(System.in);
System.out.println(“Sumar y resta de 2 tiempos”);
System.out.print(“Primer instante(HHMMSS)?”);
int t1=C.nextInt(); ht1=t1/10000; mt1=t1%10000/100; st1=t1%100;
System.out.print(“Segundo instante(HHMMSS)?”);
int t2=C.nextInt(); ht2=t2/10000; mt2=t2%10000/100; st2=t2%100;
int sum = (ht1+ht2)*3600+(mt1+mt2)*60+st1+st2;
System.out.print(“Suma= “+(sum/3600)+”:”+(sum%3600/60)+”:”+(sum%60));
int res = (ht1-ht2)*3600+(mt1-mt2)*60+st1-st2;
System.out.print(“Resta= “+(res/3600)+”:”+(res%3600/60)+”:”+(res%60));
if (t1 > t2)
System.out.print(“Mayor=“+ht1+”:”+mt1+”:”+st1);
else
System.out.print(“Mayor=“+ht2+”:”+mt2+”:”+st2);
}
}
Solución top down:
import java.util.*;
class T {
public static void main(String[] args) {
Scanner C = new Scanner(System.in);
System.out.println(“Sumar y resta de 2 tiempos”);
System.out.print(“Primer instante(HHMMSS)?”);
int t1=Tiempo.totalSegundos(C.nextInt());
System.out.print(“Segundo instante(HHMMSS)?”);
int t2=Tiempo.totalSegundos(C.nextInt());
System.out.print(“Suma=); Tiempo.escribir(t1+t2);
int mayor=Math.max(t1,t2), menor=Math.min(t1,t2);
System.out.print(“Mayor=); Tiempo.escribir(mayor);
System.out.print(“Menor=); Tiempo.escribir(menor);
System.out.print(“Resta=); Tiempo.escribir(mayor-menor);
}
}
class Tiempo{
static public int horas(int x){ return x/10000;}
static public int minutos(int x){return x/100%100;}
static public int segundos(int x){return x%100;}
static public int totalSegundos(int x){
return horas(x)*3600+minutos(x)*60+segundos(x);}
static public void escribir(int x){
System.out.println(x/3600+”:”+x%3600/60+”:”+x%60);}
}
Solución bottom-up:
class Tiempo {
int segundos;
//conviene guardar el total de segundos no mas
Tiempo (int x) {
segundos = x/10000*3600+x/100%100*60+x%100;
}
public int compareTo(Tiempo x) {
// retorna un entero < 0, == 0, > 0 según si x es mayor igual o menor
return segundos – x.segundos;
}
public Tiempo suma(Tiempo x) {
//retorna un objeto tiempo nuevo con la suma
return new Tiempo(segundos+x.segundos);
}
public Tiempo resta(Tiempo x) {
//retorna un objeto tiempo nuevo con la resta
return new Tiempo(segundos-x.segundos);
}
public String toString() {
//retorna un string “HH:MM:SS”
return segundos/3600+”:”+(segundos%3600/60)+”:”+segundos%60;
}
}
Programa
class T {
public static void main(String[] args) {
Tiempo t1 = new Tiempo(C.readInt(“Primer instante(HHMMSS)?“));
Tiempo t2 = new Tiempo(C.readInt(“Segundo instante(HHMMSS)?”);
Tiempo t3 = t1.suma(t2);
System.out.print(“Suma=”+t3.toString());
if (t1.compareTo(t2) > 0){
mayor = t1; menor = t2;
} else {
mayor = t2; menor = t1;
}
U.println(“Mayor=“+mayor.toString());
U.println(“Menor=”+menor.tostring());
U.print(“Suma =“+(t1.suma(t2)).toString()+
”Resta=”+(t1.resta(t2)).toString());
}
}
Pensamientos
• Es importante definir claramente la interfaz entre
el programa principal y los sub-programas
• El enfoque de llamado a funciones es más antiguo
que el de diseñar y construir objetos pero ambos
persiguen los mismos objetivos
• El enfoque orientado a objetos responde a la
necesidad de desarrollar software de grandes
dimensiones con menos errores
• Permite encapsular mejor el código y los datos de
un subprograma
• Apoya desarrollo de “Tipos de Datos Abstractos”
Herencia y Polimorfismo
• Conceptos íntimamente ligados entre sí y a OOP
• Herencia se refiere al uso de código ya escrito
(una clase) que se extiende para “especializar” su
función
• Polimorfismo se refiere a que un objeto puede
“verse” de varias clases diferentes a la vez
• Estos conceptos se implementan con Herencia
Simple, Clases Abstractas e Interfaces
Herencia Simple
• La herencia simple consiste en extender una clase
existente para: a) agregarle nuevas variables, b)
agregarle nuevos métodos, c) modificar métodos
import java.awt.*;
public class Figura{
int ox, oy;
import java.awt.*;
public class Circulo extends Figura{
int radio;
Figura(int x, int y) {
ox= x; oy = y;
}
Circulo(int x, int y, int z) {
super(x, y); radio = z;
}
public double area(){
return 0.0;
}
public double area(){
return Math.PI*radio*radio;
}
public double perimetro(){
return 0.0;
}
public double perimetro(){
return 2*Math.PI*radio;
}
public void draw(Graphics g) {
g.fillCircle(ox-1,oy-1,ox+1,oy+1);
}
public void draw(Graphics g) {
g.fillCircle(ox-r/2,oy-r/2,
ox+r/2,oy+r/2);
}
}
}
Herencia Simple (cont.)
import java.awt.*;
public class Rectangulo extends Figura{
int largo, ancho;
Rectangulo(int x, int y, int l, in a) {
super(x,y); largo = l; ancho = a;
}
public double area(){
return largo*ancho;
}
public double perimetro(){
return 2*(largo+ancho);
}
import java.awt.*;
import java.util.*;
public class Prog {
Arraylist<Figura> a =
new ArrayList<Figura>();
a.add(new Rectangulo(50,50, 20,30));
a.add(new Circulo(100,100,30));
a.add(new Figura(50,50));
...
Frame f = new Frame(“Ventana de Figuras”);
Canvas c = new Canvas(500,500);
f.add(c); f.setVisible(true);
...
Graphics g = c.getGraphics();
for (int i = 0; i <= a.size(); i++) {
Figura n = a.get(i);
n.draw(g);
}
public void draw(Graphics g) {
g.fillRect(ox,oy,ox+ancho,oy+largo);
}
}
}
Herencia con Clases Abstractas
• Declaran clases incompletas
con métodos abstractos
• Los que extiendan esta clase
DEBEN implementarlos
• No es posible crear objetos de
estas clases (si de sus
extendidas)
• No cambia ni el uso ni la
definición de la clase
extendida, salvo que el
compilador obliga a
implementar las funciones
abstractas
import java.awt.*;
public abstract class Figura{
int ox, oy;
Figura(int x, int y) {
ox= x; oy = y;
}
abstract public double area();
abstract public double area();
abstract public void draw(Graphics g);
}
Polimorfismo con Interfaces
• Puede declarar variables
comunes
• Contiene encabezados
(declaraciones) de funciones
(métodos) que se deben
implementar
• Las clases “implementan” la
interfaz, y con eso son también
de la clase
• El compilador tambien va a
obligar a que la clase
implemente todos los metodos
de la interfaz/interfaces que
declara implementar
public interface Figura{
int xo, yo;
public double area();
public double area();
public void draw(Graphics g);
}
import java.awt.*;
public class Circulo implements Figura{
int radio;
Circulo(int x, int y, int z) {
xo=x; yo=y; radio = z;
}
public double area(){
return Math.PI*radio*radio;
}
public double area(){
return Math.PI*radio;
}
public void draw(Graphics g) {
g.fillCircle(ox-r/2,oy-r/2,
ox+r/2,oy+r/2);
}
}
¿Herencias, abstractos o Interfaces?
• Depende (por algo existen las dos)
• Herencia simple cuando se podrían usar los
objetos de la clase original (superclase)
• Clases abstractas cuando hay un conjunto de
variables y funciones comunes, pero la clase “no
esta lista” y por lo tanto no queremos que se
usen objetos de la superclase
• Interfaces cuando no hay nada que compartir,
solo queremos asegurarnos que un objeto
perteneciente a la clase de la interfaz tenga los
métodos mencionados
Interfaz Comparable en Java
interface Comparable{
public int compareTo(Object x);
}
class Fraccion implements Comparable{
int num, den;
Fraccion(int x, int y) { num = x; den = y;}
public int compareTo(Object x){
Fraccion f=(Fraccion)x;
return a*f.b – b*f.a;
}
}
Estructura de Dato y su invariante
• Cada estructura de datos que implementa un TDA
tiene un invariante
• Conjunto de condiciones que se cumplen siempre
• Cada operación que se define sobre la estructura
tiene el derecho de suponer que se cumple el
invariante al principio y dejarlo cumpliéndose al
final
• Ej. Implementar un TDA conjunto con la siguiente
estructura de datos
a0
a1
...
an-1
...
n
Estructuras de Datos
¿Estructuras de datos?
Formas de organización y almacenamiento de datos (en
memoria). Ejemplos:
arreglo
lista enlazada
...
árbol
Estructura de Dato y su invariante
class Conjunto {
private int[] a;
private int n;
Conjunto(int x) {
a = new int[x]; n = 0;
}
public boolean agregar(int x) {
if (esta(x)) return false
a[n++] = x; return true;
}
public boolean sacar(int x) {
}
public boolean esta(int x) {
//retorna true si esta x en el conjunto
}
. . .
}
}