Dice Dynamic Pro (not simple) [C++]

[Giova411]

Ciao Ragazzi

Dati n dadi ciascuno con m facce, numerate da 1 a m, trovare il numero di modi per ottenere somma X.
X è la somma dei valori di ciascuna faccia quando vengono lanciati tutti i dadi.
Con il codice sottostante calcoliamo tutte le permutazioni = (
Ma siamo alla ricerca di una sola permutazione di ogni risultato:
esce 4 e poi 3 è lo stesso se esce 3 e poi 4 (esempio con due dadi da 4 facce e con somma 7)

Codice:

#include <iostream>
#include <string.h>
using namespace std;

int trovamodi(int m, int n, int x){
    int tabella[n + 1][x + 1];
    memset(tabella, 0, sizeof(tabella));
 
    for (int j = 1; j <= m && j <= x; j++)
        tabella[1][j] = 1;
 
    for (int i = 2; i <= n; i++)
        for (int j = 1; j <= x; j++)
            for (int k = 1; k <= m && k < j; k++)
                tabella[i][j] += tabella[i-1][j-k];
 
    return tabella[n][x];
}
 int main(void){
cout << trovamodi(4, 2, 7) << endl;
    // cout << trovamodi(4, 2, 7) << endl;
    // cout << trovamodi(4, 3, 6) << endl;
    // cout << trovamodi(6, 3, 8) << endl;
    // cout << trovamodi(4, 2, 5) << endl;
    // cout << trovamodi(4, 3, 5) << endl;
    return 0;
}


Quello che si vuole è ritornare solo i modi senza contare tutte le possibili permutazioni?
Per esempio:
trovamodi (4, 2, 7) deve tornare solo uno (perché 3 + 4 o 4 + 3 è lo stesso come già detto sopra)
Altro esempio:
trovamodi (4, 3, 6) deve dare tre modi (che sono: 1 + 1 + 4 e 1 + 2 + 3 e 2 + 2 + 2)
[in quest'ultimo caso abbiamo 3 dadi con 4 facce e vogliamo la somma 6]

Bisogna lavorare con una tabella a tre dimensioni sicuro ma non riesco a muovermi col 3D

[apatriarca]

No, basta prendere i valori dei dati ordinati.. Ci sarà infatti in questo modo un solo modo di scegliere i dadi.. A questo punto estrai un solo valore per volta, scegliendo un valore sempre minore o uguale a quello precedente.

[vict85]

Nota che tu hai \(\displaystyle a_1 + a_2 + \dotsb + a_n = X \). Ma allora posto \(\displaystyle b_1 = a_1 \), \(\displaystyle b_i = b_{i-1} + a_i \) hai che \(\displaystyle b_n = X \) e \(\displaystyle 0 < b_1 < \dotsb < b_{n-1} < b_n \). Con \(\displaystyle 1 \le b_i - b_{i-1} \le m \) dove per comodità ho posto \(\displaystyle b_{0} = 0 \). Trovare \(\displaystyle \{a_i\} \) equivale a trovare \(\displaystyle \{b_i\} \). Nota ovviamente che non devi trovare \(\displaystyle b_n \) e che l'ammissibilità di una successione può essere trovata in anticipo.

[Giova411]

Miticiii!!!!

Ok ma sto provando e non riesco a capire come "tappare" i cicli.

cout << trovamodi (4, 3, 6) << endl;
Mi stampa la seguente tabella:

0 0 0 0 0 0 0
0 1 1 1 1 0 0
0 0 1 2 3 4 3
0 0 0 1 3 6 10

Quindi il risultato (errato) sta in fondo a destra: 10 modi.
In realtà dovrei capire come memorizzare correttamente la matrice (affinché i modi siano 3)

[Giova411]

Sapete che ho sempre difficoltà con suggerimenti troppo matematici

Parlando con un esempio con due dadi.
Se esce un numero, diciamo il numero 1, vuol dire che non lo dobbiamo considerare nel lancio del secondo?
Infatti non ho capito

[apatriarca]

Un metodo abbastanza semplice utilizza un algoritmo ricorsivo che utilizza le seguenti proprietà:
1. Il valore minimo ottenibile da \(k\) dadi è \(k\).
2. Il valore massimo ottenibile da \(k\) dadi con \(m\) facce è \(k\,m\).
3. Per ottenere una singola permutazione per ogni possibile somma scegliamo il valore estratto al dado \(i+1\) in modo che sia minore o uguale di quello estratto al dado \(i\).
4. Una volta che ho scelto il valore del primo dado (supponiamo sia uguale a \(k\)), posso calcolare il numero di somme che partono da quel numero come \( F(k, n-1, x - k) \).

Nell'algoritmo ricorsivo consideri quindi tutti valori possibili del primo dado usando le proprietà 1 e 2. Calcoli quindi per ognuna il numero corrispondente usando la formula al punto 4. Spero ti piaccia.

[Giova411]

1)
Domanda sulla complessità: meglio questa soluzione rispetto ai 3 cicli? (che comunque dipendono dai dati immessi)
Non so farlo quindi chiedo ovviamente... Mi insegnasti tu che, a volte, la ricorsione è ottima (vedasi quicksort)
2)
La prima idea esclusa, ossia di usare un vettore a tre dimensioni dove abbiamo una variabile in più che ci da questo valore minimo (sopra di esso i possibili "futuri" risultati) non poteva essere un soluzione valida?
(che non so fare al momento)
3)
Col ragionamento di Vic devo "solo" capire come mettere le condizione dei 3 for?

Testo nascosto, fai click qui per vederlo

Sì ho messo i punti si

[vict85]

Nel mio metodo non hai l'unicità a meno di permutazioni, per averla devi usare un aggiustamento tipo quello presentato da Antonio.

[apatriarca]

Il metodo ricorsivo che ho presentato genera direttamente tutte le combinazioni possibili e nessun altra. Quindi la complessità è uguale al numero di tali combinazioni. L'uso della ricorsione è potenzialmente evitabile (si può riscriverlo in modo da non usarlo), ma non credo sia in questo caso determinante e la profondità di ricorsione è abbastanza limitata. In ogni caso non lo userei per valori di \(n\) particolarmente alti.. Tra tutti i metodi che forniscono l'intera lista dei valori è abbastanza ottimale (nel senso che non si può fare granché di meglio..), ma credo possa essere possibile fare qualcosa di più intelligente. Siamo in effetti interessati al numero di combinazioni e non ad una loro enumerazione..

[Giova411]

Miei Grandi Maestri avevo "preso" questo esercizio proprio per capire come lavorare con una matrice a tre dimensioni.
Nella caso in questione volevo:
int tabella[x][n][m];
Dove ovviamente si ha:
somma x da cercare
numero n di dadi
m facce che, però di volta in volta, ci indica il valore minimo del dado che può essere considerato.
(Come già scritto da voi, essa deve essere $>=$ dei valori già trovati per non avere tutte le permutazioni inutili)

Magari usando la tecnica PD/memoized si può scrivere qualcosa di meno elegante (rispetto alla soluzione di Apa) ma che rientra in ciò che vorrei imparare a fare