分三部分：一、问题由来；二、个人分析；三、数学问题。如果您直接奔着解决数学问题来的，可以直接跳到第三部分。但为了更好的理解，建议都看一遍，或许有其他更好的解题思路。 一、问题由来
昨晚群里一网友发表一组合问题，一开始以为他要从1~160正整数中取9个出来，这样的组合有多少种。他一问有这么多组合吗？重新看了一遍问题，又以为是把1~160分成9组，这样的组合有多少种。 (⊙﹏⊙)b 后跟他交流后才明白他的意思。
用通俗一点的语言重新表达下问题：从1~160正整数中取9个数（数值可一样），分别给9个人，使9个人的数值总和为160。请问这样的组合有多少个？ 二、个人分析 第一反应，数据那么大，，肯定是写个程序去处理。 首先排除153以上的数字，使用遍历法，把1~152从小到大依次给前8个人。如果前8个人的数值总和sum小于160，第9个人的数值肯定是160-sum，这样的组合便为一种组合。 在写程序的时候，使用的是递归算法。为了加快处理，每个人提取数字时的循环遍历最大值imax做了一个限制。因为每个人都会提取一个数字，最小值为1，所以第x个人的imax值等于160减去前x-1个数值总和，再减去后面剩余人的个数，即imax = 160 – sum(x-1) – (9 – x)。这样就不用再去遍历总和超过160的数字了（可以看出，这些组合数比我们要算的大的多）。下面是用的C语言写的，下标是从0开始。
#include <stdio.h>#include <stdlib.h>#define MAX_VALUE 160#define MAX_GROUP 9double count = 0;int a[MAX_GROUP];void ResultDisplay(){int i;printf("%12.0f: ", count);for(i=0;i<MAX_GROUP;i++)printf("%3d ",a[i]);printf("\n");}int Combination(int sum, int n){int i=1;if( sum>=MAX_VALUE)return -1;if(n == MAX_GROUP – 1){a[n] = MAX_VALUE – sum;count++;ResultDisplay();return 0;}for(i=1; i<=MAX_VALUE – sum – (MAX_GROUP – 1 – n);i++){a[n] = i;Combination(sum+i, n+1);}}int main(int argc, char **argv) {Combination(0,0);system("pause");return (0);} 用我的本本运行了一分钟，结果如下：
组合数已达到3万多，但前5个人还是1。这里打印耗了很多时间，如果去掉打印，结果会快N倍。去掉后运行过半小时（运行起来后，本本的风扇一直处于高速转动的状态，担心古董受不鸟，所以运行几分就暂停一小会），通过监视看到组合数达到300多亿，但第1个人的数还是1，第2个人的数字也没超过2（忘了截图，印象中还是1）。看到这样真正的天文数字，没敢再继续运行下去了，但由此推断出组合数肯定超1000亿。 PS：昨晚在群里回复说组合数肯定超1000亿。一位群管理员表现出一副很不屑和被我忽悠的样子（“1000亿？别瞎我，我输读的少”）。一向认为群管理的话会比较稳重，再说这是一个技术群。你可以怀疑我说的，我们可以一起讨论验证，但你说这样讽刺和挑衅的话，对于我来说，最好的反驳就是拿出证据放群里给他看。在打印处加了个条件中断，从99999999990（差10就1000亿）开始打印。运行了近两个小时的时间，结果终于出来了，当时已经晚上1点了，立马编辑好文字，给他回复了过去。
1000亿，第1个人还是1，零头可能都还没达到呢。。。 以上为插曲，回归正题。此数学问题提出的时候，最长运行时间仅半小时，即300多亿。当时就想有没有一个公式，能直接用公式把组合数算出来。为了直观点，就在Excel里做了几个简单点的组合，看能否找到规律和思路。如：5分为2，5分为3，5分为4，8分为4。
一开始从后面开始找规律，最后一个不用看，就看最后两个，发现如果前面所有的数之和固定，那最后两个数的和也是固定的（这是废话），那组合数为最后两个数之和，再减1。这应该很好理解，假设最后两个数之和为y，那组合分别为(1, y-1), (2, y-2), … , (y-1,1)，共y-1个。再倒数第三位数在递增的时候，y在递减。看上去很有规律，但仔细去找的时候却发现都是一些等差数列的叠加啊。 换个方向吧，从前面开始找找看。如上图，8分为4中，把第1人给不同数时的组合数给列出来了。把它的公式写出来后，发现仅适合8分为4这个组合方式，其他的都算不出正确答案。 这时，想到高中时统计学的统计方法（好像是统计学吧？），就是找到第n个与n-1个的关系。
【以为文本内容含很多博客编辑器无法显示的公式，都将使用图片】
去看日出，去散步，去欣赏大自然，
