Re: rolling dice

Elijah Cardon wrote:
"Michael Mair" <Michael.Mair@xxxxxxxxxxxxxxx> wrote
Elijah Cardon wrote:
"Michael Mair" <Michael.Mair@xxxxxxxxxxxxxxx> wrote
Elijah Cardon wrote:

Let's say I have m dice having n sides, such that n^m is not going to bust int as a datatype. With m=4 and n=6, an outcome might be {2, 5, 1, 2}. What is a good way to represent this in c so that I can check cases by brute force? EC

#include <stdio.h>

int countSumOccurrences(int n, int m, int sum);
void countSumOccurrences_Rec(int n, int m, int sum, int *pCount);

int main (void)
{
int i;
for (i = 1; i <= 5; ++i)
printf("%d 6 sided dices; occurrence of sum %d: %d times\n",
i, 2*i, countSumOccurrences(6, i, 2*i));
return 0;
}

int countSumOccurrences(int n, int m, int sum)
{
int count = 0;
countSumOccurrences_Rec(n, m, sum, &count);
return count;
}

void countSumOccurrences_Rec(int n, int m, int sum, int *pCount)
{
#define VALUE_ADJUSTMENT(v) ((v)+1)
if (m == 1) {
if (sum >= VALUE_ADJUSTMENT(0) && sum < VALUE_ADJUSTMENT(n)) {
++*pCount;
}
}
else if (m > 1) {
int i;
for (i = 0; i < n && i <= sum; ++i) {
countSumOccurrences_Rec(n, m - 1,
sum - VALUE_ADJUSTMENT(i), pCount);
}
}
}
`---

Note that you can always get rid of a recursion via using a stack.
You probably want to get rid of the VALUE_ADJUSTMENT in this case.

This is the line I wanted to take this in, but I gotta get my head around the notions of recursion and stack depth. To that I end I ask this question:
long factorial(int n) {
if (n == 1)
return 1;
return n * factorial(n - 1);
}

What is the stack depth as a function of n? If you look at the discussion in chp 10 of _C Unleashed_, it follows the execution of this source. At the end, there are n-1 paragraphs that begin:
Back on line ....
, so I think the stack depth is n-1 . If I'm wrong that it's near n, I don't see how stack depth could be less than (n-1)! . EC

I now have got back my copy of C Unleashed, so I know what you mean:
You have essentially the same structure as above:
if (m == 1)
do something to *pCount;
else if (m > 1)
hand it to the same function with (m-1)
i.e. you have the same stack depth as for the factorial() function.
The loop is merely decoration as it will not change the stack depth.
It changes the stack's contents, though:
Let's take the second run of the loop in main()
- The "first level call" to countSumOccurrences_Rec() issues
a "second level call" for i = 0, 1, 2, 3, 4.
- The stack depth for each of the "second level calls" is the same
but you have different i values and, consequently, different sum
values in the call stack


Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.
.

Relevant Pages

  • Re: Stack depth
    ... I have 1 GB RAM and i use Fedora Core. ... exotic inlining of calls (even recursiv ones), ... int fact ...
    (comp.lang.c)
  • Re: rolling dice
    ... int countSumOccurrences; ... void countSumOccurrences_Rec(int n, int m, int sum, int *pCount); ... What is the stack depth as a function of n? ...
    (comp.lang.c)
  • Re: Algorithm
    ... Wont sum of all positive numbers will be the largest sub-array? ... int getint ... struct sofar *next; ... struct sofar *discard(struct sofar *trail) ...
    (comp.lang.c)
  • Re: Arrays vs Buffers
    ... and the next array access is dependent on the value ... and then return the overall sum to the test harness ... nextPointer(int[] array, int point) ... pointer = nextPointer; ...
    (comp.lang.java.programmer)
  • Re: sum(2,4,3,5,-1,...)
    ... The only example I have to imitate is the one on p.289 ... of an array related to the first argument of the function sum I'm ... int sum ... no args, and get 0, like you can do in Scheme or C++. ...
    (comp.lang.c.moderated)