PDA

Visualizza la versione completa : [BASH] Descrivere albero planare con radice


mbt
11-06-2007, 14:35
Ciao a tutti
sono un studente d'informatica
devo fare questo progetto

Realizzare lo script tree.sh, con possibile opzione -f, che prende come
input un vettore binario u di lunghezza 2n e controlla che descriva un
albero planare con radice. Precisamente si deve testare che:
1.|u|(1)=|u|(0) (cioè il numero di elementi 1 e 0 in u è lo stesso);
2.per ogni prefisso u' di u, si ha |u'|(1)>|u'|(0).
L'opzione -f calcola anche il numero di foglie dell'albero, nel caso in
cui u rappresenti effettivamente un albero planare.
Dovranno essere effettuati tutti i controlli necessari per evitare
malfunzionamenti del programma.

===============================

Nota per la comprensione del testo:
dato un vettore binario u che soddisfi le proprietà 1. e 2. elencate sopra,
si può associare ad esso in maniera univoca un albero planare con radice
nel modo seguente:
a) al vettore vuoto di lunghezza 0 corrisponde l'albero planare avente
un solo nodo e nessun ramo;
b) se u ha lunghezza 2n>0, percorrendo u da sinistra verso destra, ogni
volta che si incontra un 1 si aggiunge un ramo all'albero, mentre ogni
volta che si incontra uno 0 si risale l'albero lungo il ramo incidente
il nodo in cui ci si trova.
Esempio:
u=(1 1 0 1 0 1 1 0 0 0) corrisponde all'albero

1
/
2
/|\
3 4 5
|
6

in quanto:
1) dal nodo 1 si scende al nodo 2 perchè u(1)=1;
2) dal nodo 2 si scende al nodo 3 perchè u(2)=1;
3) dal nodo 3 si risale al nodo 2 perchè u(3)=0;
4) dal nodo 2 si scende al nodo 4 perchè u(4)=1;
5) dal nodo 4 si risale al nodo 2 perchè u(5)=0;
6) dal nodo 2 si scende al nodo 5 perchè u(6)=1;
7) dal nodo 5 si scende al nodo 6 perchè u(7)=1;
Cool dal nodo 6 si risale al nodo 5 perchè u(Cool=0;
9) dal nodo 5 si risale al nodo 2 perchè u(9)=0;
10) dal nodo 2 si risale al nodo 1 perchè u(10)=0.

In un albero planare con radice, ciascun nodo di grado 1 diverso dalla
radice viene chiamato foglia.

HO AVUTO I PROBLEMI X REALIZZARLO
MI POTETE AIUTARE

VI RINGRAZIO TANTISSIMO

LeleFT
11-06-2007, 14:43
Non è sufficiente dire "ho avuto problemi a farlo"... devi anche dire quali sono i problemi che hai incontrato, dove lihai incontrati, postare il codice che hai scritto e dire quali sono i risultati che attendevi di vedere e quali, invece, hai ottenuto.

Così come è posta la domanda, sembrerebbe un bel gioco di parole per dire "chi me lo fa?"

Oltretutto, nel titolo non hai specificato il linguaggio (si evince dalla discussione che si parla di script bash), come il regolamento prevede.


Lascio aperta in attesa di ulteriori informazioni.


Ciao. :ciauz:

Loading