Equilibri parell/senar en arbres binaris X33722
Un arbre està equilibrat parell/senar si compleix dues condicions:
- La diferència entre el nombre de números parells i el nombre de números senars que hi ha a l’arbre és, com a màxim, 1. És a dir, que o bé hi ha tants números parells com senars a l’arbre, o bé hi ha com a màxim un número més de senars, o bé un número més de parells. Algebraicament: abs(Parells(A) − Senars(A)) ≤ 1.
- La condició anterior s’aplica a tots els subarbres.
Observeu el següent exemple:
1
|
-------- --------
| |
2 3
| |
---- ---- ------- -------
| | | |
3 3 2 1
| |
---- ---- ---- ----
| | | |
1 2 2 2
L’arbre té, en total, 6 números senars, i té 5 números parells. Per tant, compleix la primera condició. A més, com que tots els seus subarbres compleixen aquesta condició, l’arbre està parell/senar equilibrat. Considerem, per exemple, el següent subarbre de l’arbre anterior:
6
|
------- -------
| |
2 1
| |
---- ---- ---- ----
| | | |
1 2 1 2
|
1
Aquest subarbre té 4 senars i 4 parells. Per tant, compleix la primera condició.
Però hi ha un dels subarbres que no compleix aquesta condició, concretament, el subarbre marcat a dins del quadre, que té dos senars però cap parell:
6
|
------- -------
| |
2 1
| |
---- ---- ---- ----
| | | |
------ | | |
| 1 | 2 1 2
==> | | |
| 1 |
------
Aquest arbre NO està parell/senar equilibrat.
Observació: Un arbre pot complir la condició 1, però això no implica necessàriament que tots els seus subarbres la compleixin.
Observació: Un arbre buit o que té un sol node està sempre parell/senar equilibrat.
Heu d’implementar una funció que rep un arbre d’enters, i retorna un booleà indicant si l’arbre està parell/senar equilibrat. Aquesta és la capçalera:
-
Aés un arbre binari d’enters. - Torna
truesi i només siAestà parell/senar equilibrat.
bool equilibriSenarParell(const BinaryTree<int> &A);
Fixeu-vos que l’enunciat d’aquest exercici ja ofereix uns fitxers que haureu d’utilitzar per a compilar: Makefile, program.cpp, BinaryTree.hpp, equilibriSenarParell.hpp. Us falta crear el fitxer equilibriSenarParell.cpp amb els corresponents includes i implementar-hi la funció anterior. Quan pugeu la vostra solució al jutge, només cal que pugeu un tar construït així:
tar cf solution.tar equilibriSenarParell.cpp
Entrada
La primera linia de l’entrada descriu el format en el que es descriuen els arbres, o bé INLINEFORMAT o bé VISUALFORMAT. Després venen un nombre arbitrari de casos. Cada cas consisteix en una descripció d’un arbre binari d’strings que representa un arbre de directoris i fitxers. Fixeu-vos en que el programa que us oferim ja s’encarrega de llegir aquestes entrades. Només cal que implementeu la funció abans esmentada.
Sortida
Per a cada cas, la sortida conté cert si l’arbre està parell/senar equilibrat, fals altrament. Fixeu-vos en que el programa que us oferim ja s’encarrega d’escriure el resultat. Només cal que implementeu la funció abans esmentada.
Observació
Podeu implementar les funcions auxiliars que considereu necessàries, però la vostra funció i subfuncions que creeu han de treballar només amb arbres. Per a resoldre aquest exercici, no us permetem utilitzar cap mecanisme d’enmagatzemament massiu de dades a part del propi arbre binari que es rep com a paràmetre, i els strings que siguin necessaris. Us recomanem, doncs, que resolgueu aquest exercici recursivament. En les crides recursives, incloeu la hipòtesi d’inducció, és a dir una explicació del que es cumpleix després de la crida, i també la funció de fita/decreixement.
Una solució iterativa a aquest problema tindrà un zero, independentment de si passa o no el jocs de proves.
Avaluació sobre 10 punts:
- Solució lenta: 6 punts.
- Solució lenta + justificació: 8 punts.
- solució ràpida: 8 punts.
- solució ràpida + justificació: 10 punts.
Entenem com a solució lenta una que és correcta i capaç de superar els jocs de proves públics. Entenem com a solució ràpida una que és correcta i capaç de superar els jocs de proves públics i privats. La justificació val 2 punts i consisteix en definir correctament les PRE/POST de les funcions auxiliars que afegiu i en definir correctament les hipòtesis d’inducció i funcions de fita.
Input
VISUALFORMAT
1
|
-------- --------
| |
2 3
| |
---- ---- ------- -------
| | | |
3 3 2 1
| |
---- ---- ---- ----
| | | |
1 2 2 2
1
|
-------- --------
| |
2 3
| |
---- ---- ------- -------
| | | |
3 3 2 1
| |
---- ---- ---- ----
| | | |
1 2 2 1
1
|
-------- --------
| |
2 7
| |
---- ---- ------- -------
| | | |
3 5 4 11
| |
---- ---- ---- ----
| | | |
9 6 8 10
1
|
-------- --------
| |
1 7
| |
---- ---- ------- -------
| | | |
2 4 5 2
| |
---- ---- ---- ----
| | | |
9 6 8 10
1
|
----
|
2
|
----
|
1
|
----
|
2
|
----
|
1
|
----
|
2
|
----
|
1
|
----
|
2
|
----
|
1
|
----
|
2
|
----
|
1
|
----
|
2
1
|
----
|
2
|
----
|
1
|
----
|
2
|
----
|
1
|
----
|
2
|
----
|
1
|
----
|
2
|
----
|
1
|
----
|
2
|
----
|
1
|
----
|
1
Output
cert fals cert fals cert fals
Input
INLINEFORMAT 1(2(3(,),3(,)),3(2(1(,),2(,)),1(2(,),2(,)))) 1(2(3(,),3(,)),3(2(1(,),2(,)),1(2(,),1(,)))) 1(2(3(,),5(,)),7(4(9(,),6(,)),11(8(,),10(,)))) 1(1(2(,),4(,)),7(5(9(,),6(,)),2(8(,),10(,)))) 1(2(1(2(1(2(1(2(1(2(1(2(,),),),),),),),),),),),) 1(2(1(2(1(2(1(2(1(2(1(1(,),),),),),),),),),),),)
Output
cert fals cert fals cert fals
- Author
- Language
- Catalan
- Official solutions
- Make
- User solutions
- Make