**演算法筆記**
**2023/12/24 11:57**
https://web.ntnu.edu.tw/~algo/Industry.html
這個網頁目前遭到屏蔽，持續回傳403 Forbidden。我已經試誤找出屏蔽關鍵字組合，並且寄信請師大網管協助處理。~~也許選舉結束了就會恢復正常了，請各位耐心等候。~~
因為網頁流量太大，再加上網頁包含資料庫關鍵字，導致資安機制啟動。現已排除，謝謝師大網管人員！
---
**演算法筆記**
**2023/9/19 10:11**
Soft Body Simulation
https://web.ntnu.edu.tw/~algo/Simulation.html
---
**演算法筆記**
**2023/5/2 19:19**
Rigid Body Simulation
https://web.ntnu.edu.tw/~algo/Simulation.html
---
**演算法筆記**
**2023/1/11 12:33**
Logic
https://web.ntnu.edu.tw/~algo/Logic.html
---
**演算法筆記**
**2022/12/10 11:06**
手機版網頁更新。菜單過長的情況下，可以上下捲動。菜單、文章，可以左右滑動。圖片、文字區塊、程式碼，可以左右捲動。若有異常，歡迎留言。
如果沒有意外，手機版網頁操作流程就這樣定案。拖了三年終於還是自己動手做完了。
---
**演算法筆記**
**2022/12/2 14:42**
已修正，感謝！
<del>下面的count_distinct看起來也是怪怪的。稍等我幾個小時，我要重新涉獵和校訂Approximate Counting Algorithm。</del>
Flajolet–Martin Sketch也發現了錯誤，已經重新校訂。
---
**abt8601**
**2022/11/30 22:07**
[https://web.ntnu.edu.tw/~algo/AlgorithmDesign.html](https://web.ntnu.edu.tw/~algo/AlgorithmDesign.html)
在 Streaming Algorithm 中統計數字數量的第一個程式碼有問題，該程式碼沒有在 `array[i] == array[i-1]` 的時候增加 `c` 的值，導致計數的結果一直是 1。
---
**演算法筆記**
**2022/11/28 18:44**
Dynamic Programming (state / DAG) [revise]
https://web.ntnu.edu.tw/~algo/DynamicProgramming.html#4
Money Changing Problem [revise]
https://web.ntnu.edu.tw/~algo/KnapsackProblem.html#7
Word Wrap [revise]
https://web.ntnu.edu.tw/~algo/LocationAllocationProblem.html#5
Fourier Transform [revise]
https://web.ntnu.edu.tw/~algo/Convolution.html#3
---
**演算法筆記**
**2022/11/26 9:30**
一、syntax highlighter修復臭蟲、調校效能。
二、`<canvas>`觀看原始碼，啟動syntax highlighter。
三、Firefox複製貼上`<ul>`或`<ol>`，內容自動縮排（行首添加空白鍵）。這個問題目前無法解決。
四、Firefox現行版本將` `渲染成`U+00A0 No-Break Space`。Firefox複製貼上` `，不會得到空白鍵，而是得到`U+00A0`。這個問題的解決方式是避免使用` `，並且補上<code class="c">white-space: break-spaces;</code>以避免連續空白鍵合併成單獨空白鍵。另一種解決方式是避免使用小火狐，並且祈禱其他瀏覽器永遠不跟進該渲染機制。
---
**演算法筆記**
**2022/11/14 22:22**
原來如此。網頁確實寫錯了，感謝你抓到BUG！
我想了一下我為什麼寫<code class="c">c[j] = true;</code>。
我傾向修改14行<code class="c">int left = 0;</code>，而26行<code class="c">c[j] = true;</code>維持原樣。
```cpp=
int price[5] = {5, 2, 6, 11, 17};
int number[5] = {4, 5, 5, 3, 2}; // 各種錢幣的供應數量
bool c[1000+1];
void change(int m)
{
memset(c, false, sizeof(c));
c[0] = true;
for (int i = 0; i < 5; ++i)
// 各種餘數分開處理
for (int k = 0; k < price[i]; ++k)
{
int left = 0; // 沒有彈藥
// 由低價位到高價位
for (int j = k; j <= m; j += price[i])
// 先前的面額已能湊得，當前面額可以省著用。
if (c[j])
left = number[i]; // 補充彈藥
// 過去都無法湊得，一定要用目前面額硬湊。
else if (left > 0)
{
left--; // 用掉一個錢幣
c[j] = true;
}
}
if (c[m])
cout << "湊得到";
else
cout << "湊不到";
}
```
---
**換零錢小問題**
**Neil Huang**
Hello,
我已經找到問題了!如範例，要改成c[j] |= c[j-price[i]];
我在看背包問題內的https://web.ntnu.edu.tw/~algo/KnapsackProblem.html#4
範例跑起來發現怎麼湊都是湊得到，編輯到一半還不知道錯在哪，所以才離開，只想告知您而已。
謝謝
```cpp
int price[5] = {5, 2, 6, 11, 17};
int number[5] = {4, 5, 5, 3, 2}; // 各種錢幣的供應數量
bool c[1000+1];
void change(int m)
{
memset(c, 0, sizeof(c));
c[0] = true;
for (int i = 0; i < 5; ++i)
// 各種餘數分開處理
for (int k = 0; k < price[i]; ++k)
{
int left = number[i]; // 補充彈藥
// 由低價位到高價位
for (int j = k; j <= m; j += price[i])
// 先前的面額已能湊得，當前面額可以省著用。
if (c[j])
left = number[i]; // 補充彈藥
// 過去都無法湊得，一定要用目前面額硬湊。
else if (left > 0)
{
left--; // 用掉一個錢幣
c[j] |= c[j-price[i]]; //<==這裡
}
}
if (c[m])
cout << "湊得到";
else
cout << "湊不到";
}
```
---
**演算法筆記**
**2022/11/9 22:55**
感謝！網頁程式碼已經修正為你的實作方式了！
我也忘了考慮浮點數誤差。<code class="c">if (sumAB != sumC)</code>兩個浮點數直接判斷是否相等，肯定出問題。<code class="c">if (fabs(sumAB - sumC) < eps)</code>與<code class="c">const double eps = 1e-9;</code>才是正常做法。
教學文章越簡單越好。經過取捨，我選擇做一個懶人，把double改成int，歌舞昇平。
---
**abt8601**
**2022/11/8 21:34**
[https://web.ntnu.edu.tw/~algo/AlgorithmDesign.html](https://web.ntnu.edu.tw/~algo/AlgorithmDesign.html)
Freivalds' Algorithm 的實作似乎有問題，網頁中的實作會不斷重新計算 $B$ 中選中向量的總和（[維基百科頁面](https://en.wikipedia.org/wiki/Freivalds%27_algorithm)中提到的 $B \vec{r}$），因此時間複雜度為 $O \left(n^3\right)$ 而非 $O \left(n^2\right)$。
下方為 $O \left(n^2\right)$ 時間的實作。
```cpp
const int N = 10;
typedef double Matrix[N][N];
// Freivalds' Algorithm
bool verify_matrix_product(Matrix A, Matrix B, Matrix C)
{
srand(time(0));
// 驗算5次
for (int t=0; t<5; t++)
{
// 第二個矩陣，隨機挑選多個向量。
// 0是沒選中，1是選中。
bool column[N] = {};
for (int i=0; i<N; ++i)
column[i] = rand() % 2;
// 計算 B 中選中向量的總和。
double sumB[N] = {};
for (int k=0; k<N; k++)
for (int j=0; j<N; j++)
if (column[j])
sumB[k] += B[k][j];
// 以向量總和來驗算
// 逐次檢查各個元素
for (int i=0; i<N; i++)
{
double sumAB = 0, sumC = 0;
for (int k=0; k<N; k++)
sumAB += A[i][k] * sumB[k];
for (int j=0; j<N; j++)
if (column[j])
sumC += C[i][j];
if (sumAB != sumC) return false;
}
}
return true;
}
```
---
**演算法筆記**
**2022/11/5 22:22**
T-Join [revise]
https://web.ntnu.edu.tw/~algo/Matching2.html
負權重圖演算法正確性證明尚待確認。我讀過的組合最佳化書籍均採用相同證明方式，也都有相同漏洞。各位要是知道其他證明方式，麻煩留個言。
---
**演算法筆記**
**2022/11/2 19:51**
Shortest Path [revise]
https://web.ntnu.edu.tw/~algo/Path.html
Shortest Vertex-disjoint Path [revise]
https://web.ntnu.edu.tw/~algo/Path4.html
全站修正path定義，比照CLRS，「不允許點邊重複」改成「允許點邊重複」。這兩篇文章首當其衝。主要影響是「最短路徑是NP-complete問題」改成「最短路徑是P問題」。這可能影響考生成績，故特此公告。
其他文章應該不必更正內容，邏輯無矛盾。不過還是可能存在雖非故意但按其情節應注意並能注意而不注意者、雖預見其能發生而確信其不發生者。若您發現過失，懇請回報。
---
**演算法筆記**
**2022/10/16 19:48**
我要求救。如果你知道***Divide-and-Conquer Optimization***的出處是哪篇學術論文，麻煩你留言告知。謝謝。
***Divide-and-Conquer Optimization***是動態規劃的一種加速技巧。
https://cp-algorithms.com/dynamic_programming/divide-and-conquer-dp.html
---
**演算法筆記**
**2022/10/12 20:20**
Optimal Path
https://web.ntnu.edu.tw/~algo/OptimalPathProblem.html
---
**演算法筆記**
**2022/9/21 07:14**
Computational Mathematics
https://web.ntnu.edu.tw/~algo/about.html#3
---
**演算法筆記**
**2022/9/12 17:09**
Sound Effect [revise]
https://web.ntnu.edu.tw/~algo/Audio.html#4
Linear Equation: Conjugate Gradient Method [revise]
https://web.ntnu.edu.tw/~algo/LinearOptimization.html#4
---
**演算法筆記**
**2022/9/1 9:29**
Group
https://web.ntnu.edu.tw/~algo/Operation.html
Finite Field (Polynomial)
https://web.ntnu.edu.tw/~algo/FiniteField.html
Linear Cyclic Code
https://web.ntnu.edu.tw/~algo/Correction2.html
---
**演算法筆記**
**2022/6/20 11:00**
修正前言。今天才發現原來MathJax是client side。甚至可以直接使用官方提供的伺服器，不必安裝任何東西。
仍然有些東西很棘手：
一、預設字體搭配微軟正黑體，字體寬度不相稱，顯得很胖。
二、我在`<pre>`當中採用等寬字體。我不確定MathJax是否有等寬字體。然而 「要求TeX等寬」本身就是矛盾。
歡迎建議。
---
**演算法筆記**
**2022/6/19 15:03**
我試著追加Ubuntu Mono到CSS裡面，也許可以改善問題。
```css
font-family: "Cascadia Code", "Fira Code", "Consolas", "Monaco", "Ubuntu Mono",
"Microsoft JhengHei", "Microsoft YaHei Light", "Apple LiSung Light",
monospace;
```
第一排是英文字體（等寬字體），第二排是中文字體（非等寬字體），但是這些通通都是Ubuntu沒有的字體，不太可能fallback到第二排，而是fallback到最後一個項目：預設等寬字體。你的畫面照理來說應該要是預設等寬字體，但是不知為何不是。
好了，即便搞定了這個問題，字元還是無法完全整齊。總是有一些不支援的字元。終極解法是TeX（例如HackMD的dollar sign語法就是TeX的變種LaTeX）。然而，師大網頁空間不允許用戶在伺服器安裝軟體（例如MathJax），況且我也不懂TeX（反正隨時都可以學）。其他的方法像是MathML，我也不是很喜歡。所以目前就這樣吧，醜醜的，沒辦法。
---
**演算法筆記**
**2022/6/19 14:24**
你的畫面不是Fira Code！甚至不是等寬字體！雖然我不知道這是什麼字體，但是看起來有點像是Arial。
等寬字體(monospaced font)的意思是：無論哪種字元都是等寬的。無論是空白鍵還是EM Dash。你的畫面很明顯沒有對齊，原因是分子分母左方的空白鍵太窄，窄得不得了啦。
只要是等寬字體所支援的字元，保證等寬。不支援的字元，則會根據CSS列出的其餘字體來湊數。相異的等寬字體之間採用的寬度可能不太一樣，但是差異並不會太明顯，不可能像你的畫面那樣誇張。
下面是我特地使用Fira Code的畫面。中文是微軟正黑體、數學式子是Fira Code、不支援的字元應該是細明體：
下面是按照CSS設定所得到的畫面。數學式子主要是Cascadia Code：
微軟正黑體和Cascadia Code都是微軟出品。它們倆恰巧都比一般字體矮小，而且字體大小相襯。如果是微軟正黑體搭配Fira Code，那麼Fira Code就會顯得高高胖胖。為了搭配起來好看，所以我才把Cascadia Code排在第一，而把字元數量較多的Fira Code挪到後面。
小火狐有問題、金屬鉻沒問題，我猜可能是你無意間在小火狐的字型設定當中，強制指定了等寬字體是哪一個字體，而且指定的是非等寬字體。也可能是Ubuntu版本的小火狐有什麼特殊的設定，也可能是Ubuntu本身有什麼特殊的設定，但是我不熟悉Ubuntu。
HTML的`<pre>`排版正確，那是因為你的程式碼編輯器（文字編輯器），確實使用了某一種等寬字體。這部分跟瀏覽器無關。
---
**FHVirus**
**2022/6/19 11:44**
了解了，學到好多新東西，感謝大大 ><
我用的是 Ubuntu 22.04 和 Firefox ，裝了 Fira Code 的字型之後依舊沒有好，目前長的像是這個樣子：
但神奇的是去看 HTML 的 `<pre>` 裡面排版是好的，改用 chromium 開也是好的，應該是 Firefox 自己的問題。
---
**演算法筆記**
**2022/6/19 9:33**
據我所知 $cis$ 和 $cas$ 只有用於Hartley transform。沒有用於其他地方。如果你想要尋找相關資料，一種簡易的尋找方法是利用google搜尋 $cis$ 和 $cas$，關鍵字追加 $sin$ $cos$。這樣一來，搜尋結果就是三角函數的相關內容了。
我的第一條搜尋結果是維基百科：
https://en.wikipedia.org/wiki/Cis_(mathematics)
https://en.wikipedia.org/wiki/Hartley_transform#cas
Hartley transform 、$cis$、$cas$ 比較專業、比較偏門，學校課程、教科書不會介紹它們，只有專業書籍、學術論文才會介紹它們。如果你想要尋找相關資料，一種簡易的尋找方法是利用google book和google scholar。
google book，可以找到許多專業書籍。之後可以前往大學圖書館，操作公用電腦，下載電子檔：
https://www.google.com/search?tbm=bks&q=hartley+transform
google scholar，篩選2000年之後的論文，可以看到近期的相關應用：
https://scholar.google.com/scholar?q=hartley+transform&as_ylo=2000
我遇到Hartley transform是在LAME的原始碼。LAME是知名MP3 codec，聲稱用於教學用途的開源軟體。（MP3曾經是專利。也就是說LAME遊走灰色地帶。不過現在MP3專利已經過期了。）我以前曾經做過語音處理的工作，當時需要一個跨平台函式庫，可以同時用於桌機和手機。於是我用C++自幹一個快速傅立葉轉換，而同事建議我去看LAME。
https://github.com/zlargon/lame/blob/master/libmp3lame/fft.c
關於Hartley transform的效能，FFTW官方網站做了說明。大意是說r2hc跟Hartley transform差不多快，大可不必使用Hartley transform。FFTW是知名的快速傅立葉轉換函式庫，不過它說的不一定就是真理。你也可以再去找一找其他家的說法。
https://www.fftw.org/fftw3_doc/The-Discrete-Hartley-Transform.html
https://www.fftw.org/fftw3_doc/The-Halfcomplex_002dformat-DFT.html
網站上使用的等寬字體如下：
https://web.ntnu.edu.tw/~algo/style.css
```css
pre {
font-family: "Cascadia Code", "Fira Code", "Consolas", "Monaco",
"Microsoft JhengHei", "Microsoft YaHei Light", "Apple LiSung Light",
monospace;
}
```
我不確定你的電腦有哪些字體，因此我無從得知是哪種字體導致你的格式跑掉。一般來說，在各種等寬字體當中，只有「細明體」才會讓— (U+2014 EM DASH) 變成全形，而「細明體」是繁體中文瀏覽器（繁體中文作業系統）的預設等寬字型。根據上述CSS設定，當所有字體通通缺失，最後才會輪到細明體。嗯……我應該列出了各種作業系統的等寬字體，所以說我是不是漏掉了某款平板或手機瀏覽器的等寬字體？
你使用的作業系統和瀏覽器是哪一種呢？
另外，我預計格式跑掉的原因應該是 ⋅ (U+22C5 DOT OPERATOR) 和 𝑖 (U+1D456 Mathematical Italic Small I)，而不是 — (U+2014 EM DASH)。就我所知，目前沒有任何一個等寬字體支援這些特殊字元。
---
**FHVirus**
**2022/6/18 22:31**
https://web.ntnu.edu.tw/~algo/Wave.html#4
剛剛在研究哈特立轉換，看到較少用的那邊有 $cis$，不過 $cis(x)$ 一般較常表示 $\cos(x) + i \sin(x)$ ，不知道哪邊可以找到 $cis$ 和 $cas$ 的相關資料 ><
另外，分數的格式有點跑掉了，原因似乎是半形的——符號變全形了。
---
**演算法筆記**
**2022/5/11 18:57**
隨便做了一個適用於手機螢幕的版面配置。如果遭遇任何問題歡迎回報。
---
**演算法筆記**
**2022/5/11 18:50**
Network Science
https://web.ntnu.edu.tw/~algo/Data3.html
Matroid
https://web.ntnu.edu.tw/~algo/Matroid.html
---
**演算法筆記**
**2022/3/3 10:00**
Maximum s-t Flow: Karzanov's Algorithm
Maximum s-t Flow: Goldberg–Tarjan Algorithm
https://web.ntnu.edu.tw/~algo/Flow.html
---
**演算法筆記**
**2022/2/21 09:52**
https://twitter.com/googlesearchc/status/1470460215447465992
由於科高搜尋的內部錯誤，從去年12/14以後，本站所有新網頁皆未出現於科高搜尋。雖然我已經提交了sitemap，但是依然無法補救。如果你很介意、非常介意，那麼你可以暫時改用雅虎奇摩搜尋、百度搜索。實在是袂堪得呵咾。
---
**演算法筆記**
**2022/2/19 20:11**
我已將所有網頁的程式碼進行編譯、校訂錯誤。往後應該比較不容易出現低級筆誤了。
---
**演算法筆記**
**2022/2/19 08:08**
已修正，感謝。
這次的原因可能是：對i使用replace，程式碼慘不忍睹，於是手動修正，結果漏掉一個。
我看必須引進網頁版本C++編譯器，或者自己寫一個原始碼檢查工具，節省大家時間。否則這種低級筆誤肯定層出不窮。
---
**RH**
**2022/2/19 01:35**
https://web.ntnu.edu.tw/~algo/Matching.html#4
Maximum Bipartite Matching: Augmenting Path Algorithm 中兩份範例程式中主函式的 `DFS` 參數有誤（應為 **`DFS(x)`** 而非 `DFS(i)`）
分別在第 39 行（基本版）與第 28 行（預先配對版）。
---
**演算法筆記**
**2022/2/18 12:43**
Articulation Vertex / Bridge: Tarjan's Algorithm [revise]
https://web.ntnu.edu.tw/~algo/ConnectedGraph.html
Dominator: Lengauer–Tarjan Algorithm [revise]
https://web.ntnu.edu.tw/~algo/ConnectedGraph.html
Ordering
https://web.ntnu.edu.tw/~algo/Ordering.html
Scheduling
https://web.ntnu.edu.tw/~algo/Scheduling.html
---
**演算法筆記**
**2022/2/16 11:56**
報告一個BUG。若以https瀏覽本站，則（使用http網址的）\<iframe>內嵌影片無法正常顯示。
另一方面，一旦使用https瀏覽網站，往後瀏覽器遇到該網站，就會強制換成https，而且無法換回http，導致\<iframe>內嵌影片永遠無法正常顯示。
我目前想到的解法：將\<iframe>網址通通換成https，並且將本站網址全面換成https。如果大家有更好的解法，歡迎留言。
---
**演算法筆記**
**2022/2/13 08:07**
已修正，感謝。
我刷題習慣寫成a和b，謄寫到網頁要手動改成p1和p2，可能我不小心改錯了。然而我習慣用replace功能修改變數名稱，竟然漏了一個沒改到，也許當時是清明還是中元吧。
---
**RH**
**2022/2/12 15:37**
https://web.ntnu.edu.tw/~algo/Point2.html
「Sweep Line」−「平移的掃描線：座標排序」範例程式中第一個 `cmp` 函式有誤
應為 `return (p1.x <`**`p2.x`**`) || ...`
---
**演算法筆記**
**2022/1/23 10:40**
abb、aba、baa是筆誤。已經修正完畢，謝謝！
前面的「枚舉 {0,1,2,3,4} 所有排列」與後面的「枚舉 abb 所有排列」，這兩個段落是在不同時期撰寫的（也許相距五年以上吧），導致上下文不連貫，數字忽然變成了字元，莫名其妙。現在我已經統一換成數字了。文章閱讀起來應該通順多了。
---
**YA**
**2022/1/22 07:39**
https://web.ntnu.edu.tw/~algo/Backtracking.html#4
範例：枚舉 abb 所有排列，避免重複排列。
答案應該為 abb 、 aba 、 baa 。然而使用剛剛的程式碼，答案卻是這樣：
這裡好像有錯，abb、bab、bba
應該是這樣吧!?
不太會用這個東西，請見諒
---
**演算法筆記**
**2022/1/20 15:39**
Parallel Algorithm
http://web.ntnu.edu.tw/~algo/AlgorithmDesign.html
---
**演算法筆記**
**2021/12/29 04:43**
Approximation
http://web.ntnu.edu.tw/~algo/Approximation.html
---
**演算法筆記**
**2021/12/1 09:55**
先讓我囉嗦一下。網頁改版、章節調整，兩者沒有直接關係。
網頁改版，許多年才做一次。網站剛開始營運那時候，我每年都會進行大規模CSS改版，但是自從眼睛變差之後，就變懶散了。這導致粉色背景用了三年以上，灰色背景用了更久。粉色背景，應該是第六版或第七版，我沒有仔細數。更久以前還有綠色背景、藍色背景。
章節調整，屬於每日例行公事。這個網站可以想像成海量草稿，天天都會調整內容。如果造成你的不便，那麼麻煩你原諒我吧。
言歸正傳，你要的Maximal Rectangle應該是這個網頁：
http://web.ntnu.edu.tw/~algo/MaximumSubarrayProblem.html
前陣子，檔名追加了Problem。原因是我希望DP的三個子頁面（區間問題、選址問題、背包問題），網址尾端都有Problem，看起來比較整齊。順帶一提，DP子頁面本來預計還有一篇路徑問題，排在第一，但是我鴿了十年。沒意外的話，這將是有生之年系列。
你要的Simulation應該是這個網頁：
http://web.ntnu.edu.tw/~algo/Programming.html
Simulation和Modeling的地位比較尷尬。事實上，這兩個主題不是演算法設計方法，而是解題方法。這兩個主題應該放在哪裡，我一直拿不定主意。依照學習順序，我希望它倆盡早出現。依照分類方式，我希望它倆不要攪局。
我也想過改名，例如Modularization和Reduction，聽起來很有計算機科學那味。然而Modularization是程式設計方法、Reduction是演算法分析方法，它倆放在一起又變得怪怪的了。
最後再容我嘮叨幾句。首頁左上角的谷歌搜尋功能，可以找到各位想要的網頁。根據我的經驗，我每次修改網頁，谷歌最慢在一週內就會建立索引，最快甚至是隔天。然而，如果各位居住在需要科學上網才能谷歌的地方，那麼很抱歉，我沒招了。也許各位可以再來這裡留言，讓我有機會賣弄我的文采。
---
**chilin**
**2021/12/01 01:57**
您好，我是您網頁改版(還是粉色背景時)之前的讀者，我想請問一下之前似乎有提到類似[此題](https://leetcode.com/problems/maximal-rectangle/)的演算法，但現在改版後的網頁似乎找不到該頁面了，另外想請問一下改版後是否刪除了 ```simulation``` 這個章節呢？ 我印象中他原本安排在 ```Randomized Algorithm``` 後面，但現在找不到了，謝謝您
---
**演算法筆記**
**2021/11/29 11:11**
一、網頁標題頭尾對調，以符合搜尋引擎習慣。
二、網頁表頭追加<base target="blank">，超連結不再需要使用滑鼠右鍵開啟新頁面。
三、本來還想順便調整\<iframe>的loading="lazy"屬性。由於小火狐尚未實作完畢，只好留待下次處理吧。
當瀏覽器未自動更新網頁內容，網頁左上角菜單將顯示錯誤標題。如果你很介意、非常介意，你可以點選瀏覽器的⟳按鈕（快速鍵ctrl+r），迫使瀏覽器更新網頁內容。
---
**演算法筆記**
**2021/11/3 08:13**
String Searching [revise]
http://web.ntnu.edu.tw/~algo/Substring.html
感謝網友MaskRay。
---
**演算法筆記**
**2021/11/1 06:38**
Divisor [revise]
http://web.ntnu.edu.tw/~algo/Divisor.html
Partition
http://web.ntnu.edu.tw/~algo/Partition.html
Iterated Function
http://web.ntnu.edu.tw/~algo/IteratedFunction.html
---
**演算法筆記**
**2021/10/31 13:56**
Fraction
http://web.ntnu.edu.tw/~algo/Fraction.html
---
**演算法筆記**
**2021/10/14 15:11**
Number Theoretic Function
http://web.ntnu.edu.tw/~algo/NumberTheoreticFunction.html
---
**演算法筆記**
**2021/10/12 17:33**
Polynomial
http://web.ntnu.edu.tw/~algo/Polynomial.html
http://web.ntnu.edu.tw/~algo/Polynomial2.html
---
**演算法筆記**
**2021/8/19 10:43**
Matching [revise]
http://web.ntnu.edu.tw/~algo/Matching.html
---
**演算法筆記**
**2021/8/13 15:24**
是的。這樣的點，無論刪除多少，都不影響某些最大匹配，保證保留某些最大匹配。最後得到的完美匹配，不僅跟最大匹配的基數相等，也跟最大匹配的本身相符。
算法就是這樣得到的。看似是尋找匹配邊，其實是刪除未匹配點。刪完就是答案了。
圖論領域有一本經典教科書是West寫的《Introduction to Graph Theory》。很多課程講義引用他的證明，例如你提供的就是如此。然而他的證明相當簡略，畢竟人家不搞算法。
Hungarian method，這是算法作者Kuhn自己講的。Kuhn–Munkres algorithm，有滿多人這樣講的。KM algorithm，我目前只看過中國人這麼講。
---
**lpc**
**2021/8/13 11:29**
感谢您的回复。我去看了您提到的那本书，又想了下，确实是能从以下结论证明的：
> 從圖上任取一個未匹配點，如果找不到以此點作為端點的擴充路徑，那麼這張圖會有一些最大匹配不會包含此點。
我的思考如下：
从二分图的$X$部分按1~n的顺序找。假设$x_i$是第一个找不到增广路径的未匹配点，那么根据以上定理，$x_1\dots x_n$的最大匹配数与$x_1\dots x_{i-1},x_{i+1}\dots x_n$的最大匹配数相等。假设下一个找不到增广路径的未匹配点是$x_j$，那么$x_1\dots x_{i-1},x_{i+1}\dots x_n$的最大匹配数与$x_1\dots x_{i-1},x_{i+1}\dots x_{j-1},x_{j+1}\dots x_n$的最大匹配数相等。以此类推，把这些未匹配点都删除，最后得到一个完美匹配，这个数量还是和原图的最大匹配数相等。
关于Berge定理的这种表述，我想还是挺重要的，因为换成另一种表述，我完全看不出为什么只需遍历一遍。我之前找到的资料也几乎都是这种表述，如这个[lecture note](https://courses.cs.duke.edu/fall17/compsci330/lecture16note.pdf)。也很庆幸发现了您的文章，感谢您与我讨论。
关于我提到的那个结论，我写了程序暴力生成想要找到反例，但目前为止还没找到，所以我也还不确定到底是否成立。
> 匈牙利算法是最大**權**匹配的算法，而不是最大匹配的算法。你提供的所有連結，全都搞錯了這件事。
是的，大陆网络上这种误解比较常见。最大**權**匹配他们叫KM算法，虽然这和匈牙利算法是一回事。
---
**演算法筆記**
**2021/8/13 10:36**
> 從圖上任取一個未匹配點，如果找不到以此點作為端點的擴充路徑，那麼這張圖會有一些最大匹配不會包含此點。
即刻刪除此點，仍可找到這些最大匹配。更有甚者，最初就刪除此點，讓此點打從一開始就不存在，仍可找到這些最大匹配——然而我們無法預知此點，只能一邊計算、一邊刪除。
引入遞歸思想。每當發現這樣的點，就即刻刪除這樣的點，減小問題規模，減小圖的規模。
> 对于某个匹配M，如果p点作为端点找不到增广路径，那么对于之后更大的匹配M’, p点作为端点同样找不到增广路径。
先前結論不保證此處結論正確。事實上我覺得此處結論不正確，但是我懶得想反例。
如果M屬於M'，那麼此處結論有可能是正確的，但是我懶得想證明。
> Berge's lemma
> https://en.wikipedia.org/wiki/Berge's_lemma
>
> In graph theory, Berge's lemma states that a matching M in a graph G is maximum (contains the largest possible number of edges) if and only if there is no augmenting path (a path that starts and ends on free (unmatched) vertices, and alternates between edges in and not in the matching) with M.
> 在圖論當中，Berge引理是說：一張圖G的一個匹配M，當M是最大匹配，則M沒有增廣路徑，反之亦然。（增廣路徑是指：一條路徑，起點和終點是M的未匹配點，邊是M的匹配邊和未匹配邊交替出現。）
(⇒) proof by contrapositive。若M有增廣路徑，增廣之後匹配大小+1，顯然M不是最大匹配。
(⇐) 使用先前結論。這樣的點都刪除了。沒有點可以刪除了。剩餘的點全用上了。理所當然是最大匹配。
最後再提幾件事：
一、匈牙利算法是最大**權**匹配的算法，而不是最大匹配的算法。你提供的所有連結，全都搞錯了這件事。
二、我的證明來自《Network Flows: Theory, Algorithms and Applications》這本書。
三、我心中的資料可信度排名：首先是經過同儕審查的期刊論文，再來是專家的專著、專家的學校課程講義，再來是wikipedia、stackoverflow，再來是網民自編講義，最後是民科。你拿網民自編講義嘗試駁倒我這民科，那就跟小學生吵架沒有兩樣，級別太低。我建議你至少還是找幾本圖論專著來讀吧，那比較有說服力。
---
**lpc**
**2021/8/12 11:04**
您好，我是一名大陆的读者。我想请教你二分图匹配中为什么只需遍历一次比如左边结点。您写道：
> 從圖上任取一個未匹配點，如果找不到以此點作為端點的擴充路徑，那麼這張圖會有一些最大匹配不會包含此點。
>
这是对的，但是我觉得这个结论可能并不能保证不需要重复去找之前未能擴充路徑的端点。我看到一个结论，是说
>对于某个匹配M，如果p点作为端点找不到增广路径，那么对于之后更大的匹配M', p点作为端点同样找不到增广路径。
这能保证只需遍历一次。
我在好几个地方都看到这个结论，比如：
1. https://blog.csdn.net/qq_25379821/article/details/83721379
2. http://duanple.com/?p=411
3. https://www.bilibili.com/video/BV1fo4y197zA?from=search&seid=1397978860539034727 26分46秒的slide
但是证明并没有看明白。我尝试用您证明上述结论的方式去证明，但失败了。请问您知道这个结论怎么证明吗？
另一个问题是，英文资料中在讲述二分图匹配时常提及Berge定理，但不知为何，我没有看到提及您的上述结论以及我提到的结论的。请问您有看到这样的资料吗？
---
**演算法筆記**
**2021/8/11 12:15**
我方才找到了這本書的電子檔，才發現這些程式碼是你自己實作的。那麼我不客氣啦。我會抄錄到網站裡面，謝謝。
---
**演算法筆記**
**2021/8/9 07:00**
留言板我沒有存檔。http://web.archive.org/web/2019*/algonote.wordpress.com 留有少部分留言，但是沒有包含你的留言。
\| (l != r); 需要補上escape character \。我幫你補上去了。
如果左子樹小於等於樹根、右子樹大於樹根，那麼碰撞時加1。如果左子樹小於樹根、右子樹大於等於樹根，那麼碰撞時減1。大致上如此。
《Algorithms on Strings》我曾讀過，但是我已經沒有任何印象了。感謝你提供書中的程式碼，但是我可不能抄襲別人書中的程式碼。網站上的程式碼，第一個版本是我自己重新實作的，第二個版本是在網路上找到的。然而那兩個版本看上去都沒有比現在這個來的好。我要想一下怎麼處理。
---
**MaskRay**
**2021/8/9 3:37**
> 好久不見。我還記得你上次留言內容是KMP跟MP的差別，然後還有Shortest Unique Substring。我印象深刻。
感動～前者我也記得，後者印象已經模糊了。以前的留言板還有存檔嗎？
> 閉區間 `int id(int l, int r) {return (l + r) \| (l != r);}``
謝謝啓發。因爲我慣常使用[l,r)，就設法把這個表達式轉成適用於[l,r)的：
假設[5,8)分裂成[5,6)與[6,8)，那麼可以用這個方案
`int id(int l, int r) { return l+r & ~(l != r-1); }`
假設[5,8)分裂成[5,7)與[7,8)，那麼可以用這個方案
`int id(int l, int r) { return l+r-1 | (l != r-1); }`
昨天在一個聊天室裏有人說最長迴文子串的Manacher's algorithm難以理解，我就想起了你的Gusfield's Z algorithm (https://web.ntnu.edu.tw/~algo/Substring.html#6)和Manacher's algorithm的講解，推薦給了他們。
我在<Algorithms on Strings>書中的1.6 Borders and prefixes tables段落裏找到了一個挺優美的實作：
```
void prefixes(const char a[]) {
// pref[0] is initialized to 0
for (int f, g = 0, i = 1; a[i]; i++)
if (i < g && pref[i-f] != g-i)
pref[i] = min(pref[i-f], g-i);
else {
f = i;
g = max(g, i);
while (a[g] && a[g] == a[g-f]) g++;
pref[i] = g-f;
}
}
```
長度爲奇數的迴文子串的Manacher's algorithm可以類似寫作：
```cpp
r0.assign(n, 0);
r1.assign(n, 0);
// r1[i]: 以i爲中心的奇數長度最長迴文子串的長度爲2*r1[i]-1，延伸到i+r1[i]-1
for (int f, g = 0, i = 0; i < n; i++)
if (i < g && r1[2*f-i] != g-i)
r1[i] = min(r1[2*f-i], g-i);
else {
f = i;
g = max(g, i);
for (; g < n && 2*f >= g && s[2*f-g] == s[g]; g++);
r1[i] = g-f;
}
// r0[i]: 以i-1和i和i爲中心的偶數長度最長迴文子串的長度爲2*r0[i]，延伸到i+r0[i]-1
for (int f, g = 0, i = 0; i < n; i++)
if (i < g && r0[2*f-i] != g-i)
r0[i] = min(r0[2*f-i], g-i);
else {
f = i;
g = max(g, i);
for (; g < n && 2*f-1 >= g && s[2*f-1-g] == s[g]; g++);
r0[i] = g-f;
}
```
---
**演算法筆記**
**2021/8/8 17:17**
好久不見。我還記得你上次留言內容是KMP跟MP的差別，然後還有Shortest Unique Substring。我印象深刻。
你提供的連結，考察的是《Computational Geometry》那本書所提到的線段樹，不是競賽選手使用的線段樹。前者：儲存大量區間，查詢任意一個點屬於哪些區間，又或者查詢這些區間的聯集（并集）。後者：儲存一串數列，查詢任意的區間的總和。
關於連結裡面提到的論文，由於受到疫情影響，我目前無法進入圖書館取得論文。等到疫情緩和後，我才能了解詳細狀況。
關於Baltic OI 2001: Mars Maps，我是從刘汝佳那裡聽說的，下面是信件內容：
> 大陆这边最早出现是因为IOI98《形周长》，不过当时没流行起来。后来IOI2001的mobile出现，大家会了树状数组，同时也知道了那玩意还可以用线段树做。同年，Baltic OI 2001《火星地图》，官方解题报告好像把那个叫做segment tree的。后来大家发现这个有很多变形，但是思想差不多，也就没改称呼了，一直叫线段树。至于本来应该叫什么，我也不清楚
---
**MaskRay**
**2021/8/8 14:54**
版主你好，大概是10年後再一次留言:)
我今天看到這篇貼文考證了諮詢競賽中的線段樹的作者：https://endle.github.io/2021/08/07/who-invented-segment-tree/
---
**演算法筆記**
**2021/8/2 08:29**
我不是教授，我是民科。這個網站不是專著，而是筆記。話雖如此，黨國教育下的台灣，大部分的教授跟民科沒什麼兩樣就是了。以致你分不出差別吧。
我確定我有測試過"aaaaaaaaaaa"，也確定有用UVa 10526進行測試。我對照了兩邊程式碼差異，我推測是某次校訂的時候，一時手癢把 <code class="c">for (int n=1; n<N; n*=2) { CMP cmp = {rank, n, N}; ...</code> 改成 <code class="c">for (int m=2; m<=N; m*=2) { CMP cmp = {rank, m/2, N}; ...</code>，不小心玩壞了。原諒我吧。
至於CMP，還可以進一步縮寫：
```cpp=
void suffix_array(char* s, int N) {
int* rank = r[0], *new_rank = r[1];
for (int i=0; i<N; i++) {
sa[i] = i;
rank[i] = s[i];
}
for (int n=1; n<N; n<<=1) {
sort(sa, sa+N, (CMP){rank, n, N});
int r = 0;
new_rank[sa[0]] = r;
for (int i=1; i<N; i++) {
if ((CMP){rank, n, N}(sa[i-1], sa[i])) r++;
new_rank[sa[i]] = r;
}
swap(rank, new_rank);
if (r == N-1) break;
}
}
```
---
**Aaron**
**2021/8/2 03:05**
教授您好，我是Aaron，正在拜讀您的suffix array中的Prefix-doubling Algorithm程式碼，我過去也曾在這個網站上學習過許多其他演算法，真的獲益良多。
您在Prefix-doubling Algorithm使用的例子是"mississippi"，並能得到一個合理的sa，其中：
**sa = [10, 7, 4, 1, 0, 9, 8, 6, 3, 5, 2]**
但我將您的例子改為"aaaaaaaaaaa"時，預期得到的sa應該為一個嚴格遞減序列，但實際上如下：
**sa = [10, 9, 8, 7, 6, 5, 4, 0, 1, 2, 3]**
經觀察後推測，應該是下面的迴圈過早結束，由於代入cmp內的m只有一半，導致部分rank還沒機會被比出高下就結束了。
```C++
for (int m = 2; m <= N; m *= 2) {
CMP cmp = {rank, m / 2, N};
...
}
```
我認為將迴圈的判停條件設為**m < 2 * N**，應該可以解決這個問題，再次感謝教授提供的教學資源，suffix array中cmp的使用方式真的讓我驚艷不已。
---
**演算法筆記**
**2021/8/1 22:40**
<canvas>觀看原始碼的功能，已經修復完畢。
點選右上角圖示，即可觀看動畫原始碼。
---
**@birdca**
**2021/7/28 16:53**
可以 XD
感謝修正以及維護這麼優質內容的網站。
---
**演算法筆記**
**2021/7/28 13:50**
我這是很離譜的錯誤。似乎2012年發表之時就寫錯了，期間一直沒有檢查到這個錯誤。正確版本如下：
```cpp
// 宣告字元陣列（字串）。利用字串字面值進行初始化。
// 指定足夠空間：添上\0之後總共13個字元。指定的空間可以大於等於13。
// 可以編輯字元。
char s[13] = "Hello World!";
// 同上，交由編譯器自動計算空間大小：得到13。
char s[] = "Hello World!";
// 宣告字串常數，只記錄指標。一般需要添加const關鍵字。
// 不可編輯字元（未定義行為）。
char* s = "Hello World!";
```
背後原理龐大複雜，可以寫成長長一篇、讓新手崩潰的文章。內容涉及：指標pointer、陣列array、未定義長度的陣列array of unspecified length、陣列到指標的隱性轉型implicit conversion、字串C-style string、字串字面值string literal、字串常數string constant、指標的陣列array of pointers、陣列的指標pointer to array。為了社會大眾的心理健康著想，我可以選擇不解釋嗎？
---
**@birdca**
**2021/7/27 23:10**
[Data](https://web.ntnu.edu.tw/~algo/Data.html) > **程式語言的變數** > 程式第五行：
```cpp
char* s[10] = "Hello World!";
```
好像不太對？🤔
```cpp
char s[] = "Hello World!";
char *s2 = "Hello World!";
char *s3[10] = { "Hello World!" };
```
> 我試了這些都是可以在 C++ 正確執行的。
---
**演算法筆記**
**2021/7/27 20:17**
收到。謝謝。
---
**FHVirus**
**2021/7/26 15:29**
剛剛去翻了一下，在[這題](https://csacademy.com/contest/archive/task/strange-matrix/statement/) 的題解最下面的地方。
居然有證明，太感謝了！
另外，下面關於 SCC 的討論，應該是我在還沒有熟悉這個演算法的時候不小心混用兩種作法了。
兩個作法應該都是正確的，造成誤會及困擾非常抱歉。
---
**演算法筆記**
**2021/7/20 22:00**
關於線段樹，我想了一輪，你提供的方式 <code class="c">int id(int l, int r) {return (l + r) \| (l != r);}</code> 是最簡潔漂亮的解法。我會收錄到網站裡，謝謝。另外我也在Maskray的部落格找到類似的程式碼，不過他的版本比較複雜 <code class="c">int id(int l, int r) {return r-l == 1 ? 2*n+l : l+r;}</code>。
證明：一、如同二元搜尋樹，左子樹(l + r)較小、右子樹(l + r)較大、子樹樹根(l + r)介於之間。因此每個內部節點的(l + r)皆相異。每個外部節點的(l + r)顯然皆相異。然而內部節點、外部節點之間的(l + r)可能相等。外部節點是指樹葉（l == r）。二、如果(l + r)相等，那麼內部節點放在奇數位置，外部節點放在偶數位置。反過來亦可。程式碼是 <code class="c">| (l != r)</code>。
至於我先前提到的方法，實作出來會跟张昆玮的演算法大同小異，但是程式碼比較醜。就當我沒提過吧。
---
**演算法筆記**
**2021/7/20 09:14**
Numerical Recipe is a comprehensive book for a quick overview. But the implementation in the book is not being used in real world. Numerical algorithms usually get heavily optimized depending on hardware platform. Unfortunately I am no expert in that. If you have interest in FFT, you could google something like "FFT implementation in practice."
---
**Simon**
**2021/7/20 03:14**
Thanks alot to your FFT algorithm.
It help me to rewrite the fft program provided by Numerical Recipe.
[Testing](https://onlinegdb.com/j0HkWUzIn)
I add the input argument "isign", it with value of 1 and -1 for fft and ifft, respectively.
```c=
#include <stdlib.h>
#include <math.h>
#include <complex.h>
// Notice: Some library's complex.h do not support the macro "CMPLX"
#ifndef CMPLX
#define CMPLX(x,y) (double)(x)+(double)(y)*I
#endif
void swap(double complex* a, double complex* b)
{
double complex temp;
temp = *a;
*a = *b;
*b = temp;
}
// FFT compatible with double complex type of input data/signal
double complex* FFT ( double complex *data,
const int pts,
signed int isign)
{
// variables declaration
double complex *replica_data, w, wn, a, b;;
double theta, PI = 2.0*acos(0);
unsigned int i, j, k;
// memory allocation
replica_data = (double complex*)malloc(pts*sizeof(double complex));
for (i=0; i<pts; i++)
replica_data[i] = data[i];
// bit-reversal
for (i=1, j=0; i<pts; ++i){
for (k=pts>>1; !((j^=k)&k); k>>=1);
if (i>j)
swap(&replica_data[i], &replica_data[j]);
}
// FFT
for (k=2; k<=pts; k<<=1){
theta = -2.0*PI/(double)k*isign;
w = CMPLX(cos(theta), sin(theta));
for (j=0; j<pts; j+=k){
wn = CMPLX(1.0, 0.0);
for (i=j; i<j+k/2; i++){
a = replica_data[i];
b = wn*replica_data[i+k/2];
replica_data[i] = a+b;
replica_data[i+k/2] = a-b;
wn*=w;
}
}
}
if (isign == -1)
for (i=0; i<pts; i++)
replica_data[i] /= (double)pts;
return replica_data;
}
```
---
**演算法筆記**
**2021/7/19 17:21**
我這邊介紹的線段樹，top-down建立，總共4N-1格。如果要改成2N格，看來程式碼、圖片都得重新製作了。我想一下怎麼處理。慘囉原來我才是最搞笑的那位。
---
**演算法筆記**
**2021/7/19 10:26**
我把你的留言往上搬，方便判斷留言順序。
我的意思是wiwiho的資料是錯的。她的資料應該是源自oiwiki，那邊也是錯的。
full binary tree，N個外部節點（樹葉），N-1個內部節點，總共2N-1個節點。
binary tree資料結構使用陣列，樹根編號為1，左右小孩編號分別為2i、2i+1。因為第0格不能使用，所以陣列總共2N格。
區間查詢的情況下，將數列第0個數字放在最左端的樹葉，由左往右放，如此一來陣列仍是2N格。wiwiho/oiwiki沒有這樣做，而是硬生生加長陣列，把所有數字擠在同一層，才會得到4N-1。
我想可能是OJ題目很少要求記憶體用量，導致競賽選手不注重記憶體用量。競賽選手為了少寫一點程式碼，明明2N格就可以解決的事情，卻偷懶變成4N-1格，習慣很差。
順便請教一下「CSAcademy 某一題的題解」是哪一題？
---
**FHVirus**
**2021/07/18 20:44**
補個，樓主應該是誤會參考資料的意思了。
並非節點**數量**上限會到 $4N-1$，而是以左右子節點邊號為 $2i$、$2i+1$ 的話，
節點**編號**上限會到 $4N-1$，實際上有使用的還是 $2N-1$ 個。
如果不想要開那麼大的話，可以用以下小技巧（來自 CSAcademy 某一題的題解）：
```cpp=
// 節點維護範圍 [l, r]
// 我不確定是否 0base, 1base 都可以用
// 正確性我也不會證明
// 但是確實可用
int id(int l, int r){
return (l + r) | (l != r);
}
```
如此節點編號最多到 $2N$。
---
**演算法筆記**
**2021/7/3 18:33**
這個網站我知道。這是國教院（國立編譯館）頒布的標準，也是台灣教科書用語標準。然而cardinality是數學名詞，不是計算機科學名詞。cardinality源自集合論。
國教院也有出版《數學名詞》，其中cardinal number翻譯成「基數」。cardinal number就是cardinality，算是正式翻譯。我會修正網頁內容，謝謝。
https://books.google.com.tw/books?id=rqB_DwAAQBAJ&lpg=PP1&pg=PA43
順帶一提，雖然是標準，但是也能找到標準不一的例子。例如spanning tree的翻譯，五花八門：
https://terms.naer.edu.tw/search/?q=spanning+tree
| 出處 | 學術領域 | 英文詞彙 | 中文詞彙 |
| -------- | -------- | -------- | -------- |
學術名詞 | 數學名詞 | spanning tree | 展成樹 |
學術名詞 | 電子計算機名詞 | spanning tree | 跨距樹 |
學術名詞 | 工業工程名詞 | minimal spanning tree problem | 最小展開樹問題 |
辭書 | 資訊與通信術語辭典 | spanning tree algorithm | 跨距樹演算法 |
學術名詞 | 統計學名詞 | minimum spanning tree | 最小生成樹 |
辭書 | 資訊與通信術語辭典 | maximal cost spanning tree | 最大成本跨矩樹 |
學術名詞 | 數學名詞 | minimum spanning tree | 最小生成樹 |
學術名詞 | 數學名詞-兩岸數學名詞 | minimum spanning tree | 最小生成樹 |
學術名詞 | 電子計算機名詞 | minimal spanning tree{=MST} | 最短跨樹；最小生成樹 |
學術名詞 | 電子計算機名詞 | minimum spanning tree | 最小生成樹 |
順帶一提，中國中科院頒布的標準，請見：
https://www.termonline.cn/
台灣有許多數學名詞翻譯，故意和中國不同，甚至明顯翻譯錯誤（例如先前提到的點積）。原因我就不知道了。也許是美國怕軍事要塞失守、黨希望民眾思想混亂，諸如之類的。也許項武義、莫宗堅、康明昌他們那些老人家知道原因。
---
**drakeguan**
**2021/7/3 7:48**
在 http://web.ntnu.edu.tw/~algo/Matching.html 裏頭，看到你提到 `Cardinality ，尚無適當中譯`，好像的確是如此。
如果我們是日本或其它國家，專業領域的名詞都會有一份國家版翻譯。所以我有點好奇，台灣會不會也剛好有 Cardinality 在 CS 的翻譯，結果找到這 https://terms.naer.edu.tw/detail/3226986/.
| 出處/學術領域 | 英文詞彙 | 中文詞彙 |
| -------- | -------- | -------- |
| 學術名詞 (電子計算機名詞) | cardinality | 基準；基數 |
| 學術名詞 (電子工程) | cardinality | 關係基數 |
可以當作一個參考。
---
**演算法筆記**
**2021/6/20 15:18**
英文正式名稱是「cross product」，中文翻譯是「叉積」。鬼島歹丸的高中數學課本誤譯為「外積」，不知道是不是故意的。我印象中我曾向Allen講過這件事，不過他還是尊重高中數學課本的翻譯。
兩個向量的叉積應該是一個向量。輸入兩個向量，輸出一個向量。「cross product」是輸出向量，而不是運算過程。數學名詞大多用來指稱運算結果，而不是運算過程。
三維空間才有定義叉積，其他維度沒有定義叉積。換句話說，想要實施叉積，必須是三維向量。二維向量的情況下，其實需要假設輸入Z軸座標是0；根據公式，恰好輸出X軸Y軸座標是0。
叉積結果，再取絕對值（向量長度）（平方和、開根號），得到純量，恰好是平行四邊形面積（三維空間）。數學式子是|a×b| = |a||b||sinθ|。為什麼叉積恰巧得到三角函數值，我一直想不透根本原因。
---
**Howard**
**2021/6/20 00:51**
你好
我對 [point](https://web.ntnu.edu.tw/~algo/Point.html) 之中cross的演算有些疑問。
我認為向量的叉積運算應該得到向量，且為兩向量的法向量。
https://en.wikipedia.org/wiki/Cross_product
但你這邊卻用純量來考慮。
如果要得到純量，也許是叉積的平行四邊形的面積特性。
但這個純量有絕對值，因此沒有正負。
所以這個可以得到正負純量的叉積運算是不是有甚麼典故呢?
啊我找到了
http://allenchou.net/2013/07/cross-product-of-2d-vectors/
---
**演算法筆記**
**2021/5/30 19:47**
因為你看到的參考資料都是錯的。
full binary tree，N個外部節點（樹葉），N-1個內部節點，總共2N-1個節點。
---
**alan23273850**
**2021/5/29 21:46**
http://web.ntnu.edu.tw/~algo/Sequence2.html#3 有提到線段數的節點最多是 2N-1 個，但是大部分的參考資料 https://hackmd.io/@wiwiho/CPN-segment-tree#%E5%84%B2%E5%AD%98 都會說節點上限會到 4N-1 個，請問此等衝突該何解？
---
**演算法筆記**
**2021/5/1 13:47**
Sequence
http://web.ntnu.edu.tw/~algo/Sequence.html
Convolution [revise]
http://web.ntnu.edu.tw/~algo/Convolution.html
Residue [revise]
http://web.ntnu.edu.tw/~algo/Residue.html
---
**演算法筆記**
**2021/2/11 06:08**
競賽領域還有非常多DP主題：位元DP、樹狀DP、區間DP、座標DP、插頭DP、計數DP、期望DP、單調隊列優化DP、斜率優化DP、……。這些主題都是大家隨心所欲創造的，沒有什麼原則。我覺得這已經走火入魔了，我不會特地整理這些主題。
DP章節我拖稿超過五年了。因為網路資料極易取得，所以目前還沒有打算整理DP。
---
**alan23273850**
**2021/2/10 23:54**
今天遇到需要「數位 (digit) DP」的題目，感覺競賽很常出現，或許可以放在 dynamic programming 一章裡面的一節作補充。另外以前好像也聽過「狀態壓縮」的題型，可能也可以考慮一起放，謝謝！
(Digit DP 解說：https://hackmd.io/@amoshyc/rJtXgC_hw)
---
**演算法筆記**
**2021/2/8 08:46**
我是根據「勘誤的回覆的回覆」提到的測試結果：我的做法是錯的，BYVoid/Tarjan的做法是對的。而你的測試結果：兩邊都對。可能這段期間TIOJ測試資料變動了？可能你們兩位有人搞錯了？
我沒有TIOJ的帳號，也沒有找到管理者和出題者的聯絡方式，就將事情擱著了。我到現在還是不知道兩個做法的差別在哪裡。
---
**lawfung**
**2021/2/7 19:42**
哈嘍作者大大你好，我剛剛看了底下關於SCC的討論。
就我看起來無論是你的做法還是原始論文的做法都是正確的。
我也用前面留言的[扣的](https://pastebin.com/LGmtBtnb)做修改然後在TIOJ 1868測試
我測試起來也是無論用哪種作法都會AC
請問問什麼你說「如果可以想到一個反例就好了。而那個反例顯然就在TIOJ的數據庫裡面」呢？
謝謝！
p.s. 我應該可以聯繫管理員拿到測試資料，如果有必要的話
---
**演算法筆記**
**2020/12/3 10:00**
Point-to-Point Shortest Path: Label Setting Algorithm with Reweighting
http://web.ntnu.edu.tw/~algo/Path3.html
Predictive Language: LL Parser / LR Parser
http://web.ntnu.edu.tw/~algo/Language.html
Longest Increasing Subsequence [revise]
http://web.ntnu.edu.tw/~algo/Subsequence.html
Longest Common Subsequence [revise]
http://web.ntnu.edu.tw/~algo/Subsequence2.html
Sparse Linear Equation
http://web.ntnu.edu.tw/~algo/SparseLinearEquation.html
Polyhedron / Polytope
http://web.ntnu.edu.tw/~algo/Polygon.html
Graph Spectrum [revise]
http://web.ntnu.edu.tw/~algo/GraphSpectrum.html
Game Tree
http://web.ntnu.edu.tw/~algo/State.html
Representation
http://web.ntnu.edu.tw/~algo/Representation.html
---
**演算法筆記**
**2020/9/18 19:55**
有人回覆了，不過沒講到點上。詳情請見Anh Minh Tran的留言。
https://www.youtube.com/watch?v=wUgWX0nc4NY&t=870
---
**演算法筆記**
**2020/8/27 19:35**
剛剛發現這裡的SCC實作，跟我的版本相同。然後留言區也有人問了一樣的問題，然後一樣沒有答案。
https://www.youtube.com/watch?v=wUgWX0nc4NY&t=870
如果可以想到一個反例就好了。而那個反例顯然就在TIOJ的數據庫裡面。
---
**演算法筆記**
**2020/8/21 18:44**
已修正。感謝！
sort比qsort快。它們是不同的排序演算法。前者應該是introsort，後者應該是quicksort。
strcmp也大有玄機，不過這裡就不展開了。
https://www.google.com/search?q=sort+qsort+benchmark
https://www.google.com/search?q=gcc+stl+sort+algorithm
---
**FHVirus**
**2020/08/20 20:34**
http://web.ntnu.edu.tw/~algo/StringSearching2.html#2
針對 Suffix array 的地方， std::sort 應該並不慢？
對於長度1e5左右的 int 陣列試過，在 OJ 上跑的時間 std::sort 跟 std::stable_sort 都比 qsort 快喔><
---
**演算法筆記**
**2020/8/18 14:44**
Articulation Vertex / Bridge [revise]
http://web.ntnu.edu.tw/~algo/Component.html
更新一下low的描述。low是最高祖先（使用特定的走訪方式）。走訪方式有兩種不同定義，一種是many tree edges followed by 1 back edge，程式碼low[i] = min(low[i], visit[j])，另一種是many tree or back edges，程式碼low[i] = min(low[i], low[j])。其中tree edge只往下，back edge只往上。就第二種定義而言，遍歷順序將影響low值正確與否，但是完全不影響關節點、橋、雙連通分量、強連通分量的判斷結果。判斷這些東西，只需要任意祖先，不需要最高祖先。
---
**演算法筆記**
**2020/7/14 18:38**
原來TIOJ還在啊。有辦法聯繫上出題者拿到測試資料嗎？
我也補充一下，BYVoid的做法就是原始論文的做法。也就是說，我其實是在挑戰原始論文，我認為原始論文是錯誤的。
你提供的圖片當中，當起點是1，當DFS的遍歷順序是12345，那麼關於點4的low值，BYVoid的版本是3（使用dfn），我的版本是1（使用low），但是這個差異不影響正確答案。兩個版本都會得到正確結果。
```graphviz
graph graphname{
1--2;
2--3;
1--3;
3--4;
4--5;
3--5;
}
```
dfn就是visit。另外dfn改成low一樣是正確的。證明請見：
https://stackoverflow.com/questions/16250337/
兩個版本的主要差異在於if-else的地方。BYVoid的版本，一定會取小孩算low值；我的版本，不一定會取小孩算low值。
改成BYVoid的版本得到AC，那就表示出題者的程式碼和測試資料是BYVoid的版本。
---
**對於勘誤的回覆的回覆**
**2020/07/14 17:57**
在下寫的題目是[這題](https://tioj.ck.tp.edu.tw/problems/1868)
對於做法的正確性還在思考，目前只知道把程式碼換過來就會AC了。
可能是在下原本就是用不同的思路下去做，所以用了兩種想法拼在一起就錯了。
附上在下的[扣的](https://pastebin.com/LGmtBtnb)，希望能有所幫助。
麻煩您了。
補：不好意思，在下有一點不解，dfn 等價的應該是 visit？
---
**演算法筆記**
**2020/7/12 19:55**
Transitive Graph
http://web.ntnu.edu.tw/~algo/CompleteGraph.html
Chordal Graph
http://web.ntnu.edu.tw/~algo/ChordalGraph.html
---
**演算法筆記**
**2020/7/8 16:36**
網站搬遷
http://web.ntnu.edu.tw/~algo/
---
**演算法筆記**
**2020/7/6 21:24**
BYVoid的版本，i點的小孩j被強制納入計算：low[i] = min(low[i], low[j])。如果小孩j形成SCC，那麼小孩j不應該被納入計算。他這樣做應該是錯誤的，儘管我現在無法舉出實際例子。例子也許是這樣：j點恰好有cross edge或back edge，但是這條邊沒有回到i點的祖先，而是回到i點的左兄弟。
最後還是需要請你提供題目，以便進行確認。如果連測試資料都有的話，那就幫大忙了。
---
**演算法筆記**
**2020/7/6 07:47**
兩個版本對於back/forward/cross edge的處理方式稍有不同。
BYVoid的版本：使用dfn[j]。
我的版本：使用low[j]。並且精簡程式碼。
儘管程式碼看起來差異很大，但是我其實只是將dfn[j]改成low[j]。
dfn[j]改成low[j]難道是錯誤的嗎？我需要一個例子。
---
**演算法筆記**
**2020/7/6 00:33**
可以請你提供題目嗎？我用那個題目測試看看。
難道我的邏輯錯了嗎？我不太確定，我要花時間檢查一下。
---
**勘誤**
**2020/07/05 21:42**
Component 的那篇關於 tarjan 找 scc 的 code
從 // tree edge 那行開始應更正為
```cpp=1
if (!visit[j]){
DFS(j);
low[i] = min(low[i], low[j]);
}
// tree/back/forward/cross edge
// 已經遍歷過、但是尚未形成SCC的點
else if (instack[j])
low[i] = min(low[i], visit[j]);
```
正確性什麼的在下也不知道 qwq
參考的是[這篇](https://byvoid.com/zht/blog/scc-tarjan/)
改正之後寫題目就過了，所以這大概是對的吧 ><
麻煩大大了 :tada:
---
**演算法筆記**
**2020/6/16 08:38**
昨天網站持續回傳503，也許是上達天聽了。然而今天網頁伺服器依然送出Big5。所以我決定貼個連結。
http://n.sfs.tw/content/index/10436
看起來似乎是在AddDefaultCharset Big5開頭多打一個#就能解決問題了。萬分感謝！
另外我也檢查了各個教授的網站首頁，他們都有標註編碼。即便網頁伺服器沒有指定編碼，他們的網站應該還是可以正常瀏覽。
順帶一提，使用該伺服器的教授當中，葉梅珍用UTF-8、黃冠寰UTF-8和Big5兩個都用，其他教授都是Big5。照理來說，葉梅珍的網站應該要出現亂碼（沒有添加BOM），然而葉梅珍的網站沒有中文字元，所以一直以來沒有問題。黃冠寰使用UTF-8的網頁則都是亂碼，不過根據網頁內容來看，我想他應該是故意想要這麼做的。
至於師大資工系辦為何無法把那些老教授的網站搬去師大網頁伺服器（web.ntnu.edu.tw），這就不是我能提供答案的了。鷸蚌相爭漁翁得利？
---
**演算法筆記**
**2020/6/12 06:57**
我昨晚心血來潮，去除了所有網頁的BOM，結果就變現在這樣了。
師大資工的網頁伺服器似乎預設Big5編碼，而我的網頁是UTF-8編碼，於是網頁變成亂碼。
我試了.htaccess，然而網管似乎沒有開啟權限。我也想不到其他方法了。如果大家知道怎麼修改的話，麻煩教我一下。我實在是懶得再把BOM加回去了。
我有想過也許可以通知網管，請他直接在httpd.conf將我的網域改成UTF-8編碼。不過上次我去找網管是好幾年前的事情了，當時是直接衝進系辦公室搗亂，碰巧網管人在系辦公室。
當時的網管建議我趕快更換網頁伺服器。系辦的態度是：不打算開放免費網頁空間給系上師生使用。因為有幾位老教授仍有使用需求，所以系辦姑且還在維護網頁伺服器，但是所有新進師生都已經不能使用了。
我當時沒有找到合適的免費網頁空間，於是我就厚著臉皮繼續使用到現在了。系辦那邊沒說什麼就是了。只能說師大資工真的是佛心來著。
另外，如果網頁伺服器換成UTF-8編碼的話，谷歌翻譯、有道翻譯之類的網頁工具，應該就可以正常運作。之前有讀者反映這個問題，我當時的回覆應該是：我沒有網頁伺服器的管理權限，而且我本來就沒有立場使用師大資工的網頁伺服器。最後就擱置這件事了。
現在還在防疫期間，我應該沒辦法進入校園的樣子。如果事情就這麼繼續放著，會不會過幾天就上達天聽，忽然就修好了？又或者忽然就關閉了？來試試看好了。XD
---
**splitline**
**2020/6/12 05:38**
網站目前的 response header 是
`Content-Type: text/html; charset=big5`
而內文 encoding 是 utf-8，預設狀況會造成亂碼，不知道有沒有辦法修改XD
---
**演算法筆記**
**2020/6/3 07:22**
已經修正好了，謝謝！
整個網站只有這個頁面拼成breath。我想原因應該是我不小心寫錯字，原因應該跟海賊王無關。雖然現在連載頻率下降了，不過無論是演算法筆記還是海賊王都依然在繼續連載。
D之一族的梗到現在還沒有解開，究竟有沒有衰落也不知道。現在知名反賊都是D之一族，諸如革命軍首領、已被處決的海賊王父子、已被解散的王下七武海成員、超新星成員。D之一族知名度相當高、相當活躍，表面上看起來不像是衰弱的樣子。
---
**Allen**
**2020/6/02 01:50**
不好意思打擾了，在學習[Binary Tree Traversal](http://www.csie.ntnu.edu.tw/~u91029/BinaryTree.html)時發現介紹的
```
Level-order Traversal 層序遍歷
即是Breath-first Search。 # <- Should be Breadth
```
d不見了.. 請問這代表海賊王中D之一族的衰弱嗎?
---
**演算法筆記**
**2020/5/28 23:13**
Embedding
http://www.csie.ntnu.edu.tw/~u91029/Embedding.html
---
**演算法筆記**
**2020/5/28 16:39**
Transformation
http://www.csie.ntnu.edu.tw/~u91029/Transformation.html
---
**演算法筆記**
**2020/4/22 18:43**
這種點子，缺乏細節、缺乏因果推論，純粹是臆測，人人可以想出幾十幾百個。要嘛你把事情講清楚，要嘛廢話少說，歡迎討論演算法。
我聽過的，例如要不要出書、要不要群眾募資、要不要當補教老師、要不要當顧問、要不要接案、要不要找記者、要不要找民代、要不要找政府官員、要不要讀博、要不要當講師助教、……，這些廢話我都聽到膩了。要嘛你把事情講清楚，要嘛廢話少說，歡迎討論演算法。
---
**Mo**
要不要去面試一下國外廠商,
---
**演算法筆記**
**2020/3/21 15:09**
我提到的那些事項相當多，諸如程式碼行寬、表格橫向捲動、菜單按鈕、圖片縮放、字距行高、版面配置、……。而wix只能解決其中幾項，諸如版面配置、菜單按鈕。其他的項目還是必須自己處理呀。
台灣短期內不會有人幹CS相關的東西？這件事有點複雜，稍微講一下我的想法好了。
首先介紹大前提。台灣發展電子業、日本發展重工業、韓國發展化工業，這是二戰之後宗主國定下來的方針。台灣人身為戰敗國的戰俘，缺乏實力去干涉這個方針。生產半導體、換取F-16戰機，可以想成是向天子進貢、以尋求天子庇護。
台灣媒體順著這個方針，營造主體意識。大家腦內應該內建著「台積電是台灣知名的高科技公司」、「張忠謀是令人敬佩的人」。大家腦內應該沒有內建「宏達電是台灣知名的高科技公司」、「張忠謀跟連勝文的學經歷有87%像」。
因此，在台灣，計算機科學自古以來都不是台灣施政方針。民眾腦內沒有這種意識，而政府由民眾組成，於是政府就沒有這種方針。
至於政府目前的方針是什麼呢？看看科技部長陳良基的臉書文章，就能大抵知道目前施政方針。臉書文章當中，大多數是談半導體IC、談創業、談技術。跟計算機科學有關係的部分，就只有AI。勉強來說，政府還是有發展計算機科學，但只針對AI這個部分。
至於科技部推廣AI，究竟成效如何呢？這個我就不知道了，畢竟AI元年到現在也才三年，才剛開始而已。然而根據下面這篇文章，當初推動AI的陳良基、杜奕瑾、唐鳳，據我所知這三位都不是AI學者、AI工程師、AI市場分析師。我想可能要再觀望看看吧。
https://www.facebook.com/permalink.php?story_fbid=2595657210691306&id=1383694918554214
台灣能不能發展計算機科學？這是雞生蛋蛋生雞。實力不足於是眼光窄市場小，眼光窄市場小於是不願發展計算機科學，不願發展計算機科學於是實力不足。解方也很簡單：看大家想不想蹽落去。想做就強，不做就弱。懂得越多、想得越細、做得越好。就是這樣而已。
所以說，真正的問題是：台灣為什麼要發展計算機科學？台灣也可以發展其他行業，例如高精緻農業、貿易、觀光文創、電動機車、……，不見得要發展計算機科學。事實上我也不知道台灣應不應該發展計算機科學，目前資訊太少了，還需要收集更多資訊才能判斷，而我現在連要收集哪些資訊都不知道。不過解答也許很簡單：喜歡做的人就去做嘛，不喜歡就不勉強啊。
那我也只是提供一個管道，讓喜歡做的人，有機會做得更好一點。
當今世上，人類能做的事情太多了。有的需要數學和基礎科學，有的不需要。有的有趣，有的無聊。大家可以自己做選擇，適才適所。喜歡用前端和嘴砲搞定客戶的大屌，那也是能做的事情之一。喜歡做的人就去做嘛，又沒礙著誰。
只不過，如果大多數台灣人只能前端和嘴砲、只能輪班救台灣，沒有選擇的機會，甚至不知道有什麼可以選擇，那這樣不是超慘的嗎？我覺得演算法筆記的好處，就是給大家多一些選擇的機會。
好啦，講了那麼多，全是打高空。歡迎討論演算法。
---
**Mo**
如果不想花時間與金錢搞手機版相容網頁, try wix之類的網頁解決方案
基本方案是不要錢的
台灣短期內不會有人幹CS相關的東西, 眼睛裡只有台灣這種小市場, 不需要CS (其實是數學與基礎科學)的東西
用前端跟嘴炮就可以搞定客戶的大屌, 幹嘛花時間念無趣的數學？
---
**演算法筆記**
**2020/3/14 18:24**
因為本來就沒有圖片啊。還沒完成的章節，標題都會附帶(Under Construction!)。順帶一提Chordal Graph我已經拖稿7年了。雖然話這麼說，但是沒有意外的話，我會在有生之年將它完成。
---
**藍先生**
**2020/3/14 16:05**
http://www.csie.ntnu.edu.tw/~u91029/ChordalGraph.html
的圖似乎不見的
你的網站令我受益良多謝謝。
---
**演算法筆記**
**2020/2/3 19:08**
你忘記改稱呼了。
你說的沒錯，2G是2後面九個零。
1Kilo = 1000 = 10^3
1Mega = 1000000 = 10^6
1Giga = 1000000000 = 10^9
我少打了三個零，待會修正，謝謝！
這篇發表好幾年了，竟然錯了那麼久。如果你還有發現任何錯誤，麻煩繼續告知我，以便修正，謝謝！
---
**Tommy**
**2020/2/3 16:10**
請問「有了步驟數量之後，還可以進一步粗估執行時間。假設一個步驟需要 10 個 clock ，而電腦中央處理器 CPU 的時脈是 2GHz ：每秒鐘執行 2000000 個 clock ，那麼程式執行時間大約 12.4925 秒。」
上述的2GHz應該是2*10^9個clock對嗎?(若有誤解在麻煩更正小弟，謝謝)
---
**演算法筆記**
**2020/2/1 20:30**
Graph Laplacian Analysis
http://www.csie.ntnu.edu.tw/~u91029/Factoring.html
---
**演算法筆記**
**2020/1/29 08:20**
Correlation
http://www.csie.ntnu.edu.tw/~u91029/Correlation.html
---
**演算法筆記**
**2019/11/21 21:10**
以前也有人反映手機版網頁不友善。當時我回答沒有錢，後來這件事就不了了之了。這次我再解釋的詳細一點吧。
我沒有製作手機版網頁的知識與工具。我只寫了簡單的CSS：當螢幕寬度太小，則隱藏左方菜單。
想要讓網頁符合手機螢幕大小，必須調整很多東西，諸如程式碼行寬、表格橫向捲動、菜單按鈕、圖片縮放、字距行高、版面配置、……。由於我擁有製作電腦版網頁的經驗，我瞭解這些東西的背後隱藏著許多學問，並且需要花費很多心思去設計。我覺得啦，與其讓我這種一知半解又眼睛半殘的人來做，不如請專業人士來做。可惜我沒有錢。
不如說，「手機版網頁」不是重要的問題，「我沒有錢」才是更重要的問題。沒錢買飯吃，演算法筆記就要太監了，哪還有閒情逸致去管手機版網頁呢？
製作演算法筆記，沒有薪水也沒有退休金。整個台灣島沒有一個單位願意付錢僱人做這件事。背後的原因應該不單純。我可以舉一些例子。比方說，最近三任台大校長，一個被叫去研究超能力、一個不幸掛名造假論文、一個難產。又比方說，資訊學會只會頒獎和比賽，電腦學會頒發會士給蔣家親戚。
我打算全職製作演算法筆記，省吃儉用，做到破產為止。我的計畫是等待有錢人捐款，賭一把台灣人智商。
要是我能從有錢人手中拿到捐款，手機版網頁就不是什麼難題了──屆時就算我不付錢，也會有人願意主動幫忙吧。
---
**MarkTsai**
**2019/11/21 11:21**
從 PTT 拜訪貴站後，為了能嘗試不同地方用手機學習
嘗試用手機與小螢幕打開後，發現排版不友善
1. 導覽區塊的顯示
- 將瀏覽器（Chrome）縮小到 500px 時，右側的導覽列表佔了很大的空間，導致要拉到右側才能看到內容
- 在手機 (iOS Safari) 上導覽列會被隱藏，如果有小漢堡能開合導覽會更好
2. 文字過小
- 從手機 (iPhone 11, iOS Safari) 進入後，首頁的連結文字過小，需要額外放大
3. 程式碼與表格的排版（iPhone 11, iOS Safari）
- 在 Algorithm -> Algorithm 裡，時間複雜度、空間複雜度的 pseudocode 與複雜度表格會跑版
以上整理幾個小小狀況給大家參考～
---
**演算法筆記**
**2019/11/1 11:08**
剛才發現師大資工再度調整伺服器網址，www和www2都可以使用。
http://www.csie.ntnu.edu.tw/~u91029/
---
**演算法筆記**
**2019/10/3 19:20**
我一直以來都沒有關站的計畫。沒有不可抗力因素的話，網站內容將持續更新。另外，等我哪天收到有錢人的捐款，這輩子薪資有著落、生活有保障，屆時演算法筆記會弄成open source和public domain，但是我想應該不會弄成wiki。
歷年的師大資工網管都很好相處。我也從未聽過師大資工有驅逐演算法筆記的計畫。如果哪天師大資工網頁伺服器真的不給用了，我會想辦法再找個地方把網站放上去。
---
**演算法筆記**
**2019/8/21 05:55**
今早發現師大資工調整伺服器網址，www改成了www2。
http://www2.csie.ntnu.edu.tw/~u91029/
至於首頁的搜尋功能，要等谷歌重新爬完網站才能使用。我猜應該需要幾天吧。
```
路人乙:嚇死我了，我差點以為演算法筆記掛了! 幸好還活著!
```
---
**演算法筆記**
**2019/8/15 14:20**
Graph Data Structure [revise]
http://www.csie.ntnu.edu.tw/~u91029/Graph.html
---
**演算法筆記**
**2019/8/10 13:24**
啟用新留言板。
https://hackmd.io/@algorithm/B1CvppsmS
---
**演算法筆記**
**2019/8/3 9:07**
to Lo Season:
你的留言被系統自動分類成垃圾留言。我剛剛才發現你的留言，手動挪出垃圾桶。Wordpress常常判斷錯誤，今年又多了廣告，實在很不方便。我有空找找其他的留言板。
你說的完全正確。我再補充一下。
迴圈的變數k是BFS起點。如果圖有好幾個區塊，就有好幾個起點。下圖有三個區塊（其中一個區塊甚至只有一點），所以有三個起點0/2/5、三次if成立、三棵BFS tree。
http://www.csie.ntnu.edu.tw/~u91029/Component4.png
DFS的line #20也是同理，變數i是DFS起點。
那麼為什麼一個用k一個用i呢？這是因為我懶。照理來說應該要前後一致。
那麼為什麼不先介紹連通呢？也是因為我懶。教科書一般先介紹點、邊、子圖、連通、距離、樹、環，之後才介紹BFS、DFS。
那麼起點可以換嗎？可以。重新替每個點設定編號，起點就不同了。
那麼起點會影響最終結果嗎？會。BFS tree長相會改變，但是無傷大雅。不論長相，都很好用。
---
**演算法筆記**
**2019/8/3 8:36**
已經修正好了，謝謝。
迴圈變數應該是 for (int i = 2; i < n-2 ; ++i)
檢查2²到(n-2)²就可以了，1²和(n-1)²不用檢查。
---
**LFsWang**
**2019/8/2 19:40**
http://www.csie.ntnu.edu.tw/~u91029/Prime.html#6
用 22 當 example 介紹的部分有問題 2^2 ~ 20^2 應該是都不餘 1
Code square_root_primality_test
應該是 for (int i= 2 ; i<n-1; ++i)
---
**Lo Season**
**2019/7/30 23:54**
我大概懂你的意思但我還是確認一下好了，錯的話還請接正我(´・ω・`)
因為如果是連通圖的話在(k = 0)中的while裡面就會把所有的queue給pop出來，並且visit皆為true
之後k是在驗證是否所有的vertex都有被拜訪是這樣嗎?如果還有沒拜訪的點就代表連通失敗
同理DFS line:20
---
**演算法筆記**
**2019/7/30 17:41**
那層迴圈有必要存在，用來應付圖不連通的情況：雙向不通（中間沒有邊）、或者單向不通（那邊能過來，但是這邊過不去）。
---
**Lo Season**
**2019/7/30 16:08**
Graph中的BFS程式碼的13行(´・ω・`)
那層k的for loop 好像是多餘的? 還請你檢查一下謝謝!!(´・ω・`)
---
**演算法筆記**
**2019/7/12 20:40**
Fluid Simulation
http://www.csie.ntnu.edu.tw/~u91029/Motion.html
---
**演算法筆記**
**2019/6/6 7:51**
Linear Programming
http://www.csie.ntnu.edu.tw/~u91029/LinearOptimization.html
<style>code.c {border: 1px solid #000; margin: .33em !important;}</style>
Sign in with Wallet
Connect another wallet