over 2 years ago

0 緣起

在 Knuth 大師所編著的《具體數學》(Concrete Math,別名:水泥數學)時,第一章探討遞迴問題的時候就以河內塔的移動步數作為例子。河內塔的問題算是理解遞迴解題非常重要的一個基礎,大多數的 C/C++ 程式語言書籍講到遞迴函式的時候第一個就是提到河內塔問題(題目參考:TIOJ1355):

有三根柱子分別為 ,其中 柱上頭有 個圓盤,由上至下其大小分別為 ,現在我們每一步都可以把一個盤子從某一根柱子搬到另一根上頭,但是大盤子永遠不能疊在小盤子上頭。請問至少要多少步,才能讓所有盤子都搬到 柱上?

遞迴的概念也相當純粹:先把前 個盤子搬到 ,然後把第 個盤子搬到 ,再把前 個盤子從 搬到 。由於三根柱子除了編號不同以外,其餘功能都是等價的,我們便可以寫成以下遞迴:

void hanoi(int n, char From, char To, char Temp) {
    if (n > 1) hanoi(n-1, From, Temp, To);
    printf("Move disk %d from %c to %c\n", n, From, To);
    if (n > 1) hanoi(n-1, Temp, To, From);
}

今天讓我們來找出河內塔的一些性質,以及討論一些延伸的類似題。

1 順時針或逆時針

讓我們考慮以下的樣子:我們把三根柱子依照順時針排成三角形放在一個圓形的基座上,如果我們依照上面描述的方法,每次「順時針」或「逆時針」移動盤子,我們以 表示逆時針、並以 表示順時針,那麼對於 的情形,我們可以得到以下的序列:

類似地,我們對於每一個 ,我們可以從上面的遞迴式推得最佳解的序列

這個跟摺紙序列雖然有點不一樣,但是遞迴長相很像吧~
也就是說,掌握了這個點,我們就可以知道該怎麼遞迴直接求出第 步到底盤子是要順時針還是逆時針移動了!

2 直接找出第 步該做什麼

此外,我們也想知道到底在第 步的時候,該移動哪一個盤子。這點我們也可以透過以下表格觀察:

Step A B C 備註
0 (000) 初始狀態
1 (001)
2 (010)
3 (011)
4 (100)
5 (101)
6 (110)
7 (111)

我們可以毫無意外地發現:第 步要移動的盤子編號,恰好就是 ,也就是把 寫成二進位以後的最低有效位的 index!(我們可以利用 1+__lg(i&-i) 直接算出這個編號哈~)

練習題

後記

哈哈,實在是後記無力啊,真的很對不起,拖稿拖成這樣。我們下次見吧~

 
over 2 years ago

0 緣起

接下來這幾篇,筆者想要提出來與大家一起討論的,是一系列經典的「遞迴結構問題」。遞迴與自相似性質、分而治之與二分搜尋法等等其實都有某種程度的關聯。擁有了遞迴腦袋,把問題與子問題分離清楚,解題寫 code 的時候就會輕鬆許多。這一系列預計包含摺紙條問題、河內塔問題、Gray Code 問題等。

讓我們先從摺紙條問題開始吧!

註:我們把「摺紙問題」(Origami)留給計算幾何的時候使用吧!我們把今天要討論的問題定義為「摺紙條問題」(Paper Folding)

1 經典的紙條結構

最經典的問題莫過於 UVa 177 - Paper Folding 了吧!把一張紙條,向左對摺、再向左對摺、再對摺…總共 次,然後全部展開,把每一個角都折成 90 度以後,我們查看側面會得到一個形狀。請你把這個形狀以純文字的方式繪製出來,並在最後一列之後加上一個 ^ 符號表示結尾。

紙條序列(Paper Folding Sequence)

我們發現,每一次打開一個褶痕,就會轉 90 度。由於我們永遠向同一邊折,所以這個褶痕打開的時候也都會是往同一邊,我們不妨假設就通通都往左邊吧!

於是我們沿著其中一端,記錄下紙條前進的順序依次是「左轉 」還是「右轉 」:

在轉折點的前後,其實整個紙條的形狀會是完全相同的(只是向左轉了九十度把紙條打開)。所以我們可以得知,整個摺紙序列正中間是一個「左轉 」,然後,序列的後半段,就相當於逆著方向從原來的紙條末端走回開頭,即:原本左轉變成右轉、右轉變成左轉、而且序列的順序是反過來的:

因此我們可以得到遞迴關係:

想知道更多的話可以參考維基百科 Regular Paperfolding Sequence

有了「紙條序列」的定義之後,我們就可以發現:只要將摺紙序列產生出來,再依照這個序列把整條紙帶的方法畫再一個 2D array 上面,就可以解決 UVa 177 的題目了。

2 紙條與搜索範圍

我們來考慮以下的題目 PA2011 Round 4 - Plotter。題目簡述如下:考慮路徑序列 ,產生方式為:一開始 ,然後每一次把原有的序列「撐開」:若原本長度為 序列為 ,那麼新的序列會變成 然後我們把問號的地方依序交錯填入 ,得到

拜特阿瑟(波蘭OI界的靈魂人物,永遠住在拜特蘭 Byteland 的拜特阿瑟 Byteasar,總是能夠想出各種漂亮的程式題目)決定用路徑序列 畫出一條 拜特曲線:在座標平面上從 點出發,一開始往 方向前進,每一步都跨了 單位長的距離,接著根據路徑序列的順序依序左轉、或右轉,然後走完整條路。

現在給你 個座標,對於每一個座標 ,請你回答拜特阿瑟畫出來的曲線上的哪些步會恰好踏到這個座標點上?(;座標範圍

觀察

我們可以按照定義寫出前幾個序列,沒想到竟然跟摺紙序列一模一樣!──是不太意外啦,畢竟都放在同一篇文章了(笑)從這個序列的定義方式,有別於每一次展開一個褶痕,我們可以找出另一種構造紙條序列的方法,如下圖所示:

題解

當然,題解跟上面這個觀察其實沒有太大的關係,主要的觀察還是紙條序列可以用最早的方法產生出來。因此我們可以採用倍增法,維護 這個摺紙序列畫出來以後的可能踏到的座標範圍 ,如果 這個點落在 後半段,那我們把後半段紙條視為「原本紙條的逆序」計算出該點相對於這半部紙條的位置,再遞迴下去找實際的步數。

由於座標範圍只有 ,因此稍作觀察以後(為什麼!)可以得出其實我們只要考慮 就可以了的結論。

參考程式碼

請參考 https://gist.github.com/19b4985ee001b6fc90ba

延伸練習

PA2011 Round 5 - Trails:這題比前一題更複雜一點點,但是方法應該是類似的。歡迎大家一起討論怎麼實作會更理想與簡潔!

第三種定義

在上面的練習題中,作者對於紙條序列給出了第三個直接的定義:若 可以被表示成 的形式,其中 都是整數,那麼整個序列第 個位置便是 否則就是 。有趣吧!

3 後記

那個…如果圖片有奇怪的小錯誤就請大家自由忽略吧!真的很不好意思 ( ̄▽ ̄#)﹏﹏

 
over 2 years ago

0 緣起

基本上就是個為趕進度不擇手段的概念哈哈哈。

1 題目

基本上是這樣的,有個 大小的棋盤,其中某一個格子上面站了一隻史萊姆。請問你能不能用 3 個正方形拼成的 L形磚,把整個棋盤除了史萊姆以外不重疊地恰好鋪滿?如果能的話,該怎麼鋪呢?

2 解法

其實,我們只要用數學歸納法證明:無論史萊姆站在哪一格,上述鋪磚問題都可以達成。

如果盤面大小是 ,無論史萊姆站在哪一格,顯然剩下的形狀可以被一個 L形磚鋪滿。假設對於 大小的盤面上,任何一個站了一隻史萊姆的情況我們都可以用 L形磚鋪滿。現在考慮 ,我們把整個盤面分成四個 的子盤面,史萊姆會站在其中一個盤面上。我們在正中間放一片 L形磚,然後讓凹口朝向有史萊姆的那一個子盤面。

這時候我們就可以知道四個子盤面都恰好包含一個「被佔走的格子」,滿足歸納的條件。因此由歸納法可以證明出任何 的棋盤,只要被佔用一格,都仍可以被 L形磚鋪滿!

思考問題

  1. 如果史萊姆的大小是 ,在什麼樣的條件下我們可以保證 L形磚一定可以鋪滿盤面的其他地方?
  2. 證明存在一個 缺一角的 L形磚鋪法,至少要用四種顏色塗每一片磚,使得有邊相鄰的兩塊磚顏色都不相同。(即,這個鋪磚法無法三著色。)說不定有 的構造法?(三著布拉克)

3 擴展到三維

想像一下一個 的方塊去掉一小角的形狀 ,我們也可以用同樣方式證明:給定 空間中,某個格子已經擺了一隻史萊姆,可以用 把剩下的空間恰好鋪滿。

4 後記

拓展到三維這個想法第一次是在劉邦鋒教授所開授的「進階程式設計 ACP2009」期中考遇到的,當時覺得相當新奇。這題的程式碼其實沒有想像中好寫,尤其是要判斷八個部分分別遞迴下去的時候,不寫成迴圈真的不行哈哈。

5 奇怪的後記

螢幕快照 2016-02-26 下午4.56.23.png

要怎麼用 產生出以上的圖片呢~請參考下面的程式碼 :P

\begin{figure}[h]
\centering
\begin{subfigure}[c]{0.4\textwidth}
\begin{center}
\begin{tikzpicture}[scale=0.6]
\draw[black] (0,0) grid (8,8);
\fill[color=black] (6,2) rectangle (7,3);
\end{tikzpicture}
\end{center}
\end{subfigure}\ \ \ \
\begin{subfigure}[c]{0.4\textwidth}
\begin{center}
\begin{tikzpicture}[scale=0.6]
\foreach \i in {1, ..., 20} {
  \pgfmathsetmacro{\Xa}{random(180)};
  \pgfmathsetmacro{\Ya}{random(7)};
  \pgfmathsetmacro{\Za}{random(7)};
  \pgfmathparse{0.9*rnd+0.3};
  \def\cr{\pgfmathresult};
  \pgfmathparse{0.9*rnd+0.3};
  \def\cg{\pgfmathresult};
  \pgfmathparse{0.9*rnd+0.3};
  \def\cb{\pgfmathresult};
  \definecolor{MyColor}{rgb}{\cr,\cg,\cb};
\draw[fill=MyColor, cm={cos(\Xa), -sin(\Xa), sin(\Xa), cos(\Xa), (\Ya,\Za)}] (0,0)--(0,2)--(1,2)--(1,1)--(2,1)--(2,0)--cycle;
}
\end{tikzpicture}
\end{center}
\end{subfigure}
\end{figure}
 
over 2 years ago

0 緣起──最短路徑問題

一般來說,我們在解決所有點對的最短路徑問題的時候,我們會想要對所有點對 計算在圖上他們之間的最短距離 。考慮一個鄰接矩陣 ,如果我們想要得到任兩點之間走不超過兩步的最短距離,可以某種形式計算這個矩陣的「平方」。即,對於任意點對 ,我們想計算的是枚舉任意中繼點 使得

試想一下,如果我們把這裡的「加法」對應到一般矩陣的乘法,這裡的「取 Min」對應到一般矩陣的加法,那我們就可以寫成:

我們回憶一下,一般矩陣相乘有個有趣的分而治之法:Strassen 演算法,大致上是將兩個矩陣各自切成四份,然後利用加法、減法與乘法完成運算。我們有沒有辦法把 Strassen 演算法應用在我們的最短路徑問題上面呢?其實是沒辦法直接套用的。我們仔細檢視計算 Strassen 演算法的步驟,就會發現原因出在減法上面。如果只有加法與乘法,那麼可以直接分別換成「取 Min」和「加法」是可以保持遞移關係的。可惜現在必須要進行減法,式子上沒辦法把一個求最小值的式子直接地拆成兩個式子加減(有些方法可以在數字範圍不大的時候套用 Strassen 演算法,比方說把所有數字變成指數大小,然後倒數硬乘起來再取 log,如此一來這個數字就會是 min 了。)

對於與輸入數值無關演算法裡頭,目前的 (min, +) 矩陣相乘問題也還沒有發現任何多項式指數嚴格少於 3 的 的演算法。那我們今天要聊什麼呢?我們來講一個比直接按照定義相乘還快一點點的 演算法吧!更正確來說,它的複雜度會是

1 拆成條狀

矩陣相乘傳統上除了拆成四個方陣或大致切成正方形的 Strassen 系列演算法以外,我們還可以考慮以下的拆解方式:

把左邊的矩陣拆成很多條 的長條矩陣 ,然後右邊拆成很多 的長條矩陣 。那麼原本的矩陣相乘就可以表示成:

對應到我們的 (min, +) 矩陣相乘就可以表示成:

於是,我們把一個 (min, +) 矩陣相乘問題拆解成了 個長條矩陣相乘的問題。如果我們仍然按照原本的方式進行計算,每兩個 長條矩陣相乘所花費的時間是 。因此傻傻地做顯然不會有任何好處,複雜度仍是紮紮實實地 。接下來,我們就要好好地針對 (min, +) 的性質探究一番啦!

2 (min, +) 性質

我們現在把注意力集中在一個 的長條矩陣 和另一個 長條矩陣 的乘積。令 是一個 的方陣。讓我們把矩陣的乘積寫開來:

決定性的觀察!

我們注意到,如果某個 是滿足 的最小的 ,那麼,對於所有的 兩邊的總和就會比較大:

移項之後我們可以發現這個不等號的兩邊可以只跟 有關係。

假設我們現在固定這個 。如果對於 我們預處理所有的 ,並且整理成向量的形式:

我們可以發現,若 是讓 的最小 ,那麼 就應該會是一個 維度的支配點對!這也解釋了為什麼這篇的標題是(四之二)而不是(五)了,嘿嘿。

分析

因此!可能會有一點點加速的空間,讓我們來分析一下!首先,我們枚舉所有可能的 值:這包含了 總共 種可能。每一次產生所有的 需要花費 的時間。然後花 的時間找出所有在 是「正確的最小值對應的註標」情形下的支配點對。由於最後乘出來的 總共有 個值,所有輸出的支配點對恰好加起來就是 個(演算法快就快在這裡)。

我們再把最外層拆成條狀矩陣的部份考慮進來,算得時間複雜度為:

該如何選擇 的值讓上面這個 upper bound 變小呢?我們可以發現當選取

的時候,會有

兩邊代入指數函數之後可以得到 ,因此選擇這樣的 值以後可以得到時間複雜度被右邊那項決定:

我們就得到一個 的 (min, +) 矩陣相乘演算法了!

3 所有點對最短路徑問題(APSP)

前面我們描述的是所有點對「走兩步以內最短路徑問題」,那如果我們想要計算所有點對真正的最短路徑,豈不是要計算 。注意到超過一定的次方以後,。我們可以利用倍增法,依次計算這些鄰接矩陣的「平方、平方、再平方」(這裡的平方觀念仍是 (min, +) 矩陣相乘)。

但是,如此一來,我們辛辛苦苦得到的解不就必須要多一個 倍,變成了 。這比大家比較熟悉的 Floyd-Warshall 演算法還要來得悲慘呀!

不過,好消息是,Aho, Hopcroft 與 Ullman 三位大師合作的一本書《The Design And Analysis Of Computer Algorithms》裡頭就有寫道(第 204 頁):利用自動機概念加上分而治之再加上類似 Strassen 流派的拆矩陣方法,只要能夠計算兩個矩陣的 (min, +) 相乘,整個 APSP 的時間複雜度與計算一次矩陣相乘的時間應該是一樣的!

礙於篇幅,只能請大家期待(四之三)了(呵呵…你以為說有就會有嗎)!想法不難,但是能想得到這個角度才真的厲害。

於是,總結我們今天的結論:我們可以在 時間計算兩個 (min, +) 矩陣相乘,並且在相同複雜度下找出任意實數值無負圈之一般圖所有點對最短路徑長度。耶。

4 參考資料

目前世界上最快的演算法是 [Chan '07]

下面這份投影片有一些更有趣的結果跟想法(包含隨機演算法)可以參考:

https://resources.mpi-inf.mpg.de/departments/d1/teaching/ss12/AdvancedGraphAlgorithms/Slides14.pdf

感謝 DJWS 提供的參考資源:

http://theory.stanford.edu/~virgi/cs367/lecture3-56.pdf

5 練習題

請求大家協助補充各大 OJ 的相關題目!

 
over 2 years ago

0 前言

在一個二維平面上,有很多個點,我們說一個點 支配(dominate)了另一個點 ,若且唯若點 的兩個座標都嚴格大於點 的兩個座標。如下圖:我們說 A 支配了 B;D 支配了 B、C。

一個直接的問題是:給定平面上 個點 ,要如何找出所有的支配點對?(或者是,我們想要知道總共有多少點對?)顯然在極端的情形下, 個點的支配點對的數量可以高達 個(例如他們座落在直線 上),但我們希望找出一個更有效率的演算法,在輸出量不到 的時候,能夠更快解決問題。

對於二維支配點對的問題,我們可以提出一個分而治之的演算法:我們先找出所有點 座標的中位數,然後把所有點分成兩群 以及 ,接著所有的支配點對要嘛就在 裡頭,要嘛都在 裡頭,要嘛比較低的在左邊、比較高的在右邊。分別遞迴找出 的所有支配點對,然後把 中的點依照 座標排序。排完以後兩個註標追趕的方式(保持右邊的點永遠比左邊的點來得高)就可以得知所有的點對了。

以下這支程式是表示如何求出支配點對的總數。如果預先排序好 軸,我們可以寫出以下的虛擬碼:

bool compare_by_X(const Point &A, const Point &B) {
    reutrn A.x < B.x || (A.x == B.x && A.y < B.y);
}
long long countDominatingPairs(vector<Point> &P) {
    vector<Point> L, R;
    if (P.size() <= 1) return 0;
  
  //第一步:找出中位數
 auto mid = nth_element(P.begin(), P.end(), compare_by_X);
  //第二步:把點分成兩邊
 for (auto &&p : P) {
        if (p.x < mid.x)
            L.push_back(p);
        else
            R.push_back(p);
    }
    //第三步:由於 Y 座標已經排序,我們只需要掃過兩個陣列計算支配點對的數量。
 long long cnt = 0;
  for (int i = 0, j = 0; i < R.size(); i++) {
        while (j < L.size() && L[j].y < R[i].y) j++;
        cnt += j;
    }
  //遞迴與回傳結果
 return countDominantPairs(L) + countDominantPairs(R) + cnt;
}

時間複雜度為 因此解得

1 維度更高的時候怎麼辦?

維度更高的時候,我們可以從最後一個維度下手。如果我們依照最後一個維度的座標值,選取了中位數以後,把這些點分成兩部份 以及 ,這時候我們雖然可以遞迴計算 之中的支配點對,但此時並非所有 都可以形成支配點對。因此我們需要修改一下題目,讓接下來的子問題都可以符合我們要的形式:

給定兩個 維空間中的點集合 以及 ,請計算(或找出)所有支配點對 。我們令 為輸入的總點數。

因此分而治之法也即將要完成了:首先我們考慮 根據最後一個維度座標值選取的中位數 ,然後把所有 中的點根據 各分成兩群:

注意到因為 是中位數,因此我們有 以及 (思考問題:若座標值有重複時,我們該如何選取?)。分別遞迴下去以後資料量都會減半,感覺挺好地。那麼第三部分呢?顯然此時我們只需要顧慮 的情形就可以了!而且,我們還可以把維度減少一維!

複雜度分析

的時候,我們可以用 的時間解決這題。假若我們要解決的問題是 個點、 維的問題。可以得到遞迴式:

解得

2 有沒有類似題?

有的!請參考 UVa 103 Stacking Boxes 雖然沒有太直接的關聯,但是大家可以想看看要怎麼把這題的解法用進去~(在實作上可能直接用 的動態規劃就行了。)

巢狀收納箱子問題,我們可以做到 ,不過細節有點複雜,就交給有興趣的同學們討論了!

 
over 2 years ago

0 前言

在快速排序法的演算法中,假若我們要排序的數字是 。每一次的遞迴我們都會選擇其中一個數字 作為基準(英文稱為 pivot,不過中文翻譯成衛兵就覺得頓失趣味了),然後把所有數字當中,比 大的分在右邊、比 小的分在左邊,接著遞迴下去。

如果運氣比較背,我們就會得到一種很偏頗的分法,比方說,每一次我們都挑到了所有數字中最小或第二小的數字。

因此,如何準確地選擇 pivot,是一個趣味的課題。如果我們用允許使用隨機演算法,則期望的時間複雜度為 。在 1973 年的時候,由 Blum, Floyd, Pratt, Rivest 與 Tarjan 發表了一篇確定性(deterministic,即不包含任何隨機成分)的演算法,可以利用線性時間找出這一群數字的中位數。如此一來,就可以很平均地把數字分成兩邊。也就能達到理想的 時間複雜度了。

順道一提這五位作者當中,除了 Pratt(對,就是 KMP 演算法裡面的 P)以外,其他四位作者都得過資訊界最高榮譽的圖靈獎(Turing Award)。這個演算法除了被稱為 Medians of Medians 演算法以外,也被趣稱為 Five Guys Algorithm(米國好像有一家美式漢堡連鎖店叫做 Five Guys)。

1 作法

為了求得中位數,我們把題目擴大一些,目標是找出第 小(或第 大)的數字。

首先,我們先將所有數字每 5 個一組,然後找出每一組的中位數。如下圖所示:

接著我們把所有中位數蒐集起來,然後找出這些中位數的中位數 ,這個數字就被我們拿來當做 pivot。

然後利用這個 pivot,重新把所有數字分成小於 pivot 的、或是大於 pivot 的兩組。

重點來了!我們保證,至少有 個數字比 pivot 來得小(如淺紫色部分,每一組有 被算入,至少有一半的組被算入)、也至少有 個數字比 pivot 來得大(如深紫色部分)。
由於我們知道確實 pivot 的兩邊有多少數字,我們可以輕易地知道第 小的數字出現在哪一邊,然後遞迴下去。
由於每一次遞迴下去至多只會剩下原本數字個數的 ,時間複雜度可以列式為:

展開後解得 (當然我們如果用數學歸納法證明,會更直接而快速。)

2 QuickSelect

如同 QuickSort 一樣,我們也可以隨機挑選其中一個元素,並且視情況遞迴下去。因為不一定會選擇小塊或大塊的部分遞迴,所以我們以最差情形做考量(才會有 max)。期望的比較次數為:

利用數學歸納法,解得期望時間複雜度為 。當然在實作上這個方法相較確定性演算法也比較輕量一些。

3 STL

基本上如果我們想找出任何支援迭代器(Iterator)的容器 當中的第 小元素,可以直接使用 stl::nth_element() 這個函式。

http://en.cppreference.com/w/cpp/algorithm/nth_element

 
over 2 years ago

0 緣起

極小值(minimal = local minimum)與最小值(global minimum)的差異在於,最小值必須小於或等於所有我們關心的數值,極小值只要小於或等於「附近」的數值就可以了。在很大一塊 Optimization/AI 的領域中,尋找極小值,一直都是滿重要的課題之一。不過我們今天來關心的是「離散版」的極小值。

1 簡單版的問題

在一個 大小的矩形土地上,每一格都有一個高度,而且所有的高度都不一樣。在下雨過後,水總是會往比較低的地方流過去。假設這個矩形土地以外的地方都是陡峭的山壁,請問你能不能快速找到一個積水的地方?也就是說,找到一個位置,使得這個位置相鄰的兩格(邊界處為一格)的高度都比這個位置來得高?

假設用來表達這一系列土地的高度已經給定於陣列 ,我們想要實作的是一個以下的函數:

int* findLocalMinimum(int A[], int n);

我們可以利用二分搜尋法來解決這個問題。

2 真正的問題

如果我們現在把問題改成 大小的矩形土地上,每一格都有著不同的高度。請你找出任何一格極小值。

性質

如果一個連通的區域,其邊界上最小值,與之相鄰的格子較低的那格若在這個連通區域內,則這個區域內必定有極小值。證明如後:我們從邊界上的最小值出發,由於所有高度都不相同,我們每一次可以往四周走一步前往更低的地方。最後停下來的格子必定落在這個連通的區域內(否則必定經過邊界而與當初所選取的「最小值」矛盾)。

一個分而治之的作法

我們可以藉由以上的性質,得到以下的分而治之演算法:每一次把邊界與正中間的十字區域中,最小值找出來。若這個最小值本身是極小值,那我們就找到答案了。否則的話,看看最小值隔壁更小的一格屬於以下 A, B, C, D 哪一個區域,然後把搜索範圍縮小到四分之一,記得把邊界也包含進去(為什麼?)。

效率分析

每一次我們花費 的時間掃遍整個矩形的邊界和中間十字部分,並且遞迴進入其中一個 的區域內。因此我們可以列式

解得

3 衍伸的問題

如果我們現在把問題改成 大小的矩形土地呢?

如果矩形是長條形狀的,每一次切十字所需要檢查的格子數會變成 。但事實上,若是一開始的情形,我們只需要檢查短邊就可以了:然後把狀況沿著短邊的方向切成兩半,直到矩形的形狀接近正方形,再套用回前一節的技巧即可。

如此一來,不妨假設 ,時間複雜度為

解得 。值得一提的是,當 的時候這方法會退化至 ;當 的時候這方法會退化至 ,剛好完美符合前面兩個題目的複雜度。

 
over 2 years ago

0 緣起

Divide and Conquer:分而治之法,又稱為各個擊破法。基本上就是把一個問題分成很多子問題,然後各自解決這些子題目(通常是用遞迴方法),接著再把這些子題目組合得出原本問題的解。

1 快速冪問題

給定 以及正整數 ,請計算 之值。

說明

的時候,我們知道答案會是 (若 )。當 的時候,我們知道如果 是偶數,那麼只要能夠算出 ,就可以得出 。若 是奇數,則我們可以先算出 ,然後利用 就可以得到我們要的解了。

兩種變化型態

通常我們會想要計算整數 次方除以 的餘數。我們有兩種 Divide and Conquer 的方式:一種是「先遞迴再相乘」,另一種是「先相乘再遞迴」。

先遞迴再平方

int bigmod(int x, int n, int p) {
    if (n == 0) return 1 % p;
  int a = bigmod(x, n/2, p);
  return a*a%p*(n%2? 1 : x)%p;
}

先平方再遞迴

int bigmod(int x, int n, int p) {
    if (n == 0) return 1 % p;
  return bigmod(x*x%p, n/2, p)*(n%2? 1 : x)%p;
}

超心機 Case:
另外還有一種情況,若輸入的 是 64-bit 整數,那我們要注意乘法是否溢位。

分析

由於乘法和可能的取模運算相對花費時間,我們衡量這個演算法的時間好壞,基本上可以著重於乘法的計算次數。注意到當 是奇數時,每個遞迴呼叫我們必須花兩次乘法。若 為偶數,我們則需要一次乘法。因此整個演算法所需要的乘法次數為 寫成二進位後有多少個

註記

我們也可以不寫遞迴,採用 bottom-up 的方式計算 ,通常我們會把這樣的方法(或技巧)稱為倍增法(doubling trick)。這樣的想法會不斷地在各式各樣的演算法裡頭出現。

2 應用在矩陣上

假設我們今天想要計算一個矩陣 次方,也可以用完全一樣的概念。

3 應用在多項式上

假設我們今天想要計算一個 次多項式的 次方,比方說 ,那麼計算 的時候就可以利用「倍增」或「分治」的概念。假設一個 次多項式和 次多項式相乘,所需要的時間為 ,那麼計算 次多項式的 次方需要花費多少時間呢?

首先我們假設在最平凡的情形下,我們花 的時間做多項式相乘。

讓我們來試試看「先遞迴再平方」的策略:假設時間為 我們可以列式:

這樣解得

如果是「先平方再遞迴」呢?假設時間為 我們可以列式:

這樣解得

4 思考問題

  1. 如果我們今天不模 取餘數,要做大數計算,請問「先遞迴再平方」跟「先平方再遞迴」何者效率較佳?為什麼?
  2. 如果今天有一個比較快的多項式相乘作法(請參考 CLRS 第 30 章),,那麼「先遞迴再平方」與「先平方再遞迴」的時間複雜度分別為何?
 
over 4 years ago

Hi, This a demo post of Logdown.

Logdown use Markdown as main syntax, you can find more example by reading this document on Wikipedia

Logdown also support drag & drop image uploading. The picture syntax is like this:

Bloging with code snippet:

inline code

Plain Code

puts "Hello World!"

Code with Language

puts "Hello World!"

Code with Title

hello_world.rb
puts "Hello World!"

MathJax Example

Mathjax

Inline Mathjax

The answser is .

Table Example

Tables Are Cool
col 1 Hello $1600
col 2 Hello $12
col 3 Hello $1