一点一点前进...

0%

欧拉项目 | 第493题 | 彩虹谜题

发表于 分类于 ， Disqus：

题目链接

在一个坛子中有赤橙黄绿青蓝紫七种颜色的球，每种10个，共70个球。从中随机挑选出20个球，求有几种颜色的期望值。

这个题思路很明确，期望等于颜色的种数乘以对应的概率。
直接算不太好算，我们换个等价的形式。
用i j k l m n q七个数字表示每个颜色的球的数量，遍历i j k l m n q每种可能的情况，对于特定的一组值，计算出可能出现的拿法，然后乘以颜色种数，除以C(20,70)，就是对应这组值的期望值。比如3 3 3 3 3 5 0，可能出现的拿法是C(3,10) ^ 5 * C(5,10)，颜色种类是5。
这里，C(20,70)是定值，所以可以提取出来，最后除一次就可以了。

首先，给出求排列组合的函数： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static long GetCombinationsCount(long total,long pickedCount)
{
	long count = 1;

	for (int i = 0; i < pickedCount; i++)
	{
		count *= (total - i);
	}

	for (int i = 0; i < pickedCount; i++)
	{
		count /= (i + 1);
	}

	return count;
}

计算颜色种类的函数： 

1
2
3
4
private static int GetColors(int[] counts)
{
	return counts.Count(i => i != 0);
}

准备工作做完了，我们来遍历i j k l m n q，由于最多20个球，循环的时候可以做一下简单的修剪以提高效率

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
BigInteger count = 0;
for (int i = 0; i < 11; i++)
{
	for (int j = 0; i < 11 && i + j <= 20; j++)
	{
		for (int k = 0; k < 11 && i + j + k <= 20; k++)
		{
			for (int l = 0; l < 11 && i + j + k + l <= 20; l++)
			{
				for (int m = 0; m < 11 && i + j + k + l + m <= 20; m++)
				{
					for (int n = 0; n < 11 && i + j + k + l + m + n <= 20; n++)
					{
						int q = 20 - i - j - k - l - m - n;
						if (q >= 0 && q <= 10)
						{
							int[] counts = new int[] { i, j, k, l, m, n, q };
							long tmp = 1;
							foreach (var c in counts)
							{
								tmp *= Utils.GetCombinationsCount(10, c);
							}

							count += GetColors(counts) * tmp;
						}
					}
				}
			}
		}
	}
}

最后，我们除以C(20,70)

1
2
3
4
5
6
7
8
9
10
11
12
for (int i = 1; i <= 20; i++)
{
	count *= i;
}

double dc = (double)count;
for (int i = 51; i <= 70; i++)
{
	dc /= i;
}

return dc.ToString().Substring(0, 11);

整个算法简洁明了，在我机器上不到500ms就能得到结果。