 | |
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 |
[Progetto] Asteroidi
Clicca QUI per vedere il messaggio nel forum |
| overflowonline |
| Ma come... è il progetto giacimenti con qualche modifica.... ca**o è uguale... poi con la storia dell'astronave che deve attraversare il percorso sembra tutto più fico,con i giacimenti non riuscivo a vederne un'uso pratico e mi intristivo...ma dai.. cioè cambia qualcosina ma proprio poco poco... è uguale... |
| kirka85 |
uff peccato che nessuno ha postato la sol del prog giacimenti!
:( sto progetto mi sembra inumano! |
| Alececk84 |
| Però qualcuno potrebbe postarla ora...così per avere un'idea... |
| Kurt84 |
Quando spiega cos'è una regione rettangolare, y non dovrebbe essere MINORE di y0 e MAGGIORE di y0-r??
y0-r<y<y0 |
| kenShiro72 |
(X0,y0)---------- C ------------- (X0+ C,Y0)
|
|
r
|
|
(X0,y0-r)---------- C ------------- (X0+ C,Y0-r)
esempio (5,5) c=3 r=3
(5,5)---------- 3 ------------- (8,5)
|
|
3
|
|
(5,2)---------- 3 ------------- (8,2) |
| Kurt84 |
| grazie della risp ken, ma appunto se la nostra y è =3 vedi che è maggiore di y0-r (5-3=2) e minore di y0(5) |
| kenShiro72 |
scusa y come la chiami tu è
compresa tra yo e y0-3
quindi 5< y < 2
quindi 5< 3 < 2
mi sembra giusto
forse non ho capito cosa intendi
:? |
| Kurt84 |
| 5<3<2 vuol dire che 3 è maggiore di 5 e minore di 2... e mi sembra sbagliato :-). Io direi 2<3<5 |
| kenShiro72 |
| si scusa a parte il verso sbagliato. |
| kenShiro72 |
| avrà confuso il verso il prof pero il rettangolo è qullo di su |
| sbin |
Originally posted by kenShiro72
si scusa a parte il verso sbagliato.
anche a me sembra che abbia ragione Kurt84:
ci deve essere un errore: y0 >= y > y0-r e non y0 <= y < y0-r come c'è scritto nel testo.
l'accendiamo? :-) |
| Kurt84 |
| cioe dici che nn è quello in alto a sinistra il punto che t da? |
| kenShiro72 |
ok allora non si fa .....
:D |
| sbin |
Originally posted by Kurt84
cioe dici che nn è quello in alto a sinistra il punto che t da?
sì è quello in altro a sinistra! Quindi il disegno è giusto e la nostra y dovrà essere minore di y0 (e non maggiore come scritto) e maggiore di y0-r (e non minore come c'è scritto).
Ho mandato una mail di conferma al prof.. attendiamo! |
| sbin |
Originally posted by sbin
sì è quello in altro a sinistra! Quindi il disegno è giusto e la nostra y dovrà essere minore di y0 (e non maggiore come scritto) e maggiore di y0-r (e non minore come c'è scritto).
Ho mandato una mail di conferma al prof.. attendiamo!
Ecco cosa mi ha risposto Aguzzoli:
"
Ha ragione, c'e' una svista:
deve leggere
y-r < y <= y0
Grazie per la segnalazione.
"
Quindi avevamo ragione noi.. grazie a Kurt84
che se n'è accorto!
ps: non è che qualche anima pia imposterebbe il progetto Giacimenti in filez? :-) |
| kirka85 |
idee su come realizzare il piano orbitale?
dai postate Giacimenti, giusto per capire ... pleaseeeee :(
ciao |
| antares85 |
Non mi è ben chiaro il valore di Ps(x,y). Ad es, dove in pag 1 c'è:
Ps(-3,5)=Ms[0,0] cosa vuol dire? che il piano nel punto -3,5 ha il valore che c'è nella matrice Ms in 0,0? nn penso, qualcuno mi può schiarire le idee?
idem per il significato di Pr |
| overflowonline |
Ciao a tutti,per quelli che mi hanno chiesto delle info,domani pomeriggio di sicuro scrivo qualcosa,adesso sono troppo stanco e non scriverei cose sensate.. cmq io ho preso tutto il codice da algoteam....
ps: x fabio,ho letto il tuo messaggio solo ora,domani ci sentiamo via msn,scrivo qui perchè sono sicuro che leggerai... :-) |
| kirka85 |
Se consideriamo Xs=-3 e Ys=5 come nell'esempio applicando
Ms[Ys - Y , X - Xs] otteniamo con
Ps (-3,5)= (5-5, -3+3) = 0, 0
Ps (-2,5)= (5-5, -2+3) = 0, 1 |
| sbin |
Originally posted by kirka85
Se consideriamo Xs=-3 e Ys=5 come nell'esempio applicando
Ms[Ys - Y , X - Xs] otteniamo con
Ps (-3,5)= (5-5, -3+3) = 0, 0
Ps (-2,5)= (5-5, -2+3) = 0, 1
Si ma credo che volesse sapere a cosa servono questi valori più che come calcolarli.. che valori sono? Credo sia una cosa poco chiara anche a me.
x overflowonline: le dritte le dai a tutti vero? :) grazie
ps: giacimenti in filez è sempre il ben venuto ;) |
| antares85 |
esatto sbin, come calcolarli lo so, ed è semplice, ma a che mi serve sapere che Ps(-3,5)=Ms[0,0]? cosa vuol dire?
Anche perchè guardando l'esempio in fondo e provando a compilarlo a mano non mi sembra necessario qst passaggio del Ps,ma forse sbaglio... |
| sbin |
Originally posted by antares85
esatto sbin, come calcolarli lo so, ed è semplice, ma a che mi serve sapere che Ps(-3,5)=Ms[0,0]? cosa vuol dire?
Anche perchè guardando l'esempio in fondo e provando a compilarlo a mano non mi sembra necessario qst passaggio del Ps,ma forse sbaglio...
Potrebbe essere così?: nel punto Ps(-3,5) che valore devo assegnare conoscendo quelli della matrice Ms?
Infatti se guardi l'esempio completo:
S1=((2,5),3,2M1,A)
secondo i calcoli avrò:
(xs,ys=(2,5) (vedi valori in S1)
M1 è la matrice che riguarda S1
lo scopo è porre i valori di M1 nel piano Ps! (stessa cosa con M2 e M3), in altre parole.. che valori hanno i punti in Ps? per saperlo devo guardare M1! (ed m2, m3)
Esempio che valore andrà collocato in ps(2,5)? Il valore nella matrice M1 che si trova in posizione [5-5=0,2-2=0] che nel nostro caso è 1!
Che valore andrà collocato in ps(3,4)? Il valore nella matrce M1 che si trova in posizione [5-4=1,3-2=1] che nel nostro caso è 6
La stessa cosa la faccio per tutti i punti di Ps. Dove NON avrò 0<=ys-y<r e0<=x-xs<c dovrò assegnare un valore 0!
Mi sembra di essere stata un po' contorta :( spero tu abbia capito qualche cosa! |
| antares85 |
capito perfettamente sbin grazie, ora ho capito che più che altro serve solo a mettere 0 dove non vengono rispettate le condizioni per ys-y e x-xs,perchè se no bastava copiare pari pari la matrice M a partire dal punto xs,ys
ora l'ultimo problema di comprensione che mi rimane è come implementare il tutto non su un'unica matrice ma, come scritto nel testo, su più matrici,una mezza idea ce l'avrei,però mi sembra troppo complicata...mercoledì cmq vado a ricevimento dal prof e vedremo,intanto se qualcuno ha delle idee...così nl posso anche proporre al prof qnd vado
intanto inizio a scrivere un pò di codice... |
| sbin |
Originally posted by antares85
capito perfettamente sbin grazie, ora ho capito che più che altro serve solo a mettere 0 dove non vengono rispettate le condizioni per ys-y e x-xs,perchè se no bastava copiare pari pari la matrice M a partire dal punto xs,ys
ora l'ultimo problema di comprensione che mi rimane è come implementare il tutto non su un'unica matrice ma, come scritto nel testo, su più matrici,una mezza idea ce l'avrei,però mi sembra troppo complicata...mercoledì cmq vado a ricevimento dal prof e vedremo,intanto se qualcuno ha delle idee...così nl posso anche proporre al prof qnd vado
intanto inizio a scrivere un pò di codice...
Per ora niente idee.. anche perchè prima dovrei studiarmi un attimo la teoria :(
Cmq postate il più che potete!
Ciao |
| Kurt84 |
| Più che altro il problema sono le matrici sovrapposte (satelliti diversi che sorvegliano gli stessi punti). Avrei anch'io un'idea ma nn credo sia ottimale. |
| overflowonline |
Ciao a tutti,io ho fatto il progetto giacimenti che mi sembra molto simile a questo. Ripeto mi sembra molto simile,ma rileggendo bene il testo ho visto che ci sono delle differenze nella funzione principale che in questo caso è il calcolo del corridoio mentre da me era il calcolo di un'area.
Credo che siano simili non proprio uguali come avevo detto in precedenza. Cmq scrivo qui perchè c'è anche un mio amico che fà il progetto e visto che ci sono provo a dare qualche consiglio.
Premessa:io scrivo solo consigli,idee e parole che ho sentito nei vari orali dal prof per svolgere il mio progetto. Quindi non prendeteli come dogmi assoluti.. inoltre il prof premia l'ingegno e strutture dati particolarmente efficaci anche se non sono le migliori.
Nel mio caso ad esempio non ho usato il miglior algoritmo per svolgere il calcolo della funzione principale e neanche la migliore struttura dati per memorizzare i dati,però ho avuto delle idee "creative" ed "ingegnose" che sono piaciute...
Cmq venendo al dunque:
Per memorizzare i nomi dei satelliti è consigliato usare un'albero rb lessicografico in modo tale da tenere sempre bilanciato l'albero anche nel caso di inserimento di milioni di stringhe,inoltre il recupero dei dati di un satellite non implica un tempo troppo eccessivo.
Ai nodi terminali dell'albero cioè a quel nodo a cui corrisponde una determinata stringa è bene attaccare una matrice che contiene i dati del rilevamento del satellite. in questo modo quando bisogna recuperare i rilevamenti del satellite lo si fà al volo.
Quando invece viene creata la rete di satelliti si può tranquillamente usare una semplice lista che contiene solo i puntatori ai nodi dei satelliti interessati dalla rete,in questo modo non dovete scorrervi di nuovo tutto l'albero nel caso dovete recuperare più volte gli stessi valori.
Poi vabbè per recuperare un valore x,y è ovvio che dovete capire quali sono i satelliti e bisogna adottare qualche trucchetto per non scorrersi tutta la lista,questo a dir la verità non me lo ricordo bene perchè io ho usato una struttura dati diversa quindi boh...ma non è di sicuro fondamentale..
la funziona principale qui è quella del corridoio che è simile a quella del mio progetto,in pratica nel mio progetto bisogna creare una nuova matrice in modo tale che il calcolo totale richiedesse al massimo un tempo di L x L quindi L^2. Poi ogni volta si tiene conto del minimo e del massimo. Cioè provo a spiegarmi,si procede per riga e si tiene conto del massimo incontrato e del minimo e li si confrontava e ovviamente i valori venivano passati una sola volta.. e poi bisognava prendere i valori a coppie,cioè il max o il min con il numero considerato e poi si riusciva a fare la differenza e si capiva quali punti scartare qui invece è leggermente diverso visto che non c'è nessuna differenza.. quindi boh.. non è che mi sono messo a pensare alla soluzione... inoltre quando il prof me l'ha fatto vedere ci sono rimasto secco perchè mi ha fatto capire in un secondo che quella era la soluzione migliore,mentre io avevo adottato una soluzione totalmente diversa e mi ero pure spaccato la testa per giorni per pensare a qualcosa di intelligente per risolvere il problema quindi non è che mi ricordo benissimo la soluzione ottima. Era qualcosa di questo tipo,si costruisce una matrice LxL dove L è il lato che viene dato in input,nel mio caso estensione massima, e poi si prendeva massimo e minimo ogni volta si costruivano delle coppie di valori all'interno della matrice...
Spero di essere stato utile,cmq la prima parte quella sull'albero rb lessicografico con attaccate le matrici credo sia proprio la soluzione migliore... per la funzione principale penso si debba utilizzare lo stesso una matrice però non ho idea di come implementare l'algoritmo.. vabbè che altro dire... buona furtuna.... ne avrete bisogno :-) |
| sbin |
L'unica cosa a cui avevo pensato fino ad ora erano gli alberi RB per i satelliti.
Grazie! |
| Kurt84 |
Grazie dei consigli over!
Su queste cose che hai detto c sono , il mio problema principale per ora è l'implementazione del piano orbitale, hai mica qualche dritta? |
| overflowonline |
Ciao io ho preso tutto il codice per le strutture dati principali da algoteam e poi le ho modificate secondo le mie esigenze,inoltre ho dato un'occhiata ai progetti precedenti per capire come implementare alcune funzioni tipo quelle sulle stringhe.
Cmq adesso metto il project nell'area filez tanto è talmente un macello che a volte facevo fatica a capirlo pure io..ci sono dentro talmente tante idee che con il passare del tempo spesso mi dimenticavo cosa faceva una funzione..
Cmq il prof non è che guarda il pelo nell'uovo,in linea di massima vede se ci sono delle idee di fondo buone e sensate,se il progetto gira e se c'è impegno. E'ovvio che non si aspetta la perfezione se non saremmo tutti dei programmatori nati. Ad esempio nel mio progetto il codice non è per niente pulito e c'è molta confusione alla fine c'ho lavorato fino alle 10 di sera della domenica di consegna quindi non ho avuto modo di sistemarlo.. però l'idea di fondo c'è è quello che conta. Poi ovviamente all'orale ti fà notare le cose che sono sbagliate o che non vanno bene
In ogni caso pubblico il progetto perchè è grazie alla mentalità open-source che sono riuscito a finire il progetto,se non avessi avuto altri progetti da cui prendere spunto sul codice o se non ci fossero state le slides di fiorentini e di altri prof sparsi per l'italia non sò se sarei riuscito a finirlo in tempo. Inoltre mi sento in debito con wikipedia perchè una marea di informazioni le ho trovate lì... vabbè tra 5 minuti c'è progetto con relazione nell'area filez.
ps:non faccio come certa gente che se la mena a farti fare 2 fotocopie dei suoi appunti perchè è la persona più complessata del mondo e pensa che alle sue spalle si architettitono chissà quali cospirazioni diaboliche.Se stai leggendo ti comunico che non ti pensiamo mai,manco di striscio... mi è venuto in mente solo ora questo discorso..Chi mi conosce sà a chi mi riferisco... |
| Kurt84 |
| Grazie 1000 over che dio ti benedica. |
| kirka85 |
| grazie over.... mitico |
| imperator |
ringrazio anch'io
in bocca al lupo a tutti!!!!!! |
| antares85 |
| Mi aggiungo ai ringraziamenti (questo è lo spirito giusto!) |
| liver82 |
| Scusate ma non mi trovo molto con l'errore che è stato segnalato al prof su y0-r<y<=y0, allora non è sbagliato anche x0<=x<x0? x e y a cosa si riferiscono esattamente? Grazie mille!! |
| liver82 |
Originally posted by liver82
Scusate ma non mi trovo molto con l'errore che è stato segnalato al prof su y0-r<y<=y0, allora non è sbagliato anche x0<=x<x0? x e y a cosa si riferiscono esattamente? Grazie mille!!
Volevo solo avvisarvi che ho capito questo passaggio di non stare a rispondermi...:-p
Però volevo porvi un quesito, secondo voi il controllo per vedere se il punto fà parte della matrice non dovrebbe essere così:
Ms[ys-y,x-xs] se 0<=ys-y<=r e 0<=x-xs<=c perchè altrimenti come lo mette giù il prof. c ed r sarebbero esclusi così da non comprendere l'ultima riga e l'ultima colonna, no? |
| KAKA' |
Ciao ragazzi qulacuni mi puo dire come ha fatto il prof calcolare
C1 = C(1; 3) C2 = C(2; 2) nella regione Rettangolare
T1 = Rett((1; 5); 3; 5). mi fatte un grandissimo favore xke mi sono fermato qua.... |
| antares85 |
devi calcolare un xc e un k tale che (rispettando le condizioni poste) venga massimizzato Tr(C). in poche parole data la rete di satelliti provi tutte le combinazioni possibili di xc e k e prendi quella che ti da Tr(C) maggiore.
come codice non c sono ancora arrivato ma l'ho capita così.
Piuttosto qualcuno ha idee x la creazione del piano orbitale?
direi che per ogni satellite si crea la sua matrice, e poi..? |
| t30n3 |
| ringrazio x il codice, speriamo ke questa volta sia quella buona! |
| Andrej |
Scusate ma qualcuno ha capito se nella funzione rete i nomi inseriti devono essere tutti presenti nei satelliti oppure basta che ne esista uno per distruggere la rete esistente?
Grazie |
| Kurt84 |
| Andrej Io penso tutti... |
| Andrej |
Ok Kurt84 grazie 1000!
Vi rompo con l'ultima domanda:
con satellite inserisco solo il satellite e con rete inizio a monitorare?
Grazie ciao |
| Kurt84 |
si Andrej , se nn c'è inserisci il satellite e con la rete ti crei una nuova mappa dei punti..
Ragazzi io stavo pensando di andare a trovare Fiorentini domani.. Siccome vengo da un paese molto lontano (prov d Novara) secondo voi ci sarà una ressa allucinante (visto che è il suo orario di ricevimento)? Mi conviene prendere appuntamento per un altro giorno? Non vorrei aspettare ore o peggio non essere ricevuto. Grazie |
| iuz-lab |
Originally posted by KAKA'
Ciao ragazzi qulacuni mi puo dire come ha fatto il prof calcolare
C1 = C(1; 3) C2 = C(2; 2) nella regione Rettangolare
T1 = Rett((1; 5); 3; 5). mi fatte un grandissimo favore xke mi sono fermato qua....
beh tu prendi i valori di T e sostituisci il primo numero con il primo di C ed il quarto con il secondo di C..
T1((1, 5)), 3, 5); C1(1, 3);
Rect((1, 5), 3, 3)
T1((1, 5)), 3, 5); C1(2, 2);
Rect((2, 5), 3, 2)
nell'allegato c'e' una rappresentazione grafica della prima parte dell'esempio..
spero aiuti qualcuno..
sempre se non ho capito male.. |
| iuz-lab |
| scusate ma qui si possono anche postare piccole parti di codice od e' una cosa proibita? |
| ideafix |
| basta usare il buon senso ;) |
| iuz-lab |
un'po' di codice..
niente di che ho iniziato a dichiarare le prime funzioni per gestire i rettangoli che poi riempiro' con i valori necessari..
le due strutture che utilizzo.. la prima per dichiarare rettangoli nel formato punto sinistro basso e punto destro alto (per calcolare meglio intersezioni etc..).. la seconda e' nel formato voluto dalle specifiche..
typedef struct rect *rectangle;
typedef struct rect_un *rectangle_un;
crea un rettangolo nel primo formato di cui sopra..
rectangle rect_create (int x1, int y1, int x2, int y2);
crea un rettangolo nel secondo formato di cui sopra..
rectangle_un rect_un_create (int x, int y, int r, int c)
converte dal primo formato al secondo..
rectangle rect_un_to_rect (rectangle_un r);
riceve due rettangoli nel primo formato e restituisce 1 nel caso si intersechino, 0 altrimenti..
int rect_intersect (rectangle r1, rectangle r2);
riceve due rettangoli nel primo formato e restituisce l'intersezione (non so' se funziona)..
rectangle rect_intersection (rectangle r1, rectangle r2);
spero di non aver violato regole di posting..
comunque il codice non e' assolutamente testato ne tantomeno garantito funzionante o consigliato per l'utilizzo.. |
| KAKA' |
| Grazie mile uiz-lab |
| Nautilus |
| una fatica solo per capire il senso di 'sto progetto |
| Spedom |
Originally posted by Nautilus
una fatica solo per capire il senso di 'sto progetto
Magra consolazione.......ma non sei il solo ad avere problemi del genere!!!
:? |
| fedrica |
Ciao ragazzi/e!!!qualcuno riesce a darmi qualche suggerimento su come sviluppare la funzione corridoio del progetto asteroidi???
Grazie 1000 in anticipo per la collaborazione!!! |
| ideafix |
Fedrica ho unito il tuo post al 3d già esistente
ciao ;) |
| iuz-lab |
Originally posted by fedrica
Ciao ragazzi/e!!!qualcuno riesce a darmi qualche suggerimento su come sviluppare la funzione corridoio del progetto asteroidi???
Grazie 1000 in anticipo per la collaborazione!!!
non credo possa essere discusso troppo l'algoritmo che risolve il problema..
io ti posso dire che ho elaborato un algoritmo che nel caso peggiore ha complessita' O(n(n+1)/2).. se avete trovato soluzioni migliori.. postate postate postate.. |
| ideafix |
| anche l'algoritmo che avevo pensato io ha la complessita O(n^2) |
| sbin |
Originally posted by overflowonline
Cmq venendo al dunque:
Per memorizzare i nomi dei satelliti è consigliato usare un'albero rb lessicografico in modo tale da tenere sempre bilanciato l'albero anche nel caso di inserimento di milioni di stringhe,inoltre il recupero dei dati di un satellite non implica un tempo troppo eccessivo.
Ai nodi terminali dell'albero cioè a quel nodo a cui corrisponde una determinata stringa è bene attaccare una matrice che contiene i dati del rilevamento del satellite. in questo modo quando bisogna recuperare i rilevamenti del satellite lo si fà al volo.
Ciao.. domanda:
dici che ai nodi terminali bisogna attaccare la matrice dei dati del rilevamento.
Non ho capito una cosa però.. prendendo il tuo progetto:
hai costruito l'albero RB lessicografico e all'ultimo nodo hai messo i dati del satellite compresa una lista di valori (cioè quelli della matrice). Giusto?
Ma nel consiglio che hai dato riconfermi questa cosa o quando dici che è bene attaccargli la matrice non intendi una lista con i valori della matrice ma una matrice vera e propria? (sul libro di laboratorio ho visto che usa un array di puntatori per costruire una matrice).
Mi è venuto questo dubbio proprio ora che ho finito la parte di inserimento e aggiornamento.. usando la lista come avevi fatto tu.. no nvorrei rifare tutto!! :-(
Grazie. |
| ideafix |
Ciao a tutti ,
alla fine che struttura dati avete scelto per rappresentare il piano? |
| iuz-lab |
| per i rilevamenti una matrice semplice.. quando devo trovare il corridoio massimo riesco a ridurre tutto il necessario a una sequenza di int.. |
| antares85 |
| qualcuno mi sa dire dv posso trovare un esempio dove si accettano in input n nomi e non un numero predefinito di nomi? |
| ideafix |
x Antares : qualche spunto lo puoi trovare sul sito di Auzzoli fra gli esercizi fatti a laboratorio (mi sembra 5 lez. di labo), anche se quello fatto per lab era bufferizzato, io per il prog ho fatto 1 funzione + semplice.
X Iuz-lab ma in che momento crei la matrice?
Cioè mi spiego meglio.. la Mappa Pr associata alla rete R , la create nel momento in cui viene lanciata la funzione rete(a1,a2......an) o la create successivamente ? |
| antares85 |
| ci avevo già guardato...denghiù lo stesso ;) |
| iuz-lab |
Originally posted by ideafix
X Iuz-lab ma in che momento crei la matrice?
Cioè mi spiego meglio.. la Mappa Pr associata alla rete R , la create nel momento in cui viene lanciata la funzione rete(a1,a2......an) o la create successivamente ? [/B]
direi sucessivamente.. se e solo se si richiede la ricerca del corridoio..
a quel punto controllo quali satelliti della rete cadono all'interno del rettangolo interessato e procedo con la ricerca del corridoio massimo.. |
| iuz-lab |
nuovo codice di rectangle.c..
l'altro presentava qualche bug.. in questo sembrano non esserci errori evidenti (l'ho testato ma solo superficialmente)..
ho cambiato le strutture in la struttura.. cosi' ho meno funzioni e ne semplifico l'uso..
<EDIT>
rimosso allegato
</EDIT> |
| iuz-lab |
piccola considerazione..
sembra che alla fine il problema si possa vedere come:
data una sequenza di numeri, trovare la sequenza di numeri contigui tale che la loro somma sia la maggiore ottenibile..
ex..
dato 3 5 -2 5 6 4 -6 9
soluzione 5 6 4
sembra un problema NP-C quindi a meno che qualcuno non abbia niente da dire o mi smentisca direi che l'unica cosa saggia da fare per essere sicuri di trovare la soluzione sia provare tutte le combinazioni (che non sarebbe nemmeno difficile).. |
| ideafix |
scusa dato
3 5 -2 5 6 4 -6 9
la soluzione è
3 5 -2 5 6 4 -6 9
o mi sbaglio ?? |
| ideafix |
sul discorso della Np completezza ... devo ancora rifletterci ma secondo me non è NP-c !
un altra domanda Iuz:
ma quindi quando lanci la funzione Rete() in che struttura salvi i satelliti membri della rete?? |
| iuz-lab |
Originally posted by ideafix
scusa dato
3 5 -2 5 6 4 -6 9
la soluzione è
3 5 -2 5 6 4 -6 9
o mi sbaglio ??
si hai ragione (scusate ma non ho ancora dormito e tra un'po' devo incontrare una persona)..
dato 4 -7 5 6 4 -8 3 2 soluzione 5 6 4
(dovrebbe andare ma a questo punto non garantisco)..
sembra NP-C o comunque NP-h se non lo e' ed e' piu' semplice.. tanto di guadagnato.. |
| iuz-lab |
Originally posted by ideafix
un altra domanda Iuz:
ma quindi quando lanci la funzione Rete() in che struttura salvi i satelliti membri della rete?? [/B]
se deve esistere una ed una sola rete direi che posso mettere un flag all'interno di ogni satellite da settare a true nel caso sia utilizzato dalla rete corrente o false altrimenti.. |
| sbin |
Domanda stupida:
ma per costruire la matrice dei satelliti (attaccata all'albero RB) usate un semplice array di array (quindi statica) o un array di puntatori (quindi dinamica)? la seconda versione da quanto ho capito serve se si deve usare un'unica funzione che elabori matrici di dimensioni diverse.
grazie |
| iuz-lab |
Originally posted by sbin
Domanda stupida:
ma per costruire la matrice dei satelliti (attaccata all'albero RB) usate un semplice array di array (quindi statica) o un array di puntatori (quindi dinamica)? la seconda versione da quanto ho capito serve se si deve usare un'unica funzione che elabori matrici di dimensioni diverse.
grazie
io credo che usero' un array bidimensionale allocato dinamicamente (che praticamente e' un array di puntatori ad array di interi)..
qualcosa del genere dovrebbe funzionare..
int **array2d (int r, int c)
{
int p;
int **m = malloc(r * sizeof(int *));
for (p = 0; p < r; p++) {
m[p] = malloc(c * sizeof(int));
}
return m;
}
in questo modo posso fare qualcosa del tipo..
int **sat = array2d(5, 5);
sat[0][0] = 1;
sat[0][1] = 2;
etc..
il discorso dell'unica funzione non l'ho capito.. |
| ideafix |
Ciao ragazzi mi è stato fatto notare che i file postati da Iuz-Lab contengono troppo codice.
devo quindi rimuoverli.
purtroppo la regola è sempre la stessa:
qualche suggerimento implementativo va bene, codice implementato no |
| sbin |
Originally posted by iuz-lab
io credo che usero' un array bidimensionale allocato dinamicamente (che praticamente e' un array di puntatori ad array di interi)..
il discorso dell'unica funzione non l'ho capito..
Quindi utilizzi un array di puntatori. ok
Per il discorso delle funzioni:
libro Kelley Didattica e prorammazione (vecchia edizione), sul capitolo delle matrici fa un esempio:
mettiamo che devo scrivere una funzione per calcolare il determinante di un amatrice. Se uso un array di array dovrò costruirmi una funzione per ogni tipo di matrice, ad esempio una per una matrice 3x3 e una per una matrice 4x4. Questa cosa non è accettabile! perchè voglio costruirmi una funzione Determinante che possa esaminare matrici qualsiasi.. quindi ricorro a matrici dinamiche (array di puntatori).
Questo è quello che intendevo.
Grazie e ciao |
| Kurt84 |
ciao ragazzi avrei bisogno di un parere:
la scanf("%s"stringa) mi memorizza automaticamente una sequenza di caratteri, fermandosi quando trova un carattere di spaziatura.
Dal momento che considera come carattere di spaziatura anche \n (a capo) , come faccio a asapere quando interrompermi???
L'ideale sarebbe che restituisse il carattere letto ma nn lo fa.
Devo crearmi una funzione apposta che scandisce carattere per carattere?
Grazie ciao |
| Kurt84 |
| ok niente penso di aver risolto, ho creato una funzione apposta che fa il lavoro della scanf ma mi restituisce 0 quando trova un \n |
| sbin |
Originally posted by iuz-lab
se deve esistere una ed una sola rete direi che posso mettere un flag all'interno di ogni satellite da settare a true nel caso sia utilizzato dalla rete corrente o false altrimenti..
Scusa, ma dopo quando devi ripescare i dati dei satelliti non impiegneresti tempo O(nlgn) invece di un Theta(n) che richiederebbe la ricerca in una lista?
Se non sbaglio devi cercare n satelliti e il tempo di ricerca per ogni satellite è O(lgn).
Calcola che purtroppo le complessità mi sono un po' ostiche :-( |
| Nautilus |
ma per alberi rb lessicografici
intendete i red-black ? |
| antares85 |
| si si intende red-black, con le chiavi ordinate in ordine alfabetico (come dizionario). |
| Nautilus |
quindi al posto dei numeri interi come chiave utilizzo una stringa
ok chiaro
Grazie mille |
| liver82 |
| Ciao Ragazzi! Scusate ma l'ultimo esempio dei corridoi C5=C(3,1) C6=C(5,1), non è sbagliato? Perchè M del corridoio C5 è uguale a 8 mentre M del corridoio C6 è uguale a 4. Quindi dovrei prendere solo il corridoio C5. Giusto? Grazie mille!! |
| sbin |
Originally posted by liver82
Ciao Ragazzi! Scusate ma l'ultimo esempio dei corridoi C5=C(3,1) C6=C(5,1), non è sbagliato? Perchè M del corridoio C5 è uguale a 8 mentre M del corridoio C6 è uguale a 4. Quindi dovrei prendere solo il corridoio C5. Giusto? Grazie mille!!
sbagliato! Il rettangolo che prendi in cosiderazione ha la seguente struttura:
x=3,y=5......................x=5,y=5
.
.
.
.
.
x=3,y=4......................x=5,y=4
quindi non devi guardare i coefficienti presenti in y=3!!!
quindi hai coefficienti di transitabilità di -2+6=4 in un corridoio e -1+5=4 nell'altro.
tutti e due hanno ampiezza =1, quindi li puoi prendere tutti e due. |
| liver82 |
| Sì, sono un babbo io...non avevo visto che il rettangolo era di 2 righe!! :-) Grazie mille!!! |
| antares85 |
| scusate ma l'output deve comparire comando dopo comando (se il comando prevede la stampa) o prima tutti i comandi in input e poi tutto l'output? GRAZIE |
| sbin |
Originally posted by antares85
scusate ma l'output deve comparire comando dopo comando (se il comando prevede la stampa) o prima tutti i comandi in input e poi tutto l'output? GRAZIE
spero comando dopo comando! altrimenti ho sbagliato :) |
| Andrej |
Anche io penso comando dopo comando.
Altrimenti ho sbagliato anche io!
Qualcuno conosce Aguzzoli; nel senso che il mio progetto da gli output corretti ma a parte che è inefficiente ed ha anche alcune scelte implementative non ottimali.
Basta per passare?
Grazie |
| Nautilus |
ho provato a iscrivermi ma il suo corso non compare.
ha gia' chiuso le iscrizioni? |
| antares85 |
| si quelle per quest'appello da un pezzo |
| antares85 |
Scusate, domanda stupida: nella funzione c se io ho un corridoio con k ad es 6, ma k non rispetta la condizione 0 < k <= c - (xc - x0), devo 'abbassare' k finchè non la rispetta?
O per Grazia Divina la condizione è sempre verificata e non devo fare nessun controllo? |
| sbin |
Originally posted by antares85
Scusate, domanda stupida: nella funzione c se io ho un corridoio con k ad es 6, ma k non rispetta la condizione 0 < k <= c - (xc - x0), devo 'abbassare' k finchè non la rispetta?
O per Grazia Divina la condizione è sempre verificata e non devo fare nessun controllo?
Il testo dice che c e k devo stare dentro il rettangolo T, quindi presumo tu debba abbassare. Anche perchè il corridoio deve stare all'interno di T.. quindi anche il k.
.. rileggendo pero' nonho capito bene.. tu sai se in alcuni casi io tuo algoritmo di porta k fuori dal rettangolo o stai chiedendo se questo è possibile? l'algoritmo che ho implementato io non mi porta mai fiuori dal rettangolo.. però dipende dall'algoritmo che hai adottato tu!!!
ciao |
| Kurt84 |
| chebbello ho finito |
| Paul03 |
| Kurt hai letto il mio PM? Appena lo leggi contattami che ho bisogno di chiederti dei consigli |
| KAKA' |
Ciao ragazzi io ho una domanda magari qulkuno se mi risponde mi fa un favore di damre qualke idea come avete fato per risolvere
aggiorna (sigma. file) mi manca solo questa |
| antares85 |
| X sbin: no l'algoritmo che ho fatto io rispetta la condizione automaticamente,anche se l'ho provato solo con l'esempio c -8 -1 5 13, diciamo che volevo sapere se nel programma avete messo un controllo della condizione oppure no... |
| sbin |
Originally posted by antares85
X sbin: no l'algoritmo che ho fatto io rispetta la condizione automaticamente,anche se l'ho provato solo con l'esempio c -8 -1 5 13, diciamo che volevo sapere se nel programma avete messo un controllo della condizione oppure no...
bhe.. se il tuo algoritmo rispetta in automatico la condizione (come il mio).. in teoria non dovresti controllare niente.. altrimenti vuol dire che non funziona :-)
Prova con tanti esempi!!!
X TUTTI: che complessità hanno i vosti algoritmi per 't' e 'c'? xkè vorrei effettuare un'ottimizzazione ma non avrei voglia di scervellarmi ancora.. anche perchè dovrei studiare da zero per l'orale enon c'è molto tempo! magari se giriamo tutti sulla stessa complessità mi tengo il programma che ho già finito.. O(n) per 't' e r*c*O(n) per 'c' (più o meno). La complessità di 'c' mi sembra un po' elevata :-( che dite?!?
n numero satelliti
r righe di T
c colonne di T
grazie! |
| sbin |
Originally posted by KAKA'
Ciao ragazzi io ho una domanda magari qulkuno se mi risponde mi fa un favore di damre qualke idea come avete fato per risolvere
aggiorna (sigma. file) mi manca solo questa
io ho semplicemente cercato il satellite e gli ho detto di mettere nella sua matrice i dai di filenuovo. I dati li ho sovrascritti tutti, indipendentemente se era un numero uguale al precedente o diverso.. spero la cosa non importi x l'orale. |
| Kurt84 |
| io corridoio l'ho fatta con complessità O(n), è stato un martirio. |
| sbin |
Originally posted by Kurt84
io corridoio l'ho fatta con complessità O(n), è stato un martirio.
Che balle.. io avrei finito.. ma ho 10000 dubbi e cerco di capire se si poteva fare di meglio.. sto perdendo un sacco di tempo e non ne vengo a capo.. forse è meglio che non mi faccia altri problemi e cominci a prepararmi per l'orale!
Che voi sappiate.. quelli che compaiono nel calendario degli orali.. hanno passato automaticamente il progetto indipendentemente dal voto o chi ha consegnato è chiamato in automatico all'orale e potrebbe non passare il progetto?
Poi: se il programma funziona e le strutture dati usate non sono ottime (le mie spero non facciano tanto schifo).. c'è il rischio che ti rimandi a casa o ti danno cmq un 18 per pietà?
grazie a chiunque sappia rispondermi. |
| Kurt84 |
| se funziona e hai rispettato la consegna penso che te lo faccia passare(il progetto), poi il voto cambierà a seconda dell'efficienza del programma(per come la vedo io). |
| antares85 |
| per quello che so io l'importante è che funzioni con l'esempio del prof, poi se funziona anche con altri esempi tanto meglio, poi il voto varia a seconda dell'efficienza e dell'orale che fai. |
| leti |
Qualcuno sa com è l'orale con fiorentini??
E' bravo o fa tante menate??
Grazie mille a tutti:D |
| antares85 |
URGENTE!!! Ragazzi/e ma nell'esempio del prof la seconda c:
c -8 0 5 13 non è (-7 12) invece di (-8 13) ??? |
|
|
|
|
