Car4m (Normal User)
Newbie
Messaggi: 7
Iscritto: 19/06/2015
|
Given n dice each with m faces, numbered from 1 to m, find the number of ways to get sum X.
X is the summation of values on each face when all the dice are thrown.
With the following code we return all the permutations =(
But we are looking for just one permutations of each result: 4 and 3 is the same of 3 and 4 (with two dices and sum 7)
Codice sorgente - presumibilmente C++ |
#include <iostream> #include <string.h> using namespace std; int findWays(int m, int n, int x){ int table[n + 1][x + 1]; memset(table, 0, sizeof(table)); for (int j = 1; j <= m && j <= x; j++) table[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++) table[i][j] += table[i-1][j-k]; return table[n][x]; // forse dobbiamo avere un vettore a 3 dimensioni? table[ ] [ ] [ ] ? } int main(void){ cout << findWays(4, 2, 7) << endl; // cout << findWays(4, 2, 7) << endl; // cout << findWays(4, 3, 6) << endl; // cout << findWays(6, 3, 8) << endl; // cout << findWays(4, 2, 5) << endl; // cout << findWays(4, 3, 5) << endl; return 0; }
|
So how we can return just the ways not counting all the possible permutations?
For example:
findWays(4, 2, 7) have to return just one (because 3+4 or 4+3 is the same)
findWays(4, 3, 6) have to give three ways (1+1+4 and 1+2+3 and 2+2+2)
|