PRO2 Parcial Teoria 11/10

/* PROBLEMA 1: PREFIX MAXIM DE SUMA ZERO */

int long_pref_sumax(const vector<int> &v)
/* Pre: cert */
/* Post: el resultat es la longitud del prefix mes llarg de v que suma zero */
{
  int i, j, suma;
  i = j = suma = 0;
  /* Inv: 0 <= i <= v.size(), posicio que consultem actualment
   *      0 <= j <= v.size(), longitut prefix de v[0..i]
   *      suma val la suma dels elements de v[0..i-1]
   */
  while (i < v.size()) {
    suma += v[i];
    ++i;
    if (suma == 0) j = i;
  }
  /* A: i == v.size()
   *    j es la longitud del prefix maxim de v
   *    suma es la suma dels elements de v[0..v.size()-1]
   */
  return j;
}


/*****************************************************************************/


/* PROBLEMA 2: ARBRE D'ALTURES */

int max_altura(const Arbre<int>& a1, const Arbre<int>& a2)
/* Pre: cert */
/* Post: retorna l'altura màxima de dos arbres a1 i a2 */
{
  if (a1.es_buit() && a2.es_buit()) return 0;
  else if (a1.es_buit() && !a2.es_buit()) return a2.arrel();
  else if (!a1.es_buit() && a2.es_buit()) return a1.arrel();
  else {
    int x = a1.arrel();
    int y = a2.arrel();
    if (x > y) return x;
    else return y;
  }
}


Arbre<int> arbre_alt(Arbre<int>& a)
/* Pre: cert */
/* Post: el resultat es un arbre ambn la mateixa forma que a, on cada element
 *       es l'altura del subarbre d'a que te com a arrel el corresponent de
 *       l'esmentat element
 */
{
  Arbre<int> resultat;
  Arbre<int> a1, a2;
  if (!a.es_buit()){
    a.fills(a1, a2);
    if (!a1.es_buit() || !a2.es_buit()) {
      a1 = arbre_alt(a1);
      a2 = arbre_alt(a2);
    }
    resultat.plantar(max_altura(a1, a2), a1, a2);
    /* HI: Si els fills d'un arbre a estan buits, significa que tenim un element que es una fulla,
     *     que per definicio te altura 1 per tant el l'arbre d'altures li assignem el valor 1.
     *     A cada crida recursiva descendim per l'arbre fins arribar a una fulla i poder aplicar HI
     */
  }
  return resultat;
}

//JosepRivaille