C ++中的组合数(N选择R) [英] Number of combinations (N choose R) in C++
问题描述
这里我尝试用C ++写一个程序来查找NCR。但我有一个问题的结果。这是不正确的。你能帮我找到程序中的错误吗?
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;
}
推荐答案
它应该是 fact(n)/ fact(r)/ fact(nr)
,但这反过来是一种非常低效的计算方式。
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:
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;
}
如果结果不合适,您可以计算对数和,并获得组合不精确地作为双。或者使用任意精度的整数库。
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.
我将我的解决方案放到另一个,因为ideone.com最近一直在丢失代码片段,而另一个问题仍然关闭到新的答案。
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.
#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";
}
这篇关于C ++中的组合数(N选择R)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!