Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Need help, loops...

Reply
Thread Tools

Need help, loops...

 
 
Fei Liu
Guest
Posts: n/a
 
      04-22-2010
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;
}
 
Reply With Quote
 
 
 
 
Arny
Guest
Posts: n/a
 
      04-22-2010


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
 
Reply With Quote
 
 
 
 
Fei Liu
Guest
Posts: n/a
 
      04-22-2010
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;
}
 
Reply With Quote
 
Ben
Guest
Posts: n/a
 
      04-23-2010
> 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:ow(10.0, n)/9;
int end = start/10 + std:ow(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

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Need to "shred" hardive..need software. Xeno Chauvin Computer Support 4 03-13-2005 01:26 PM
Need help with need to Force Garbage Collect John Java 1 08-19-2004 03:32 PM
Need help! I need to add lead zeros to a textbox Teep ASP .Net 2 06-21-2004 01:04 PM
Please help!!! Need datagrid selection to fill textboxes...Need quick!! TN Bella ASP .Net 1 06-18-2004 01:31 AM
Need to compare Photos to DVD software - Need Help? Bob Digital Photography 4 02-04-2004 02:13 AM



Advertisments