不用递归编写函数计算从m选n的组合数？

Question

不能用递归函数啊

Answer 1

不用递归就用循环。从m选n的组合数为((m-n+1)/1)((m-n+2)/2)...(m/n)，可以保存p，每次都让p乘(m-n+i)/i，i从1循环到n就得到了结果。注意((m-n+1)/1)...((m-n+i)/i)是从m-n+i选i的组合数，是一个整数，因此我们只需要用整形变量存储p，且得到的是精确值。

以下是样例C++程序：

unsigned comb(unsigned m, unsigned n)
{
unsigned p = 1;
for (unsigned i = 1, j = m - n + 1; i <= n; ++i, ++j) {
p *= j;
p /= i;
}
return p;
}

Answer 2

有人为你做好了，这是我搜集的一个不错的组合算法，需要了解算法可以参考：

#ifndef __btb_combination_hpp_def
#define __btb_combination_hpp_def

#include <algorithm>

namespace btb
{
////////////////////////////////////////////////////////////////////
// combination for STL permutation
//
// init_combination (first, middle, last)
// adjust_combination (first, middle, last)
// combination (first1, last1, first2, last2)
// next_combination (first, middle, last)
// prev_combination (first, middle, last)
////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////
// separate_merge: merge [first1, last1) and [first2, last2), then fill
// the min element to [first1, last1), left to [first2,
// last2)
////////////////////////////////////////////////////////////////////
template <typename Iter>
void
separate_merge (Iter first1, Iter last1, Iter first2, Iter last2)
{
typedef typename std::iterator_traits<Iter>::value_type value_type;
typedef typename std::iterator_traits<Iter>::difference_type diff_t;

if ((first1 == last1) || (first2 == last2))
return;
first1 = std::upper_bound(first1, last1, *first2);
if (first1 == last1)
return;
last2 = std::lower_bound(first2, last2, *(last1-1));
if (first2 == last2)
return;

diff_t len1 = std::distance(first1, last1);
diff_t len2 = std::distance(first2, last2);
bool min1 = len1 < len2;
diff_t lent = min1 ? len1 : len2;
value_type *tmp = new value_type[lent];

if (min1)
{
std::copy(first1, last1, tmp);
Iter p = first2;
value_type* q = tmp;
Iter i;
for (i = first1; i != last1; ++i)
if (*p < *q)
*i = *p++;
else
*i = *q++;
for (i = first2; (i != last2) && (p != last2); ++i)
if (*p < *q)
*i = *p++;
else
*i = *q++;
for (; i != last2; ++i, ++q)
*i = *q;
}
else
{
std::copy(first2, last2, tmp);
Iter p = last1;
value_type* q = tmp+lent;
Iter i;
for (Iter i = last2; i != first2;)
if (*(p-1) < *(q-1))
*--i = *--q;
else
*--i = *--p;
for (i = last1; (i != first1) && (p != first1);)
if (*(p-1) < *(q-1))
*--i = *--q;
else
*--i = *--p;
for (; i != first1;)
*--i = *--q;
}

delete[] tmp;
}

///////////////////////////////////////////////////////////////////
// __combination_sort: merge sort the [first, last)
///////////////////////////////////////////////////////////////////
template <typename Iter>
void
__combination_sort (Iter first, Iter last)
{
typedef typename std::iterator_traits<Iter>::difference_type diff_t;
diff_t len = std::distance(first, last);
if (len <= 1)
return;

if (len == 2)
{
if (*first > *--last)
std::iter_swap (first, last);
}
else
{
Iter middle = first;
std::advance(middle, len / 2);
__combination_sort (first, middle);
__combination_sort (middle, last);
separate_merge (first, middle, middle, last);
}
}

//////////////////////////////////////////////////////////////////////
// init_combination: init the (first, midle, last) to the min or the
// max combination
//////////////////////////////////////////////////////////////////////
template <typename Iter>
void
init_combination (Iter first, Iter middle, Iter last, bool min = true)
{
__combination_sort (first, middle);
__combination_sort (middle, last);
if (min)
separate_merge (first, middle, middle, last);
else
separate_merge (middle, last, first, middle);
}

//////////////////////////////////////////////////////////////////////
// adjust_combination: make the (first, middle, last) to a right
// combination. [first, middle) are the elements
// selected in, [middle, last) are selected out
//////////////////////////////////////////////////////////////////////
template <typename Iter>
void
adjust_combination (Iter first, Iter middle, Iter last)
{
__combination_sort (first, middle);
__combination_sort (middle, last);
}

/////////////////////////////////////////////////////////////////////
// combination: get next combination.
//
// [first1, last1): the elements selected in \\
// [first2, last2): the elements selected out
/////////////////////////////////////////////////////////////////////
template <typename Iter>
bool
combination (Iter first1, Iter last1, Iter first2, Iter last2)
{
if ((first1 == last1) || (first2 == last2))
return false;

Iter qmax = last2;
--qmax;
Iter pout1 = std::lower_bound(first1, last1, *qmax);
bool fin = pout1 == first1;
Iter left1, left2;
if (!fin)
{
Iter pout = pout1;
--pout;
Iter qin = std::upper_bound(first2, last2, *pout);
std::iter_swap (pout, qin);
left1 = pout;
++left1;
left2 = qin;
++left2;
}
else
{
left1 = first1;
left2 = first2;
}
separate_merge (left1, last1, left2, last2);
return !fin;
}

/////////////////////////////////////////////////////////////////////
// next_combination: get next combination.
//
// [first, middle): the elements selected in \\
// [middle, last): the elements selected out
/////////////////////////////////////////////////////////////////////
template <typename Iter>
inline bool
next_combination (Iter first, Iter middle, Iter last)
{
return combination (first, middle, middle, last);
}

/////////////////////////////////////////////////////////////////////
// prev_combination: get prev combination.
//
// [first, middle): the elements selected in \\
// [middle, last): the elements selected out
/////////////////////////////////////////////////////////////////////
template <typename Iter>
inline bool
prev_combination (Iter first, Iter middle, Iter last)
{
return combination (middle, last, first, middle);
}
}

#endif

// 上面是库文件，下面是个测试：

#include <iostream>
#include <iterator>
using namespace std;

int main()
{

int a[] = {1, 2, 3, 4, 5};
int iSize = sizeof(a)/sizeof(a[0]);
int* piBeg = a;
int* piMid = a + iSize / 2 - (iSize & 1 ? 0 : 1);
int* piEnd = a + iSize;
// C(3, 5);
int iSelect = 3;

// 如果数组是无序的首先要初始化，第一，三个参数分是数组的首地址和超尾地址
// 第二个参数是数组中间一个元素的地址
// 该地址应该为:
// addr = a + n/2 (n = 2*x+1, x = {1,2,3,...})
// addr = a + n/2-1 (n = 2*x, x = {1,2,3,...})
btb::init_combination(piBeg, piMid, piEnd);

do
{
copy(piBeg, piBeg + iSelect, ostream_iterator<int>(cout, " "));
cout << endl;
}while(btb::next_combination(piBeg, piBeg + iSelect, piEnd));
}

Answer 3

//例：从5个数11 13 15 17 19中选3个数的方法 vc编写
#include<iostream>
using namespace std;
int main()
{
int a[5]={11,13,15,17,19};
int i,j,k,l,m,n=0;
for(i=0;i<=1;i++)
for(j=0;j<=1;j++)
for(k=0;k<=1;k++)
for(l=0;l<=1;l++)
for(m=0;m<=1;m++)
if(i+j+k+l+m==3)
{
if(i==1) cout<<" "<<a[0]<<" ";
if(j==1) cout<<" "<<a[1]<<" ";
if(k==1) cout<<" "<<a[2]<<" ";
if(l==1) cout<<" "<<a[3]<<" ";
if(m==1) cout<<" "<<a[4]<<" ";
n++;
cout<<endl;
}
cout<<"共有"<<n<<"种选法"<<endl;
return 0;
}

Answer 4

什么意思，就是计算Cmn么？是的话，循环可以搞定了