Thread: Problem with nCr - Pascals Triangle

I just made a small prog to work out probabilities. Originally I had an array containing elements of pascals triangle, used by the prog. Since it was quite limited i switched to using the nCr formula I found here: http://ptri1.tripod.com/

I tested the nCr function and it worked as expected, but for some reason when I added it to my prog it suddenly mangles the output. Heres my code:

Code:

#include <stdio.h>
#include <ctype.h>
void probability();
double power(double num, int exp);
int factoral(int n);
int nCr(int n, int r);
int again();

int main()
{
    do
        probability();
    while(again());
    return 0;       
}   
 
void probability()
{
     const static char tri[5][6] = 
     {
            {1, 1, 0, 0, 0, 0},
            {1, 2, 1, 0, 0, 0}, 
            {1, 3, 3, 1, 0, 0},
            {1, 4, 6, 4, 1, 0},
            {1, 5,10,10, 5, 1}
     };
            
     int n=0, i;
     double p=-1, q;
     
     printf("Enter a number of events: ");
     while(n < 1 || n > 5) scanf("&#37;i", &n);     
     printf("Enter the probability each events success: ");
     while(p<0.0 || p>1.0) scanf("%lf", &p);
     
     q = 1.0 - p;
     
     double p1, q1, r;
     for(i=0; i<=n; i++)
     {
         p1 = power(p, n-i);
         q1 = power(q, i);
         r =  p1*q1*nCr(n-1, i);   //THIS DOES NOT WORK
         //r = tri[n-1][i]*p1*q1;  //BUT THIS DOES
         printf("%lf\t%i/%i\n", r, n-i, n);       
     }          
}
double power(double num, int exp)
{
    if(! exp) return 1.0;  
    int i; 
    double result = num;
    for(i=1; i<exp; i++)
        result *= num;
    return result;       
}  

int factoral(int n)
{
    int i, f=1;
    for(i=2; i<=n; i++) f*=i;
    return f;
}

int nCr(int n, int r)
{
    //     n!
    // ___________
    //  r! (n-r)!
    int a = factoral(n);
    int b = factoral(r);
    int c = factoral(n-r);
    return a / (b * c);
}

int again()
{
    char ch = '\0';
    while(ch != 'y' && ch != 'n')
    {
        while((ch=getchar())!='\n');
        printf("Run again? (Y/N)");
        ch = getchar();
        ch = tolower(ch);
    }
    return(ch == 'y')? 1: 0;
}

Can anyone tell me why it dosent work?

Thanks.

Nevermind I managed to fix it. It was stupidly simple; I just had to remove the -1 >_<

Ok I have a different problem now that I cant work out. Since its related to the same prog I figured I'd add it here.

Basically, the progam works but does weird things if you enter lots of events.

On 15 or more events some probabilities become negative, which should not be possible. I got no idea why this would be happening unless it was due to floating point innaccuracy or overflow, but I'm using doubles.

Also if 50 or more events are entered the whole program crashes for me. Heres the code again. You should be able to see what I mean if you test it:

Code:

#include <stdio.h>
#include <ctype.h>
void probability();
double power(double num, int exp);
int factoral(int n);
int nCr(int n, int r);
int again();

int main()
{
    do
        probability();
    while(again());
    return 0;       
}   
 
void probability()
{
     int n=0, i;
     double p=-1, q, p1, q1, result;
     
     printf("Enter a number of events: ");
     while(n < 1 || n >99) scanf("%i", &n);     
     printf("Enter the probability each events success: ");
     while(p<0.0 || p>1.0) scanf("%lf", &p);
     
     q = 1.0 - p;     

     for(i=0; i<=n; i++)
     {
         p1 = power(p, n-i);
         q1 = power(q, i);
         result =  p1*q1*(double)nCr(n, i);  
         printf("%lf\t%i/%i\n", result, n-i, n);       
     }          
}

double power(double num, int exp)
{
    if(! exp) return 1.0;  
    int i; 
    double result = num;
    for(i=1; i<exp; i++)
        result *= num;
    return result;       
}  

int factoral(int n)
{
    int i, f=1;
    for(i=2; i<=n; i++) f*=i;
    return f;
}

int nCr(int n, int r)
{
    //     n!
    // ___________
    //  r! (n-r)!
    int a = factoral(n);
    int b = factoral(r);
    int c = factoral(n-r);
    return a / (b * c);
}

int again()
{
    char ch = '\0';
    while(ch != 'y' && ch != 'n')
    {
        while((ch=getchar())!='\n');
        printf("Run again? (Y/N)");
        ch = getchar();
        ch = tolower(ch);
    }
    return(ch == 'y')? 1: 0;
}

How can i tell where the problem is?

Cheers.

I don't see any basis for your claim that you're using doubles, since factoral and nCr are all integer functions. And 15! is 1.3 x 10^12, which requires about 40 bits to store, so integer overflow should happen in that neck of the woods.