Problem with nCr - Pascals Triangle

This is a discussion on Problem with nCr - Pascals Triangle within the C Programming forums, part of the General Programming Boards category; I just made a small prog to work out probabilities. Originally I had an array containing elements of pascals triangle, ...

  1. #1
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218

    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.

  2. #2
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Nevermind I managed to fix it. It was stupidly simple; I just had to remove the -1 >_<

  3. #3
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    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.

  4. #4
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    In nCr(), if b * c overflows you might have issues.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  6. #6
    uint64_t...think positive xuftugulus's Avatar
    Join Date
    Feb 2008
    Location
    Pacem
    Posts
    355
    But there could be a way to compute nCr without going to floating point simply by taking advantage of the divisions and performing less multiplications. However even with such an approach, overflow would not be far...
    My thinking: nCr(15,4) = 15!/4!*11! = (12*13*14*15)/(1*2*3*4) which can be computed in an int no?
    Code:
    ...
        goto johny_walker_red_label;
    johny_walker_blue_label: exit(-149$);
    johny_walker_red_label : exit( -22$);
    A typical example of ...cheap programming practices.

  7. #7
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Thanks guys, using long long fixed the problem.

    Theres just one more issue. If I enter 30 events all probabilities wind up being 0 (with some as -0 for some reason). Would this be due to limitations with doubles, long long, or is there something else I am doing wrong?

    Cheers.

    Edit: yeah I guess I'm going to need a big num library if i want to do this sort of stuff. Guess I'll just cap the maximum number of events for now.
    Last edited by mike_g; 03-11-2008 at 05:35 PM.

  8. #8
    uint64_t...think positive xuftugulus's Avatar
    Join Date
    Feb 2008
    Location
    Pacem
    Posts
    355
    Stop using built in types! Get a BigInteger library and factorialize your program to infinity.
    Code:
    ...
        goto johny_walker_red_label;
    johny_walker_blue_label: exit(-149$);
    johny_walker_red_label : exit( -22$);
    A typical example of ...cheap programming practices.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. pas triangle problem...
    By limitmaster in forum C++ Programming
    Replies: 6
    Last Post: 08-21-2006, 05:22 AM
  2. Laptop Problem
    By Boomba in forum Tech Board
    Replies: 1
    Last Post: 03-07-2006, 06:24 PM
  3. Replies: 5
    Last Post: 11-07-2005, 11:34 PM
  4. loop problem
    By rhymewithnothin in forum C Programming
    Replies: 16
    Last Post: 09-24-2005, 02:06 PM
  5. half ADT (nested struct) problem...
    By CyC|OpS in forum C Programming
    Replies: 1
    Last Post: 10-26-2002, 09:37 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21