mi serve una formula matematica

Hai una curiosità o un problema con Game Maker? Domanda e ti sarà risposto!
Avatar utente
jumoonp
GMI VIP
Messaggi: 3292
Iscritto il: 13/01/2008, 20:59
Contatta:

mi serve una formula matematica

Messaggio da jumoonp »

salve ragazzi...

devo calcolare quante combinazioni ci sono addizionando 4 addendi la cui somma totale sia sempre di ugual valore.
I 4 addendi non possono superare il valore di 15....

per esempio:
0+0+15+15=30
15+1+5+9=30
ect ect...
Spoiler
Gabriele Dell'Otto e Lee bermejo

Immagine

Avatar utente
doom13
Moderatore
Messaggi: 2093
Iscritto il: 31/08/2012, 15:40
Specialità: Programmazione
Uso: GM:Studio 2
Contatta:

Re: mi serve una formula matematica

Messaggio da doom13 »

jumoonp ha scritto:la cui somma totale sia sempre di ugual valore..
Sempre uguale a 30 oppure anche altri valori?
Immagine
Spoiler
Maze [sospeso]
Isom (titolo provvisorio) (Windows & Android) [sospeso]
Keep Calm & Jump (Android) [In corso]
The Graywall (Windows) [Completo]
DTB (Windows & Android) [Completo]
The Last Spell (Windows) [Completo]
Dukenstein: Return to the house (Windows) [Completo]
DMSystem (Windows) [Completo]
"Things get hard sometimes guys... But remember, dicks get hard too, but they don't stay hard forever. Don't give up!"

Avatar utente
jumoonp
GMI VIP
Messaggi: 3292
Iscritto il: 13/01/2008, 20:59
Contatta:

Re: mi serve una formula matematica

Messaggio da jumoonp »

doom13 ha scritto:
jumoonp ha scritto:la cui somma totale sia sempre di ugual valore..
Sempre uguale a 30 oppure anche altri valori?
il totale deve essere sempre dello stesso valore, in questo caso dell'esempio è sempre 30
Spoiler
Gabriele Dell'Otto e Lee bermejo

Immagine

Avatar utente
doom13
Moderatore
Messaggi: 2093
Iscritto il: 31/08/2012, 15:40
Specialità: Programmazione
Uso: GM:Studio 2
Contatta:

Re: mi serve una formula matematica

Messaggio da doom13 »

jumoonp ha scritto:
doom13 ha scritto:
jumoonp ha scritto:la cui somma totale sia sempre di ugual valore..
Sempre uguale a 30 oppure anche altri valori?
il totale deve essere sempre dello stesso valore, in questo caso dell'esempio è sempre 30
Allora non lo so, se hai la pazienza di aspettare 4 o 5 mesi :asd:
Immagine
Spoiler
Maze [sospeso]
Isom (titolo provvisorio) (Windows & Android) [sospeso]
Keep Calm & Jump (Android) [In corso]
The Graywall (Windows) [Completo]
DTB (Windows & Android) [Completo]
The Last Spell (Windows) [Completo]
Dukenstein: Return to the house (Windows) [Completo]
DMSystem (Windows) [Completo]
"Things get hard sometimes guys... But remember, dicks get hard too, but they don't stay hard forever. Don't give up!"

Avatar utente
ScemEnzo
Membro
Messaggi: 130
Iscritto il: 27/05/2014, 15:05
Specialità: Programmatore
Uso: GM:Studio 1.4 Standard
Località: Napoli
Contatta:

Re: mi serve una formula matematica

Messaggio da ScemEnzo »

Stavo cercando di trovare una formula matematica con quel poco che so sulla probabilistica e sulle variabili aleatorie, ma mi sorge un dubbio:
Vuoi una formula matematica vera e propria oppure un algoritmo?
Se vuoi una vera e propria formula matematica, ho provato per passi e sintetizzare una formula sembra una cosa abbastanza dispendiosa.
Contatti Giochi Immagine

Avatar utente
doom13
Moderatore
Messaggi: 2093
Iscritto il: 31/08/2012, 15:40
Specialità: Programmazione
Uso: GM:Studio 2
Contatta:

Re: mi serve una formula matematica

Messaggio da doom13 »

Qua ci andava a pennello la saccenza di Breston...

Comunque le combinazione totali che puoi ottenere dovrebbero essere 16*4, di queste ovviamente solo una piccolissima parte fanno al caso tuo.
Vediamo se ricordo qualcosa dalle superiori che mi possa servire.
Immagine
Spoiler
Maze [sospeso]
Isom (titolo provvisorio) (Windows & Android) [sospeso]
Keep Calm & Jump (Android) [In corso]
The Graywall (Windows) [Completo]
DTB (Windows & Android) [Completo]
The Last Spell (Windows) [Completo]
Dukenstein: Return to the house (Windows) [Completo]
DMSystem (Windows) [Completo]
"Things get hard sometimes guys... But remember, dicks get hard too, but they don't stay hard forever. Don't give up!"

Avatar utente
pacmino
GMI Guru
Messaggi: 2569
Iscritto il: 03/06/2009, 16:38
Specialità: Scazzato cronico
Uso: GM:Studio 2
Località: Seconda stella a destra questo è il cammino e poi dritto, fino al mattino...
Contatta:

Re: mi serve una formula matematica

Messaggio da pacmino »

tu insomma chiedi in quanti modi si possono sommare 4 numeri dal 0 a x in maniera tale che la somma finale sia sempre z

credo che siano combinazioni con ripetizione http://www.ripmat.it/mate/l/lb/lbcb.html

poi tu vorresti anche che ti venga data la dimostrazione cioè la tabellina con le possibili combinazioni
Immagine

Avatar utente
doom13
Moderatore
Messaggi: 2093
Iscritto il: 31/08/2012, 15:40
Specialità: Programmazione
Uso: GM:Studio 2
Contatta:

Re: mi serve una formula matematica

Messaggio da doom13 »

Ho scitto al volo due righe di codice su GM:

Codice: Seleziona tutto

comb = 0;
for(val1 = 0; val1 < 16; val1++)
{
    show_debug_message("val1: "+string(val1));
    for(val2 = 0; val2 < 16; val2++)
    {
        show_debug_message("val2: "+string(val2));
        for(val3 = 0; val3 < 16; val3++)
        {
            show_debug_message("val3: "+string(val3));
            for(val4 = 0; val4 < 16; val4++)
            {
                show_debug_message("val4: "+string(val4));
                sum = val1+val2+val3+val4;
                if(sum == 30)
                    comb++;
            }
        }
    }
}

show_debug_message("Numero combinazioni: "+string(comb));
Vengono 2736 combinazioni :)
Immagine
Spoiler
Maze [sospeso]
Isom (titolo provvisorio) (Windows & Android) [sospeso]
Keep Calm & Jump (Android) [In corso]
The Graywall (Windows) [Completo]
DTB (Windows & Android) [Completo]
The Last Spell (Windows) [Completo]
Dukenstein: Return to the house (Windows) [Completo]
DMSystem (Windows) [Completo]
"Things get hard sometimes guys... But remember, dicks get hard too, but they don't stay hard forever. Don't give up!"

Avatar utente
ScemEnzo
Membro
Messaggi: 130
Iscritto il: 27/05/2014, 15:05
Specialità: Programmatore
Uso: GM:Studio 1.4 Standard
Località: Napoli
Contatta:

Re: mi serve una formula matematica

Messaggio da ScemEnzo »

pacmino ha scritto: credo che siano combinazioni con ripetizione http://www.ripmat.it/mate/l/lb/lbcb.html
Wow, fantastico OoO peccato che non ci sia la dimostrazione :(
Comunque non risolve il problema dal momento che lo scopo è proprio sapere il numero di volte in cui un dato output si ripete nelle combinazioni.
Se si prova a fare per passi, all'aumentare del valore somma le cose si complicano tantissimo, da che lo 0 ha quattro combinazioni ad 1 che ne ha dieci.
Il numero totale di combinazioni si può ottenere facilmente con la tecnica dei complementi alla base che, in questo caso, corrisponde proprio a quella esadecimale:

16^(0)+16^(1)+16^(2)+16^(3) = 4369 combinazioni

il problema è selezionare le combinazioni opportune che danno una certa somma, cosa che riesce facile con il for indentato dell'algoritmo in codice.
Ultima modifica di ScemEnzo il 19/05/2015, 19:31, modificato 1 volta in totale.
Contatti Giochi Immagine

Avatar utente
ScemEnzo
Membro
Messaggi: 130
Iscritto il: 27/05/2014, 15:05
Specialità: Programmatore
Uso: GM:Studio 1.4 Standard
Località: Napoli
Contatta:

Re: mi serve una formula matematica

Messaggio da ScemEnzo »

doom13 ha scritto: Vengono 2736 combinazioni :)
Che fico, stavo pensando allo stesso identico algoritmo XD
Comunque era per questo che l'avevo chiesto.
Si potrebbe anche dare la possibilità di variare la somma tra 0 e 60
Contatti Giochi Immagine

Avatar utente
Breston
Membro
Messaggi: 84
Iscritto il: 21/08/2014, 15:51
Specialità: Nothing
Uso: GM:Studio 2
Contatta:

Re: mi serve una formula matematica

Messaggio da Breston »

ScemEnzo ha scritto:probabilistica
Intendevi statistica o probabilità? E cosa c'entra in questo caso? Non c'è nulla di aleatorio.
Facciamo un po' di chiarezza sul numero totale delle combinazioni possibili con n cifre m-arie.
Il metodo intuitivo per capirlo è immaginare di aggiungere ad una stringa qualunque una cifra m-aria. Le combinazioni sono state moltiplicate per m, infatti ci sarà una nuova stringa per ogni valore della cifra aggiunta.
Segue che le combinazioni di n cifre m-arie sono [latex]m^n[/latex], nel nostro caso 16^4 = 65536 possibili combinazioni, che corrisponde anche al numero di iterazioni che esegue il ciclo for più interno del codice di brute force passato più sopra, che come mostra la formula cresce esponenzialmente secondo il numero di cifre o valori, ed è quindi terribilmente inefficiente.
ScemEnzo ha scritto: 16^(0)+16^(1)+16^(2)+16^(3) = 4369 combinazioni
Dovrebbe essere: valore*base^posizione, oppure valore*peso, dove peso = base^posizione.
In questo caso 15*16^0 + 15*16^1 + 15*16^2 + 15*16^3 = 65536, è il valor massimo di una parola di quattro cifre in codice esadecimale, che come dici coincide con il numero di combinazioni.

Per quanto riguarda l'algoritmo potrebbe essere sufficiente aggiungere un pizzico di euristica, per esempio bloccando un ciclo for la dove la somma sia già oltre quella richiesta.
Si può poi rendere lo script ricorsivo per consentire di risolvere l'intera classe di problemi (per qualunque numero di cifre).

Avatar utente
doom13
Moderatore
Messaggi: 2093
Iscritto il: 31/08/2012, 15:40
Specialità: Programmazione
Uso: GM:Studio 2
Contatta:

Re: mi serve una formula matematica

Messaggio da doom13 »

Ora sono contento.
Immagine
Spoiler
Maze [sospeso]
Isom (titolo provvisorio) (Windows & Android) [sospeso]
Keep Calm & Jump (Android) [In corso]
The Graywall (Windows) [Completo]
DTB (Windows & Android) [Completo]
The Last Spell (Windows) [Completo]
Dukenstein: Return to the house (Windows) [Completo]
DMSystem (Windows) [Completo]
"Things get hard sometimes guys... But remember, dicks get hard too, but they don't stay hard forever. Don't give up!"

Avatar utente
Wolfrost
Membro super
Messaggi: 692
Iscritto il: 03/08/2014, 13:08
Specialità: Programmazione
Uso: GM:Studio 1.4 Pro
Località: Una galassia lontana lontana...
Contatta:

Re: mi serve una formula matematica

Messaggio da Wolfrost »

doom13 ha scritto:Ora sono contento.
Immagine

Immagine

Avatar utente
ScemEnzo
Membro
Messaggi: 130
Iscritto il: 27/05/2014, 15:05
Specialità: Programmatore
Uso: GM:Studio 1.4 Standard
Località: Napoli
Contatta:

Re: mi serve una formula matematica

Messaggio da ScemEnzo »

Breston ha scritto: Intendevi statistica o probabilità? E cosa c'entra in questo caso? Non c'è nulla di aleatorio.
Si scusa, confondo facilmente le cose per il corso che ho seguito all'università.
Intendevo riferirmi a quelle poche conoscenze che ho riguardo il calcolo delle combinazioni.
Breston ha scritto: 15*16^0 + 15*16^1 + 15*16^2 + 15*16^3 = 65536
Cavolo :spat: avevo dimenticato di moltiplicare per il numero di valori per ogni elemento.
Contatti Giochi Immagine

Avatar utente
pacmino
GMI Guru
Messaggi: 2569
Iscritto il: 03/06/2009, 16:38
Specialità: Scazzato cronico
Uso: GM:Studio 2
Località: Seconda stella a destra questo è il cammino e poi dritto, fino al mattino...
Contatta:

Re: mi serve una formula matematica

Messaggio da pacmino »

Immagine

Avatar utente
jumoonp
GMI VIP
Messaggi: 3292
Iscritto il: 13/01/2008, 20:59
Contatta:

Re: mi serve una formula matematica

Messaggio da jumoonp »

Si, mi sono espresso male, mi serviva l'algoritmo per snocciolare le combinazioni su txt
Spoiler
Gabriele Dell'Otto e Lee bermejo

Immagine

Avatar utente
ScemEnzo
Membro
Messaggi: 130
Iscritto il: 27/05/2014, 15:05
Specialità: Programmatore
Uso: GM:Studio 1.4 Standard
Località: Napoli
Contatta:

Re: mi serve una formula matematica

Messaggio da ScemEnzo »

jumoonp ha scritto:mi serviva l'algoritmo
Allora for indentato is the way ;)
Oltre all'ottimizzazione che ha proposto Breston con un controllo sul superamento della soglia massima della somma, puoi tagliare i for anche con un controlo sulla soglia minima relativo alla somma finale che vuoi ottenere e relativa al variare dell'addendo considerato (cioè per ogni for indentato).

Può sembrare una finezza, ma si fa questo ed altro pur di ostacolare dei lentissimi e pesantissimi for indentati
Contatti Giochi Immagine

Avatar utente
Breston
Membro
Messaggi: 84
Iscritto il: 21/08/2014, 15:51
Specialità: Nothing
Uso: GM:Studio 2
Contatta:

Re: mi serve una formula matematica

Messaggio da Breston »

Difatti credo proprio che sia possibile dimostrare che se applichi sia il controllo sul minimo che sul massimo in ogni for, quello più interno produrrà esclusivamente combinazioni valide, e dunque è l'algoritmo ottimo.

Avatar utente
Breston
Membro
Messaggi: 84
Iscritto il: 21/08/2014, 15:51
Specialità: Nothing
Uso: GM:Studio 2
Contatta:

Re: mi serve una formula matematica

Messaggio da Breston »

Per non saper cosa fare questa mattina ho scritto il codice, ed effettivamente è come pensavo.

Codice: Seleziona tutto

/*******************************************************************************
*  @brief      Trova tutte le combinazioni di numeri la cui somma sia fissata
*
*  @usage      FindCombinations(4,30,15)
*
*  @param      p il numero massimo di addendi
*  @param      S la somma che si deve ottenere
*  @param      t il valor massimo di ogni addendo
*******************************************************************************/
void FindCombinations(int p, int S, int t, int partialsum = 0, string comb = "")
{
    // Trova estremo inferiore m e superiore M su cui ciclare
    // m è il numero per cui partialsum+m+(p-1)*t = S
    // M è il numero per cui M+partialsum = S
    int m = S - (p - 1) * t - partialsum;
    if (m < 0) m = 0;
    int M = S - partialsum;
    if (M > t) M = t;

    for (int i = m; i <= M; i++)
    {
        if (p > 1)
            FindCombinations(p - 1, S, t, partialsum + i,
                comb + i.ToString() + " ");
        else
        {
            // Questo è il ciclo for più interno:
            // Non c'è bisogno di controllare che la somma sia S
            Console.WriteLine(comb + i.ToString());
        }
    }
}
È in C# ma immagino sappiate convertirlo.
Potrei fornirvi anche una dimostrazione matematica del perché funziona, ma preferisco vedere se riuscite a farla da soli :twisted: .

Avatar utente
doom13
Moderatore
Messaggi: 2093
Iscritto il: 31/08/2012, 15:40
Specialità: Programmazione
Uso: GM:Studio 2
Contatta:

Re: mi serve una formula matematica

Messaggio da doom13 »

Breston ha scritto:Potrei fornirvi anche una dimostrazione matematica del perché funziona, ma preferisco vedere se riuscite a farla da soli :twisted: .
Nun ce interessa, vogliamo la pappa pronta :asd:

Preparati Breston che più tardi se ho tempo ho un altro quesito per te :twisted:
Immagine
Spoiler
Maze [sospeso]
Isom (titolo provvisorio) (Windows & Android) [sospeso]
Keep Calm & Jump (Android) [In corso]
The Graywall (Windows) [Completo]
DTB (Windows & Android) [Completo]
The Last Spell (Windows) [Completo]
Dukenstein: Return to the house (Windows) [Completo]
DMSystem (Windows) [Completo]
"Things get hard sometimes guys... But remember, dicks get hard too, but they don't stay hard forever. Don't give up!"

Rispondi

Chi c’è in linea

Visitano il forum: Nessuno e 37 ospiti