Dice Dynamic Pro (not simple) [C++]
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)
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
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)
#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
Risposte
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.
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.
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)
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)
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
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
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.
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.
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?
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?
Nel mio metodo non hai l'unicità a meno di permutazioni, per averla devi usare un aggiustamento tipo quello presentato da Antonio.
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..
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
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
Sapete bene che sono un tardone!!! 
Questo tipo di problema si potrebbe risolvere quasi come il seguente? (Dynamic Programming Solution)
http://www.geeksforgeeks.org/dynamic-pr ... in-change/
Usando quindi un vettore che contiene le facce (ovvio si deve moltiplicare poi per il numero di dadi dati)
Questo tipo di problema si potrebbe risolvere quasi come il seguente? (Dynamic Programming Solution)
http://www.geeksforgeeks.org/dynamic-pr ... in-change/
Usando quindi un vettore che contiene le facce (ovvio si deve moltiplicare poi per il numero di dadi dati)
Analizzo il problema con una certa attenzione.
Sia \(\displaystyle 1\le a_1 \le \dotsb \le a_n \le m \) e sia \(\displaystyle b_0 = 0 \), \(\displaystyle b_i = b_{i-1} + a_i \). Ovvero \(\displaystyle b_k = \sum_{i=1}^k a_i \). Inoltre vogliamo che \(\displaystyle b_n = x \).
Supponiamo di avere \(\displaystyle a_i \) e quindi \(\displaystyle b_i \). Devo trovare \(\displaystyle m_{i+1} \), \(\displaystyle M_{i+1} \) tali che \(\displaystyle m_{i+1} \le b_{i+1} \le M_{i+1} \). Le condizioni più facili sono \(\displaystyle m_{i+1} \ge b_i + a_i = 2b_i - b_{i-1} \) e che \(\displaystyle M_{i+1} \le b_i + m \). D'altra parte ci sono altre condizioni.
La prima di queste condizioni è \(\displaystyle m_{i+1} + (n-i-1)m \ge x \), ovvero che \(\displaystyle x \) sia raggiungibile. La seconda è che \(\displaystyle M_{i+1} + (n-i-1)(M_{i+1}-b_i) \le x \) ovvero che il passo possa essere mantenuto senza superare \(\displaystyle x \).
In altre parole \(\displaystyle m_{i+1} = \max\bigl\{b_i + a_i, x - (n-i-1)m\bigr\} \) e \(\displaystyle M_{i+1} = \min\Bigl\{ b_i + m, \frac{x + (n-i-1)b_i}{n-i} \Bigr\} \)
Usando queste condizioni sono uscito con questo:
[edit] Ovvamente si poteva lavorare direttamente con a e non calcolare b. Le condizioni sono simili, forse il tutto veniva anche più facile
. Non so, l'ho fatto così
Sia \(\displaystyle 1\le a_1 \le \dotsb \le a_n \le m \) e sia \(\displaystyle b_0 = 0 \), \(\displaystyle b_i = b_{i-1} + a_i \). Ovvero \(\displaystyle b_k = \sum_{i=1}^k a_i \). Inoltre vogliamo che \(\displaystyle b_n = x \).
Supponiamo di avere \(\displaystyle a_i \) e quindi \(\displaystyle b_i \). Devo trovare \(\displaystyle m_{i+1} \), \(\displaystyle M_{i+1} \) tali che \(\displaystyle m_{i+1} \le b_{i+1} \le M_{i+1} \). Le condizioni più facili sono \(\displaystyle m_{i+1} \ge b_i + a_i = 2b_i - b_{i-1} \) e che \(\displaystyle M_{i+1} \le b_i + m \). D'altra parte ci sono altre condizioni.
La prima di queste condizioni è \(\displaystyle m_{i+1} + (n-i-1)m \ge x \), ovvero che \(\displaystyle x \) sia raggiungibile. La seconda è che \(\displaystyle M_{i+1} + (n-i-1)(M_{i+1}-b_i) \le x \) ovvero che il passo possa essere mantenuto senza superare \(\displaystyle x \).
In altre parole \(\displaystyle m_{i+1} = \max\bigl\{b_i + a_i, x - (n-i-1)m\bigr\} \) e \(\displaystyle M_{i+1} = \min\Bigl\{ b_i + m, \frac{x + (n-i-1)b_i}{n-i} \Bigr\} \)
Usando queste condizioni sono uscito con questo:
#include <iostream>
int trovamodi(int m, int n, int x);
void nuovomodo(int &cont, int b[], int step, int m, int n, int x);
int main(void)
{
std::cout << trovamodi(4, 2, 7) << std::endl;
std::cout << trovamodi(4, 3, 6) << std::endl;
std::cout << trovamodi(6, 3, 8) << std::endl;
std::cout << trovamodi(4, 2, 5) << std::endl;
std::cout << trovamodi(4, 3, 5) << std::endl;
return 0;
}
int trovamodi(int m, int n, int x)
{
int *b = new int[n+1];
int r = 0;
b[0] = 0;
int const m1 = x - (n-1)*m;
int const bmin = (m1 > 1) ? m1 : 1;
int const M1 = x/n;
int const bmax = (M1 < m) ? M1 : m;
for(int i = bmin; i <= bmax; ++i)
{
b[1] = i;
nuovomodo(r, b, 1, m, n, x);
}
return r;
}
void nuovomodo(int &cont, int b[], int step, int m, int n, int x)
{
if(step != n-1)
{
int const m1 = x - (n - step - 1)*m;
int const m2 = 2*b[step] - b[step-1];
int const bmin = (m1 > m2) ? m1 : m2;
int const M1 = (x + (n - step - 1)*b[step])/(n-step);
int const M2 = b[step] + m;
int const bmax = (M1 < M2) ? M1 : M2;
for(int i = bmin; i <= bmax; ++i)
{
b[step+1] = i;
nuovomodo(cont, b, step+1, m, n, x);
}
}
else
{
++cont;
b[n] = x;
for(int i = 1; i != n; ++i)
{
std::cout << b[i]-b[i-1] << " + ";
}
std::cout << b[n] - b[n-1] << std::endl;
}
}
[edit] Ovvamente si poteva lavorare direttamente con a e non calcolare b. Le condizioni sono simili, forse il tutto veniva anche più facile
. Non so, l'ho fatto così
Vic non ho parole. Ci sto dietro da giorni
Che invidiaaaaaaaa 
Avevo dimenticato un controllo iniziale tipo
//se la somma è troppo alta rispetto ai dadi (considerando i massimi valori delle facce non si raggiunge lo stesso la x cercata)
if (m*n <= x)
return (m*n == x);
//se la somma è troppo bassa rispetto ai dadi
if (n >= x)
return (n == x);
Che dire???
GRAZIE
Sono tornato da mesi, anche se in questi giorni sono un po' preso con gli ultimi esami.
In bocca al lupo!! Spacchi tutti son sicuro!!! 
Ancora Grazie!!!!!!!!!!!!
Ancora Grazie!!!!!!!!!!!!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo