View Full Version : [C] progetto vasca pesci
matteo.pata
06-07-2010, 21:44
Ragazzi avrei bisogno di una mano per il progetto di algoritmi vi posto un po' di specifiche.Mi servirebbe una mano per l'utilizzo di una struttura dati adeguata.
La vasca è rettangolare e, al momento della partenza del De Pescis, contiene solo uova. Ogni uovo si
trova in una posizione x; y sul fondo della vasca (la x rappresenta la distanza dal bordo Est della vasca
e la y quella dal bordo Nord). Ogni notte se ne schiudono un certo numero. Il pesciolino pesa di solito
assai poco all'inizio della propria vita; ci sono comunque alcune variazioni casuali in questo peso iniziale.
Appena nato, il pesciolino elegge a propria tana il punto dove è nato. Da questo punto si guarda intorno,
e per lui ogni cosa che si muova (non le uova, dunque, ma solo altri pesci) è una potenziale preda.
Di giorno avvengono un certo numero di attacchi fra barracuda. Gli attacchi sono rapidissimi: pratica-
mente istantanei. Il pesce attaccante, scelta una vittima, gli si precipita addosso, divorandola o venendone
divorato. Se sopravvive, torna subito alla propria tana. L'esito dello scontro è determinato dalla più anti-
ca regola del mare: il pesce più grande (cioè il più pesante) mangia quello più piccolo. Attaccare fornisce
tuttavia un vantaggio: quando attacca, un pesce combatte come se avesse un peso maggiorato del 50%.
Nel raro caso di parità, vince comunque l'attaccante.
Dopo ogni pasto fratricida, un pesce incrementa il proprio peso di un decimo di quello della vittima che
ha appena divorato.
Gli attacchi avvengono prevalentemente fra pesci vicini di casa. I barracuda sono infatti creature molto
prevedibili: infallibilmente, sono sempre i due pesci più vicini ad attaccarsi per primi. Fra questi, è
sempre l'individuo più giovane, cioè il più irruento, ad attaccare l'altro (per più giovane si intende quello
nato dopo, fosse pure di pochi minuti). Fra diversi pesci potenzialmente attaccanti con prede altrettanto
distanti, si muoverà per primo il più giovane. Se lo stesso pesce deve scegliere fra prede altrettanto vicine,
si muoverà prima verso quella più giovane.
Le vacanze del professore
Il professore si assenta per un gran numero di giornate. Come sappiamo, ogni notte di assenza si possono
schiudere alcune uova, e ogni giorno avvengono alcuni attacchi. L'ordine e il numero delle nascite, i dati
relativi, il numero degli attacchi che avvengono durante ogni giorno, eccetera sono tutti descritti in un
le che il programma prende in input, no alla notte in cui si schiude l'ultimo uovo. Anche dopo questa
notte, cioè anche quando tutte le uova inizialmente presenti si sono schiuse, l'assenza del professore si
prolunga e i pesci continuano a divorarsi reciprocamente, giorno dopo giorno, no a che non ne rimane
uno solo.
Si vuole sapere la posizione e il peso dell'ultimo pesce rimasto cos come lo ritrova il distratto De Pescis
al ritorno dalle sue troppo prolungate vacanze.
Inoltre si vuole tener traccia del susseguirsi delle fortune dei vari barracuda. In particolare, si vuole
sapere in ogni momento quale sia il pesce dominante, cioè quello di peso massimo. Per fare questo, ogni
volta che emerge un nuovo pesce dominante, si vuole sapere la sua posizione (cioè quella della sua tana)
e il suo peso, al momento del \sorpasso".
Nota: ci sono tre casi in cui ciò può accadere.
A) quando un pesce, dopo un pasto, supera nel peso (i pareggi non contano) il pesce precedentemente
più grande;
B) quando nasce un pesce particolarmente vigoroso, già in partenza più grosso del precedente pesce di
peso massimo; notare che questo succede anche quando nasce il primo pesce.
C) quando il pesce attualmente più grosso viene pappato, e un altro gli subentra.
INPUT
L'input è un le di testo che descrive una serie di notti alternate a giorni, iniziata e terminata da una
notte. Nella prima riga compare il numero di notti presenti nel le.
Una notte è segnalata da una riga contenente la lettera N seguita dal numero di uova che si schiuderanno
quella notte. Ogni lieto evento è descritto, in ordine di tempo, da una riga successiva dove vengono
speci cati tre numeri: le posizioni x e y dell'uovo che si schiude, in metri (precise al millimetro), e il peso
iniziale del pesciolino w in decine di grammi (con una precisione del centesimo di grammo).
Un giorno è segnalato da una riga contenente la lettera G seguita dal numero di attacchi che si manifestano,
al massimo, quel giorno. Il numero e ettivo potrebbe essere inferiore perchè, quando rimane un solo pesce,
non sono possibili ulteriori attacchi prima della notte successiva.
OUTPUT
L'output deve consistere in una o più righe. Ogni riga corrisponde all'emergere di un nuovo pesce di
dimensione massima, oppure al ritorno del prof. De Pescis (che avviene troppo tardi, quando ormai è
rimasto un solo pesce, probabilmente a amatissimo). La riga deve cominciare dalla lettera che identi ca
il tipo di evento: A, B o C, col signi cato descritto sopra, oppure D, che corrisponde al ritorno del
professore.
Dopo la lettera che identi ca l'evento, deve comparire nella stessa riga: il numero di pesci presenti
attualmente nell'acquario, e la posizione (sia x che y) e il peso attuale del pesce dominante.
Suggerimenti
Dati due punti A e B nel piano aventi coordinate, rispettivamente, (xA; yA) e (xB; yB), la distanza
che li separa si trova banalmente col teorema di Pitagora:
rad((xA + xB)2 + (yA + yB)).
Ragazzi io avevo pensato a uno HEAP però volevo sentire un po' anche i vostri pareri....grazie mille
Ripeto non chiedo la risoluzione del progetto ma una mano nel trovare la struttura dati da utilizzare.
lupoxxx87
06-07-2010, 22:28
un heap non è totalmente ordinato, quindi non va bene
un heap non è totalmente ordinato, quindi non va beneinfatti, anche perché se vuoi controllare quale sia il massimo in O(1) ti basta salvarlo in una variabile a parte (oltre a tenerlo nella tua struttura dati) da aggiornare quando il pesce viene mangiato o viene "superato"
uno heap non è molto adatto a search e delete, operazioni fondamentali nel tuo caso.. molto meglio un avl
matteo.pata
07-07-2010, 12:47
infatti, anche perché se vuoi controllare quale sia il massimo in O(1) ti basta salvarlo in una variabile a parte (oltre a tenerlo nella tua struttura dati) da aggiornare quando il pesce viene mangiato o viene "superato"
uno heap non è molto adatto a search e delete, operazioni fondamentali nel tuo caso.. molto meglio un avl
un albero binario bilanciato in altezza ma ordinato su cosa però....distanza tra un uovo e l'altro oppure altro??
un albero binario bilanciato in altezza ma ordinato su cosa però....distanza tra un uovo e l'altro oppure altro??no be', pensavo alla dimensione a dire il vero, ma i pesci non si muovono se non per attaccare? in tal caso decisamente meglio lo heap
nel senso, se va aggiornato poco, e ogni aggiornamento avviene a seguito di un estrazione di minimo, va bene lo heap
matteo.pata
08-07-2010, 19:08
dai ragazzi una mano......:help:
wingman87
08-07-2010, 19:31
Io partirei facendo un po' di ordine nelle specifiche:
Un pesce ha le seguenti caratteristiche:
posizione x,y
peso
data_nascita
Quando avviene un attacco, questo avviene sempre tra i 2 pesci (se ce ne sono) più vicini ed è sempre il più giovane ad attaccare la preda più vicina più giovane. Il pesce vincente è determinato dal peso dei contendenti, ma l'attaccante ha un bonus del 50% ed inoltre vince in caso di parità. Il pesce vincente aumenta il proprio peso del 10% del peso del perdente. Il pesce vincente rimane nella propria posizione (l'attacco è istantaneo), l'altro scompare.
Il file di input:
per ogni notte ci dice dove nascono i pesci, in quale ordine, e ci dice il peso con uno scarto di +-5cg (se ho capito bene);
per ogni giorno invece ci dice quanti attacchi al più avvengono (se resta un solo pesce non possono più esserci attacchi ma se ci sono pesci a sufficienza gli attacchi avvengono tutti).
Ora devo andare a mangiare.
EDIT: eccomi, edito sopra alcune cose che mi sono accorto di aver dimenticato.
Il file di output:
Ogni qualvolta che nell'acquario si presenta un nuovo "peso massimo" (pesce più pesante), questo va annotato sul file, scrivendo:
- da cosa deriva questo "sorpasso"
A - Un pesce, mangiandone un altro ha superato il "peso massimo"
B - E' nato un nuovo pesce più grande del "peso massimo"
C - Il "peso massimo" è stato mangiato
- il numero di pesci presenti nell'acquario
- la posizione e il peso del "peso massimo"
wingman87
08-07-2010, 20:34
Hai delle restrizioni sulla complessità dell'algoritmo?
Provo a esporti quello che stavo pensando:
Potresti tenere uno heap per ogni pesce. Per ogni pesce avrai quindi disponibile il più giovane e vicino a quel pesce.
Quando deve avvenire un attacco scorri tutti i pesci per determinare la coppia designata, poi simuli l'attacco ed elimini da ogni heap il pesce perdente ed aggiorni il peso del pesce vincente (non è necessario farlo in ogni heap se metti i collegamenti giusti).
Quando nasce un nuovo pesce scorri tutti i pesci aggiungendo agli heap associati il nuovo pesce ed aggiungendo allo heap del nuovo pesce ogni pesce.
In questo modo se non erro la complessità in spazio sarà n^2 ma quella in tempo sarà nlog(n)
lupoxxx87
08-07-2010, 23:31
mah... io non sono così convinto sullo heap.
ricordati che ogni cancellazione e ogni inserimento necessitano di un riordinamento dello heap, il che sarebbe notevolmente costoso avendo un heap per ogni pesce.
e il fatto che tu hai continui inserimenti e cancellazioni mi fa pensare a qualcosa simile a un albero binario (o rb, o b+) in cui tenere ordinate le distanze (come struttura da-a) e una hash table in cui tenere i pesci.
bisognerebbe valutare se, a seconda delle istanze, è necessario fare inserimenti alla radice negli alberi.
comunque opererei facendo
n inserimenti nell'albero e nella hash table in corrispondenza dei giorni
ogni notte:
cancellare il nodo più a sx
attaccare il pesce "a" con il pesce "da"
a seconda dell'esito, variare i dati di una riga hash e cancellare l'altra.
eviterei l'hash per le distanze perchè andrebbe riordinato in seguito ad ogni cancellazione, un bst non necessita di questo
wingman87
09-07-2010, 00:20
mah... io non sono così convinto sullo heap.
ricordati che ogni cancellazione e ogni inserimento necessitano di un riordinamento dello heap, il che sarebbe notevolmente costoso avendo un heap per ogni pesce.
L'inserimento in uno heap richiede un tempo O(log(n)), dovendolo fare per ogni pesce otterresti un tempo O(nlog(n)). Il problema sarebbe la cancellazione ma si potrebbe postporre finché un pesce mangiato non arriva alla cima dello heap (quindi dovrà esserci un controllo da espletare con una semplice ricerca binaria ad esempio).
e il fatto che tu hai continui inserimenti e cancellazioni mi fa pensare a qualcosa simile a un albero binario (o rb, o b+) in cui tenere ordinate le distanze (come struttura da-a) e una hash table in cui tenere i pesci.
bisognerebbe valutare se, a seconda delle istanze, è necessario fare inserimenti alla radice negli alberi.
comunque opererei facendo
n inserimenti nell'albero e nella hash table in corrispondenza dei giorni
ogni notte:
cancellare il nodo più a sx
attaccare il pesce "a" con il pesce "da"
a seconda dell'esito, variare i dati di una riga hash e cancellare l'altra.
eviterei l'hash per le distanze perchè andrebbe riordinato in seguito ad ogni cancellazione, un bst non necessita di questo
Anch'io avevo pensato altre soluzioni, sono rimasto però bloccato quando ho pensato al fatto che quando un pesce muore, se era il più vicino ad altri pesci andrebbe aggiornato il pesce più vicino a questi e non ho trovato un modo efficiente di farlo.
Es:
Abbiamo i pesci 1,2,3 e 4
Mettiamo che 2,3,4 hanno come pesce più vicino 1. 2 è il più vicino e lo attacca e vince. Ora dovrò ricalcolare il pesce più vicino per tutti i pesci.
In verità basterebbe calcolare la coppia di pesci più vicini, però anche così non mi è venuto in mente un modo efficiente per farlo (solo con complessità quadratica).
A meno che non tieni in memoria tutte le distanze tra ogni pesce... che è quello che facevo con gli heap.
Mi rendo conto comunque che la mia soluzione non è quel granché (credo).
in fin dei conti la soluzione più stupida potrebbe essere la migliore: un array
ti permette di trovare la coppia di pesci con distanza minima in O(nlogn), la cancellazione è O(1) e l'inserimento ti può costare una realloc, ma diciamo che comunque mediamente ti costa O(1) se fai crescere con un fattore di crescita decente l'array
ovviamente il pesce di peso massimo lo tieni in una variabile a parte e via
ps: l'algoritmo O(nlogn) per i punti con distanza minima è il numero 3 discusso in queste dispense: http://twiki.di.uniroma1.it/pub/Algoritmi2/WebHome/DISP_divide.pdf
non so se ce ne siano di migliori, io conosco questo :X
lupoxxx87
09-07-2010, 12:21
Anch'io avevo pensato altre soluzioni, sono rimasto però bloccato quando ho pensato al fatto che quando un pesce muore, se era il più vicino ad altri pesci andrebbe aggiornato il pesce più vicino a questi e non ho trovato un modo efficiente di farlo.
...forse una matrice di adiacenza dinamica...
però il fatto che coordinate x,y siano continue rende il piano infinito, e non discretizzabile, non è facilmente utilizzabile.
forse, a questo punto, l'heap è il più veloce
...forse una matrice di adiacenza dinamica...
però il fatto che coordinate x,y siano continue rende il piano infinito, e non discretizzabile, non è facilmente utilizzabile.
forse, a questo punto, l'heap è il più veloceusare un heap per distanza minima vuol dire avere tutte le coppie nello heap, quindi se hai n pesci, nello heap ci sono n(n-1)/2 = O(n²) nodi e come dicevi prima eliminare 1 nodo vuol dire eliminarne n-1
matteo.pata
09-07-2010, 18:11
in fin dei conti la soluzione più stupida potrebbe essere la migliore: un array
ti permette di trovare la coppia di pesci con distanza minima in O(nlogn), la cancellazione è O(1) e l'inserimento ti può costare una realloc, ma diciamo che comunque mediamente ti costa O(1) se fai crescere con un fattore di crescita decente l'array
ovviamente il pesce di peso massimo lo tieni in una variabile a parte e via
ps: l'algoritmo O(nlogn) per i punti con distanza minima è il numero 3 discusso in queste dispense: http://twiki.di.uniroma1.it/pub/Algoritmi2/WebHome/DISP_divide.pdf
non so se ce ne siano di migliori, io conosco questo :X
Stavo dando un occhio interessante la cosa quindi dici di utilizzare quel tipo di algoritmo usando un array per trovare la distanza minima e di tenere a parte una variabile per il pesce + grande che ogni volta sostituisco.nella struttura del pesce quindi dovre tenere
posizione x
posizione y
peso pesce
creazione ??? in quanto devo vedere per il fatto di chi attacca per primo...
L'inserimento poi dici di farlo all'inizio dell'array oppure alla fine.
L'array lo tengo ordinato oppure no.
vi ringrazio intanto molto e se riusciete a darmi qualche altra dritta ve ne sarei molto grato....;)
Stavo dando un occhio interessante la cosa quindi dici di utilizzare quel tipo di algoritmo usando un array per trovare la distanza minima e di tenere a parte una variabile per il pesce + grande che ogni volta sostituisco.nella struttura del pesce quindi dovre tenere
posizione x
posizione y
peso pesce
creazione ??? in quanto devo vedere per il fatto di chi attacca per primo...
L'inserimento poi dici di farlo all'inizio dell'array oppure alla fine.
L'array lo tengo ordinato oppure no.
vi ringrazio intanto molto e se riusciete a darmi qualche altra dritta ve ne sarei molto grato....;)se vedi come funziona quell'algoritmo tenerlo ordinato è un po' dura perché va ordinato prima per x e poi per y, in compenso ordinare prima di eseguirlo per x ti costa O(nlogn) quindi la complessità rimane O(nlogn)
per la creazione dico: allochi inizialmente un array di una certa dimensione, e inserisci sempre in fondo e incrementi una variabile che ti indica il numero di elementi effettivamente in uso dell'array, appena lo riempi fai una realloc facendolo crescere di un 50% ad esempio.. così non devi fare realloc ogni volta, ma hai un po' di margine, chiaramente per eliminare scambi l'ultimo elemento dell'array con quello che devi cancellare e decrementi la variabile che indica il numero di elementi dell'array utilizzati
usare un heap per distanza minima vuol dire avere tutte le coppie nello heap, quindi se hai n pesci, nello heap ci sono n(n-1)/2 = O(n²) nodi e come dicevi prima eliminare 1 nodo vuol dire eliminarne n-1
questo si può risolvere usando un flag per ogni pesce, che dice se è vivo o se è già stato mangiato. quando si estrae dallo heap si verifica che entrambi i pesci coinvolti siano ancora vivi.
il che vuol dire avere come spazio occupato qualcosa che non è neanche limitato da O(n^k) per qualsiasi k intero :P
quello dell'array mi sembra un buon compromesso tra spazio e complessità onestamente
matteo.pata
11-07-2010, 22:45
ok ragazzi grazie della mano da domani mi metto sotto con l'implementazione di quell'algoritmo se qualcuno mi vuole dare una mano è sempre ben accetta visto che lavoro e il mio tempo a disposizione è veramente poco........Grazie intanto a tuttie dell'aiuto che mi state dando....;) ;)
matteo.pata
12-07-2010, 19:04
up ragazzi qualche manima nella stesura della funzione....:help:
wingman87
12-07-2010, 19:09
up ragazzi qualche manima nella stesura della funzione....:help:
Che metodo hai scelto di usare? Quali problemi hai incontrato?
matteo.pata
12-07-2010, 19:23
ho scelto il metodo di tuccio con l'array per calcolare la distanza minima però avendo il pseudocodice non saprei da dove iniziare....cavolo le mie doti nel programmare sono un po' scorsa....e poi invece non saprei come fare gli attacchi e tenere il pesce maggiore.Con l'array avevo pensato tipo ogni volta che si aggiungeva un pesce di calcore la distanza minima tra tutti i pesci e quindi in base alla distanza minima di effettuare l'attacco e poi aggiornare la variabile globale con il pece più grande.Una volta effettuato l'attacco però mi sono chiesto come faccio ad eliminare dall'array il pesce che ormai non esiste più?? quindi dovrei usare una'ltra struttura dati per memorizzare i pesci e fare gli attacchi o sbaglio??
lo PSEUDO CODICE è questo:
(http://img689.imageshack.us/i/catturafu.png/)
Uploaded with ImageShack.us (http://imageshack.us)
Quello che segue è lo pseudocodice dell’ implementazione appena descritta. DISTANZA-MIN1 prende in input il vettore P
i cui punti sono stati preliminarmente ordinati rispetto alla coordinata x
L’algoritmo fa uso di una sottoprocedura FONDI. Scopo della chiamata a FONDI(PS, PD) `e quello di riordinare i punti del
sottovettore P rispetto alla coordinata y in tempo O(n) sfruttando il fatto che i punti dei sottovettori PS e PD sono gia
ordinati.
Una manina please......
wingman87
12-07-2010, 19:27
Solo una cosa: hai tenuto conto anche dell'età nel calcolo della coppia di pesci di distanza minima?
Per l'eliminazione mi sembrava ottima l'idea di tuccio`:
per la creazione dico: allochi inizialmente un array di una certa dimensione, e inserisci sempre in fondo e incrementi una variabile che ti indica il numero di elementi effettivamente in uso dell'array, appena lo riempi fai una realloc facendolo crescere di un 50% ad esempio.. così non devi fare realloc ogni volta, ma hai un po' di margine, chiaramente per eliminare scambi l'ultimo elemento dell'array con quello che devi cancellare e decrementi la variabile che indica il numero di elementi dell'array utilizzati
matteo.pata
12-07-2010, 19:46
ok perfetto si ci avevo pensato all'età...pensavo banalmente a un intero nella struttura pesce che ad ogni pesce inserito viene incrementato e settato correttamente nella struttura pesce appena creata.
4
N 3
47.400000 32.800000 0.023470
46.700000 70.900000 0.014500
44.000000 93.600000 0.019870
G 2
N 3
81.100000 25.800000 0.016510
99.300000 49.100000 0.041560
43.100000 82.300000 0.040930
G 2
N 5
15.300000 89.900000 0.039700
40.400000 37.000000 0.030760
87.600000 69.900000 0.042940
75.700000 70.500000 0.035260
89.300000 86.800000 0.037810
G 4
N 5
88.500000 1.800000 0.045190
29.100000 78.800000 0.057250
66.000000 65.600000 0.046090
22.500000 70.400000 0.040780
61.700000 52.200000 0.062860
Questo è un file di esempio di input.
Dove N sta ad indicare la nascita del pesce e G indica il numero di attacchi.
Quindi pensavo che inserivo i primi 3 pesci nell'array faccio due attacchi e mi rimane un solo pesce poi aggiungo gli altri pesci e mi devo calcolare di nuovo tutta le distanze minime ogni volta che effettuo un attacco giusto.
Cioè calcolo distanza minima
eseguo attacco tra i due pesci più vicini all'interno del array.
Controllo il vincente e vedo se ha superato il maggiore e al massimo scambio.
Sposto il pesce da cancellare in ultima posizione e sposto il puntatore di fine array indietro di una posizione.
Rifaccio stesso procedimento per il secondo attacco della seconda giornata...giusto??
wingman87
12-07-2010, 20:00
Direi di sì. Sull'età dei pesci della coppia mi riferivo al fatto che nel testo dell'esercizio diceva che se ci sono più coppie di pesci con la stessa distanza (minima) bisogna sempre scegliere la coppia con il pesce più giovane, se il suddetto pesce è coinvolto in più coppie bisogna considerare la coppia in cui c'è la vittima più giovane.
il che vuol dire avere come spazio occupato qualcosa che non è neanche limitato da O(n^k) per qualsiasi k intero :P
quello dell'array mi sembra un buon compromesso tra spazio e complessità onestamente
dato che n è il numero di pesci inseriti, la dimensione dell'heap rimane O(n^2). se proprio vuoi risparmiare lo spazio dei pesci morti, puoi eliminare nodi non solo quando estrai dalla testa, ma anche mentre li fai scorrere dopo l'estrazione o quando li incontri mentre inserisci nuove distanze, in certi casi risulta addirittura vantaggioso e negli altri puoi sempre lasciarli lì, a seconda di quanto spazio vuoi/puoi sacrificare per le prestazioni.
Potresti adattare l'algoritmo e le funzioni di sugarscape e fare una cosa fatta bene con una simulazione visuale su matrice :)
matteo.pata
13-07-2010, 19:32
RAgazzi so che vi sto rompendo i m*****i e lo capisco.
Lo pseudocodice che ho messo sopra però non capisco come implementarlo quando dice
SOL1 <---DISTANZA-MIN (ps)
SOL2 <---DISTANZA-MIN (pd)
intende due chiamate ricorsive oppure no...:confused:
poi sotto dove dice
Q <--- i punti p con coordinata x nell'intervallo .......
devo praticamente cercare tutte le coppie che stanno in questo range dif-x,dif+x di valori :confused:
SOL3 <--- la coppia a distanza minima tra i punti Q che distano tra loro al più 7 posizioni.
Qui cosa intende....come lo implemento :confused:
Ragazzi veramente una mano per implementare questa funzione. :help:
wingman87
13-07-2010, 20:29
RAgazzi so che vi sto rompendo i m*****i e lo capisco.
Lo pseudocodice che ho messo sopra però non capisco come implementarlo quando dice
SOL1 <---DISTANZA-MIN (ps)
SOL2 <---DISTANZA-MIN (pd)
intende due chiamate ricorsive oppure no...:confused:
Direi di sì.
poi sotto dove dice
Q <--- i punti p con coordinata x nell'intervallo .......
devo praticamente cercare tutte le coppie che stanno in questo range dif-x,dif+x di valori :confused:
Non le coppie ma i punti la cui coordinata x è compresa in quel range
SOL3 <--- la coppia a distanza minima tra i punti Q che distano tra loro al più 7 posizioni.
Qui cosa intende....come lo implemento :confused:
Questo però non l'ho capito, o meglio quello che ho capito non capisco come possa essere implementato efficientemente
wingman87
13-07-2010, 20:39
Ho guardato sul pdf.
Grazie alla proprietà appena dimostrata, per la ricerca di punti in Q a distanza inferiore a δ, basterà ordinare i punti di Q per coordinata y non decrescente e poi, per ciascun punto, calcolare la distanza tra questo e i 7 che lo seguono nell’ordinamento, per un totale di O(|Q|) confronti.
matteo.pata
14-07-2010, 22:18
up
come dice wingman, quella funzione mentre lavora riordina anche per y facendo una specie di mergesort, praticamente quindi dopo aver visto quali sono i punti a distanza minima a sinistra e destra della mediana, devi controllare se ci sono punti con distanza minore "a cavallo" (uno a sinistra e uno a destra)
per controllare in O(n) si sfrutta il fatto che non può essere un punto che dista più di 7 posizioni nell'array ordinato per y (ed è proprio per questo che si ordina man mano, e si usa quella specie di mergesort per fare il tutto in O(nlogn)), quindi fai 7 confronti per ogni pesce
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.