| Precedente :: Successivo |
| Autore |
Messaggio |
ulisse
Dio maturo
Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)
|
 Inviato: 25 Apr 2006 21:11 Oggetto: * QUIZ: Fibonacci e il trattamento dei reflui |
 |
|
Fibonacci e il trattamento dei reflui
Ci sono n città che si affacciano su un fiume. Queste, attraverso la rete fognaria, scaricano nel fiume i rispettivi reflui non trattati inquinandone le acque.
Per ridurre l'inquinamento viene deciso di comune accordo tra le città di costruire delle centrali di trattamento dei reflui.
Risulta economicamente vantaggioso costruire una o più centrali di trattamento lungo la fogna principale (tra la città e il fiume) e poi convogliare le acque di scarico da una città senza centrale di trattamento verso una città contigua dotata di centrale di trattamento. Non è invece vantaggioso suddividere le acque di scarico di una città tra due città adiacenti perché ciò comporta la costruzione di due distinte centrali per la stessa città.
Calcolare il numero f(n) di soluzioni economicamente vantaggiose. In figura i casi n = 1 ed n = 2.
L'ultima modifica di ulisse il 01 Mag 2006 16:10, modificato 1 volta |
|
| Top |
|
 |
camicius
Mortale pio
Registrato: 29/12/05 19:46
Messaggi: 28
|
| Inviato: 27 Apr 2006 13:53 Oggetto: |
|
|
Risulta possibile una tattica di questo tipo?
| Codice: | città1-------------------->città2----------------->città3
|
v
depuratore
|
v
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
|
|
| Top |
|
|
ulisse
Dio maturo
Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)
|
| Inviato: 28 Apr 2006 19:37 Oggetto: |
|
|
| camicius ha scritto: | | Risulta possibile una tattica di questo tipo? |
Yessssssssss!
.... e benvenuto a camicius!!!
Edit: ho tolto il grafico di camicius perché mi sono accorto che riportandolo si sballa l'allineamento
L'ultima modifica di ulisse il 01 Mag 2006 11:14, modificato 1 volta |
|
| Top |
|
|
Benny
Moderatore Hardware e Networking
Registrato: 28/01/06 14:35
Messaggi: 6382
Residenza: Non troppo vicino, mai troppo lontano
|
| Inviato: 29 Apr 2006 13:47 Oggetto: |
|
|
Dipende molto dal numero di abitanti equivalenti di ogni città, dalle precipitazioni medie della zona, dalla morfologia e qualità del terreno, dal coefficiente di afflusso in fognatura...
E poi la centrale ha linee separate per acque grigie e nere? O tutto confluisce in un unico collettore?
Queste cose devo saperle, sennò come faccio a progettare un impianto di depurazione adeguato? Mi troverei a sovrastimare o sottostimare le effettive necessità...
Fibonacci non era gran cosa come idraulico!
Ok, la devo smettere di rompere solo perché non ho capito come risolvere il problema... |
|
| Top |
|
|
lordbluto
Mortale adepto
Registrato: 21/01/06 12:50
Messaggi: 37
|
| Inviato: 29 Apr 2006 22:35 Oggetto: fibonacci? |
|
|
se capisco bene la risposta... | ulisse ha scritto: | | Yessssssssss! |
| Citazione: | secondo me la rappresentazione più semplice è quella di un numero binario di n bit
ogni città con centrale di trattamento è un uno, ogni città che manda altrove è uno zero ( anche ecologicamente...  ) che mandi ad una città o a due per il calcolo è indifferente, è sempre possibile combinare in modo da non dover suddividere lo scarico di una città.
le soluzioni economicamente vantaggiose sono quindi 2^n - 1
cioè il valore rappresentato dal numero binario composto da n cifre meno 1, che rappresenta la situazione senza centrali di trattamento.
Fibonacci era un depistaggio?  |
|
|
| Top |
|
|
lordbluto
Mortale adepto
Registrato: 21/01/06 12:50
Messaggi: 37
|
| Inviato: 30 Apr 2006 11:40 Oggetto: Chiarimento |
|
|
forse però serve un piccolo chirimento sul testo del gioco:
| ulisse ha scritto: | Per ridurre l'inquinamento viene deciso di comune accordo tra le città di costruire delle centrali di trattamento dei reflui.
Risulta economicamente vantaggioso costruire una o più centrali di trattamento lungo la fogna principale (tra la città e il fiume) e poi convogliare le acque di scarico da una città senza centrale di trattamento verso una città contigua dotata di centrale di trattamento. Non è invece vantaggioso suddividere le acque di scarico di una città tra due città adiacenti perché ciò comporta la costruzione di due distinte centrali per la stessa città. |
forse doveva essere:
Per ridurre l'inquinamento viene deciso di comune accordo tra le città di costruire delle centrali di trattamento dei reflui.
Risulta economicamente vantaggioso costruire uno o più collettori di raccolta lungo la fogna principale (tra la città e il fiume) e poi convogliare le acque di scarico da una città senza centrale di trattamento verso una città contigua dotata di centrale di trattamento. Non è invece vantaggioso suddividere le acque di scarico di una città tra due città adiacenti perché ciò comporta la costruzione di due distinti collettori per la stessa città.
a meno che non si intenda che se si convogliano i propri liquami verso un'altra città questa debba essere dotata di due centrali di trattamento.
attendo lumi...  |
|
| Top |
|
|
ulisse
Dio maturo
Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)
|
| Inviato: 01 Mag 2006 13:16 Oggetto: |
|
|
Chiedo scusa ma è da ieri che cerco di rispondere invano...
Oggi finalmente c'è un po' di campo (una piccola modifica sono riuscito a inviarla) così mi sono messo sotto a rispondere.
Ho voluto fare il furbo e rispondere on-line col risultato che mentre postavo un'ora di lavoro mi è comparso il terribile messaggio "pagina non disponibile" !!! 
Voi dite: "Beh, torna indietro e ti ricompare la pagina di edit con tutto il suo contenuto"
Balle!
Sto usando IE con chissà quale settaggio strano e, trascorso qualche minuto, quando torno indietro i campi che avevo compilato risultano vuoti!
Chi è causa del suo mal pianga sè stesso
Vabbè... ci riprovo...
A Benny avevo risposto con una citazione recitata con accento bolognese: "Svicolo a tutta mancina!"
A Lordbluto, invece, avevo detto che non sono un gran esperto di liquami Quindi avevo precisato i termini del problema:
ogni città può trattare i reflui (propri e/o altrui) o smistarli verso una città contigua ma non può suddividere ovvero se tratta i reflui li tratta tutti e se non tratta i reflui li smista tutti verso un'unica direzione (o verso la città di destra o verso quella di sinistra ma non verso entrambe).
Inoltre commentavo la sua scelta (di adottare le stringhe binarie per rappresentare il sistema) col seguente aiutino.
| Citazione: | La scelta è ottima ma il modello si basa su una considerazione erronea.
Ogni città può formalmente essere in 4 stati:
1) non smista
2) smista a dx
3) smista a sx
4) smista sia a dx che a sx
Ora le possibilità sono due:
1) si ingloba subito il vincolo di non suddivisione e si usa un trit (bit a tre stati) per rappresentare lo stato di una città e gli ulteriori vincoli si escludono in fase di conteggio
2) si rappresenta lo stato di una città con 2 bit e si escludono in fase di conteggio sia il vincolo di non suddivisione sia gli ulteriori vincoli |
Infine, a tutti avevo dato il seguente aiutone:
| Citazione: |
Io ho adottato la rappresentazione 2) ovvero 2 bit per ogni città. Dunque ogni configurazione è rappresentata da una stringa binaria di lunghezza 2n:
00 = la città non smista
01 = la città smista a dx
10 = la città smista a sx
11 = la città smista sia a dx che a sx
Non è necessario considerare i reflui in entrata perché già codificati con i reflui in uscita da una città contigua
Dalle possibili configurazioni vanno tolte quelle in conflitto coi vincoli:
1) non si possono suddividere i reflui ovvero gli stati 11 sono esclusi
2a) a destra di uno stato 01 ci può essere solo uno stato 01 o uno stato 00
2b) l'ultima città a destra non può essere nello stato 01
2c) a sinistra di uno stato 10 ci può essere solo uno stato 10 o uno stato 00
2d) la prima città a sinistra non può essere nello stato 10
Dunque le configurazioni lecite sono rappresentate da tutte e sole le stringhe binarie di lunghezza 2n che:
i) iniziano con 0 per il vincolo 2d)
ii) finiscono con 0 per il vincolo 2b)
iii) non contengono due 1 consecutivi per i vincoli 1) 2a) e 2c)
Quante sono queste stringhe?
|
Poiché nella risposta è coinvolta la successione di Fibonacci suggerisco di chiamare F(n) l'n-esimo numero di Fibonacci.
Infine, il fatto che la successione di Fibonacci sia definita ricorsivamente dovrebbe suggerire l'approccio induttivo nella risoluzione del problema. |
|
| Top |
|
|
lordbluto
Mortale adepto
Registrato: 21/01/06 12:50
Messaggi: 37
|
| Inviato: 01 Mag 2006 18:34 Oggetto: |
|
|
ehm, si, l'avevo semplificato un po'...
per il numero di Fibonacci posso suggerire un più esplicito fib(n), con indice che parte da 0, più comodo in molti casi?
per capirsi, fib(2) = 2, fib(4) = 5...
| Citazione: | allora vediamo...
Per quanto apprezzata ho abbandonato la rappresentazione binaria che in qualche modo mi ha portato fuori strada 
rianalizzando il problema diciamo che se per un numero n-1 di città esistono x soluzioni per n ci saranno 2x soluzioni legate ai due "stati" della nuova città che si aggiunge a destra della stringa, se cioè la nuova città scarica autonomamente o se spedisce le sue schifezze a quella subito alla sua sinistra.
Per ognuno dei due stati sono valide tutte le soluzioni precedenti.
a queste si aggiungono però alcune soluzioni che contemplano gli stati illeciti della soluzione di n-1, quelli cioè in cui la città più a destra smista a sua volta a destra.
Quanti sono questi casi?
siccome le ultime due città a destra, la nuova e la sua contigua hanno una configurazione univoca, il numero di soluzioni è legato a quello delle soluzioni y per n-2.
Anche qui sono valide quelle legali y più quelle illecite, siamo quindi ad una serie di Fibonacci, butterei li un
f(n) = fib(2n-1)
ma per dirvi perchè ci devo lavorare ancora un po'... 
|
|
|
| Top |
|
|
ulisse
Dio maturo
Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)
|
| Inviato: 19 Mag 2006 00:22 Oggetto: |
 |
|
| lordbluto ha scritto: | butterei li un
f(n) = fib(2n-1)
ma per dirvi perchè ci devo lavorare ancora un po'...
|
Se passi alla rappresentazione binaria (usando due bit per ogni città - vedi aiutone) la spiegazione della tua formula (che è giusta) arriva gratis! |
|
| Top |
|
|
|
FAQ
Cerca
Lista utenti
Gruppi
Registrati
Profilo
Messaggi privati
Log in
