problema da naz oii '11

Programmazione, algoritmica, teoria dell'informazione, ...
Rispondi
ileo83
Messaggi: 69
Iscritto il: 03 giu 2011, 23:44
Località: pisa

problema da naz oii '11

Messaggio da ileo83 »

E' il problema 1: "per un pugno di baht".

chiede in pratica, date tante monete, diciamo N, di trovare il minimo resto che non e' possible dare.
io pensavo di costruire tutte le combinazioni degli N elementi a k a k, per tutti i k: 1<=k<=N.
dopodiche' farci le somme con tutte queste combinazioni, e dall'insieme dei numeri che ci esce, vedere
qual'e' il minimo intero non presente.

Inoltre, per fare le combinazioni, pensavo di costruire iterativamente le disposizioni, partendo da le disposizioni
degli N ad 1 ad 1. poi da queste, aggiungendo un elemento, formare quelle a 2 a 2, etc etc.
In questo modo, negli insiemi formati, ciascuna combinazione sara' ripetuta diverse volte, ma per il momento me ne frego.
a questo punto, con le disposizioni ci faccio le somme che dicevo prima.
quindi ciascuna somma sara' ripetuta diverse volte, ma siccome non so come altro fare, le tengo tutte.

domanda: siccome non le ho mai fatte le oii, voi dite che una tale soluzione e' una buona soluzione?
anche nel senso di tempo di esecuzione. altrimenti, pensate che e' il caso di formare direttamente le combinazioni ed evitare cosi di ripetere ciascuna somma piu' volte?
oppure conviene procedere in altro modo?

insomma: qualcuno piu' esperto sa dire come e' meglio fare il problema?
Il vecchio conio OO
lerks
Messaggi: 10
Iscritto il: 19 nov 2009, 18:22

Re: problema da naz oii '11

Messaggio da lerks »

Costruire tutte le combinazioni possibili e' un approccio estremamente lento: dovresti considerare $ 2^N $ sottoinsiemi e, in quanto N (se ricordo bene) puo' essere anche dell'ordine dei milioni, puoi vedere da solo che il tempo necessario per terminare la computazione e' troppo.

Ti spiego brevemente la soluzione ufficiale:

Supponi di avere le monete in ordine crescente di valore. Chiamiamo $ v_i $ il valore della i-esima moneta e chiamiamo $ t_i $ la somma dei valori delle prime i monete.
Supponi che con le prime i monete si riescano ad ottenere tutti i resti da 1 fino a $ t_i $, e quindi il minimo resto non ottenibile sia $ t_i+1 $.
Si nota che se $ v_{i+1} > t_i+1 $ allora non c'e' nessun modo di ottenere il valore $ t_i+1 $: prendendo tutti gli elementi fino a i si ottiene un valore minore e prendendo uno degli elementi successivi ad i si ottiene un valore maggiore. Al contrario se $ v_i \le t_i+1 $ si dimostra facilmente che con le prime i+1 monete posso ottenere tutti i valori da 1 a $ t_{i+1} $.

Nella pratica devi:
  • ordinare gli elementi in input
  • partire considerando il valore 1 come minimo resto non ottenibile
  • considerare, nell'ordine, tutti gli elementi e vedere se il loro valore e' minore o uguale al minimo resto non ottenibile
  • se non lo e' allora il minimo resto non ottenibile e' il valore che hai appena usato nel confronto: lo stampi e termini l'esecuzione del programma
  • altrimenti sommi il valore dell'elemento che stai considerando al valore del minimo resto non ottenibile e passi all'elemento successivo
ileo83
Messaggi: 69
Iscritto il: 03 giu 2011, 23:44
Località: pisa

Re: problema da naz oii '11

Messaggio da ileo83 »

ho capito, grazie.
il fatto e' che le soluzioni non sono disponibili
da nessuna parte. sul sito ufficiale non ci sono,
spero di aver fatto un buon post :)
Il vecchio conio OO
Rispondi