Miércoles 16 de Junio

Temas:

Recetas para pasar de arreglos asociativos a arreglos nativos

Haga las siguientes transformaciones:

Con la clase Map Con arreglos nativos
Map tab= new Map() String[] tab= new String[tamaño+1];
tab.put(i,v); tab[i]= v;
... tab.getString(i) ... ... tab[i] ...
Ejemplos:

Un programa que construye un arreglo con 100 líneas leídas de la consola:

    // con Map                // Con [ ]
    Map lineas= new Map();    String[ ] lineas= new String[101];
    int i= 1;                 int i= 1;
    while (i<=100) {          while (i<=100) {
      String lin= readLine();   String lin= readLine();
      lineas.put(i, lin);       lineas[i]= lin;
      i= i+1;                   i= i+1;
    }                         }
Un programa que busca un elemento en el arreglo que contenga el string "hola":

    int i=1;
    while (i<=100) {
      if (indexOf(lineas[i], "hola")!=-1)
        break;
      i= i+1;
    }
    if (i<=100)
      ... exito ...
    else
      ... fracaso ...

Ejercicio 1: función que calcula la suma de los elementos de un arreglo x de n reales.

    double suma(double[ ] x, int n) {
      // entrega x[0]+x[1]+x[2]+...+x[n-1]
      ...
      return ...
    }
¡Solución sin while!

La idea es diseñar una solución que descomponga el problema en subproblemas más simples de resolver. Estos son subproblemas más simples:

El segundo subproblema es efectivamente más simple porque el arreglo tiene un elemento menos que en el problema inicial. Entonces, se puede escribir una función recursiva que resuelva el problema general.

    double suma(double[ ] x, int n) {
      if (n==0)
        return 0;
      else
        return suma(x, n-1)+x[n-1];
    }
La invocación recursiva de suma(x, n-1) se justifica por el principio de abstracción: podemos suponer que los subproblemas ya están resueltos.

Observe que no sirve considerar como subproblema sumar los elementos de una arreglo de n reales, porque no es más simple que el problema inicial. Por lo tanto, la siguiente solución se pisa la cola: 

    double suma(double[ ] x, int n) {
      return suma(x, n);
    }
En realidad en este programa la recursión es infinita porque carece del caso base.

Ejercicio 2:

Sin usar la instrucción while, escriba una función que calcule el máximo valor en un arreglo x de n números reales:

    double max(double[ ] x, int n) {
      ...
    }
Ejemplo:

Función que retorna la posición del máximo en el arreglo:

    int posMax(double[ ] x, int n) {
      // i tal que x[i]>=x[j], para todo j en [0,n-1]
      if (n==1)
        return 0;
      else {
        int i= posMax(x, n-1);
        if (x[n-1]>x[i])
          return n-1;
        else
          return i;
      }
    }

Enumeradores

Motivación

Escribir un programa que lea el archivo datos.txt, que contiene números, y entregue en pantalla cuantas veces aparece cada número (debe entregar la frecuencia de cada número). Por ejemplo, si el archivo contiene: 

    1 10 1 3 7 7 1 8
El programa debe mostrar en pantalla:

    3 -> 1 vez
    10 -> 1 vez
    1 -> 3 veces
    7 -> 2 veces
    8 -> 1 vez
El orden en que se despliegan las frecuencias no está especificado. Los números no están acotados.

Solución tentativa: colocar las frecuencias en un arreglo asociativo frec, de manera que frec.getInt(num) entregue la cantidad de veces que ha aparecido el entero num.

    Map frec= new Map();
    TextReader lect= new TextReader("datos.txt");
    while (true) {
      int num= lect.readInt();
      if (lect.eofReached())
        break;
      frec.put(num, frec.getInt(num));
    }
El problema es que es un error invocar frec.getInt(num) cuando el arreglo frec no tiene ningún valor asociado a num. En los arreglos asociativos el método isMapped permite saber si una llave posee un valor asociado o no. El siguiente código determina el número de apariciones de la llave num sin producir error:

    int veces= 0;
    if ( frec.isMapped(num) )
      veces= frec.getInt(num);
Sin embargo, persiste otro problemar. ¿Cómo determinar cuáles son todas las llaves que poseen algún valor en el arreglo asociativo? Esto se puede hacer con un enumerador de la clase KeyEnum. Un enumerador es un objeto que permite visitar todas las llaves de un arreglo:

    KeyEnum enum= frec.keys(); // enumerador para las llaves
    while (enum.hasMoreKeys()) {
      int num= enum.nextKey();
      ...
    }
El enumerador entrega todas las llaves, pero en cualquier orden. La solución del problema completo es entonces:

    Map frec= new Map();
    TextReader lect= new TextReader("datos.txt");
    while (true) { // Cuenta las apariciones
      int num= lect.readInt();
      if (lect.eofReached())
        break;
      int veces= 0;
      if (frec.isMapped(num))
        veces= frec.getInt(num);
      frec.put(num, veces+1);
    }
    // Muestra los resultados
    KeyEnum enum= frec.keys();
    while (enum.hasMoreKeys()) {
      int num= enum.nextKey();
      println(num+" -> "+frec.getInt(num));
    }
Los arreglos asociativos de la clase Map pueden tener llaves dispersas, es decir que las llaves no necesariamente se encuentran en un intervalo de enteros de la forma [1,n] o [0,n-1]. El espacio total requerido en memoria será proporcional al número de llaves que posean asociado. En los arreglos nativos los índices siempre deben estar en un intervalo fijo de la forma [0,n-1] y el espacio requerido es proporcional a n.

Tarea