Here I try to write a program in C++ to find NCR. But I've got a problem in the result. It is not correct. Can you help me find what the mistake is in the program?
#include <iostream>
using namespace std;
int fact(int n){
if(n==0) return 1;
if (n>0) return n*fact(n-1);
};
int NCR(int n,int r){
if(n==r) return 1;
if (r==0&&n!=0) return 1;
else return (n*fact(n-1))/fact(n-1)*fact(n-r);
};
int main(){
int n; //cout<<"Enter A Digit for n";
cin>>n;
int r;
//cout<<"Enter A Digit for r";
cin>>r;
int result=NCR(n,r);
cout<<result;
return 0;
}
A nice way to implement n-choose-k is to base it not on factorial, but on a "rising product" function which is closely related to the factorial.
The rising_product(m, n) multiplies together m * (m + 1) * (m + 2) * ... * n, with rules for handling various corner cases, like n >= m, or n <= 1:
See here for an implementation nCk as well as nPk as a intrinsic functions in an interpreted programming language written in C:
This code doesn't use operators like
+
and<
because it is type generic (the typeval
represents a value of any kinds, such as various kinds of numbers including "bignum" integers) and because it is written in C (no overloading), and because it is the basis for a Lisp-like language that doesn't have infix syntax.In spite of that, this n-choose-k implementation has a simple structure that is easy to follow.
Legend:
le
: less than or equal;ge
: greater than or equal;trunc
: truncating division;plus
: addition,mul
: multiplication,one
: aval
typed constant for the number one.the line
should be
or even
Use
double
instead ofint
.UPDATE:
Your formula is also wrong. You should use
fact(n)/fact(r)/fact(n-r)
this is for reference to not to get time limit exceeded while solving nCr in competitive programming,i am posting this as it will be helpful to u as you already got answer for ur question, Getting the prime factorization of the binomial coefficient is probably the most efficient way to calculate it, especially if multiplication is expensive. This is certainly true of the related problem of calculating factorial (see Click here for example).
Here is a simple algorithm based on the Sieve of Eratosthenes that calculates the prime factorization. The idea is basically to go through the primes as you find them using the sieve, but then also to calculate how many of their multiples fall in the ranges [1, k] and [n-k+1,n]. The Sieve is essentially an O(n \log \log n) algorithm, but there is no multiplication done. The actual number of multiplications necessary once the prime factorization is found is at worst O\left(\frac{n \log \log n}{\log n}\right) and there are probably faster ways than that.
Your formula is totally wrong, it's supposed to be
fact(n)/fact(r)/fact(n-r)
, but that is in turn a very inefficient way to compute it.See Fast computation of multi-category number of combinations and especially my comments on that question. (Oh, and please reopen that question also so I can answer it properly)
The single-split case is actually very easy to handle:
Demo: http://ideone.com/aDJXNO
If the result doesn't fit, you can calculate the sum of logarithms and get the number of combinations inexactly as a double. Or use an arbitrary-precision integer library.
I'm putting my solution to the other, closely related question here, because ideone.com has been losing code snippets lately, and the other question is still closed to new answers.
Recursive function is used incorrectly here.
fact()
function should be changed into this:};
Recursive call should be made in
else
part.NCR()
function should be changed into this: