转载

一篇算法讲解的注解

前言

从公式到算法之前的完整路径应该是：数学公式->中文公式->中文算法->英文算法

偶然看到一篇算法文章，讲解了 百度2016校园招聘之编程题 的核心算法思路，我根据它又整理出自己的解题思路。

第一题

题目在原文中可以找到，这里就直接讲解具体的是如何做的。

首先，输入行号（整数n），接着是每行的数据

那可以定义函数为

/**  * 解题函数  * @param  {int}    $row_num 行号  * @param  {Array}  $rows    每行的数据，其元素为string型，即一行数据  * @return {Array}           每行数据在总排列中第几小，形如：[1, 3, 454]  */ function question($row_num, $rows = []) {}

读取到了数据，就要一条一条先由string转化为数组，(在PHP中，string类型可以直接当数组使用，就可以免掉这一步)再计算其序号。我们将结果存储在数组$orders中。

现在我们拿到了

$row_num = 3; $rows = [     'abcdefghijkl',     'bcdefghaijkl',     'bcdefghijkla', ];  $orders = []; foreach ($rows as $row) {     $orders[] = get_order($row); }

get_order方法即计算一行数据序号的方法。

依照公式，对于每一行数据，我们首先还是要遍历该数据中每个字符，再获取该字符在整个

$row = 'abcdefghijkl';

序号= a在字段表中的大小 a在字符串的位号的阶乘 + b在字段表中的大小 b在字符串的位号的阶乘 + ... l在字段表中的大小 * l在字符串的位号的阶乘

我们这里遍历这个字符串，计算这个字母：在字段表中的大小 * 在字符串的位号的阶乘

最后将所有字母的值都加起来，即是该字符串的序号。

$order = 0; for($i = 1; $i =< 12; $i ++) {     $order += get_rank($row[$i]) * get_jeicheng(12 - $i); }

伪代码：

$序号 = 0; for($i = 1; $i =< 12; $i ++) {     $序号 += 当前字母在字母表中的排序 * 字母在字符中的位号阶乘; }

这里有一个优化点，即求阶乘。原文中作者是直接计算阶乘，但其实我们已经可以确定，要用到的也就是十二个阶乘值，所以其实可以只计算一遍，将这十个阶乘值都存在数组中，实际计算过程中要用到哪个直接取就行了。

第二道题

第二道题里，大部分流程都和第一道题一样，只有核心算法那里不同。

定义函数为

/**  * 解题函数  * @param  {int} $row_num 行号  * @param  {Array}  $rows 每行数据在总排列中第几小，形如：[1, 3, 454]  * @return {Array}        每行的数据，其元素为string型，形如：['abcdefghijkl', 'abcdeghijklf']  */ function question2($row_num, $orders = []) {}

现在我们拿到了

$row_num = 3; $orders = [     1     3,     454, ];  $rows = []; foreach ($orders as $order) {     $rows[] = get_row($order); }  get_row($order);

获得了单个order。假设是 454 ，则根据公式，其对应字母为

题目中是12个字符，范围太大，原文中为了说明公式，将范缩小至4个字符。

假设只有abcd四个字符，单个order为9时，其对应字母为bcda。计算公式为

1、9 / 6 = 1 ... 3

2、3 / 2 = 1 ... 1

3、1 / 1 = 1 ... 0

所以我们可得到计算公式了：

从最高位开始，我们来将数字还原为字段

【abcd的排序都是从0位开始排】

1*3! + 1*2! + 1*1! + 0*0! = 9

我们现在来分解以上公式的意义，先来看1*3!

它的中文意义为

【abcd中第1位大的字母】*3!

abcd中，a排第0位、b排第1位、c排第2位、d排第3位，所以这里就是b作为字符串最高位的字母。【b***】

接下来来看1*2!

由于abcd四个字母中b已经确定下来了，所以现在它的中文意义为【剩余字母中第1位大的字母】，即【acd中第1位大的字母】*2!

acd中，a排第0位、c排第1位、d排第2位，所以这里就是c作为字符串第3位的字母。

【bc**】

好了，道理都懂了，接下来依次类推，我们即可将字符串还原为【bcda】

所以，现在换成12位字母，算法要如何处理呢？

首先，假设我们拿到了order = 456；

接着，先计算最高位的字母，用order / 11!，获得其取整结果和取余结果。

根据其取整结果，即可知道最高位的字母在当前12字母的排位，我们可以确定当前字母了。

取余结果即可继续用于计算下一位字母。依次类推，即可将字符串还原回来。

伪代码：

$序号 = 456; $字符串 = ''; $字母表 = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l']; for($i = 11; $i >= 0; $i --) {     $取整结果 = $序号 / $i 的阶乘;     $取余结果 = $序号 % $i 的阶乘;     $当前字母 = $字母表[$取整结果];     更改字母表，把取出来的字母后面的字母都向前移动一位     $字符串 .= $当前字母;     $序号 = $取余结果; }

第三题原文已经解释得很清楚了，这里就跳过。

第四题

第四题其实是四道算法题中最最复杂的，但原文作者可能是嫌解释太麻烦，反倒讲解得最少。这里就重点解析第四道题的算法。

首先，我们来还原题目。

以样例为例：

n = 2, a = 1, b = 3, x = 4，

则从[1, 3]中取出2个数的组合共有六对：

(1, 1), (1, 2), (1, 3),

(2, 2), (2, 3),

(3, 3)

其中，能组合成4，即相加为4的只有(1, 3), (2, 2)。

假设n=2, x=4的概率表示为rate(4, 2)，其概率计算公式为

取两个数和为4概率 = 取一个数为1的概率 取一个数为3的概率 + 取一个数为2的概率 取一个数为2的概率 + 取一个数为3的概率*取一个数为1的概率

rate(4, 2) = rate(1, 1)*rate(3, 1) + rate(2,1)*rate(2,1) + rate(3,1)*rate(1,1)

可以进一步归纳为

rate(4,2) = rate(1,1)*rate((4-1),1) + rate(2,1)*rate(4-2,1) + rate(3,1)*rate((4-3),1)

我们现在将数字替换为字母

rate(x,n) = rate(1,n-1)*rate(x-1,n-1) + rate(2,n-1)*rate(x-2,n-1) + rate(3,n-1)*rate(x-3,n-1)

现在，我们将[1, 3]区间替换成字母[a,b]，公式可以进一步归纳为

rate(x,n) = rate(a,1)*rate(x-a,n-1) + rate(a+1,1)*rate(x-(a+1),n-1) + ... + rate(b,1)*rate(x-b,n-1)

其中x-b>=a

至此，我们已可以确定，在区间[a,b]内取n个数其和为x的概率即为rate(x,n)，这可以处理为一个递归函数，当n=1时，即可确定其值。

伪代码

$区间下限 = a; $区间上限 = b; $区间数字个数 = $区间上限 - $区间下限 + 1; function rate($x, $n) {     // 当只取一个数时，其概率可以确定下来了     if($n == 1) {         if($x > $区间上限 || $x < $区间下限) {             return 0;         } else {             return 1/$区间数字个数;         }     }      $概率 = 0;     for($i = $区间上限; $i < $区间下限; $i ++) {         if($x-$i < $区间下限) break;          $概率 += rate($i,1)*rate($x-$i, $n-1);     }     return $概率; }

虽然我的解析过程过于啰嗦，但是它绝对够详细。如果有一天我忘记了这道算法，再回过头来看，也能保证自己可以看懂。

原文 https://segmentfault.com/a/1190000005060870

正文到此结束