一篇算法講解的注解

fevin 發(fā)布于2019-06-27 13:40 / 638人閱讀

摘要：前言從公式到算法之前的完整路徑應(yīng)該是數(shù)學(xué)公式中文公式中文算法英文算法偶然看到一篇算法文章，講解了百度校園招聘之編程題的核心算法思路，我根據(jù)它又整理出自己的解題思路。

前言

從公式到算法之前的完整路徑應(yīng)該是：
數(shù)學(xué)公式->中文公式->中文算法->英文算法

偶然看到一篇算法文章，講解了百度2016校園招聘之編程題的核心算法思路，我根據(jù)它又整理出自己的解題思路。

第一題

題目在原文中可以找到，這里就直接講解具體的是如何做的。
首先，輸入行號（整數(shù)n），接著是每行的數(shù)據(jù)
那可以定義函數(shù)為

/**
 * 解題函數(shù)
 * @param  {int}    $row_num 行號
 * @param  {Array}  $rows    每行的數(shù)據(jù)，其元素為string型，即一行數(shù)據(jù)
 * @return {Array}           每行數(shù)據(jù)在總排列中第幾小，形如：[1, 3, 454]
 */
function question($row_num, $rows = []) {}

讀取到了數(shù)據(jù)，就要一條一條先由string轉(zhuǎn)化為數(shù)組，(在PHP中，string類型可以直接當(dāng)數(shù)組使用，就可以免掉這一步)再計算其序號。我們將結(jié)果存儲在數(shù)組$orders中。

現(xiàn)在我們拿到了

$row_num = 3;
$rows = [
    "abcdefghijkl",
    "bcdefghaijkl",
    "bcdefghijkla",
];

$orders = [];
foreach ($rows as $row) {
    $orders[] = get_order($row);
}

get_order方法即計算一行數(shù)據(jù)序號的方法。

依照公式，對于每一行數(shù)據(jù)，我們首先還是要遍歷該數(shù)據(jù)中每個字符，再獲取該字符在整個

$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 ++) {
    $序號 += 當(dāng)前字母在字母表中的排序 * 字母在字符中的位號階乘;
}

這里有一個優(yōu)化點，即求階乘。
原文中作者是直接計算階乘，但其實我們已經(jīng)可以確定，要用到的也就是十二個階乘值，所以其實可以只計算一遍，將這十個階乘值都存在數(shù)組中，實際計算過程中要用到哪個直接取就行了。

第二道題

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

定義函數(shù)為

/**
 * 解題函數(shù)
 * @param  {int} $row_num 行號
 * @param  {Array}  $rows 每行數(shù)據(jù)在總排列中第幾小，形如：[1, 3, 454]
 * @return {Array}        每行的數(shù)據(jù)，其元素為string型，形如：["abcdefghijkl", "abcdeghijklf"]
 */
function question2($row_num, $orders = []) {}

現(xiàn)在我們拿到了

$row_num = 3;
$orders = [
    1
    3,
    454,
];

$rows = [];
foreach ($orders as $order) {
    $rows[] = get_row($order);
}

get_row($order);

獲得了單個order。假設(shè)是 454 ，則根據(jù)公式，其對應(yīng)字母為

題目中是12個字符，范圍太大，原文中為了說明公式，將范縮小至4個字符。
假設(shè)只有abcd四個字符，單個order為9時，其對應(yīng)字母為bcda。計算公式為
1、9 / 6 = 1 ... 3
2、3 / 2 = 1 ... 1
3、1 / 1 = 1 ... 0

所以我們可得到計算公式了：
從最高位開始，我們來將數(shù)字還原為字段
【abcd的排序都是從0位開始排】
1*3! + 1*2! + 1*1! + 0*0! = 9
我們現(xiàn)在來分解以上公式的意義，先來看1*3!
它的中文意義為
【abcd中第1位大的字母】*3!
abcd中，a排第0位、b排第1位、c排第2位、d排第3位，所以這里就是b作為字符串最高位的字母?！綽***】
接下來來看1*2!
由于abcd四個字母中b已經(jīng)確定下來了，所以現(xiàn)在它的中文意義為【剩余字母中第1位大的字母】，即【acd中第1位大的字母】*2!
acd中，a排第0位、c排第1位、d排第2位，所以這里就是c作為字符串第3位的字母。
【bc**】
好了，道理都懂了，接下來依次類推，我們即可將字符串還原為【bcda】

所以，現(xiàn)在換成12位字母，算法要如何處理呢？
首先，假設(shè)我們拿到了order = 456；
接著，先計算最高位的字母，用order / 11!，獲得其取整結(jié)果和取余結(jié)果。
根據(jù)其取整結(jié)果，即可知道最高位的字母在當(dāng)前12字母的排位，我們可以確定當(dāng)前字母了。
取余結(jié)果即可繼續(xù)用于計算下一位字母。依次類推，即可將字符串還原回來。

偽代碼：

$序號 = 456;
$字符串 = "";
$字母表 = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l"];
for($i = 11; $i >= 0; $i --) {
    $取整結(jié)果 = $序號 / $i 的階乘;
    $取余結(jié)果 = $序號 % $i 的階乘;
    $當(dāng)前字母 = $字母表[$取整結(jié)果];
    更改字母表，把取出來的字母后面的字母都向前移動一位
    $字符串 .= $當(dāng)前字母;
    $序號 = $取余結(jié)果;
}

第三題原文已經(jīng)解釋得很清楚了，這里就跳過。

第四題

第四題其實是四道算法題中最最復(fù)雜的，但原文作者可能是嫌解釋太麻煩，反倒講解得最少。這里就重點解析第四道題的算法。

首先，我們來還原題目。

以樣例為例：
n = 2, a = 1, b = 3, x = 4，
則從[1, 3]中取出2個數(shù)的組合共有六對：
(1, 1), (1, 2), (1, 3),
(2, 2), (2, 3),
(3, 3)
其中，能組合成4，即相加為4的只有(1, 3), (2, 2)。

假設(shè)n=2, x=4的概率表示為rate(4, 2)，其概率計算公式為
取兩個數(shù)和為4概率 = 取一個數(shù)為1的概率取一個數(shù)為3的概率 + 取一個數(shù)為2的概率取一個數(shù)為2的概率 + 取一個數(shù)為3的概率*取一個數(shù)為1的概率
rate(4, 2) = rate(1, 1)*rate(3, 1) + rate(2,1)*rate(2,1) + rate(3,1)*rate(1,1)
可以進(jìn)一步歸納為
rate(4,2) = rate(1,1)*rate((4-1),1) + rate(2,1)*rate(4-2,1) + rate(3,1)*rate((4-3),1)
我們現(xiàn)在將數(shù)字替換為字母
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)

現(xiàn)在，我們將[1, 3]區(qū)間替換成字母[a,b]，公式可以進(jìn)一步歸納為
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

至此，我們已可以確定，在區(qū)間[a,b]內(nèi)取n個數(shù)其和為x的概率即為rate(x,n)，這可以處理為一個遞歸函數(shù)，當(dāng)n=1時，即可確定其值。

偽代碼

$區(qū)間下限 = a;
$區(qū)間上限 = b;
$區(qū)間數(shù)字個數(shù) = $區(qū)間上限 - $區(qū)間下限 + 1;
function rate($x, $n) {
    // 當(dāng)只取一個數(shù)時，其概率可以確定下來了
    if($n == 1) {
        if($x > $區(qū)間上限 || $x < $區(qū)間下限) {
            return 0;
        } else {
            return 1/$區(qū)間數(shù)字個數(shù);
        }
    }

    $概率 = 0;
    for($i = $區(qū)間上限; $i < $區(qū)間下限; $i ++) {
        if($x-$i < $區(qū)間下限) break;

        $概率 += rate($i,1)*rate($x-$i, $n-1);
    }
    return $概率;
}

雖然我的解析過程過于啰嗦，但是它絕對夠詳細(xì)。如果有一天我忘記了這道算法，再回過頭來看，也能保證自己可以看懂。