# 演算法筆記 - Message Board **演算法筆記** **2020/7/14 at 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 at 17:57** 在下寫的題目是[這題](https://tioj.ck.tp.edu.tw/problems/1868) 對於做法的正確性還在思考,目前只知道把程式碼換過來就會AC了。 可能是在下原本就是用不同的思路下去做,所以用了兩種想法拼在一起就錯了。 附上在下的[扣的](https://pastebin.com/LGmtBtnb),希望能有所幫助。 麻煩您了。 補:不好意思,在下有一點不解,dfn 等價的應該是 visit? -- **演算法筆記** **2020/7/12 at 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 at 16:36** 網站搬遷 http://web.ntnu.edu.tw/~algo/ -- **演算法筆記** **2020/7/6 at 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 at 07:47** 兩個版本對於back/forward/cross edge的處理方式稍有不同。 BYVoid的版本:使用dfn[j]。 我的版本:使用low[j]。並且精簡程式碼。 儘管程式碼看起來差異很大,但是我其實只是將dfn[j]改成low[j]。 dfn[j]改成low[j]難道是錯誤的嗎?我需要一個例子。 -- **演算法筆記** **2020/7/6 at 00:33** 可以請你提供題目嗎?我用那個題目測試看看。 難道我的邏輯錯了嗎?我不太確定,我要花時間檢查一下。 -- **勘誤** **2020/07/05 at 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 at 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 at 06:57** 我昨晚心血來潮,去除了所有網頁的BOM,結果就變現在這樣了。 師大資工的網頁伺服器似乎預設Big5編碼,而我的網頁是UTF-8編碼,於是網頁變成亂碼。 我試了.htaccess,然而網管似乎沒有開啟權限。我也想不到其他方法了。如果大家知道怎麼修改的話,麻煩教我一下。我實在是懶得再把BOM加回去了。 我有想過也許可以通知網管,請他直接在httpd.conf將我的網域改成UTF-8編碼。不過上次我去找網管是好幾年前的事情了,當時是直接衝進系辦公室搗亂,碰巧網管人在系辦公室。 當時的網管建議我趕快更換網頁伺服器。系辦的態度是:不打算開放免費網頁空間給系上師生使用。因為有幾位老教授仍有使用需求,所以系辦姑且還在維護網頁伺服器,但是所有新進師生都已經不能使用了。 我當時沒有找到合適的免費網頁空間,於是我就厚著臉皮繼續使用到現在了。系辦那邊沒說什麼就是了。只能說師大資工真的是佛心來著。 另外,如果網頁伺服器換成UTF-8編碼的話,谷歌翻譯、有道翻譯之類的網頁工具,應該就可以正常運作。之前有讀者反映這個問題,我當時的回覆應該是:我沒有網頁伺服器的管理權限,而且我本來就沒有立場使用師大資工的網頁伺服器。最後就擱置這件事了。 現在還在防疫期間,我應該沒辦法進入校園的樣子。如果事情就這麼繼續放著,會不會過幾天就上達天聽,忽然就修好了?又或者忽然就關閉了?來試試看好了。XD -- **splitline** **2020/6/12 at 05:38** 網站目前的 response header 是 `Content-Type: text/html; charset=big5` 而內文 encoding 是 utf-8,預設狀況會造成亂碼,不知道有沒有辦法修改XD -- **演算法筆記** **2020/6/3 at 07:22** 已經修正好了,謝謝! 整個網站只有這個頁面拼成breath。我想原因應該是我不小心寫錯字,原因應該跟海賊王無關。雖然現在連載頻率下降了,不過無論是演算法筆記還是海賊王都依然在繼續連載。 D之一族的梗到現在還沒有解開,究竟有沒有衰落也不知道。現在知名反賊都是D之一族,諸如革命軍首領、已被處決的海賊王父子、已被解散的王下七武海成員、超新星成員。D之一族知名度相當高、相當活躍,表面上看起來不像是衰弱的樣子。 -- **Allen** **2020/6/02 at 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 at 23:13** Embedding http://www.csie.ntnu.edu.tw/~u91029/Embedding.html -- **演算法筆記** **2020/5/28 at 16:39** Transformation http://www.csie.ntnu.edu.tw/~u91029/Transformation.html -- **演算法筆記** **2020/4/22 at 18:43** 這種點子,缺乏細節、缺乏因果推論,純粹是臆測,人人可以想出幾十幾百個。要嘛你把事情講清楚,要嘛廢話少說,歡迎討論演算法。 我聽過的,例如要不要出書、要不要群眾募資、要不要當補教老師、要不要當顧問、要不要接案、要不要找記者、要不要找民代、要不要找政府官員、要不要讀博、要不要當講師助教、……,這些廢話我都聽到膩了。要嘛你把事情講清楚,要嘛廢話少說,歡迎討論演算法。 -- **Mo** 要不要去面試一下國外廠商, -- **演算法筆記** **2020/3/21 at 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 at 18:24** 因為本來就沒有圖片啊。還沒完成的章節,標題都會附帶(Under Construction!)。順帶一提Chordal Graph我已經拖稿7年了。雖然話這麼說,但是沒有意外的話,我會在有生之年將它完成。 -- **藍先生** **2020/3/14 at 16:05** http://www.csie.ntnu.edu.tw/~u91029/ChordalGraph.html 的圖似乎不見的 你的網站令我受益良多謝謝。 -- **演算法筆記** **2020/2/3 at 19:08** 你忘記改稱呼了。 你說的沒錯,2G是2後面九個零。 1Kilo = 1000 = 10^3 1Mega = 1000000 = 10^6 1Giga = 1000000000 = 10^9 我少打了三個零,待會修正,謝謝! 這篇發表好幾年了,竟然錯了那麼久。如果你還有發現任何錯誤,麻煩繼續告知我,以便修正,謝謝! -- **Tommy** **2020/2/3 at 16:10** 請問「有了步驟數量之後,還可以進一步粗估執行時間。假設一個步驟需要 10 個 clock ,而電腦中央處理器 CPU 的時脈是 2GHz :每秒鐘執行 2000000 個 clock ,那麼程式執行時間大約 12.4925 秒。」 上述的2GHz應該是2*10^9個clock對嗎?(若有誤解在麻煩更正小弟,謝謝) -- **演算法筆記** **2020/2/1 at 20:30** Graph Laplacian Analysis http://www.csie.ntnu.edu.tw/~u91029/Factoring.html -- **演算法筆記** **2020/1/29 at 08:20** Correlation http://www.csie.ntnu.edu.tw/~u91029/Correlation.html -- **演算法筆記** **2019/11/21 at 21:10** 以前也有人反映手機版網頁不友善。當時我回答沒有錢,後來這件事就不了了之了。這次我再解釋的詳細一點吧。 我沒有製作手機版網頁的知識與工具。我只寫了簡單的CSS:當螢幕寬度太小,則隱藏左方菜單。 想要讓網頁符合手機螢幕大小,必須調整很多東西,諸如程式碼行寬、表格橫向捲動、菜單按鈕、圖片縮放、字距行高、版面配置、……。由於我擁有製作電腦版網頁的經驗,我瞭解這些東西的背後隱藏著許多學問,並且需要花費很多心思去設計。我覺得啦,與其讓我這種一知半解又眼睛半殘的人來做,不如請專業人士來做。可惜我沒有錢。 不如說,「手機版網頁」不是重要的問題,「我沒有錢」才是更重要的問題。沒錢買飯吃,演算法筆記就要太監了,哪還有閒情逸致去管手機版網頁呢? 製作演算法筆記,沒有薪水也沒有退休金。整個台灣島沒有一個單位願意付錢僱人做這件事。背後的原因應該不單純。我可以舉一些例子。比方說,最近三任台大校長,一個被叫去研究超能力、一個不幸掛名造假論文、一個難產。又比方說,資訊學會只會頒獎和比賽,電腦學會頒發會士給蔣家親戚。 我打算全職製作演算法筆記,省吃儉用,做到破產為止。我的計畫是等待有錢人捐款,賭一把台灣人智商。 要是我能從有錢人手中拿到捐款,手機版網頁就不是什麼難題了──屆時就算我不付錢,也會有人願意主動幫忙吧。 -- **MarkTsai** **2019/11/21 at 11:21** 從 PTT 拜訪貴站後,為了能嘗試不同地方用手機學習 嘗試用手機與小螢幕打開後,發現排版不友善 1. 導覽區塊的顯示 - 將瀏覽器(Chrome)縮小到 500px 時,右側的導覽列表佔了很大的空間,導致要拉到右側才能看到內容 - 在手機 (iOS Safari) 上導覽列會被隱藏,如果有小漢堡能開合導覽會更好 2. 文字過小 - 從手機 (iPhone 11, iOS Safari) 進入後,首頁的連結文字過小,需要額外放大 3. 程式碼與表格的排版(iPhone 11, iOS Safari) - 在 Algorithm -> Algorithm 裡,時間複雜度、空間複雜度的 pseudocode 與複雜度表格會跑版 以上整理幾個小小狀況給大家參考~ -- **演算法筆記** **2019/11/1 at 11:08** 剛才發現師大資工再度調整伺服器網址,www和www2都可以使用。 http://www.csie.ntnu.edu.tw/~u91029/ -- **演算法筆記** **2019/10/3 at 19:20** 我一直以來都沒有關站的計畫。沒有不可抗力因素的話,網站內容將持續更新。另外,等我哪天收到有錢人的捐款,這輩子薪資有著落、生活有保障,屆時演算法筆記會弄成open source和public domain,但是我想應該不會弄成wiki。 歷年的師大資工網管都很好相處。我也從未聽過師大資工有驅逐演算法筆記的計畫。如果哪天師大資工網頁伺服器真的不給用了,我會想辦法再找個地方把網站放上去。 -- **演算法筆記** **2019/8/21 at 05:55** 今早發現師大資工調整伺服器網址,www改成了www2。 http://www2.csie.ntnu.edu.tw/~u91029/ 至於首頁的搜尋功能,要等谷歌重新爬完網站才能使用。我猜應該需要幾天吧。 ``` 路人乙:嚇死我了,我差點以為演算法筆記掛了! 幸好還活著! ``` -- **演算法筆記** **2019/8/15 at 14:20** Graph Data Structure [revise] http://www.csie.ntnu.edu.tw/~u91029/Graph.html -- **演算法筆記** **2019/8/10 at 13:24** 啟用新留言板。 https://hackmd.io/@algorithm/B1CvppsmS -- **演算法筆記** **2019/8/3 at 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 at 8:36** 已經修正好了,謝謝。 迴圈變數應該是 for (int i = 2; i < n-2 ; ++i) 檢查2²到(n-2)²就可以了,1²和(n-1)²不用檢查。 -- **LFsWang** **2019/8/2 at 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 at 23:54** 我大概懂你的意思但我還是確認一下好了,錯的話還請接正我(´・ω・`) 因為如果是連通圖的話在(k = 0)中的while裡面就會把所有的queue給pop出來,並且visit皆為true 之後k是在驗證是否所有的vertex都有被拜訪是這樣嗎?如果還有沒拜訪的點就代表連通失敗 同理DFS line:20 -- **演算法筆記** **2019/7/30 at 17:41** 那層迴圈有必要存在,用來應付圖不連通的情況:雙向不通(中間沒有邊)、或者單向不通(那邊能過來,但是這邊過不去)。 -- **Lo Season** **2019/7/30 at 16:08** Graph中的BFS程式碼的13行(´・ω・`) 那層k的for loop 好像是多餘的? 還請你檢查一下謝謝!!(´・ω・`) -- **演算法筆記** **2019/7/12 at 20:40** Fluid Simulation http://www.csie.ntnu.edu.tw/~u91029/Motion.html -- **演算法筆記** **2019/6/6 at 7:51** Linear Programming http://www.csie.ntnu.edu.tw/~u91029/LinearOptimization.html