Member Avatar for confusedndazed

Hello people, this is my second attempt to get help for the same code. First post is unsolved. I apologize for any confusion in my posts but I'm confused myself so it's somewhat hard for me to properly explain that which I don't even understand....:$....

I have been given the following information:

/* pseudocode for Binomial
Coefficients */
int binomial(int n, int k)
{
If (n < k) Then return (0)
Else
{
Set denominator = 1*2*...*k
Set numerator = (n-k+1)*(n-k+2)*...*(n-1)*n
return (numerator / denominator)
} // else
End if
}

Here is my code thus far, sorry if it's really bad:

#include <iostream>

using namespace std ;

int binomial(int n, int k) ; // function prototype


int main ()
{
    
    int n, k ; // parameters for the binomial number
    int result ;
    
    cout << endl ;
    
    // read in n & k
    
    cout << "Enter n (positive integer) : " ;
    cin >> n ;
    
    cout << "Enter k (positive integer) : " ;
    cin >> k ;
    
    result = binomial(n,k); 
    
    cout << "Binomial number " << n << "C" << k
         << " = " << result << endl ;
         
    return (0) ;
}

int binomial(int n, int k)

{
    int numerator, denominator ;
    int i ; // needed to compute numerator & denominator
    
    if (n < k) Then
{
    return (0) ; 
}
  else
  {
      denominator = 1*2*...*k ; 
      
      for ( i = k : <= n ; i=i+1)
     denominator = * ;
     numerator = (n-k+1)*(n-k+2)*...*(n-1)*n

     
     return (numerator / denominator) ; 
}

I am very new and lost so please bear with me in your replies, as I still may not "get it".....Thanks!!

  • 4 Contributors
  • 5 Replies
  • 131 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by lotrsimp12345

Dani AI

Generated

There are useful pointers already from , and , but a simple factorial-first implementation will quickly hit overflow and can be harder to get right as a beginner. A compact, safer approach is the multiplicative method: reduce k to the smaller of k and n-k, then build the combination iteratively so you never compute full n! or k!. This runs in O(k) time and uses constant memory.

The key idea (no factorials shown here) is to multiply and divide at each step so intermediate growth is limited. Use a 64-bit result type for moderate inputs and, if available, a larger intermediate type to reduce overflow risk. For truly large n use a big-integer library.

Example C++ function (uses 128-bit intermediate on GCC/Clang; replace with a big-int type for arbitrary precision):

#include <cstdint>

uint64_t binomial(unsigned int n, unsigned int k) {
    if (k > n) return 0;
    if (k > n - k) k = n - k;
    uint64_t result = 1;
    for (unsigned int i = 1; i <= k; ++i) {
        unsigned __int128 tmp = result;
        tmp *= (n - k + i);
        tmp /= i;
        result = static_cast<uint64_t>(tmp);
    }
    return result;
}

Checklist/troubleshooting: validate inputs (nonnegative, k<=n), beware overflow (64-bit tops out around 1.8e19), and avoid recursive factorial for large k. For exact results on large n, use a multiprecision type such as Boost.Multiprecision::cpp_int.

Recommended Answers

All 5 Replies

Member Avatar for mrnutty

>>denominator = 1*2*...*k

I hope you know thats not valid. 1 * 2 * 3 ... k is called the factorial of K

So if K was 5, the the denominator will be 1 * 2 * 3 * 4 * 5.

So make a function : unsigned long factorial(unsigned long num);
Where it returns the factorial of the parameters passed. So if num
was 5, then the call would be : denominator = factorial(5); // = 120

Fix that then post back, because there are other problems.

Member Avatar for Agni

By binomial coefficient you mean finding the combinatorial number, is that right ? So you should be using the formula n!/(n-k)!*k!

for this the pseudocode should be

numerator=1*2*3..*n
fact1 = 1*2*3...*n-k
fact2 = 1*2*3....*k
denominator = fact1 * fact2
binomial coefficient = numerator/denominator

can you code that?

Member Avatar for lotrsimp12345

you probably need a factorial function to find 1*2...*k.

it should probably be recursive

Member Avatar for confusedndazed

>>denominator = 1*2*...*k

I hope you know thats not valid. 1 * 2 * 3 ... k is called the factorial of K

So if K was 5, the the denominator will be 1 * 2 * 3 * 4 * 5.

So make a function : unsigned long factorial(unsigned long num);
Where it returns the factorial of the parameters passed. So if num
was 5, then the call would be : denominator = factorial(5); // = 120

Fix that then post back, because there are other problems.

Thanks but how do I find out what number k is? You used 5 as an example right? I'm really confused about this....

Member Avatar for lotrsimp12345

you pass in k to your function i believe.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.