Need help, loops...

Discussion in 'C++' started by Fei Liu, Apr 22, 2010.

  1. Fei Liu

    Fei Liu Guest

    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:
    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <numeric>
    #include <iterator>
    using namespace std;

    int main(void){

    unsigned int n, i,k;

    while(cin){
    cin >> n;
    string line;
    getline(cin, line);

    unsigned int min=n, max=n*6, sum=0;
    vector<unsigned int> dice(n);

    for(i=min; i <= max; i ++){

    for(k=0; k < n; k ++)
    for(j=1; j <= 6; j ++)
    dice[k] = j;

    sum = accumulate(dice.begin(), dice.end(), 0);
    if(sum == i) {
    copy(dice.begin(), dice.end(),
    ostream_iterator<unsigned int>(cout, " "));
    cout << i << ' ' << endl;
    }
    }
    }
    return 0;
    }
     
    Fei Liu, Apr 22, 2010
    #1
    1. Advertising

  2. Fei Liu

    Arny Guest

    On 22.04.2010 17:13, 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


    I would solve it by finding all possible combinations, then the unique
    combinations, and then create the permutations based on the unique
    combinations.

    - RaZ
     
    Arny, Apr 22, 2010
    #2
    1. Advertising

  3. Fei Liu

    Fei Liu Guest

    Victor Bazarov wrote:
    > Fei Liu wrote:
    >> 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)

    >
    > I think this is commonly solved using recursion.
    >
    > V

    Good idea, I have a working prototype, it's slow (exponential) but
    produces correct answer.

    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <numeric>
    #include <iterator>
    using namespace std;

    typedef vector<unsigned int>::iterator dice_iterator;
    typedef vector<unsigned int>::reverse_iterator dice_reverse_iterator;

    void add_and_carry(dice_reverse_iterator iter, int position){

    (*iter)++;
    if(*iter == 7 && position != 0){
    add_and_carry(iter+1, position-1);
    *iter = 1;
    }
    }

    int main(void){

    unsigned int n, i,k;

    while(cin){
    cin >> n;
    string line;
    getline(cin, line);

    unsigned int min=n, max=n*6, sum=0;
    vector<unsigned int> dice(n);
    dice_iterator iter = dice.begin();

    for(i = min; i <= max; i++){
    for(; iter != dice.end(); iter ++)
    *iter = (i-1)/n+1;
    iter = dice.begin();
    do{

    sum = accumulate(dice.begin(), dice.end(), 0);
    if(sum == i) {
    copy(dice.begin(), dice.end(),
    ostream_iterator<unsigned int>(cout, " "));
    cout << i << ' ' << endl;
    }
    add_and_carry(dice.rbegin(), n-1);
    } while(*iter != 7);
    }
    }
    return 0;
    }
     
    Fei Liu, Apr 22, 2010
    #3
  4. Fei Liu

    Ben Guest

    > 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:


    If n is small, you can use a single unsigned integer to store the
    combinations. A 64 bit integer can work with n <=18, this will be a lot
    faster than using a vector.

    If that is the case, the solution is trivial:

    int n = 4;
    int sum = 8;

    int start = sum - n + std::pow(10.0, n)/9;
    int end = start/10 + std::pow(10.0, n - 1) * (sum - n + 1);

    while (start <= end)
    {
    std::cout << start << "\n";
    start += 9;
    }

    Of course, this assumes a 10-sided dice :). How to adjust the algorithm so
    that it outputs 6-sided dice numbers is left for you as an exercise.

    Regards,
    Ben
     
    Ben, Apr 23, 2010
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Rob

    help with infinite loops and scanf

    Rob, Jul 26, 2003, in forum: C Programming
    Replies:
    8
    Views:
    774
    Peter Shaggy Haywood
    Jul 29, 2003
  2. jstreet10
    Replies:
    1
    Views:
    344
    Sean Ross
    Dec 3, 2003
  3. Me
    Replies:
    2
    Views:
    247
  4. Steve

    Need help with Wx and loops

    Steve, Feb 24, 2010, in forum: Perl Misc
    Replies:
    1
    Views:
    93
    Steve
    Feb 24, 2010
  5. _TT_
    Replies:
    3
    Views:
    96
Loading...

Share This Page