Re: Need help, loops...
Stuart Golodetz wrote:
Fei Liu wrote:
Hi,
I am trying to write a program to count dices. The program takes a
single integer 'n' (number of dice), it then outputs between 'n' and
'6*n', what combinations of the n dice result sums to it. Say, n=4,
sum=5, then it outputs 1 1 1 2 5, 1 1 2 1 5, 1 2 1 1 5, 2 1 1 1 5. I
am stuck with a problem, since my program is supposed to accept
arbitrary number of dice, I can't come up with a way to code the
loops. Remember it needs to iterate through arbitrary number of dices.
Here is what I have (compilies/runs/result is wrong for obvious reasons)
Let me know if you can come up with a smart pattern to solve this:
Sounds like a dynamic programming problem.
Stu
For example (assuming I haven't done anything dumb):
#include <iostream>
#include <vector>
void output(const std::vector<std::vector<std::vector<int> > >& table,
int i, int j, std::vector<int>& st)
{
if(i != 0 || j != 0)
{
const std::vector<int>& entry = table[i][j];
for(std::vector<int>::const_iterator it=entry.begin(),
iend=entry.end(); it!=iend; ++it)
{
st.push_back(*it);
output(table, i - 1 , j - *it, st);
st.pop_back();
}
}
else
{
std::copy(st.begin(), st.end(), std::ostream_iterator<int>(std::cout,
" "));
std::cout << '\n';
}
}
int main()
{
int n = 4, sum = 10;
std::vector<std::vector<std::vector<int> > > table(n+1);
table[0].resize(sum+1);
table[0][0].push_back(0);
for(int i=1; i<=n; ++i)
{
table[i].resize(sum+1);
for(int j=1; j<=sum; ++j)
{
// Maximum dice roll that won't put us over
// the amount to make.
int m = std::min(6, j);
for(int k=1; k<=m; ++k)
{
if(!table[i-1][j-k].empty())
{
table[i][j].push_back(k);
}
}
}
}
std::vector<int> st;
output(table, n, sum, st);
return 0;
}
This is probably not the most efficient way of doing this for a single
query, I should add :) It's great if you want to answer lots of these
queries though.
HTH,
Stu