国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

一篇算法講解的注解

fevin / 571人閱讀

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

前言

從公式到算法之前的完整路徑應該是：
數學公式->中文公式->中文算法->英文算法

偶然看到一篇算法文章，講解了百度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作為字符串最高位的字母?！綽***】
接下來來看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 $概率;
}

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/21547.html

相關文章

  • Java進階之路

    摘要：探索專為而設計的將探討進行了何種改進，以及這些改進背后的原因。關于最友好的文章進階前言之前就寫過一篇關于最友好的文章反響很不錯，由于那篇文章的定位就是簡單友好，因此盡可能的摒棄復雜的概念，只抓住關鍵的東西來講，以保證大家都能看懂。 周月切換日歷 一個可以進行周月切換的日歷，左右滑動的切換月份，上下滑動可以進行周，月不同的視圖切換，可以進行事件的標記，以及節假日的顯示，功能豐富 Andr...

    sushi 評論0 收藏0

  • Java相關

    摘要：本文是作者自己對中線程的狀態線程間協作相關使用的理解與總結，不對之處，望指出，共勉。當中的的數目而不是已占用的位置數大于集合番一文通版集合番一文通版垃圾回收機制講得很透徹，深入淺出。 一小時搞明白自定義注解 Annotation（注解）就是 Java 提供了一種元程序中的元素關聯任何信息和著任何元數據（metadata）的途徑和方法。Annotion(注解) 是一個接口，程序可以通過...

    wangtdgoodluck 評論0 收藏0

  • Spring AOP就是這么簡單啦

    摘要：是一種特殊的增強切面切面由切點和增強通知組成，它既包括了橫切邏輯的定義也包括了連接點的定義。實際上，一個的實現被拆分到多個類中在中聲明切面我們知道注解很方便，但是，要想使用注解的方式使用就必須要有源碼因為我們要 前言 只有光頭才能變強 上一篇已經講解了Spring IOC知識點一網打盡！，這篇主要是講解Spring的AOP模塊~ 之前我已經寫過一篇關于AOP的文章了，那篇把比較重要的知...

    Jacendfeng 評論0 收藏0

  • Java3y文章目錄導航

    摘要：前言由于寫的文章已經是有點多了，為了自己和大家的檢索方便，于是我就做了這么一個博客導航。 前言 由于寫的文章已經是有點多了，為了自己和大家的檢索方便，于是我就做了這么一個博客導航。 由于更新比較頻繁，因此隔一段時間才會更新目錄導航哦～想要獲取最新原創的技術文章歡迎關注我的公眾號：Java3y Java3y文章目錄導航 Java基礎 泛型就這么簡單 注解就這么簡單 Druid數據庫連接池...

    KevinYan 評論0 收藏0

  • Spring自動注入的簡單實現

    摘要：有多種注入的策略，比如按照裝配名稱，或者是默認實現了接口或者抽象類的子類實例對象來注入。這個方法中，做了一些簡單的判斷，如果這個類本身就不是一個抽象類或者不是一個接口，那么這個類就是第一個合適的類。 申明：本文不是講解Spring如何使用注解，本文只是通過一個簡單的實現，來理解Spring是如何注入一個對象的。 ??用過Spring的同學都知道，Spring利用注解來實現依賴注入，使得...

    joyvw 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<