Homework (compito per casa) 5

Alberi di Natale

Vedi anche: DomandeHomework504, SoluzioneHomework504, RisultatiHomework504



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:
 
............3
........6..........8
............... 1.....4
.........................2

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:

 

8(4(6,2),5(1,*))  
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:

 

8(1(6,2),5(1,*))

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.

Attenzione NON producete nessuna altra scritta oltre i numeri, altrimenti il test automatico del vostro programma fallirà miseramente! frown

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
gcc -g -o natale natale.c
  • eseguite il programma scrivendo
./natale

Come consegnare il programma

  • Avete tempo fino a Venerdì 14 gennaio alle ore 23.59 (ora sono le 00:19 del 29).
  • Consegnate il testo del programma sorgente C da voi scritto. Io lo compilerò e testerò.
  • Usate esclusivamente la pagina di consegna. Non verranno accettate spedizioni via email.

-- IvanoSalvo - 16 Dec 2004


This topic: Programmazione1/AA0506/PZ > WebHome > HomeWork504
Topic revision: r2 - 2004-12-17 - IvanoSalvo
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback