一点一点前进...

0%

欧拉项目 | 第205题 | 骰子游戏

发表于 分类于 ， Disqus：

原题链接
Peter有九个4个面的骰子，类似于金字塔的样子，每个面上标有数字，分别是1-4。
Colin有六个6个面的骰子，就是正常的骰子了，每个面上标有数字，分别是1-6。
现在他俩比赛，各投掷一次，点数之和比较大的胜。点数之和一样的话算作平局。
问题是，Peter胜利的概率是多少？要求答案是0.abcdefg这种形式。也就是小数点后面有七位数字。

看到题目的想法是，不要用double类型，可能会有精度误差，以至于最后的答案不正确。
那就只考虑分子好了，因为分母就是4的9次方，6的6次方，最后得到答案的前一步除一下就好。

首先计算Peter扔出的点数之和的概率分布。我使用一个字符串表示Peter掷出的结果，字符串长度为九，每一个字符只能是1-4这四个数字。下面是一段递归代码，得到了所有可能的结果： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private static List<string> PeterResults = new List<string>();
private static void GenPeterResults(string num, int nth)
{
    for (int i = 1; i <= 4; i++)
    {
        if (nth == 8)
        {
            PeterResults.Add(num + i);
        }
        else
        {
            GenPeterResults(num + i, nth + 1);
        }
    }
}

运气不错，数组的长度是4的9次方。看样子代码写对了。
接着构造一个数组，用于存放每种点数之和出现的次数。该次数除以4的9次方就是概率，但是正如前面所说的，我只考虑分子。 

1
2
3
4
5
foreach (var s in PeterResults)
{
    int[] digits = s.Select(c => int.Parse(c.ToString())).ToArray();
    Peter[digits.Sum()]++;
}

下面计算Colin扔出的结果的概率分布。其实，上述算法肯定是有效的。不过，考虑Colin只有6个骰子，用int值表示，111111-666666也不过50万种组合，换个更暴力的算法。 

1
2
3
4
5
6
7
8
for (int i = 111111; i <= 666666; i++)
{
    int[] digits = i.ToString().Select(c => int.Parse(c.ToString())).ToArray();
    if (digits.Where(digit => digit == 0 || digit > 6).Count() == 0)
    {
        Colin[digits.Sum()]++;
    }
}

如果出现了数字0或者比6大的数字，那么是不符合题目要求的，扔掉即可。

好了两个概率分布都有了，开始比赛吧。如果Peter的点数比Colin大，计算下概率，最后加起来就好了。 

1
2
3
4
5
6
7
8
9
10
11
long numerator = 0;
for (int p = 0; p < Peter.Length; p++)
{
    for (int c = 0; c < Colin.Length; c++)
    {
        if (p > c)
        {
            numerator += Peter[p] * Colin[c];
        }
    }
}

其实p和c从1开始就可以了，但是不会对正确性和性能有什么影响，而且看起来更优美。
现在，分母是4的9次方乘以6的6次方。那么用分子除以分母，保留7位小数就是答案了。 

1
return ((double)numerator / 262144 / 46656).ToString("F7");