Newsgroup: it.comp.lang.perl
Titolo: Somma di numeri

Salve a tutti,
ho questo problema: da una parte un numero e dall'altra una lista di n
numeri (genericamente minori del primo); devo trovare quali possibili
combinazioni degli n numeri hanno come somma il numero "totale".
Qualcuno mi sa suggerire una soluzione un po' piu` leggera di provare
tutte le combinazioni di n, n-1, n-2, ... numeri?
Grazie,
-- 
 te0 - mailto:
t...@slut.panservice.it
- Fletto i muscoli e sono nel vuoto -

Grazie,
se sono tutti minori del primo e diversi tra loro non c'è un' altra
soluzione. e poi che c'entra col perl?

,
Fe wrote:
 >>Salve a tutti,
 >>ho questo problema: da una parte un numero e dall'altra una lista di n
 >>numeri (genericamente minori del primo); devo trovare quali possibili
 >>combinazioni degli n numeri hanno come somma il numero "totale".
 >>Qualcuno mi sa suggerire una soluzione un po' piu` leggera di provare
 >>tutte le combinazioni di n, n-1, n-2, ... numeri?
 >>
 >>Grazie,
 >
 >se sono tutti minori del primo e diversi tra loro non c'è un' altra
 >soluzione. e poi che c'entra col perl?
Beh, non esistendo it.comp.algoritmi e dovendo io fare il programma in
perl, ho pensato che se qualcuno avesse saputo suggerirmi un algoritmo,
il perl sarebbe stato il linguaggio migliore in cui esprimersi.
Grazie comunque


 Grazie,
Non c'č soluzione al tuo problema che non provando tutte le possibili
combinazioni (o quasi...)
Il problema č NPC, una classe di algoritmi risolvibili solo in tempo
esponenziale.
Sul nostro sito 
http://www.softwareplanet.net
 c'č anche il Forum di
algoritmi.
ciao!


wrote:
 Ammesso che i numeri della seconda tabella siano in ordine
(ascendente o discendente non importa) e che siano in quantità tale da
giustificare il codice aggiunto potresti comunque ridurre la quantità
dei numeri da controllare cercando prima di identificare una fascia
relativa (vecchio algoritmo di ordinamento in basic).
Cerco di spiegarlo meglio con un esempio.
Supponiamo che tu abbia una tabella di 4.000 numeri ordinati ma non
progressivi che vanno da 1 a 10.000, che il tuo numero fisso sia A e
che il totale cercato sia TOT.
1. Verifica la somma per il 2.000mo elemento della tabella (elemento
centrale) :   A + numero = totale.  Si puo' avere:
1a.   totale = TOT: hai trovato quello che cerchi;
1b.   totale > TOT: hai trovato il puntatore MAX; 
1c.  totale <  TOT: hai trovato il puntatore MIN.
A questo punto hai gia' dimezzato la tabella (dal primo elemento a MAX
nel caso 1a, da MIN all'ultimo elemento della tabella nel caso 1b).
Ripetendo ricorsivamente il procedimento puoi in questo modo ridurre
sempre piu' il numero di elementi su cui effettuare la ricerca.
Infine, se la quantita' di elementi non è tale da giustificare questo
procedimento, puoi sempre effettuare una suddivisione empirica della
tabella (ad esempio, ad 1/6):
1.  verifica la somma per gli elementi della tabella in posizione 2/6,
3/6, 4/6 e 5/6 ed identifica i puntatori MIN e MAX
2. Effettua la verifica finale di TOT solo sugli elementi della
tabella compresi tra MIN e MAX.
Ciao.
 
--------------------------


 Grazie comunque
Se non ricordo male su it.scienza.informatica giravano anche questioni di
tale genere. Oppure puoi provare a chiedere su it.scienza.matematica.
it.fan.dewdney esiste ancora? (sempre che si scriva cosi' :))
ciao
Stefano