面试题60：n个骰子的点数

从等可能样本空间出发，忠实还原递归枚举与两张数组交替累计两种解法，并用分布不变量验证结果。

学习目标

  • 能用递归枚举或交替数组累计 n 个骰子的点数和概率
  • 能解释"两颗骰子 11 种和并不等概率"的原因
  • 能利用对称性验证分布的正确性

从“两颗骰子为什么不是十一种等概率”开始

两颗骰子的点数和可以是2到12，看起来有11个结果，但它们并不等概率。和2只有有序结果(1,1)，和7却有(1,6)、(2,5)直到(6,1)共6条路径。概率必须按底层等可能结果计数，不能按“不同点数和”平均分配。

题目默认每颗骰子公平、彼此独立。n颗骰子的共有6的n次方个结果；点数和s最小为n，最大为6n，因此只会访问5n+1个和状态。

n≤s≤6n,∣Ωn∣=6n,#{s}=5n+1n \le s \le 6n, \qquad \lvert\Omega_n\rvert = 6^n, \qquad \#\{s\}=5n+1
点数和分布（以 2 骰为例）：计数关于峰值对称1223344556675849310211112点数和 s（2..12）；峰值和 7 有 6 种，总样本 6² = 36递推：f(n, s) = Σ f(n-1, s-i)，i=1..6（末颗骰子的 6 种点数）n 骰可达和 n..6n，共 5n+1 个状态；概率 = 计数 / 6ⁿ。滚动数组只需上一轮与当前轮两张表。
计数数组只需覆盖可达和；概率分母来自所有等可能的有序投掷结果。

先预测两颗骰子从和2到和12的计数：它应从1逐步增到6，再对称地降回1。若得到11个相同概率，说明模型把“和”误当成了等可能基本事件。

方法一：每条投掷路径

作者第一种方法为计数数组分配5n+1个位置。真实和sum存入下标sum-original，因此最小和n映射到0，最大和6n映射到5n。这种按可达和聚合路径数量的槽位称为。

外层循环先选择第一颗骰子的1到6。递归参数original始终保存骰子总数，current表示还处于多少颗骰子的递归层，sum保存当前路径累计和。当current等于1时，当前sum已包含全部n颗骰子，直接把对应计数桶加一。

把“还需处理c层、当前累计和为t”的过程写成递推，可见每个非叶节点都分出6个子问题：

R(c,t)={count⁡[t−n]+=1,c=1,∑f=16R(c−1,t+f),c>1.R(c,t)= \begin{cases} \operatorname{count}[t-n] \mathrel{+}= 1, & c=1,\\ \displaystyle\sum_{f=1}^{6} R(c-1,t+f), & c>1. \end{cases}

这里的没有重复或遗漏：每一层唯一确定一颗骰子的点数，每个叶子与一个有序n元组一一对应。n为2时，外层第一颗骰子产生6个分支，每个分支再访问6个叶子，共36次计数。

int g_maxValue = 6;
 
void Probability(int original,
                 int current,
                 int sum,
                 int* counts) {
    if (current == 1) {
        ++counts[sum - original];
    } else {
        for (int face = 1;
             face <= g_maxValue;
             ++face) {
            Probability(original,
                        current - 1,
                        sum + face,
                        counts);
        }
    }
}
 
void Probability(int number, int* counts) {
    for (int first = 1;
         first <= g_maxValue;
         ++first) {
        Probability(number,
                    number,
                    first,
                    counts);
    }
}

这个入口看起来像“current等于number后又递归number次”，其实外层已经选择了第一颗骰子；当current从number降到1时，只再选择了number-1颗。若把入口改为sum等于0而不同时重写终止条件，就会多算或少算一层。

递归法时间复杂度为O(6的n次方)，调用栈O(n)，计数数组O(n)。它最接近问题定义，也适合小n核对，但不适合作者测试中的n=11：仅叶子就有362,797,056个，打印之前已要遍历三亿多条路径。

方法二：把上一轮分布一次

更高效的做法不再区分产生同一和的具体路径，而是保存“k颗骰子得到和s有多少种方法”。增加一颗骰子时，最后一颗可以是1到6；去掉它后，前k-1颗必须得到s-face。

C(k,s)=∑f=16C(k−1,s−f),C(1,s)={1,1≤s≤6,0,otherwise.C(k,s)=\sum_{f=1}^{6} C(k-1,s-f), \qquad C(1,s)= \begin{cases} 1,&1\le s\le6,\\ 0,&\text{otherwise}. \end{cases}

这是。第k轮只依赖第k-1轮，完整二维表没有必要；作者用申请两张长度6n+1的存储，一张只读、一张只写，完成当前轮后翻转flag。

“递归枚举或动态规划”都在统计同一个样本空间；区别只是前者逐叶访问，后者把相同中间和合并为一个状态。

两个数组如何交替累计次数

初始flag为0，先把第一张数组下标1到6设为1。处理第k颗骰子时，读取pProbabilities[flag]，写入pProbabilities[1-flag]。目标数组小于k的位置先清零；每个有效和i也先清零，再从上一轮i-1到i-6的计数累加。

void PrintProbability_Solution2(int number) {
    if (number < 1)
        return;
 
    int* counts[2];
    counts[0] =
        new int[6 * number + 1]();
    counts[1] =
        new int[6 * number + 1]();
 
    int flag = 0;
    for (int sum = 1; sum <= 6; ++sum)
        counts[flag][sum] = 1;
 
    for (int dice = 2;
         dice <= number;
         ++dice) {
        for (int sum = 0;
             sum < dice;
             ++sum) {
            counts[1 - flag][sum] = 0;
        }
 
        for (int sum = dice;
             sum <= 6 * dice;
             ++sum) {
            counts[1 - flag][sum] = 0;
            for (int face = 1;
                 face <= sum && face <= 6;
                 ++face) {
                counts[1 - flag][sum] +=
                    counts[flag][sum - face];
            }
        }
        flag = 1 - flag;
    }
 
    // 最终分布位于 counts[flag]。
    delete[] counts[0];
    delete[] counts[1];
}

这正是原章的“两个数组交替累计次数”。flag翻转必须发生在整轮写完之后；若在计算某个sum时就翻转，当前轮会混读新旧状态。目标位置也必须先清零，因为两张数组会隔一轮复用，旧计数不能带进新分布。

对第k轮，和范围为k到6k，共5k+1个状态，每个状态最多读取6项。因此总时间是从k等于2到n的线性状态数之和，即O(n平方)；两张数组各长6n+1，空间O(n)。固定六面骰子时常数6不计入渐进阶。

从计数得到点数和的概率

公平独立条件下，每条有序路径概率都为6的负n次方，所以将计数除以总路径数即可。所有概率之和应为1，这既是归一化，也是最便宜的整体正确性检查。

Pr⁡(Sn=s)=C(n,s)6n,∑s=n6nC(n,s)=6n,∑s=n6nPr⁡(Sn=s)=1\Pr(S_n=s)=\frac{C(n,s)}{6^n}, \qquad \sum_{s=n}^{6n}C(n,s)=6^n, \qquad \sum_{s=n}^{6n}\Pr(S_n=s)=1

作者用科学计数格式逐行打印“和: 概率”。函数不返回容器，测试也没有断言，因此原程序更像演示输出。工程接口应返回按和从n到6n排列的概率数组，让调用者决定打印、绘图或比较容差。

对称性为什么是强校验

把每颗骰子点数f映射为7-f，会把总和s一一映射为7n-s，而且不改变路径数量。因此计数关于3.5n对称；总和两端各只有一条路径，中部附近达到峰值。

C(n,s)=C(n,7n−s),E[Sn]=7n2,Var⁡(Sn)=35n12C(n,s)=C(n,7n-s), \qquad \mathbb{E}[S_n]=\frac{7n}{2}, \qquad \operatorname{Var}(S_n)=\frac{35n}{12}
1
4
4
5
10
6
20
7
35
8
56
9
80
10
104
11
125
12
140
13
146
14
140
15
125
16
104
17
80
18
56
19
35
20
20
21
10
22
4
23
1
24
四颗骰子的计数关于和 14 对称，峰值 146；两端和 4、24 都只有一种路径。

四颗骰子的计数从和4处的1增长到和14处的146，再完全对称地下降到和24处的1。只检查概率和为1仍可能放过“桶整体错位”；再检查两端、对称点和峰值位置，能定位索引偏移或边界遗漏。

若骰子有偏或彼此不独立，对称性与统一分母都可能失效。此时状态仍可卷积，但数组值应直接存概率并按各面权重转移，不能继续把路径数除以6的n次方。

作者整数实现的范围边界

作者把计数和total都存为int，并用pow的double结果转换为int。官方最大输入n=11时，总路径数362,797,056、峰值计数25,090,131，常见32位int仍可容纳。

n=12时总路径数为2,176,782,336，已超过常见有符号32位int上限；浮点转整数超出可表示范围，程序不再可靠。更大的n还会让单个计数桶溢出。只把total改为double不能修复计数数组本身。

可以在明确上限时用无符号64位计数；若只需要概率，可每增加一颗骰子就把上一轮概率除以6并分发到六个新和，避免指数级整数计数。下面的版本直接维护long double概率质量：

#include <vector>
 
std::vector<long double>
dicesProbability(int number) {
    if (number < 1)
        return {};
 
    std::vector<long double> previous(1, 1.0L);
    for (int dice = 1;
         dice <= number;
         ++dice) {
        std::vector<long double> current(
            previous.size() + 6, 0.0L);
 
        for (std::size_t sum = 0;
             sum < previous.size();
             ++sum) {
            for (int face = 1;
                 face <= 6;
                 ++face) {
                current[sum + face] +=
                    previous[sum] / 6.0L;
            }
        }
        previous.swap(current);
    }
 
    return {
        previous.begin() + number,
        previous.end()
    };
}

这个版本仍是O(n平方)时间和O(n)空间，但概率加法会有微小舍入误差。测试概率和时应使用容差，不能要求浮点结果严格等于1。若业务需要精确有理数，应保留大整数计数并单独保存分母。

作者六组输入实际覆盖什么

main依次调用Test(1)、Test(2)、Test(3)、Test(4)、Test(11)、Test(0)。每个Test先运行递归法，再运行动态规划法；但它只打印两份输出，没有自动比较。

n为1验证初始化，2到4能人工核对递推和对称性，11展示较大输入，0验证两个算法遇到无效输入直接返回。需要注意：Test包装函数仍会打印标题，而两个求解函数对0不打印分布。

官方用例没有负数、整数溢出、双解逐项一致、概率和与对称性断言。现代测试应把递归限制在小n作为参考实现，再让动态规划与参考逐桶比较。

#include <cassert>
#include <cmath>
#include <numeric>
 
void verifyDistribution(
    const std::vector<long double>& p,
    int number) {
    assert(p.size() ==
           static_cast<std::size_t>(
               5 * number + 1));
 
    const long double total =
        std::accumulate(
            p.begin(), p.end(), 0.0L);
    assert(std::fabs(total - 1.0L) <
           1e-15L);
 
    for (std::size_t left = 0;
         left < p.size();
         ++left) {
        const std::size_t right =
            p.size() - 1 - left;
        assert(std::fabs(
            p[left] - p[right]) < 1e-15L);
    }
}
 
void testDicesProbability() {
    assert(dicesProbability(0).empty());
    assert(dicesProbability(-1).empty());
 
    for (int n = 1; n <= 11; ++n)
        verifyDistribution(
            dicesProbability(n), n);
}

实际容差应与n和数值类型匹配；上述范围使用long double通常足够，但跨平台测试可适当放宽。还应对n=2断言精确的整数比例1、2、3、4、5、6、5、4、3、2、1除以36，以防一个“对称且归一”的错误分布侥幸通过。

本章练习

练习

问题 1： 两颗骰子和为 7 为什么比和为 2 概率大？

问题 2： 递归枚举与 DP 交替数组各自的适用场景？

问题 3： 如何验证分布的正确性？

概念说明

本章核心概念包括：n个骰子的点数，点数和的概率。理解这些概念是掌握解题方法的关键，需要结合具体示例与边界条件反复练习。

本章回顾

  1. n个骰子的点数来自6的n次方个等可能有序结果，和范围为n到6n。
  2. 点数和的概率等于对应计数桶中的路径数除以6的n次方。
  3. 递归枚举或动态规划统计的是同一批路径，前者逐叶访问，后者合并相同中间和。
  4. 作者用两个数组交替累计次数，隔离上一轮读取与当前轮写入。
  5. 递归时间O(6的n次方)，滚动动态规划时间O(n平方)、空间O(n)。
  6. 计数总和、对称性、边缘计数、峰值和双解一致性共同构成验证链。
  7. 原int实现只适合有限n；n=12起连总路径数都超出常见32位有符号范围。
  8. 作者测试1、2、3、4、11、0，但只打印，不自动断言。

名词解释

名词解释

本章出现的专业名词，用大白话再讲一遍。

样本空间
所有可能结果的集合，n 颗骰子共 6^n 种。
递归枚举
遍历所有投掷序列，统计每个和出现的次数。
卷积
把上一轮分布与当前骰子 1-6 均匀分布叠加。
复习本章（5 题）

讨论

评论区加载中…