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: was: "mod operator for signed integers"
    ... unsigned int. ... performed in type 'unsigned int'. ... If the sum were performed in type 'int', ... it should be equal to n-1 ...
    (comp.lang.c)
  • 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: Performance of hand-optimised assembly
    ... Why not use unsigned for sum in the test harness? ... int is better yet because the output will then be same across machines. ... gcc -O3 seems ... but taking an average by eye my best asm version was *slower* than ...
    (comp.lang.c)
  • Re: [PATCH] input: Introduce light-weight contact tracking
    ... seems the patch was damaged somehow. ... static int illegal(int nslot, int npos, unsigned x) ... int i, j, sum; ...
    (Linux-Kernel)