在这里，我尝试用 C++ 编写一个程序来查找 NCR。但是我的结果有问题。这是不正确的。你能帮我找出程序中的错误吗？
#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;
}
您的公式完全错误，应该是fact(n)/fact(r)/fact(n-r)，但这反过来又是一种非常低效的计算方式。
请参阅快速计算多类别组合数，尤其是我对该问题的评论。（哦，请重新打开该问题，以便我可以正确回答）
单拆分的情况其实很容易处理：
unsigned nChoosek( unsigned n, unsigned k )
{
if (k > n) return 0;
if (k * 2 > n) k = n-k;
if (k == 0) return 1;
int result = n;
for( int i = 2; i <= k; ++i ) {
result *= (n-i+1);
result /= i;
}
return result;
}
演示：http: //ideone.com/aDJXNO
如果结果不合适，您可以计算对数之和，并将组合数不精确地作为双精度数。或者使用任意精度整数库。
我在这里将我的解决方案放在另一个密切相关的问题上，因为 ideone.com 最近一直在丢失代码片段，而另一个问题仍然没有新的答案。
#include <utility>
#include <vector>
std::vector< std::pair<int, int> > factor_table;
void fill_sieve( int n )
{
factor_table.resize(n+1);
for( int i = 1; i <= n; ++i )
factor_table[i] = std::pair<int, int>(i, 1);
for( int j = 2, j2 = 4; j2 <= n; (j2 += j), (j2 += ++j) ) {
if (factor_table[j].second == 1) {
int i = j;
int ij = j2;
while (ij <= n) {
factor_table[ij] = std::pair<int, int>(j, i);
++i;
ij += j;
}
}
}
}
std::vector<unsigned> powers;
template<int dir>
void factor( int num )
{
while (num != 1) {
powers[factor_table[num].first] += dir;
num = factor_table[num].second;
}
}
template<unsigned N>
void calc_combinations(unsigned (&bin_sizes)[N])
{
using std::swap;
powers.resize(0);
if (N < 2) return;
unsigned& largest = bin_sizes[0];
size_t sum = largest;
for( int bin = 1; bin < N; ++bin ) {
unsigned& this_bin = bin_sizes[bin];
sum += this_bin;
if (this_bin > largest) swap(this_bin, largest);
}
fill_sieve(sum);
powers.resize(sum+1);
for( unsigned i = largest + 1; i <= sum; ++i ) factor<+1>(i);
for( unsigned bin = 1; bin < N; ++bin )
for( unsigned j = 2; j <= bin_sizes[bin]; ++j ) factor<-1>(j);
}
#include <iostream>
#include <cmath>
int main(void)
{
unsigned bin_sizes[] = { 8, 1, 18, 19, 10, 10, 7, 18, 7, 2, 16, 8, 5, 8, 2, 3, 19, 19, 12, 1, 5, 7, 16, 0, 1, 3, 13, 15, 13, 9, 11, 6, 15, 4, 14, 4, 7, 13, 16, 2, 19, 16, 10, 9, 9, 6, 10, 10, 16, 16 };
calc_combinations(bin_sizes);
char* sep = "";
for( unsigned i = 0; i < powers.size(); ++i ) {
if (powers[i]) {
std::cout << sep << i;
sep = " * ";
if (powers[i] > 1)
std::cout << "**" << powers[i];
}
}
std::cout << "\n\n";
}
N 选择 R 的定义是计算两个乘积，然后除以另一个，
(N * N-1 * N-2 * ... * N-R+1) / (1 * 2 * 3 * ... * R)
但是，乘法可能会很快变得太大并溢出现有数据类型。实现技巧是将乘法和除法重新排序为，
(N)/1 * (N-1)/2 * (N-2)/3 * ... * (N-R+1)/R
保证在每一步结果都是可整除的（对于 n 个连续数字，其中一个必须能被 n 整除，这些数字的乘积也是如此）。
例如，对于 N 选择 3，N、N-1、N-2 中的至少一个将是 3 的倍数，对于 N 选择 4，N、N-1、N-2、N 中的至少一个-3 将是 4 的倍数。
下面给出的 C++ 代码。
int NCR(int n, int r)
{
if (r == 0) return 1;
/*
Extra computation saving for large R,
using property:
N choose R = N choose (N-R)
*/
if (r > n / 2) return NCR(n, n - r);
long res = 1;
for (int k = 1; k <= r; ++k)
{
res *= n - k + 1;
res /= k;
}
return res;
}
实现 n-choose-k 的一个好方法不是基于阶乘，而是基于与阶乘密切相关的“上升积”函数。
rising_product(m, n) 将 m * (m + 1) * (m + 2) * ... * n 与处理各种极端情况的规则相乘，例如 n >= m 或 n <= 1：
请参阅此处以实现 nCk 以及 nPk 作为用 C 编写的解释性编程语言中的内在函数：
static val rising_product(val m, val n)
{
val acc;
if (lt(n, one))
return one;
if (ge(m, n))
return one;
if (lt(m, one))
m = one;
acc = m;
m = plus(m, one);
while (le(m, n)) {
acc = mul(acc, m);
m = plus(m, one);
}
return acc;
}
val n_choose_k(val n, val k)
{
val top = rising_product(plus(minus(n, k), one), n);
val bottom = rising_product(one, k);
return trunc(top, bottom);
}
val n_perm_k(val n, val k)
{
return rising_product(plus(minus(n, k), one), n);
}
这段代码没有使用像+and这样的运算符，<因为它是泛型类型（该类型val表示任何类型的值，例如各种数字，包括“bignum”整数），并且因为它是用 C 编写的（没有重载），并且因为它是没有中缀语法的类 Lisp 语言的基础。
尽管如此，这个 n-choose-k 实现具有易于遵循的简单结构。
图例：：le小于或等于；ge: 大于或等于；trunc: 截断除法；plus: 加法, mul: 乘法, one:val数字一的类型常量。
使用double而不是int.
更新：
你的公式也是错误的。你应该使用fact(n)/fact(r)/fact(n-r)
线
else return (n*fact(n-1))/fact(n-1)*fact(n-r);
应该
else return (n*fact(n-1))/(fact(r)*fact(n-r));
甚至
else return fact(n)/(fact(r)*fact(n-r));
递归函数在这里用错了。fact()功能应改为：
int fact(int n){
if(n==0||n==1) //factorial of both 0 and 1 is 1. Base case.
{
return 1;
}else
return (n*fact(n-1));//recursive call.
};
应else部分进行递归调用。
NCR()功能应改为：
int NCR(int n,int r){
if(n==r) {
return 1;
} else if (r==0&&n!=0) {
return 1;
} else if(r==1)
{
return n;
}
else
{
return fact(n)/(fact(r)*fact(n-r));
}
};
// CPP program To calculate The Value Of nCr
#include <bits/stdc++.h>
using namespace std;
int fact(int n);
int nCr(int n, int r)
{
return fact(n) / (fact(r) * fact(n - r));
}
// Returns factorial of n
int fact(int n)
{
int res = 1;
for (int i = 2; i <= n; i++)
res = res * i;
return res;
}
// Driver code
int main()
{
int n = 5, r = 3;
cout << nCr(n, r);
return 0;
}
这是为了参考在竞争性编程中解决 nCr 时不超过时间限制，我发布这个是因为它对你有帮助，因为你已经得到了你的问题的答案，获得二项式系数的素数分解可能是最计算它的有效方法，尤其是在乘法成本高昂的情况下。这对于计算阶乘的相关问题当然是正确的（例如，请参见单击此处）。
这是一个基于埃拉托色尼筛法的简单算法，用于计算素数分解。这个想法基本上是在使用筛子找到素数时遍历它们，然后还要计算它们有多少倍数落在 [1, k] 和 [n-k+1,n] 范围内。Sieve 本质上是一个 O(n \log \log n) 算法，但没有进行乘法运算。一旦找到素数分解，实际所需的乘法次数最多为 O\left(\frac{n \log \log n}{\log n}\right)，并且可能有比这更快的方法。
prime_factors = []
n = 20
k = 10
composite = [True] * 2 + [False] * n
for p in xrange(n + 1):
if composite[p]:
continue
q = p
m = 1
total_prime_power = 0
prime_power = [0] * (n + 1)
while True:
prime_power[q] = prime_power[m] + 1
r = q
if q <= k:
total_prime_power -= prime_power[q]
if q > n - k:
total_prime_power += prime_power[q]
m += 1
q += p
if q > n:
break
composite[q] = True
prime_factors.append([p, total_prime_power])
print prime_factors