Aiuto per la soluzione di un problema numerico
Prima di tutto, essendomi iscritto da pochi minuti, un saluto generale dallo ZioPaolo a tutto il forum di matematicamente.
Cercavo un algoritmo per risolvere il seguente problema:
Trovare tutte le n-ple, con n fissato, di numeri interi e maggiori di 1 la cui somma è pari ad S.
Tanto per avere una idea, $ 10 < S < 1000 $ mentre $ 2 < n < (S-n) $ con $ S,n in NN $
Ho scritto già due programmini per risolvere in maniera "bruta", ma risultano troppo complessi.
1° tentativo:
Cambiare la rappresentazione da decimale a modulo $ S $ di tutti i numeri interi $ in [0 , S^(n)] $
Scartare ogni numero avente almeno uno $ 0 $ od un $ 1 $ fra le cifre che lo compongono.
Scartare ogni numero avente come somma delle proprie cifre un numero diverso da $ S $.
Scartare eventuali numeri aventi più di $ n $ cifre.
2° tentativo:
Scrivo un numero avente le $ (n-1) $ cifre più significative pari a $ 2 $ e la cifra meno significativa pari ad $ M $ dove $ M = S - 2(n-1) $.
Tale numero rappresenta il mio punto di partenza e lo chiamerò $ N_0 $
Ho poi implementato l'algoritmo per eseguire le addizioni in colonna (sì, quello che ci insegnano alle elementari), facendo in modo che quando si cerca di sommare $ 1 $ alla cifra corrente e tale cifra vale $ M $ si generi riporto sulla cifra successiva e la cifra corrente venga posta uguale a $ 2 $.
Con questo algoritmo incremento tante volte $ N_0 $ di 1, scrivendo tutti i risultati, finchè non ottengo riporto sulla cifra più significativa.
Infine scarto ogni risultato avente come somma delle proprie cifre un numero diverso da $ S $.
Ho notato una notevole riduzione dei tempi di calcolo passando dal 1° al 2° programma, ma credo che si possa fare ancora meglio.
Idee ?
Cercavo un algoritmo per risolvere il seguente problema:
Trovare tutte le n-ple, con n fissato, di numeri interi e maggiori di 1 la cui somma è pari ad S.
Tanto per avere una idea, $ 10 < S < 1000 $ mentre $ 2 < n < (S-n) $ con $ S,n in NN $
Ho scritto già due programmini per risolvere in maniera "bruta", ma risultano troppo complessi.
1° tentativo:
Cambiare la rappresentazione da decimale a modulo $ S $ di tutti i numeri interi $ in [0 , S^(n)] $
Scartare ogni numero avente almeno uno $ 0 $ od un $ 1 $ fra le cifre che lo compongono.
Scartare ogni numero avente come somma delle proprie cifre un numero diverso da $ S $.
Scartare eventuali numeri aventi più di $ n $ cifre.
2° tentativo:
Scrivo un numero avente le $ (n-1) $ cifre più significative pari a $ 2 $ e la cifra meno significativa pari ad $ M $ dove $ M = S - 2(n-1) $.
Tale numero rappresenta il mio punto di partenza e lo chiamerò $ N_0 $
Ho poi implementato l'algoritmo per eseguire le addizioni in colonna (sì, quello che ci insegnano alle elementari), facendo in modo che quando si cerca di sommare $ 1 $ alla cifra corrente e tale cifra vale $ M $ si generi riporto sulla cifra successiva e la cifra corrente venga posta uguale a $ 2 $.
Con questo algoritmo incremento tante volte $ N_0 $ di 1, scrivendo tutti i risultati, finchè non ottengo riporto sulla cifra più significativa.
Infine scarto ogni risultato avente come somma delle proprie cifre un numero diverso da $ S $.
Ho notato una notevole riduzione dei tempi di calcolo passando dal 1° al 2° programma, ma credo che si possa fare ancora meglio.
Idee ?
Risposte
Noto che il tuo algoritmo (2) prova tutte le combinazioni, mentre a priori non è necessario. Es. se S=12, n=3 si trovano 3+4+5 ma anche 5+4+3, che direi sono la stessa ennupla (o ti interessa anche l'ordine?), e oltretutto prova tutte le combinazioni, quindi nel nostro esempio:
parte da 2+2+8
poi trova 2+3+2
... 2+3+3
... 2+3+4
Potresti cercare di migliorarlo senza ripartire tutte le volte da 2 quando "riporti".
Ma anche: se parti dalla configurazione n[0]=M n[1]=2 ... sai che decrementando (togliendo 1) dal primo numero, uno dei restanti deve essere incrementato; prendi il primo dei restanti e lo incrementi (se possibile) e ripeti il procedimento, ottenendo:
M, 2, 2, 2
M-1, 3, 2, 2
M-1, 2, 3, 2
M-1, 2, 2, 3
M-2, 3, 2, 3
M-2, 3, 3, 2
ecc..
In questo modo generi solo le combinazioni che ti interessano.
parte da 2+2+8
poi trova 2+3+2
... 2+3+3
... 2+3+4
Potresti cercare di migliorarlo senza ripartire tutte le volte da 2 quando "riporti".
Ma anche: se parti dalla configurazione n[0]=M n[1]=2 ... sai che decrementando (togliendo 1) dal primo numero, uno dei restanti deve essere incrementato; prendi il primo dei restanti e lo incrementi (se possibile) e ripeti il procedimento, ottenendo:
M, 2, 2, 2
M-1, 3, 2, 2
M-1, 2, 3, 2
M-1, 2, 2, 3
M-2, 3, 2, 3
M-2, 3, 3, 2
ecc..
In questo modo generi solo le combinazioni che ti interessano.
Grazie mille Rggb per l'idea.
In effetti era la prima che mi era venuta in mente, ma non ero riuscito a tradurla in un algoritmo.
Inoltre l'ordine dei numeri per me è importante, quindi le ennuple 3+4+5 e 5+4+3, per esempio, sono entrambe da cercare.
In riferimento al tuo esempio numerico, la cosa che trovo più difficile da spiegare al povero computer è che arrivati, per esempio, al passo in cui il primo numero vale M-3 bisogna:
prima sommare 3 (se possibile) ad uno dei restanti (e fare le permutazioni);
poi bisogna sommare 2 sempre a quel numero lì e 1 ad un altro dei rimanenti (e permutare);
poi sceqlierne un altro a cui sommare l'uno, ecc...
In effetti scrivendo questa risposta, mi sta venendo un'idea....
Provo a scrivere un programma ricorsivo che la implementi e vi faccio sapere.
Grazie mille
In effetti era la prima che mi era venuta in mente, ma non ero riuscito a tradurla in un algoritmo.
Inoltre l'ordine dei numeri per me è importante, quindi le ennuple 3+4+5 e 5+4+3, per esempio, sono entrambe da cercare.
In riferimento al tuo esempio numerico, la cosa che trovo più difficile da spiegare al povero computer è che arrivati, per esempio, al passo in cui il primo numero vale M-3 bisogna:
prima sommare 3 (se possibile) ad uno dei restanti (e fare le permutazioni);
poi bisogna sommare 2 sempre a quel numero lì e 1 ad un altro dei rimanenti (e permutare);
poi sceqlierne un altro a cui sommare l'uno, ecc...
In effetti scrivendo questa risposta, mi sta venendo un'idea....
Provo a scrivere un programma ricorsivo che la implementi e vi faccio sapere.
Grazie mille
Infatti, direi ci vuole una f() che ricorsivamente preso in ingresso un indice, chiami se stessa con l'indice successivo finché non è arrivata alla fine della sequenza (array o cosa altro vuoi).
Inoltre, direi che l'algoritmo che ti ho proposto le trova tutte: parte da M, 2, 2.... e finisce con 2, 2,... M che sono lo stesso gruppo di numeri con permutazioni diverse.
Inoltre, direi che l'algoritmo che ti ho proposto le trova tutte: parte da M, 2, 2.... e finisce con 2, 2,... M che sono lo stesso gruppo di numeri con permutazioni diverse.
Evviva !!!
Ho finalmente ottenuto ciò che volevo. Ecco lo pseudo-codice:
definite le variabili
indice = -1 ed ennupla come array di N elementi
funzione(Somma , n , indice , N):
indice = indice +1
se (indice = N):
ennupla[indice] = Somma
print ennupla
altrimenti:
for ( i = 2 ; i <= (Somma - 2*(n-1)) ; i++):
ennupla[indice] = i
funzione((Somma-i), (n-1) , indice, N)
fine.
Alla chiamata iniziale, i parametri N ed n dovranno essere uguali, ad esempio:
funzione(10,2,-1,2)
trova tutte le coppie (N=2) che danno come somma 10:
[2, 8]
[3, 7]
[4, 6]
[5, 5]
[6, 4]
[7, 3]
[8, 2]
Grazie mille Rggb per la dritta.
Ho finalmente ottenuto ciò che volevo. Ecco lo pseudo-codice:
definite le variabili
indice = -1 ed ennupla come array di N elementi
funzione(Somma , n , indice , N):
indice = indice +1
se (indice = N):
ennupla[indice] = Somma
print ennupla
altrimenti:
for ( i = 2 ; i <= (Somma - 2*(n-1)) ; i++):
ennupla[indice] = i
funzione((Somma-i), (n-1) , indice, N)
fine.
Alla chiamata iniziale, i parametri N ed n dovranno essere uguali, ad esempio:
funzione(10,2,-1,2)
trova tutte le coppie (N=2) che danno come somma 10:
[2, 8]
[3, 7]
[4, 6]
[5, 5]
[6, 4]
[7, 3]
[8, 2]
Grazie mille Rggb per la dritta.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo