C ++中的组合数（N选择R）

本文介绍了C ++中的组合数（N选择R）的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

这里我尝试用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; }

演示： ideone/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.

我将我的解决方案放到另一个，因为ideone最近一直在丢失代码片段，而另一个问题仍然关闭到新的答案。

I'm putting my solution to the other, closely related question here, because ideone 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"; }