Ejemplos de soluciones del examen final de PRO2, junio 2012.
------------------------------------------------------------

Problema 1: Se han recuperado los nombres de los campos de la clase Cua tal
como aparecen en el material de laboratorio (seguent en vez de seg, etc), por
si se quiere probar la operación sobre máquina.

Los comentarios indican el papel de cada variable y cada rama de if.
Consideramos que un elemento de C es "visitado" en la vuelta del bucle en que
su valor se compara con k.

void mou_grans_cua(Cua &c, int k)
  /* Pre: p.i. vacia, c=C */
  /* Post: se ha eliminado de c y se han colocado en el p.i. todos los 
     elementos de C mayores que k, en el mismo orden relativo en que aparecian
     en C; c contiene el resto de elementos de C en el orden relativo original */
{
  if (c.primer_node != NULL) {          // solo hacemos algo si C no es vacia
    node_cua* auxc = c.primer_node;     // elemento en curso de C
    c.primer_node = NULL;         // primero de los visitados y no movidos de C
    c.ultim_node = NULL;          // ultimo de los visitados y no movidos de C
    // (primer_node y ultim_node son lo equivalente para los movidos al p.i.) 
    while (auxc != NULL){               // mientras queden elementos por visitar
      if (auxc->info > k) {               // si hay que mover auxc
	if (ultim_node == NULL) primer_node = auxc; // si p.i. esta vacia
	else ultim_node->seguent = auxc;            // si p.i. no esta vacia
	ultim_node = auxc; 
	++longitud;
      }
      else {                              // si no hay que mover auxc
	if (c.ultim_node == NULL) c.primer_node = auxc; // si aún no se ha 
                                                        // movido ninguno
	else c.ultim_node->seguent = auxc;          // si ya se ha movido alguno
	c.ultim_node = auxc;
      }
      auxc = auxc->seguent;  // avanzamos
    }
    // arreglamos los seg de ult y c.ult si es necesario 
    if (ultim_node != NULL) ultim_node->seguent = NULL;
    if (c.ultim_node != NULL) c.ultim_node->seguent = NULL;
    // y actualizamos la longitud de c
    c.longitud-=longitud;
  }
}


Notad que en cada vuelta del bucle se realizan las siguientes operaciones:

- 2 comparaciones y 3 asignaciones, si hay que mover el elemento en curso de C
- 2 comparaciones y 2 asignaciones, si no hay que moverlo.
- la comprobación de la condición del bucle
- la asignación para avanzar en el bucle

Hay muchas otras soluciones correctas, que usan algunas variables auxiliares
más y aplican algunas instrucciones más en cada caso.  En el examen no
penalizamos este hecho, salvo que se cometan verdaderos excesos. También hay
soluciones correctas no tan simétricas, es decir, que hacen más cosas en el
primer caso que en el segundo.

Sí se penaliza el crear nodos nuevos (new) y aún más si no se aplica el
correspondiente delete. Obviamente, también hay penalizaciones si las colas
quedan mal enlazadas, si se intenta acceder al ->seg de un puntero sin haber
comprobado que dicho puntero no es NULL o si alguno de los prim, ult o longitud
del p.i. o de c quedan con valores incorrectos.

Existen soluciones más sofisticadas que permiten diversas mejoras: por ejemplo,
es posible ahorrar el if que inicializa a primer_node o el de c.primer_node si
podemos garantizar que entramos en el bucle habiendo inicializado ya uno u
otro. También hay soluciones buenas sin usar *ningun* puntero auxiliar: una
opción para ello es usar un for basado en la longitud de C, pero también se ha
aplicar alguna idea original más.







Problema 2: La solución más sencilla y eficiente y menos expuesta a errores
consiste en usar una inmersión que retorna un puntero a node_arbreNari.

ArbreNari (int n, ArbreGen<T> &g)
/* Pre: n>=2 */
/* Post: el resultat és un arbre n-ari que aproxima l'arbre general g */
{
  N = n; 
  if (g.es_buit()) primer_node = NULL; 
  else primer_node = aproxima(n,g);
}


static node_arbreNari* aproxima(int n, ArbreGen<T> &g)
/* Pre: n>=2, g no és buit */
/* Post: el resultat apunta al node arrel d'una jerarquia de nodes que 
   formen un arbre n-ari que aproxima l'arbre general g */
{ 
  // aprovechamos que los subarboles de un arbol general no pueden ser vacios
  // para ahorrarnos un if (g.es_buit())

  node_arbreNari* aux = new node_arbreNari;                    // (1)
  aux->info = g.arrel();
  aux->seg = vector<node_arbreNari*> (n);
  int m = min(n, g.nombre_fills());                            // (2)
  vector<ArbreGen<T> > v;
  g.fills(v);
  for (int i=0; i<m; ++i) aux->seg[i] = aproxima(n,v[i]);
  for (int i=m; i<n; ++i) aux->seg[i] = NULL;                  // (3)
  return aux;
}

(1) es obligatorio crear nodos node_arbreNari nuevos

(2) es preferible obtener este min y usar estos dos for simples, en lugar de un
único for con un if dentro

(3) en algunas versiones de C++, los elementos de un vector de punteros se
inicializan automáticamente a NULL, pero en otras no; en algunas, la
instrucción aux->seg = vector<node_arbreNari*> (n,NULL) es válida, pero en
otras no.

Se pueden obtener versiones correctas pero no tan eficientes (y expuestas a
errores difíciles de prever) mediantes inmersiones que no retornen punteros
sino árboles N-arios, o sean void y los obtengan en el parámetro implícito o
como parámetros por referencia. Incluso, se puede obtener un diseño recursivo
*sin inmersión*, pero con inconvenientes similares.

Se consideran errores graves las asignaciones inconsistentes (puntero=arbol o
viceversa) y los accesos a posiciones fuera de rango del vector de los hijos de
g. Se consideran errores muy graves los accesos a campos del árbol general (por
ejemplo, g.primer_node->info o g.primer_node->seg[i]).