[ALGORITMO] : calcolo delle somme possibili dato un risultato conosciuto

[oureyes]

date le mie scarse capacità matematiche chiedo qui un aiuto per risolvere un problema forse banale....

ecco il quesito :

conoscendo il risultato finale, e sapendo inoltre quanti numeri sono all'interno del calcolo, come posso arrivare a scoprire quali somme portano a quel risultato?

non riesco bene a capire se la cosa è una stupidata oppure no, mi ci sono spaccato la testa per un po ma mai arrivando alla soluzione.

ringrazio chiunque provi ad illuminarmi.

ciao

[KrOW]

Ciao . . . Sono tutt' altro che un genio in matematica ma dubito fortemente che esista un algoritmo/calcolo che faccia quello che dici . . . Sei sicuro di una possibile esistenza dell' algoritmo/calcolo???

[zar87]

ci ho provato 10 minuti ma ce una serie di varianti impressionanti...

es:
risultato = 10 ;
num calcoli = n ;(es: n = 2 ; )
somme = (x+y) : 1+9, 2+8, 3+7, 4+6, 5+5
(inizializzi n variabili x,y poi le infili in un while o do-while e ogni volta (in qst caso)
x++ e y--) fino a quando x = y lui le somma

se n = 3
ci vogliono in somma 3 variabili (x,y,z) e il gioco ricomincia... prova!!!! fammi sapere, ma non ti garantisco nulla!!

[MItaly]

Numeri naturali, giusto? Perché se sono relativi o razionali già diventa impossibile.

[oureyes]

intanto ringrazio per il passaggio e le risposte.

si sto parlando di numeri interi positivi, e vi metto un piccolo esempio tanto per capire meglio:

avendo come risultato : 7
e come numero di cifre che compongono la somma : 3

le somme che mi dovrebbero venire fuori dovrebbero essere :
--------------
somma 1 = 4+2+1
somma 2 = 3+3+1
somma 3 = 3+2+2
--------------

i due dati di cui siamo a conoscenza però sono variabili , quindi difficile risolverlo con dei semplici cicli while, ed il risultato sarà sempre maggiore del numero di cifre che compongono la somma.

lo so è un casino , non ci spero neanche più oramai...

provo comunque a fare qualche esperimento con il consiglio di zar87.

grazie 1000

[Krek_Stealth]

il problema è interessante prometto di ridarci un'occhiata con + calma domani.

Prima però dovresti definire un attimo una cosa che per te potrebbe essere ovvia ma per me non lo è.

Considerando le somme che hai scritto per esempio, l'ordine dei numeri è importante o no?

se

somma 1 = 4+2+1
somma 2 = 3+3+1
somma 3 = 3+2+2

con 3+1+3 parlo sempre di somma2 o è un'altra somma?

la domanda vale per tutte le combinazioni 4+2+1 e 1+2+4 o 1+4+2 rappresentano sempre la somma 1, etc...

la somma dei tre numeri rappresenta la stessa somma anche se addendi uguali non sono nello stesso ordine?

Grazie.

cmq il problema ha una soluzione in tutti e due i casi, anche se nel caso in cui si debba tenere in considerazione la posizione degli addendi la cosa si complica, il problema è risolvibile con carta e penna anche se è un pò macchinoso, quindi l'algoritmo esiste, ma ho qualche difficolta a scriverlo in maniera semplice.

ti faccio un esempio di come lo vedo io il problema.

per esempio prendo 21 come totale e 5 addendi.

R= 21 n= 5

si parte da

somma 01) 17+1+1+1+1
somma 02) 16+2+1+1+1
somma 03) 15+3+1+1+1
somma 04) 15+2+2+1+1
somma 05) 14+4+1+1+1
somma 06) 14+3+2+1+1
somma 07) 14+2+2+2+1
somma 08) 13+5+1+1+1
somma 09) 13+4+2+1+1
somma 10) 13+3+2+2+1
..............
proseguendo
..............
somma xx) 9+9+1+1+1
9+8+2+1+1
9+7+3+1+1
9+7+2+2+1
9+6+4+1+1
9+6+3+2+1
9+6+2+2+2
( 9+9+1+3+2 ) questa non la scrivo perchè è uguale a 9+6+3+2+1
9+5+5+1+1

etc .... ti assicuro che si trovano tutte le somme, l'algoritmo cel ho in testa e spero di tirarlo fuori, soprattutto spero che non sia l'ora tarda a avermi confuso le idee.

Cmq di base si ragiona cosi: dati R e n si assegna al primo numero valore R-n+1 e a gli altri valore 1. poi si va via via sottraendo uno al primo numero (r-n+1) e a ogni passaggio che si toglie uno dal primo numero poi si ridistribuisce il tolto fra gli altri numeri, poi mantendo fisso il pirmo numero si va a togliere uno alla volta numeri al secondo e si ridistribuiscono... etc,etc ..

Essendo più un problema di matematica che di programmazione e dato che con gli interi ci si fa un pò di tutto è sicuramente un problema che è già stato risolto da qualche matematico.

[oureyes]

grazie per l'interessamento,

definisco meglio alcuni aspetti che ho tralasciato:

1) non servono tutte le combinazioni , quindi la somma 3+1+3 fa parte sempre della 2° combinazione

2) l'ordine dei numeri non è importante , ma per semplicità credo che mettere in ordine numerico , dal più grande al più piccolo, il primo addendo sia la cosa migliore.

3) si la somma dei numeri rappresentano le stesse somme anche in ordine diverso.

Per semplicità credo si meglio provare con cifre abbastanza basse, per evitare di sprecare troppa carta

[zar87]

il discorso fatto da Krek_Stealth è ottimo, mi convince !!!

In effetti è più un giochetto matematico da fare su carta e penna, e da esso se ne trae un algoritmo, il che non è subito visibile credo !!!!

Mi togli una curiosità?? Ma a che ti serve questo programma?? x la scuola??
Se fosse così, ci sono esercizi mollto molto molto più istruttivi da fare !!!
Probabilmente mi sbaglierò !!!

Ciao e facci sapere, quando hai fatto il programma (c o c++??) posta il codice!!!!

[oureyes]

Che sia un gioco matematico non c'è dubbio

Sul fatto invece che siano un paio di cicli, dove a ogni passaggio che si toglie uno dal primo numero si ridistribuisca il tolto fra gli altri numeri , non mi sembra molto corretto; basti pensare solo che il numero del primo addendo di ogni combinazione non è sempre detto che sia un numero inferiore al precedente.

Questo programma non mi serve per la scuola, ma per un lavoro.

Innanzi tutto quello che sto cercando è "l'Enumerazione delle partizioni di ordine k"

e la soluzione dell'algoritmo viene spiegato nel capitolo 3 del Kreher-Stinson

ho però qualche difficolta di analisi e a riportarlo su php

[zar87]

soluzione dell'algoritmo viene spiegato nel capitolo 3 del Kreher-Stinson

Il capitolo 3 inizia da pag 67... mi permette di vedere fino alla pag 55

In effetti il mio ragionamento era campato in ario da soli 5 minuti di riflessione!!!, non ho abbozzato nulla ne fatto simulazioni !!!