这里我尝试用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;
}
如果结果不合适，您可以计算对数之和并得到不精确的双精度组合数。或者使用任意精度整数库。
我将我的解决方案放在这里，因为 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:
请参阅 here，了解 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);
}
此代码不使用
+<val尽管如此，这个 n-choose-k 实现具有一个简单的结构，易于遵循。
图例：
legetruncplusmuloneval线
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));
使用
doubleint更新：
你的公式也是错误的。你应该使用
fact(n)/fact(r)/fact(n-r)这是在竞争性编程中解决 nCr 时不要超出时间限制的参考，我发布此内容是因为这会对您有所帮助，因为您已经得到了问题的答案， 获得二项式系数的素因数分解可能是计算它的最有效的方法，特别是在乘法成本昂贵的情况下。这对于计算阶乘的相关问题来说当然是正确的（例如，请参见单击此处）。
这是一个基于埃拉托色尼筛法的简单算法，用于计算素因数分解。这个想法基本上是在使用筛子找到质数时遍历它们，然后计算它们的倍数中有多少落在 [1, k] 和 [n-k+1,n] 范围内。筛子本质上是一个 O(n \log \log n) 算法，但没有进行乘法运算。一旦找到质因数分解，实际所需的乘法次数最坏的是 O\left( rac{n \log \log n}{\log n} 正确）并且可能有比这更快的方法。
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
这里错误地使用了递归函数。
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.
};
递归调用应该在
elseNCR()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;
}
尝试删除事实函数后面的分号。