在dota的100多个英雄中，技能最多的无疑是召唤师，英文叫carl。
召唤师有冰，雷，火三种球可以选择，选择不同的球就可以组合出不同的技能。把这个问题抽象一下，就是
有A种球3个，B种球3个，C种球3个，从这9个球中选出3个，问有多少种取法。同一类中的球不做区分，有如下10种：
AAA
AAB
AAC
ABB
ABC
ACC
BBB
BBC
BCC
CCC
这个序列明显是规律的。可以使用回溯的方式生成。代码如下：
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int* bit = new int[n+1];
for (int i = 0; i <= n; i++)
{
bit[i] = 0;
}
int cur = 0;
int sum = 0;
while (1)
{
bit[cur]++;
if (cur)
{
if (bit[cur] <= n && n - 1 == cur)
{
sum++;
cout << bit[0] << " " << bit[1] << " " << bit[2] << endl;
}
if (bit[cur] > n || n == cur)
{
cur--;
}
else
{
cur++;
bit[cur] = bit[cur-1] - 1;
}
}
else
{
if (bit[cur] > n)
{
break;
}
else
{
cur++;
bit[cur] = bit[cur-1] - 1;
}
}
}
cout << sum << endl;
}
当然了，对于回溯来说，时间复杂度是很高的，输入为n时，时间复杂度为O(nn)。当n特别大时，这种方式显然效率太低。
有没有可能从数学的角度来求解这个问题呢…似乎可以用排列组合的方式来完成。
首先把这个问题抽象成如下问题。
有N种球，每种各N个，从这N*N个球中取出N个，问有多少种取法。
或者，有N种球，每种球正无限个，从中取出N个，问有多少种方式。乍看下去，可能这个问题有些复杂，可以把这个问题进行一次拆分。
从N种球中取…如果只有1种球，从中取出N个，那么只有1中方法。
从2种球中取，为了和上一种情况区分开，我们保证2种球中每一种至少取了1个，如果能算出这个值，那么总的种数如下：
？中的表达式未知。
问题转换为怎么从2至n种球中取出n个，且每种球至少取一个。
可以把这个问题继续转换一下。
2种球的时候，第1种取a个（0<a<n），第2种取n-a个。这个时候，问题转换成了把n个相同的球放入2个不同的筒中，且每个筒不为空。这两个问题的解是一一对应的，因为我们可以把1号筒中的球当成第1种球，2号筒中的球作为第2种球，反之依然，第1种球中取出的放在第一个筒中，第2种球中取出的放入第二个筒中……
现在需要解决怎样把n个球放入2至n个筒中，且每个筒不空。
我们还是以2个筒来示例，似乎可以这样：
首先取出两个球，分别放入两个筒中，这样保证了2个筒一定不空，剩下的n-2个球，每一个球有2种选择，所以最后的答案是2n-2，对吗？
考虑这种情况，第3个球放入1号筒，第4个球放入2号筒；这种情况和，第3个球放入2号筒，第4个球放入1号筒。它们重复了…….因此这种方式不对。
这样考虑，把n个球排成一行，那么一共有n-1个空位，在这n-1个空位中插入一个分隔符，就把n种球分成了2类……3个筒时插入2个分隔符……….
最后得到这个式子：
为把n个球放入i个筒中，且每个筒不空。
所以最后的结果为：
感谢天骄师兄一起讨论的半个上午……
（原文章时间2012-2-24）
网友评论