Originally posted by Guepe
Per ora mi riguardo un po di C con cui non ho molta dimestichezza prima di incominciare a scrivere codice a caso pieno di errori :D

Originally posted by pirlo21
hai ragione...questo vorrebbe dire però che se non usiamo una lista ma un grafo, le componenti debbano essere indicizzate in base al codice indentificativo... però nell'ordinamento per costo e nella funzione lineare, ci andiamo a complicare la vita...il tutto senza contare che se bisogna veramente tenere conto dell'ordine di fissaggio è ancora più complicato

Originally posted by elrod
Ciao a tutti,

io sono rimasto un passo indietro... non riesco a capire nell'esempio con i due dispositivi:

D1 = ((c6,20),(c5,19),c1,4),(c4,2),c2,7)) e D2=((c2,1),(c3,8),(c1,11))

come ha fatto a calcolare l'estensione del primo dispositivo... il secondo l'ho capito... è la somma delle aree ma il primo no....

grazie ;)

Originally posted by carla86
l'estensione del primo dispositivo la devi calcolare calcolando le aree dei componenti, ma facendo attenzione ha sommare una volta sola le aree sovrapposte.
Io ti dico come l'ho calcolata io:
-parto da il componente che hai in posizione 19 che è il componente c5 che ha area 5x5; il componente in posizione 20, ossia c c6 è completamente sovrapposto dal componente c5 di cui hai gia calcolato l'area quindi c6 nn lo consideri senno riconsidereresti due volte la stessa area.
- hai in posizione 2 il componente di area 10x1, ma in realtà ha solo 2 unità della sua area non sovrapposte da nessun altro componente
-poi ce il componente in posizione 4 ossia il componente c1 che ha area 4x3
-e poi ce il componente in posizione 7, ossia il componente c2 che però è in parte sovrapposto dal componente c1 di cui hai gia calcolato l'area quindi da questo devi togliere la parte sovrapposta.
calcolato cosi ti viene esattamente 49 come da lui calcolato.

Originally posted by carla86
appunto xke ci sono più criteri di ricerca che secondo me dobbiamo usare la struttura dati su cui la ricerca costa meno.
poi conta che su due funzioni componente (in cui cmq devi cercare se gia esiste) e in stampa, devi ordinare le componenti in ordine di codice, in una di costo e in stampa in base alla famiglia è sempre in ordine di codice..
quindi io credo ke opterò x indicizzare su codice identificativo.

Originally posted by kalbiz
mi sembra corretto, utilizziamo una struttura dati ad albero.
probabilmente mi sfugge però qualcosa a prescindere dalla struttura utilizzata, quando faccio una ricerca, la faccio per chiave ...
se memorizzo nel mio albero binario di ricerca come chiave il codice, come sembrerebbe ovvio, come faccio poi a ricercare per famiglia ? o ordinare in base al costo ?

Originally posted by BeppeGoal
Ma scusate, non riesco a capire come vengono definiti i ganci, come faccio a sapere che un componente parte dalla posizione 20 piuttosto che da un'altra? Nell'esempio del prof il gancio non viene mai dato come input

Originally posted by Guepe
Per la disposizione lineare dopo un po di prove penso di aver capito il perchè scelga proprio quella anche se ne esistono altre con dimensione massima uguale ma ordine diverso di componenti.
Per l(2 7 17 24 26) sceglie il dispositivo formato dalle componenti che hanno maggior estensione e che soddisfano il criterio di linearità.
Ci sono 8 (se non mi sbaglio) possibili dispositivi lineari formati da:
c1 (L=4 E=12) posizioni possibili: 1°,2°,3°
c2 (L=6 E=12) posizioni possibili: 2°,3°
c3 (L=3 E=24) posizioni possibili: 1°,2°,3°
c5 (L=5 E=25) posizioni possibili: 1°,2°,3°
c6 (L=2 E=8) posizioni possibili: 4°
Dovendo avere estensione massima il dispositivo dovrà contenere per forza c5,c3 e uno tra c1 e c2 che hanno estensione uguale, ed ovviamente c6 che è l'unico a soddisfare il criterio linearità per l'ultima posizione.
Da una prima analisi, visto che nell'esempio diceva che le soluzioni possibili erano soltanto (c5,c1,c3,c6) e (c5,c2,c3,c6) ho pensato che scegliesse l'ordine dei componenti in base anche alla lunghezza di essi, infatti alla prima posizione sceglie c5, alla seconda sia c1 che c2 e alla terza c3 ma poi come soluzione finale nell'output sceglie (c5,c1,c3,c6) e quindi sto criterio va a farsi benedire....
bah pensavo di aver trovato una soluzione ma invece mi ritrovo punto a capo, quindi mi continuo a domandare perché proprio (c5,c1,c3,c6) è quella giusta quando

(c5,c2,c3,c6)
(c1,c3,c5,c6)
(c1,c5,c3,c6)
(c3,c2,c5,c6)
(c3,c5,c2,c6)
(c5,c3,c2,c6)
(c3,c1,c5,c6)

hanno estensione uguale e rispettano il criterio di linearità????

Originally posted by carla86
anke qui magari è una risposta stupida xo' ho fatto questo ragionamento:
siamo tutti daccordo ke x avere l'estensione massima deve per forza avere c5 e c3. poi l'unica che ci sta in posizione 4 è c6.
ora poteva scegliere tra c1 e c2 ma siccome sono tutte e due con estensione uguale ha scelto quella che è stata inserita x prima (in ordine lessicografico) e quindi c1?!
come ragionamento potrebbe essere o è una cavolata?

Alla fine voi come struttura x cosa avete optato? Io ho optato per un'albero red-black.

Originally posted by Guepe
allora dovrebbe essere (c1,c3,c5,c6) la sequenza corretta se si guardasse l'ordine di inserimento, o anzi (c5,c3,c1,c6) seguendo prima l'ordine per estensione e in caso di ugualianza in base all'inserimento....

Originally posted by carla86
no no io continuavo il tuo ragionamento.
secondo me è giusto come hai ragionato tu e l'ultima scelta che ha fatto il prof ossia se scegliere tra c1 e c2 ha scelto il primo in ordine lessicografico perchè l'estensione era uguale.

Originally posted by lux87
ragazzi volevo un aiuto: un consiglio su come fare ad inserire nel main i comandi "o" ed "l" (seconda e quarta riga della tabella).
grazie

Originally posted by misterx
sto guardandi gli alberi RB e non ho esperienza di questi quindi chiedo consigli.

avendo implementato l'albero ed avendolo popolato, non mi è chiaro ora cosa passare come parametri alle seguenti funzioni per la visita dei nodi in ordine

grazie

void inord(rbnode *p, rbnode *nil, void (*op)(rbnode *))
{
if(p != nil) {
inord(p->left,nil,op);
(*op)(p);
inord(p->right,nil,op);
}
}

/ **************************************************
**************************/
/*procedura che serve alla visita ordinata del grafo rb, chiama specificando il nodo di partenza*/
void inorder(rbtree *p, void (*op)(rbnode *))
{
inord(p->root, p->nil, op);
}

Originally posted by loreste
Dunque, sto aiutando un amico a fare questo progetto....
Abbiamo utilizzato un albero di ricerca ordinato per Id, in questo modo quando stampiamo tutti i componenti sono già ordinati con la ricerca simmetrica, se stampo per famiglia eseguo sempre la ricerca simmetrica, se fa parte della famiglia allora stampo.
Manca solo il punto della linearità, l'esempio del docente (esempio 1) è chiaro in quanto da per scontato su quali ganci sono appesi i componenti, ma nel progetto non è chiaro su quali ganci collocare i componenti, esempio
l(2 7 17 24 26)
quale/i componente si trova sul gancio 2??????
qualche idea?

Originally posted by carla86

...
infatti io domani mattina vado a ricevimento (gliel'ho chiesto via mail) proprio x capire bene sta situazione del lineare...
anke xke tra l'altro non ti da neanche quante posizioni sono, x cui come leggi tutte le posizioni per poi inserirle in qualche struttura?

Originally posted by loreste
Per carla86
io ho implementato un albero di ricerca ordinato per ID, ho una funzione, che dato un ID mi restituisce il nodo, clono il nodo e creo un altro albero con tutti i nodi che mi interessano ordinandoli per costo, stampo i dati e distruggo il secondo albero

Originally posted by BeppeGoal
Scusa Carla,
cosa intendi per estensione massima?
Che tra tutti i componenti che formano dispositivi lineari, si sceglie il dispositivo con l'estensione massima?

Originally posted by fa88bio
ciao a tutti...a quanto ho capito io la funzione lineare fissa la posizione dei componenti al momento della chiamata alla funzione stessa:::
l(2 7 17 24 26) significa che:
si ha a dispozizione 26-2=24 come lunghezza max del dispositivo;
il primo componente deve avere lunghezza <= di 7-2=5 unità;
il secondo <= 17-7=10 unità;
il terzo <=24-17=7 unità;
il quarto <=26-24 unità..
per questo motivo i dispositivi possono essere piu di uno e di questi si vuole stampare solo quello avente area totale maggiore....
Il problema appunto è ke se come primo componente ad esempio, nella struttura dati ce ne sono 4 che nn superano la lughezza, come secondo ce ne sono 6,ecc.....bisogna provare un numero abbastanza grosso di combinazioni per ottenere i dispositivi
il problema quindi è che quello di implementare un algoritmo che provi tutte le possibili combinazioni sui componenti

Originally posted by Spr1gg4N
altra domanda: ma quando un albero (creato magari per un'operazione momentanea) non mi serve più, come faccio esplicitamente a deallocarlo?

Originally posted by mark
bella domanda: io inizializzo banalmente il puntatore alla radice a NULL, purtroppo è una sporca che non dealloca la memoria

Originally posted by Spr1gg4N
mmm si potrebbe una soluzione...però prima cmq bisogna eliminare tutti i nodi altrimenti la memoria è cmq occupata.

Originally posted by Spr1gg4N
Per quanto riguarda la funzione lineare ho un paio di domande:
1) se non esiste una componente che stia nello spazio tra due ganci che si fa? Si lascia vuoto quello spazio oppure si stampa il messaggio di errore?

2) nell'esempio 2, come secondo componente mette c1 oppure c2 che hanno entrambi estensione 12....come mai non sceglie c3 che è più corto dei precedenti ma ha estensione maggiore (24)?

EDIT:
-------------
quindi come soluzione possibile dell'esempio 2 io metterei anche:
69: (<c5,2>,<c3,7>,<c1,17>,<c6,24>) oppure
69: (<c5,2>,<c3,7>,<c2,17>,<c6,8>)

voi che dite?

Originally posted by Spr1gg4N

Qualche idea sulla mia domanda riguardo la funzione lineare?
E' l'ultima cosa che mi manca per finire il progetto ma sono bloccato :(

Originally posted by kalbiz
se ho anche solo un componente che si adatta ad uno dei ganci perchè non dovrebbe costruire un dispositivo ??
cioè
c 1 2 3 2 5
c 2 3 4 3 5

l 2 4 5

dovrebbe restituire
c 1 2 3 2 5

Originally posted by misterx
io ho toccato il meno possibile evitando di eliminare quello che non è strattamente chiaro, al massimo viene passato un parametro che non viene usato in questa implementazione

Originally posted by Spr1gg4N
ragazzi ma voi come avete risolto per l'input del comando "o" (ordina)?
non riesco proprio a creare un array di int che aumenti dimensione man mano che viene inserito un nuovo numero in input -.-'

Originally posted by Spr1gg4N
ragazzi ma voi come avete risolto per l'input del comando "o" (ordina)?
non riesco proprio a creare un array di int che aumenti dimensione man mano che viene inserito un nuovo numero in input -.-'

Originally posted by Spr1gg4N
Per quanto riguarda la funzione lineare ho un paio di domande:
1) se non esiste una componente che stia nello spazio tra due ganci che si fa? Si lascia vuoto quello spazio oppure si stampa il messaggio di errore?

2) nell'esempio 2, come secondo componente mette c1 oppure c2 che hanno entrambi estensione 12....come mai non sceglie c3 che è più corto dei precedenti ma ha estensione maggiore (24)?

EDIT:
-------------
quindi come soluzione possibile dell'esempio 2 io metterei anche:
69: (<c5,2>,<c3,7>,<c1,17>,<c6,24>) oppure
69: (<c5,2>,<c3,7>,<c2,17>,<c6,8>)

voi che dite?

Originally posted by mark
sporca numero 2

usare la funzione inorder() per visitare tutto l'albero e usare nodedelete() o similare per eliminare tutti i nodi

infine eliminare la radice con NULL

Originally posted by carla86
ciao!!
qualcuno d voi ke ha implementato gli alberi di ricerca binaria e ha implementato anke la funzione di distruggere l'albero.
quando andate a compilare con -Wall e -ansi anke a voi da questo warning:

In function ‘distruggialbero’:
progetto.c:459: warning: suggest parentheses around assignment used as truth value

secondo voi da cosa è dovuto? vi copio la mia riga 459
while(p = cancella(p, p));

grazie

Originally posted by Guepe
sto impazzendo sull'ordinamento per costo...io mi ritrovo una lista su kiave id con dentro i componenti presi dall'albero. come faccio a ordinarli in base al costo? come avete fatto voi?

Originally posted by Guepe
Risolto!!ho abbandonato le liste e ho creato u nalbero nuovo e poi inorder fa tutto, rimane solo un problema....nn mi prende l'ultimo componente nella ricerca e nn so il perchè...bah continuo a far prove....

Originally posted by carla86
qualcuno ha fatto la funzione lineare?!?!

io mi sa ke sono fusa..
sono riuscita a leggere tutte le posizioni inseritemi cn il comando l e le ho memorizzate in una lista.
mi sono creata un'altro albero rb con i componenti ordinati per area (come da qualcuno suggerito).
ma ora nn so come calcolare, o meglio nn so dove memorizzare le distanze, ogni volta la distanza tra una posizione e la successiva x poter controllare ke il massimo ritornatomi dall'albero ordinato per area possa stare in quella posizione.

qualche idea??

Originally posted by Guepe
Non so dove sbaglio ma dopo tre ore mi sto per mangiare il pc!!
Carla nella funzione ordina per creare un albero nuovo inserendo i componenti con kiave c (costo) tu come hai fatto? Hai riscritto le funzioni di inserimento dei componenti nell'albero? Cosi facendo mi continua a ordinarli per id anche se nelle due funzioni la posizione dei nodi è definita dalle equazioni con il costo come paramentro.....nn capisco come sia possibile...

Originally posted by Guepe
Non so dove sbaglio ma dopo tre ore mi sto per mangiare il pc!!
Carla nella funzione ordina per creare un albero nuovo inserendo i componenti con kiave c (costo) tu come hai fatto? Hai riscritto le funzioni di inserimento dei componenti nell'albero? Cosi facendo mi continua a ordinarli per id anche se nelle due funzioni la posizione dei nodi è definita dalle equazioni con il costo come paramentro.....nn capisco come sia possibile...