HomeWork504 < Programmazione1/AA0506/PZ

Tags: view all tags

---++ Homework (compito per casa) 5 
---++ Alberi di Natale
 
Vedi anche: DomandeHomework504, SoluzioneHomework504, RisultatiHomework504
----
%TOC%
----

---+++ Descrizione
In un albero binario di interi, *una pallina rossa* è un nodo in cui la radice è etichettata con un numero intero maggiore o uguale di tutte le etichette presenti nei sottoalberi. Una *pallina blu* è un nodo in cui la radice è etichettata con un numero intero minore o uguale a tutte le etichette presenti nei sottoalberi. 
Un nodo *esterno destro* è o la radice o il figlio destro di un nodo esterno destro.
Un nodo *esterno sinistro* è o la radice o il figlio sinistro di un nodo esterno sinistro. Un nodo e' *esterno* se è un nodo esterno sinistro o esterno destro.
Un *albero di natale* è un albero binario di interi in cui i nodi esterni sono tutti o palline blu o palline rosse.
Il programma dovrà semplicemente stampare 1 se l'albero in input è un albero di natale e 0 altrimenti.

---++++ Input
L'albero in input verrà rappresentato da una stringa che segue la seguente sintassi: 
   * l' *albero vuoto* è rappresentato dal carattere '*';
   * un albero *foglia* (cioè un albero con entrambi i figli vuoti) è rappresentato semplicemente dal contenuto del campo informazione;
   * gli altri alberi sono rappresentati nella forma: radice(FS, FD), dove radice è il contenuto dell'informazione nella radice e FS ed FD sono rispettivamente rappresentazione del sottoalbero sinistro e destro. 
Ad esempio, la stringa "3(6, 8(1,4(*,2)))" rappresenta l'albero binario:
<pre style='background:lightgrey'> 
............3
........6..........8
............... 1.....4
.........................2
</pre>

Osservate che le foglie, sono riconoscibili dal fatto che non sono seguite dal carattere "(". 
*Suggerimento*: osservate che se scrivete una procedura ricorsiva per creare un albero in memoria con la consueta struttura a puntatori, osservate che la presenza di una virgola chiude la lettura di un sottoalbero sinistro, e la presenza di una parentesi tonda chiusa chiude la lettura di un sottoalbero destro.


---++++ Output
   * produrre in output semplicemente il numero 1 o il numero 0 a seconda che l'albero di input sia o non sia un albero di Natale.


*IMPORTANTE* 
   * non far produrre al programma altri output oltre a quelli richiesti.  

Ecco un esempio di input in cui il programma deve rispondere 0:
<pre style='background:lightgrey'> 

8(4(6,2),5(1,*))  
</pre>
Questo perchè c'è un nodo esterno (il 4), che non è nè una pallina blu, nè una pallina rossa).


Ecco un esempio di input in cui il programma deve rispondere 1:
<pre style='background:lightgrey'> 

8(1(6,2),5(1,*))
</pre>


In questo caso la radice è una pallina rossa, l'1 è una pallina blu, il 5 una pallina rossa. Osservate che, stando alle definizioni date, le foglie sono sempre sia palline blu che palline rosse.

__%RED%Attenzione%FINE%__ NON producete nessuna altra scritta oltre i numeri, altrimenti il test automatico del vostro programma fallirà miseramente! :-(

---+++ Come compilare ed eseguire il programma
   * usate un editor per scrivere il testo del programma e salvatelo in formato *testo semplice* in un file con l'estensione *.c* (ad esempio di nome trexpuno.c)
      * NON usate Word, Openoffice, Kword, Abiword che introducono caratteri strani
   * compilate (e contemporaneamente linkate) il programma con il comando
<pre style='background:lightgrey'>
gcc -g -o natale natale.c
</pre>
   * eseguite il programma scrivendo
<pre style='background:lightgrey'>
./natale
</pre>


---+++ Come consegnare il programma

   * Avete tempo fino a *%RED%Venerdì 14 gennaio alle ore 23.59%FINE%* (ora sono le *%SERVERTIME{"$hou:$min del $day"}%*).
   * Consegnate *il testo del programma sorgente C* da voi scritto. Io lo compilerò e testerò.
   * Usate *esclusivamente* la <a href="/~prog1/consegna-Prog5.html">pagina di consegna</a>. Non verranno accettate spedizioni via email.

   * Set ALLOWTOPICCHANGE = Users.DocentiProg1Group

-- Users.IvanoSalvo - 16 Dec 2004