6.4 抽象建模能力

计算机只是一种工具，它被用来解决实际生产生活中的问题。程序员的工作就是把各种现实问题抽象成数学模型并用计算机的编程语言表达出来，因此有些面试官喜欢从日常生活中抽取提炼出问题考查应聘者是否能建立数学模型并解决问题。要想顺利解决这种类型的问题，应聘者除了需要具备扎实的数学基础和编程能力，还需要具有敏锐的洞察力和丰富的想象力。

建模的第一步是选择合理的数据结构来表述问题。实际生产生活中的问题千变万化，而常用的数据结构只有有限的几种。我们在根据问题的特点综合考虑性能、编程难度等因素之后，选择最合适的数据结构来表达问题，也就是建立模型。比如在面试题61“扑克牌中的顺子”中，我们用一个数组表示一副牌，用11、12和13分别表示J、Q、K，并且用0表示大小王。在面试题62“圆圈中最后剩下的数字”中，我们可以用一个环形链表模拟一个圆圈。

建模的第二步是分析模型中的内在规律，并用编程语言表述这种规律。我们只有对现实问题进行深入细致的观察分析之后，才能找到模型中的规律，才有可能编程解决问题。例如，在本书2.4.1节提到的“青蛙跳台阶”问题中，它内在的规律是斐波那契数列。再比如面试题60“n个骰子的点数”问题，其本质是求数列f(n)=f(n-1)+f(n-2)+f(n-3)+f(n-4)+f(n-5)+f(n-6)。找到这个规律之后，我们就可以分别用递归和循环两种不同的方法去写代码。然而，并不是所有问题的内在规律都是显而易见的。在面试题62“圆圈中最后剩下的数字”中，我们经过严密的数学分析之后才能找到每次从圆圈中删除数字的规律，从而找到一种不需要辅助环形链表的快速方法来解决问题。

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

题目：把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。

玩过麻将的人都知道，骰子一共有6个面，每个面上都有一个点数，对应的是1～6之间的一个数字。所以n个骰子的点数和的最小值为n，最大值为6n。另外，根据排列组合的知识，我们还知道n个骰子的所有点数的排列数为6n。要解决这个问题，我们需要先统计出每个点数出现的次数，然后把每个点数出现的次数除以6n，就能求出每个点数出现的概率。

解法一：基于递归求骰子点数，时间效率不够高

现在我们考虑如何统计每个点数出现的次数。要想求出n个骰子的点数和，可以先把n个骰子分为两堆：第一堆只有一个；另一堆有n-1个。单独的那一个有可能出现1～6的点数。我们需要计算1～6的每一种点数和剩下的n-1个骰子来计算点数和。接下来把剩下的n-1个骰子仍然分成两堆：第一堆只有一个；第二堆有n-2个。我们把上一轮那个单独骰子的点数和这一轮单独骰子的点数相加，再和剩下的n-2个骰子来计算点数和。分析到这里，我们不难发现这是一种递归的思路，递归结束的条件就是最后只剩下一个骰子。

我们可以定义一个长度为6n-n+1的数组，将和为s的点数出现的次数保存到数组的第s-n个元素里。基于这种思路，我们可以写出如下代码：

int g_maxValue = 6;

void PrintProbability(int number)

{

if(number < 1)

return;

int maxSum = number * g_maxValue;

int* pProbabilities = new int[maxSum - number + 1];

for(int i = number; i <= maxSum; ++i)

pProbabilities[i - number] = 0;

Probability(number, pProbabilities);

int total = pow((double)g_maxValue, number);

for(int i = number; i <= maxSum; ++i)

{

double ratio = (double)pProbabilities[i - number] / total;

printf("%d: %e\n", i, ratio);

}

delete[] pProbabilities;

}

void Probability(int number, int* pProbabilities)

{

for(int i = 1; i <= g_maxValue; ++i)

Probability(number, number, i, pProbabilities);

}

void Probability(int original, int current, int sum,

int* pProbabilities)

{

if(current == 1)

{

pProbabilities[sum - original]++;

}

else

{

for(int i = 1; i <= g_maxValue; ++i)

{

Probability(original, current - 1, i + sum, pProbabilities);

}

}

}

上述思路很简洁，实现起来也容易。但由于是基于递归的实现，它有很多计算是重复的，从而导致当number变大时性能慢得让人不能接受。关于递归的性能讨论，详见本书2.4.1节。

解法二：基于循环求骰子点数，时间性能好

可以换一种思路来解决这个问题。我们可以考虑用两个数组来存储骰子点数的每个总数出现的次数。在一轮循环中，第一个数组中的第n个数字表示骰子和为n出现的次数。在下一轮循环中，我们加上一个新的骰子，此时和为n的骰子出现的次数应该等于上一轮循环中骰子点数和为n-1、n-2、n-3、n-4、n-5与n-6的次数的总和，所以我们把另一个数组的第n个数字设为前一个数组对应的第n-1、n-2、n-3、n-4、n-5与n-6个数字之和。基于这种思路，我们可以写出如下代码：

void PrintProbability(int number)

{

if(number < 1)

return;

int* pProbabilities[2];

pProbabilities[0] = new int[g_maxValue * number + 1];

pProbabilities[1] = new int[g_maxValue * number + 1];

for(int i = 0; i < g_maxValue * number + 1; ++i)

{

pProbabilities[0][i] = 0;

pProbabilities[1][i] = 0;

}

int flag = 0;

for (int i = 1; i <= g_maxValue; ++i)

pProbabilities[flag][i] = 1;

for (int k = 2; k <= number; ++k)

{

for(int i = 0; i < k; ++i)

pProbabilities[1 - flag][i] = 0;

for (int i = k; i <= g_maxValue * k; ++i)

{

pProbabilities[1 - flag][i] = 0;

for(int j = 1; j <= i && j <= g_maxValue; ++j)

pProbabilities[1-flag][i]+=pProbabilities[flag][i-j];

}

flag = 1 - flag;

}

double total = pow((double)g_maxValue, number);

for(int i = number; i <= g_maxValue * number; ++i)

{

double ratio = (double)pProbabilities[flag][i] / total;

printf("%d: %e\n", i, ratio);

}

delete[] pProbabilities[0];

delete[] pProbabilities[1];

}

在上述代码中，我们定义了两个数组pProbabilities[0]和pProbabilities[1]来存储骰子的点数之和。在一轮循环中，一个数组的第n项等于另一个数组的第n-1、n-2、n-3、n-4、n-5及n-6项的和。在下一轮循环中，我们交换这两个数组（通过改变变量flag实现）再重复这一计算过程。

值得注意的是，上述代码没有在函数里把一个骰子的最大点数硬编码（Hard Code）为6，而是用一个变量g_maxValue来表示。这样做的好处是，如果某个厂家生产了其他点数的骰子，那么我们只需要在代码中修改一个地方，扩展起来很方便。如果在面试的时候我们能对面试官提起对程序扩展性的考虑，则一定能给面试官留下很好的印象。

源代码：

本题完整的源代码：

https://github.com/zhedahht/CodingInterviewChinese2/tree/master/60_ DicesProbability

测试用例：

功能测试（1、2、3、4个骰子的各点数的概率）。

特殊输入测试（输入0）。

性能测试（输入较大的数字，如11）。

本题考点：

考查应聘者的数学建模能力。不管采用哪种思路解决问题，我们都要先想到用数组来存放n个骰子的每个点数出现的次数，并通过分析点数的规律建立模型，最终找到解决方案。

考查应聘者对递归和循环的性能的理解。

面试题61：扑克牌中的顺子

题目：从扑克牌中随机抽5张牌，判断是