problema da naz oii '11
Inviato: 21 giu 2011, 15:10
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?
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?