 | |
Il progetto dsy.it è l'unofficial support site dei corsi di laurea del Dipartimento di Scienze dell'Informazione e del Dipartimento di Informatica e Comunicazione della Statale di Milano. E' un servizio degli studenti per gli studenti, curato in modo no-profit da un gruppo di essi. I nostri servizi comprendono aree di discussione per ogni Corso di Laurea, un'area download per lo scambio file, una raccolta di link e un motore di ricerca, il supporto agli studenti lavoratori, il forum hosting per Professori e studenti, i blog, e molto altro...
In questa sezione è indicizzato in textonly il contenuto del nostro forum |
[ALGORITMI - TORELLI] Progetto "RECINTI"
Clicca QUI per vedere il messaggio nel forum |
| lino |
| Domani esce il testo..... speriamo in bene. |
| Jacoposki |
| speriamo in bene sì, diobono. |
| ZeroByte |
| E' online il testo del progetto!! In bocca al lupo a tutti coloro che devono affrontarlo!! |
| superfabius |
A me sembra molto più semplice del precedente
No? |
| fixxxer |
| si, in effetti è moooooolto + semplice |
| lino |
| Solo una domanda..... qualcuno di voi potrebbe spiegarmi, sulla base dell'esempio riportato, come si calcola la capienza del recinto? |
| lino |
| altra domanda..... alla funzione recinto cosa mettete come paramentri? |
| Jacoposki |
| a prima vista direi che recinto prenderà come parametro un array di int... visto che il numero di int non è prefissato mi pare l'unico modo. |
| Jacoposki |
| la capienza del recinto boh... sospetto che c'entri qualcosa quel paragrafetto sul determinante della matrice 2x2 ma ci devo ragionare un po' su :) |
| superfabius |
| io nn capisco la storia della matrice ....lo calceolerei in altro modo il numer odi punti |
| superfabius |
Originally posted by superfabius
io nn capisco la storia della matrice ....lo calceolerei in altro modo il numer odi punti
capita :D
poi altra roba........
Per quanto riguarda la costruzione del recinto nella prima pagina viene scritto:
"Non verrà mai chiesto di costruire i recinti
R(2, 2, .....) R(0, 3, ....) "
Quindi non ci si deve preoccupare assolutamente della costruzione del recinto o si deve fare un controllo che verifica la correttezza del poligono? :? |
| Jacoposki |
| no, questo è come l'altra volta: si suppone un input corretto. |
| mazob |
Ciao
forse la mia domanda non torverà risposta, ma volevo un consiglio, secondo voi è meglio creare 2 o 3 strutture dati?
Io pensavo 3 ma non so come gestire la relazione d'ordinamento stretto tra le specie.
Grazie |
| lino |
| A che tipo di struttura dati avete pensato per organizzare gli inserimenti di piante? |
| mitnik |
| io sto pensando ad un albero, ma resta comunque difficile come disporre le piante secondo la relazione d'ordine che intercorre tra una e l'altra! bho! non mi sembra banale. Voi che dite?? |
| mitnik |
| magari si puo trovare qualche cosa sullìordinamento di ordine parziale |
| superfabius |
Io le piante le sparo in una lista ....con l'abero devo fare un sacco di operazioni per ordinarle o inserirle...
la cosa che mi preoccupa è il recinto!!!!!!!!!!!!!!!
Grafo!!!!!!!!! |
| mazob |
| io metterei il recinto in una lista magari chiusa |
| superfabius |
Originally posted by mazob
io metterei il recinto in una lista magari chiusa
dopo provo :D
ma la storia delle matrici secondo voi serve?
il mcd sui lati mi serve ok
il determinante potrebbe servirmi va bene
pero' non ho capito quel k> < = 0 come lo devo sfruttare |
| mitnik |
Originally posted by superfabius
Io le piante le sparo in una lista ....
ok! ma il problema rimane l'ordinamento. Ad un certo punto tu devi sapere se per esempio un garofano è < di una rosa. Come fai per questo? |
| superfabius |
Originally posted by mitnik
ok! ma il problema rimane l'ordinamento. Ad un certo punto tu devi sapere se per esempio un garofano è < di una rosa. Come fai per questo?
quando viene stabilita la relazione d'ordine ordino la lista....o se viene stabilita prima come nell'esempio sparo dentro le piante facendo un controllo per ordinarle |
| Polo |
| MA voi come risolvete il problema della conta sui punti all-interno del poligono soprattutto quelli hai bordi la storia delle matrici la usate ??? |
| mazob |
| Scusa, ma come fai ad ordinare tutte le piante sulla relazione d'ordine se sono coppie di valori separati? |
| mitnik |
Originally posted by mazob
Scusa, ma come fai ad ordinare tutte le piante sulla relazione d'ordine se sono coppie di valori separati?
anche secondo me questo è un probelma. Si potrebbero memorizzare in un albero in cui il figlio sx è in relazione mentre quello dx non lo è. Potrebbe andare bene anche se ci potrebbero essere (una volta inseriti tanti elementi) più nodi con lo stesso nome. Mha.. |
| mitnik |
| è uscita una versione corretta del progetto! sinceramente i cambiamenti a me non dicono molto però ci sono! |
| Jacoposki |
| ha cambiato "retta" con "semiretta", mi pare.... mmm già prima non capivo cosa mi stesse dicendo con 'sta storia delle rotazioni, adesso poi che è anche andato a ritoccarlo capisco ancora meno CHE COSA sta cercando di dirmi.... gh. |
| Col. Kurtz |
Originally posted by mazob
Scusa, ma come fai ad ordinare tutte le piante sulla relazione d'ordine se sono coppie di valori separati?
L'ordine viene spiegato nel testo del progetto, in una noticina a pie' pagina (pagina 5).
a = (x1, y1)
b = (x2, y2)
a < b sse (x1 < x2) O (x1 = x2 E y1 < y2).
Non è difficile.
A meno che tu non ti riferisca alle relazioni prese in input, esempio "origano < rosmarino"? |
| Jacoposki |
la noticina di pagina 5 si riferisce ai punti del piano, non alle piante. Anch'io ho problemi a capire come far funzionare la funzione "Minore"... l'altra notte sentivo una vocina che mi diceva "B-Alberi, B-Alberi, B-Alberi...", oggi ho l'impressione che i B-Alberi non c'entrino un'ostia ma potrei sbagliarmi :(
Stanotte pensavo a qualche giochino con le liste... chessò, una lista di tutte le piante indicate come "minori" di un'altra pianta, con puntatori alla pianta rispettivamente indicata come "maggiore", ma non mi pare una struttura sufficientemente organizzata da poter determinare in modo decente se sia possibile o meno aggiungere una nuova relazione d'ordine all'elenco.
Mah. Sigh. |
| mazob |
Originally posted by Col. Kurtz
L'ordine viene spiegato nel testo del progetto, in una noticina a pie' pagina (pagina 5).
a = (x1, y1)
b = (x2, y2)
a < b sse (x1 < x2) O (x1 = x2 E y1 < y2).
Non è difficile.
A meno che tu non ti riferisca alle relazioni prese in input, esempio "origano < rosmarino"?
Io mi riferivo alle relazioni tra specie, anche io pensavo di ordinare le piante per punto.
E per fortuna che è più semplice degli altri ... sono due gg che penso alle strutture dati e non ho ancora la < idea... se continua cosi dovrò abbandonare.. |
| lino |
Creare una lista con tutti e soli i nomi nuovi delle piante man mano che vengono insertiti e associare ad ogni nome la lista delle piante in relazione con essa.
es.
begonia<geranio
rosmarino<menta
gardenia<primula
geranio<oleandro
begonia-->geranio-->oleandro
rosmarino-->menta
gardenia-->primula
se viene inserita la relazione oleandro<menta?
Qual' è la struttura che si può usare? |
| Col. Kurtz |
| Secondo me c'è qualche cosa alla quale non avete ancora pensato... magari uno degli ultimi argomenti. ;) |
| eskimo |
La struttura dati che più si adatta secondo me è il grafo... sono partito con l'idea di usare un albero: il figlio di un nodo (che rappresenta una pianta) se c'è è perchè c'è una regola inserita che dice che quel nodo è < del padre. Un nodo può avere quanti figli vuole... in modo che siano uguali (cioè la funzione confronta restituisce <> per i fratelli). L'operazione più costosa è quando viene inserita una pianta che si trova esattamente i mezzo fra un padre e un figlio.. in tal caso è un po un casino ma si può fare.
Quello che sballa tutto è quando si inserisce una regola che fa in modo che la stessa pianta abbia due padri... in quel caso si forma il grafo....( a dir la verità è ancora un albero ma è sulla buona strada per fare dei cicli o cmq richiede il link al padre per seguire tutte le regole)
a questo punto sono un po' in difficoltà... altro che progetto più facile!
cmq col.kurtz perchè ci devi far stare sulle spine... su su rivelaci quest'intuizione... :?:)
:)
Paolo |
| lino |
| Qualcuno mi spiega per favore come ha fatto a calcolare la capienza del recinto? |
| superfabius |
| venite in chat del dsy :D |
| superfabius |
l'unica cosa possibile mi sembra quella di duplicare i dati
no?
tenrere tutte le relazioni legate tra di loro è un casino |
| Col. Kurtz |
Originally posted by eskimo
La struttura dati che più si adatta secondo me è il grafo... sono partito con l'idea di usare un albero: il figlio di un nodo (che rappresenta una pianta) se c'è è perchè c'è una regola inserita che dice che quel nodo è < del padre. Un nodo può avere quanti figli vuole... in modo che siano uguali (cioè la funzione confronta restituisce <> per i fratelli). L'operazione più costosa è quando viene inserita una pianta che si trova esattamente i mezzo fra un padre e un figlio.. in tal caso è un po un casino ma si può fare.
Quello che sballa tutto è quando si inserisce una regola che fa in modo che la stessa pianta abbia due padri... in quel caso si forma il grafo....( a dir la verità è ancora un albero ma è sulla buona strada per fare dei cicli o cmq richiede il link al padre per seguire tutte le regole)
a questo punto sono un po' in difficoltà... altro che progetto più facile!
cmq col.kurtz perchè ci devi far stare sulle spine... su su rivelaci quest'intuizione... :?:)
:)
Paolo
L'intuizione è quella del grafo, ma ti fai troppe seghe mentali :).
Con un grafo "orientato" (lo chiama così il libro in italiano?), è semplice. Cicli non dovrebbe farne, visto che se il nodo A è "minore" del nodo B e il nodo B è "minore" del nodo C, non può essere che il nodo C sia minore del nodo A. |
| superfabius |
Originally posted by Col. Kurtz
L'intuizione è quella del grafo, ma ti fai troppe seghe mentali :).
Con un grafo "orientato" (lo chiama così il libro in italiano?), è semplice. Cicli non dovrebbe farne, visto che se il nodo A è "minore" del nodo B e il nodo B è "minore" del nodo C, non può essere che il nodo C sia minore del nodo A.
si esatto il grafo orientato è l'unica altrimenti con altre struttuure dati si devono duplicare le chiavi e con il grafo orientato non ci sono ambiguità per quanto riguarda le gerarchie di relazioni
edit: e per quanto riguarda la correttezza delle relazioni si fa un controllo sulla formazione di cicli...ovvero quando si forma un ciclo vuol drie che la relazione è sbagliata
:P
re-edit: l'algoritmo che si potrebbe utilizzare è quello di topological sort...c'e' sul libro di algo
alla prossima puntata per il recinto :D |
| Polo |
| Ma peri il calcolo dell area voi come fate??? |
| mitnik |
| Il calcolo dell'area è un problema! anche perchè all'area poi si dovranno aggiungere i punti presenti sui lati del poligono. |
| eskimo |
Per quanto abbia trovato la struttura dati non riesco ancora ad essere tranquillo: come la implementereste? sul libro da due implementazioni, di cui una con le liste ma che cmq usa un array per memorizzare i nodi (come interi)... solo che non è scalabile! usare una lista di liste? mi sembra molto laborioso... ma forse è l'unica! :(
P. |
| Col. Kurtz |
Originally posted by eskimo
Per quanto abbia trovato la struttura dati non riesco ancora ad essere tranquillo: come la implementereste? sul libro da due implementazioni, di cui una con le liste ma che cmq usa un array per memorizzare i nodi (come interi)... solo che non è scalabile! usare una lista di liste? mi sembra molto laborioso... ma forse è l'unica! :(
P.
Beh, un'array lo puoi sempre ri-allocare ;).
Ma la lista di liste dovrebbe andarti bene ugualmente. |
| superfabius |
per trovare i punti interni al recinto a che avete pensato?
scandire i punti da quello piu' a sinistra e creare ogni volta il rettangol omassimo calcolando l'area e poi aumentare o diminure le coordinate di 1 fin oa quando non si arriva a finire al punto + a dx
?! |
| eskimo |
| scusa superfabius, potresti rispiegare il tuo metodo?? perchè forse l'hai scritto un po di fretta :pensa: |
| superfabius |
Originally posted by eskimo
scusa superfabius, potresti rispiegare il tuo metodo?? perchè forse l'hai scritto un po di fretta :pensa:
si ho scritto una cagata
:D
bho è un casino sto recinto |
| eskimo |
| si infatti neanche io riesco a capire come usare quella ceppa di determinante....sigh....l'unico che mi funzica è il metodo del MCD, che trova i punti toccati da un segmento... ma per l'area (che userei per capire quanti punti ha un recinto all'interno) niente da fare.. è ambiguo, non mi da i punti che ci sono veramente :wall: |
| superfabius |
| la cosa che non capisco io è la storia della retta che si sovrappone.... |
| Col. Kurtz |
Uffa, anche io mi incasino lì.
Ho praticamente finito ma mi manca la funzione capienza(). :( |
| superfabius |
Non vedo nulla rigurado a un inserimento sbagliato delle piante.
Ad esmpio se nel punto 2, 2 è già stata inserita la pianta X e in input mi arriva
i 2 2 y
devo dare in output qualcosa del tipo "non è possibile inserire la pianta" oppure non faccio nulla?
non mi pare che nell'input dato da lui ci sia una situazione simile |
| Col. Kurtz |
Originally posted by superfabius
Non vedo nulla rigurado a un inserimento sbagliato delle piante.
Ad esmpio se nel punto 2, 2 è già stata inserita la pianta X e in input mi arriva
i 2 2 y
devo dare in output qualcosa del tipo "non è possibile inserire la pianta" oppure non faccio nulla?
non mi pare che nell'input dato da lui ci sia una situazione simile
Non devi fare nulla.
Nel progetto non lo richiede.
Quanto al parallelogramma... ho finito! Ma non ho capito la storia delle rotazioni, e infatti ho trovato un'altra soluzione. |
| mitnik |
| ci dai un mano a trovare l'area del poligono?? io ho trovato delle soluzioni teoriche ma anche facendole a mano su carta non mi viene il risultato esatto. |
| Col. Kurtz |
Ogni poligono di n lati è scomponibile in n - 2 triangoli.
L'area di un triangolo a questo punto dovreste saperla calcolare tutti. |
| mitnik |
| scusa ma un poligono di n lati non è scomponibile in n triangoli in cui ogni lato è la base di un triangolo? |
| mitnik |
| ahh! forse intendi n-2 triangoli se considero le diagonali che partono da un solo vertice. |
| Col. Kurtz |
Originally posted by mitnik
ahh! forse intendi n-2 triangoli se considero le diagonali che partono da un solo vertice.
Esatto. Visto che il testo del progetto ci assicura anche che il recinto non sarà mai un poligono convesso. |
| superfabius |
Domanda idiota:
Le piante non devono necessariamente essere dentro il recinto vero?! E quando stampo le piante le stampo tutte non solo quelle dentro il recinto giusto?E la selezione pero' riguarda solo quelle dentro... |
| eskimo |
| si... proprio accussì! |
| Col. Kurtz |
Originally posted by superfabius
Domanda idiota:
Le piante non devono necessariamente essere dentro il recinto vero?! E quando stampo le piante le stampo tutte non solo quelle dentro il recinto giusto?E la selezione pero' riguarda solo quelle dentro...
No, le piante non devono necessariamente essere dentro il recinto.
Ma sul testo del progetto dice di stampare solo quelle nel recinto. |
| eskimo |
| grande curtz... hai corretto il mio mess... ho detto di si per fretta...ooops! |
| Col. Kurtz |
| Ma è normale ritrovarsi a progetto finito con circa 600 righe di codice? :asd: |
| wlf3d_it |
qualcuno saprebbe darmi qualche suggerimento su come implementare un grafo ORIENTATO.....?
grazie |
| desaf78 |
x eskimo(scrive gatsu04): compa ma quella frase da dove ti è uscita????
xke "a ricinu sulu i paleimmitani"
accusi=cosi |
| desaf78 |
Io l'ho fatto tutto il progetto...era facilissimo
(per chi volesse puo' mandarmi il suo codice magari x darvi una mano......)... |
| Paolopaoli |
| Ma avete trovato l'algoritmo che "dice" se un punto è fuori o dentro il recinto? |
| Col. Kurtz |
Originally posted by desaf78
Io l'ho fatto tutto il progetto...era facilissimo
(per chi volesse puo' mandarmi il suo codice magari x darvi una mano......)...
Geniale. ;)
Originally posted by Paolopaoli
Ma avete trovato l'algoritmo che "dice" se un punto è fuori o dentro il recinto?
[/B]
Si. Niente di più facile. |
| Polo |
| Come avete fatto a capire se un punto è nel recinto io semplicemnete controllando che sia in almeno uno dei n -2 triangoli che compone il poligono ma nn so se è infallibile.... |
| Paolopaoli |
Sì. Niente di più facile.
Nel senso che è facile da costruire o da trovare nel libro? |
| lino |
| Qualcuno sa dirmi come implementare la funzione capienza? |
| Col. Kurtz |
Originally posted by Paolopaoli
[B]
Nel senso che è facile da costruire o da trovare nel libro?
Nel libro, che io sappia, non c'è.
A occhio e croce mi vengono in mente almeno due modi per risolvere il problema.
Tre se ce ne aggiungiamo uno trigonometrico, ma non penso sia consigliabile usare le funzioni definite in math.h. ;)
Toh, facciamo quattro con la storia del parallelogramma e le aree. |
| York |
Originally posted by Col. Kurtz
Nel libro, che io sappia, non c'è.
A occhio e croce mi vengono in mente almeno due modi per risolvere il problema.
Tre se ce ne aggiungiamo uno trigonometrico, ma non penso sia consigliabile usare le funzioni definite in math.h. ;)
Toh, facciamo quattro con la storia del parallelogramma e le aree.
Illuminaci un pò più dettagliatamente :D |
| pusio |
| non riesco a trovare l'algoritmo per vedere se un punto è fuori o dentro il recinto |
| superfabius |
per vedere se un punto è dentro o fuori si deve sfruttare il determinante della matrice.....
il punto che mi viene dato è il punto a,a nel suo esempio mentre un lato scelto ad hoc è il punto 0,0 (a+b ,a+b).
Ora devo calcolare il punto b,b e se il determinante è negativo vuol dire che è orario ovvero è dentro
solo che bisogna scegliere il lato giusto della figura e quello mi sfugge :D |
| mazob |
Domanda:
come si calcola il gdc fra i punti p1 e p2 punti, per sapere il numero di punti presenti sul segmento?
grazie |
| Piccolomomo |
Originally posted by mazob
Domanda:
come si calcola il gdc fra i punti p1 e p2 punti, per sapere il numero di punti presenti sul segmento?
grazie
Guarda per esempio qui
ma devi correggerlo un pochino per calcolare il numero di punti. |
| karlost |
Sono riuscito a fare tutta la parte che riguarda il poligono(recinto) ma sono in serissimi problemi sul come si faccia ad implementare il grafo per la relazione minore, qualcuno gentilmente avrebbe qualche suggerimento oppure potrebbe indirizzarmi su qualche sito web che possa illuminarmi a fare questo grafo.
Grazie 10000000...! |
| Jericho |
| Liste di adiacenza... come hai risolto la capienza? :? Io ho usato un metodo alla brutta maniera almeno per pararmi il c... ma è veramente brutto! |
| mazob |
Capienza :
a me la prima capienza di esempio viene corretta 133, ma le altre 2, non vengono una mi da 170 e l'altra 343 anzichè 173 e 341, qualcuno ha avuto lo stesso problema?
Saluti |
| Jacoposki |
| c'è qualche modo per stabilire l'aciclicità (o meno) di un grafo a partire dalla rappresentazione con liste di adiacenza o con matrice? O si deve per forza implementarsi una qualche ricerca in profondità? |
| Jacoposki |
| boh... più o meno ho finito... che voi sappiate si incazza se gli porto le copie cartacee martedì? non per altro, è che ho ottenuto la prima versione più o meno funzionante un'ora fa... |
| mazob |
| C'è qualche anima pia che ha consegnato il progetto con esito posito che vuole postarlo nell'area filez??? |
| Jacoposki |
| domanda idiota: come faccio a fare il file per fargli leggere i comandi? visto che sono scemo e non c'avevo voglia, finora glieli davo tutti a mano ogni volta che testavo (tanto crashava decisamente presto :D ), ma adesso che arriva quasi in fondo ogni volta è un dramma... ho provato a fare un .bat con i comandi, ma cerca di eseguirli come comandi dos... aiuto grazie :) |
| Col. Kurtz |
Originally posted by mazob
C'è qualche anima pia che ha consegnato il progetto con esito posito che vuole postarlo nell'area filez???
Scaramanzia... lo faccio dopo l'orale. |
| Col. Kurtz |
Originally posted by Jacoposki
domanda idiota: come faccio a fare il file per fargli leggere i comandi? visto che sono scemo e non c'avevo voglia, finora glieli davo tutti a mano ogni volta che testavo (tanto crashava decisamente presto :D ), ma adesso che arriva quasi in fondo ogni volta è un dramma... ho provato a fare un .bat con i comandi, ma cerca di eseguirli come comandi dos... aiuto grazie :)
Metti tutti i comandi su un file:
code:
c
< cicuta prezzemolo
< prezzemolo cannabis
r 0 0 0 4 4 4 4 0
i 2 2 cannabis
...
f
nella stessa directory del programma compilato. Facciamo finta che tu abbia chiamato il file in.txt
Poi da shell di dos se sei sotto windows (penso di si, vista la domanda):
-vai nella directory del progetto compilato e scrivi
code:
recinti < in.txt
dove al posto di recinti c'è il nome dell'eseguibile.
Semplice. |
| Jacoposki |
ah non deve essere un bat... ecco dove sbagliavo ^^
grazie :) |
| Jacoposki |
| mmm non va... non fa un tubo e dopo un po' da' errore di memoria virtuale in esaurimento. Il bello è che mettendo i comandi a mano gira senza problemi (sbagliando, ma vabbè) e non va in loop da nessuna parte... sigh. |
| mazob |
Ciao
x caso c'è qualche anima "pia" che ha superato l'esame e vuole postare il suo progetto?
in modo capire perchè il mio non funzionasse.
Grazie
Saluti |
| superfabius |
| Nella lista di iscrizioni agli esami sul sifa non mi compare ancora l'appello di algoritmi del 1° giugno. Qualcuno si è già iscritto o non sono ancora venute fuori le iscrizioni? |
|
|
|
|
