Doneu definicions inductives de les funcions que es demanen a continuació
tals que permetin fer una funció recursiva per resoldre-les. 

No vull codi C++, només definicions matemàtiques per casos. De vegades
pot passar que la funció que es demana no es defineix recursivament,
sinó cridant una altra funció que és la que es defineix recursivament. 
Altres vegades, cal cridar aquesta funció que es defineix recursivament,
a més de donar una definició recursiva per la que es demana. 

Noteu que tampoc demano una definició que doni, si s'implementa directament,
una solució recursiva molt eficient. En el tema 6 parlarem de com accelerar
algunes d'aquestes deifinicions ineficients. 

1. donat un vector v de doubles i dos índexos a i b, retorneu la suma de v[a..b]

/* Pre: .... */
/* Post: el resultat és la suma de v[a..b]
double suma(const vector<double> &v, int a, int b);

Esquema de la definició que voldria:

suma(v,a,b)  = 0 si..., i si no és blabla suma(v,...,....) blablabla

Hi ha vàries definicions diferents correctes en aquest cas, a veure si les trobeu.

2. siguin v1 i v2 dos vectors que nomes contenen enters entre 0 i 9. Podem 
interpretar que representen enters, on la posició 0 és el dígit menys significatiu.
Digueu si v1 representa un enter més gran, més petit, o igual que v2.

/* Pre: ... */
/* Post: retorna 1 si v1[i..v1.size()-1] codifica un enter > que el codificat per v2[i..v2.size()-1]
   0 si codifiquen el mateix enter, i -1 si < */
int compara(const vector<int>& v1, const vector<int>& v2, int i);

v1 i v2 no tenen necessàriament la mateixa mida.
P.ex., si v1 = [3,0,5] i v2 = [3,2,0,0] v1 representa 503 i v2 23, per tant 
caldria retornar 1. 

3. Digueu si una pila de doubles és creixent de dalt a baix, és a dir, si cada element és estrictament
més gran que el que té a sota. Per exemple, [6, 4, 2, -1] és creixent, però [6, 4, 7, -1] no és creixent. 

4. Digueu si tots els elements d'una pila són diferents. 
Pista: useu una funció cerca(pila p, int x)

5. Digueu si una pila té algun element dominant.
x es dominant en la pila si és mes gran que la suma de tots els elements
que té per sota. Per exemple, en la pila [3 13 -5 8 2 4] (on 3 és al cim), 
8 > 2 + 4 és ún element dominant, i 13 > -5+8+2+4 un altre, i la funció
hauria de retornar cert amb les dues piles. 
En canvi, la pila [4,3,2] no té cap element dominant (no es considera que
el 2 domini la pila buida que té per sota), i la funció hauria de retornar fals. 
Pista. Useu una funció auxiliar suma(pila p).

6. Digueu si una pila és fàsica. Fàsica vol dir que té es pot dividir en dues parts.
una amb elements positius, a dalt, i a baix una amb només negatius. 
o sigui si hi ha un i tal que e(1)...e(i) són positius i e(i+1)... e(n) són negatius 
(tant la part positiva com la negativa poden ser buides). 
Per exemple, [3,2,-5,-6,-1], [-2,-4] i [4,7,8] són fàsiques les tres. 
En canvi [3,-1,2,5] i [-1,-4,3] i [2,0,-1] no són fàsiques.
Pista: 
funcio auxiliar tots_negatius(p) (que heu de definir inductivament també)
que diu si p conté només nombres negatius.

7. dir si una pila és prefix d'una altra. P1 és prefix de P2 si P2 es pot construir
agafant P1 i posant-hi alguns elements addicionals al damunt


----------- Solucions -----------

1. 

suma(v,a,b) = 0 si a > b
i si a <= b dues opcions: 
suma(v,a,b) = v[a]+suma(v,a+1,b)
            = suma(a,b-1)+v[b]

alternativament, la segona equació 
pot expandir-se amb una que tracta el cas a=b,
però no cal. 

També pot definir-se

suma(v,a,b) = suma(v,a,(a+b)/2) + suma(v,(a+b)/2,b)

Però atenció perquè llavors cal tractar el cas 
a=b separadament, sinó quan a = b-1 o quan a = b
alguna de les crides recursives no fa decrèixer res.
No dona tampoc una solució més eficient que les altres, perquè
igualment es recorren tots els elements.

2. Ho faig per al cas en que sabem que tenen la mateixa mida.
Els casos en que tenen mides diferents es poden tractar amb casos bases i, 
per exemple, una funció que mira si un bocí de vector és tot 0 o conté un número >0, 
o bé amb condicions engorroses sobre v1.size() i v2.size(). 

Fixeu-vos que ja introdueixo un paràmetre "i" que
permet fer immersió d'eficiència. Si només hagués
demanat "comparar v1 i v2", caldria fer-la. 

compara(v1,v2,i) = 0 si i = v1.size()
     = compara(v1,v2,i+1) si compara(v1,v2,i+1) != 0
     i si compara(v1,v2,i+1) = 0, llavors
     -1 si v1[i]<v2[i], 1 si v1[i]>v2[i], i 0 altrament
     
Com a deures addicionals, mireu la immersió
al revés: en comptes de comparar v[i..v.size()-1], comparar
amb v[0..i]

compara(v1,v2,i) = 0 si i = -1, i si i>=0, 
                   1 si v1[i]>v2[i]
                   -1 si v1[i]<v2[i]
                   compara(v1,v2,i-1) si v1[i]=v2[i]
                   
3. pila creixent

creixent(p) = cert si mida(p) <= 1
   (es a dir, si buida o p.pop() es buida)
   
altrament, creixent(p) = (p.top() > p.pop().top() 
                          and creixent(p.pop())
                          
Repeteixo que en aquest tipus d'exercicis faig servir
p.pop() com si retornés una pila, però que en la STL
és pop retorna void i no es pot usar així.

A partir d'aquesta definició treiem:

bool creixent(pila p) {
    if (p.e_buida()) return true;
    else { 
        x = p.top();
        p.pop();
        if (p.ex_buida()) return true;
        else {
            return (x > p.top() and creixent(p));
        }
    }
} 

Fixem-nos que el primer cas base només s'usa si la pila
inicial és buida. En qualsevol altre cas, s'usarà el segon
cas base (que també comprova si p és buida). Es pot
evitar aquesta raresa usant mida(p), si es permet. 

4. 

diferents(pila buida) = cert

diferents(pila p no buida) = 
      not pertany(p.top(),p.pop()) and diferents(p.pop())
      
Aquesta solució compara cada element amb tots els que té per sota, 
i per tant té cost quadràtic en la mida de la pila. Això es inevitable
(no hi ha immersió d'eficiència que ho arregli) si només
podem usar variables simples, vectors, llistes, piles, etc.

Però té una solució eficient si podem fer servir els maps que
us han explicat a laboratori. La veieu?

5. 

te_dominant(pilabuida) = fals
te_dominant(pila amb un element) = fals
te_dominant(p de mes d'un element) = (p.top() > suma(p.pop()) o te_dominant(p.pop())

una implementació directa a partir d'aquesta definició serà ineficient
perquè recorrerà dos cops la pila, una per calcular la suma i una per
comprovar si la resta de la pila té un dominant. 

S'evita fent una immersió d'eficiencia de l'estil

// Pre: cert
// Post: el resultat diu si p te algun element dominant, i sum conte
// la suma dels elements de p
bool i_te_dominant(pila p, int& sum)

6.

fasica(pbuida) = true
fasica(p no buida) = tots_negatius(p.pop()) si p.top() < 0
          = false si p.top() = 0
          = fasica(p.pop()) si p.top() > 0
          
amb 

tots_negatius(pbuida) = true
tots_negatius(p) = p.top() < 0 and tots_negatius(p.pop())

7. 

una solució: 

prefix(buida,p) = cert
prefix(nobuida,buida) = fals
prefix(p1,p2) = iguals(p1,p2) or prefix(p1,p2.pop())

Però la seva implementació directa porta a un algorisme ineficient
perquè per a cada element de p2 es recorren (en el cas pitjor) 
tot p1 i p2, cal fer còpies, etc. 

Si algú veu una immersió d'eficiència d'aquesta definició que 
doni una solució lineal, li estaré agraït. 

Si suposem que tenim size() que funciona en temps unitat, aquesta és una
implementació més eficient: 

prefix(p1,p2) = fals si p1.size() > p2.size()
prefix(p1,p2) = iguals(p1,p2) of p1.size() == p2.size()
prefix(p1,p2) = prefix(p1,p2.pop()) if p1.size() < p2.size()

Fins i tot si size() recorrés tota la pila, podria fer-se
eficient fent una única crida a p.size() en la crida inicial
(un sol cop) i anar passant la mida decrementada en 1 
a la funció d'immersió. 

Aquest exemple demostra com és d'important trobar la bona definició
per donar una solució ben eficient.