一篇算法講解的注解

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

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

前言

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

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

第一題

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

/**
 * 解題函數(shù)
 * @param  {int}    $row_num 行號(hào)
 * @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類(lèi)型可以直接當(dāng)數(shù)組使用，就可以免掉這一步)再計(jì)算其序號(hào)。我們將結(jié)果存儲(chǔ)在數(shù)組$orders中。

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

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

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

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

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

$row = "abcdefghijkl";

序號(hào)= a在字段表中的大小 a在字符串的位號(hào)的階乘 + b在字段表中的大小 b在字符串的位號(hào)的階乘 + ... l在字段表中的大小 * l在字符串的位號(hào)的階乘

我們這里遍歷這個(gè)字符串，計(jì)算這個(gè)字母：
在字段表中的大小 * 在字符串的位號(hào)的階乘

最后將所有字母的值都加起來(lái)，即是該字符串的序號(hào)。

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

偽代碼：

$序號(hào) = 0;
for($i = 1; $i =< 12; $i ++) {
    $序號(hào) += 當(dāng)前字母在字母表中的排序 * 字母在字符中的位號(hào)階乘;
}

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

第二道題

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

定義函數(shù)為

/**
 * 解題函數(shù)
 * @param  {int} $row_num 行號(hào)
 * @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);

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

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

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

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

偽代碼：

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

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

第四題

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

首先，我們來(lái)還原題目。

以樣例為例：
n = 2, a = 1, b = 3, x = 4，
則從[1, 3]中取出2個(gè)數(shù)的組合共有六對(duì)：
(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)，其概率計(jì)算公式為
取兩個(gè)數(shù)和為4概率 = 取一個(gè)數(shù)為1的概率取一個(gè)數(shù)為3的概率 + 取一個(gè)數(shù)為2的概率取一個(gè)數(shù)為2的概率 + 取一個(gè)數(shù)為3的概率*取一個(gè)數(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個(gè)數(shù)其和為x的概率即為rate(x,n)，這可以處理為一個(gè)遞歸函數(shù)，當(dāng)n=1時(shí)，即可確定其值。

偽代碼

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

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

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

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