m(_ _)m http://www.csie.ntnu.edu.tw/~u91029/GreatestCommonDivisor.html
請問這裡面的擴充”歐基里德法”裡的”Iterative”的範例程式碼是不是要改成
1. int gcd(int a, int b, int& i, int& j)
2. {
3. int i_ = 1, j_ = 0, c = a, d = b;
# i = 0, j = 1;
4. while (true)
5. {
6. int q = c / d, r = c % d, t;
7. if (r == 0) break;
8. c = d; d = r;
9. t = i_; i_ = i; i = t – q * i;
10. t = j_; j_ = j; j = t – q * j;
11. }
12. return d;
13. }
不然會重複宣告
身為板主應該也是可以回應的吧？
偷偷踩一下
賀新居落成XD
歡迎歡迎呀。 : )
你貼了這則迴響之後，
我才發現原來迴響得要版主同意才會發佈，
於是我趕快去調整了一下網誌的設定，
現在不管是誰都可以馬上看到自己的迴響囉！
想問一下版主你的＜code＞＜/code＞，是自已在.css做的嗎?
還是有其他現成的樣板
不好意思，我在wordpress.com裡找到了@@”
我是在wordpress.com的FAQ裡面找到的：
http://faq.wordpress.com/2007/09/03/how-do-i-post-source-code/
DJWS,恭喜晉升Web2.0 XD
關於您所寫的LCS很棒,
但有一點我有疑問 可能是筆誤
在計算LCS長度中：
# for (int i=1; i<=seq1_length; i++)
# for (int j=1; j<=seq2_length; j++)
# if (seq1[i] == seq2[j])
// 這裡加上的 1 是指 ch1 的長度為 1
array[i][j] = array[i-1][j-1] + 1;
seq1和seq2若從i=1,j=1開始 那seq1[0] seq2[0]就無法計算了..
另外您那行駐解可以說清楚一點嘛 有點難理解xd
程式碼我改好囉，不過註解我倒是沒改。因為該程式碼是計算LCS的長度，而非LCS，所以遇到ch1的時候，就改為+1囉。
文章已經發佈在網誌上，歡迎移到該文章下繼續討論。
我該不該把我的連結改成連結這個網頁？
還是http://www.csie.ntnu.edu.tw/~u91029/的舊址？
都可以呀！我已經設定好轉址了，所以不管是用哪一個連結，最終都會到達一樣的網頁。:)
您好,我是來自湖南師大附中的一名高二學生,現為Vijos的管理員.
Vijos現為大陸最大的信息學奧賽(英文縮寫為OI,面向中學生,與ACM/ICPC區分開來)在綫評測網站(OJ),在OI領域有著較大的影響力.
您的ZeroJudge是我最近在搜索測試數據(測資?)的時候意外發現的.我們希望能夠與您合作,辦一次難度適當的比賽.不知道您的看法怎樣?
期待您的回復…
你好，
ZeroJudge並不是我架設的OJ。
不過我曾跟ZeroJudge的管理員通過信，
這是管理員的email：jiangsir@tea.nknush.kh.edu.tw
您可以直接聯絡他，洽詢比賽事宜。
非常感謝.
原來搬新家了
祝賀站運昌隆
我很羨慕會演算法的coder(因為我自己不會)
所以, 期待有更多關於介紹演算法的好文
GOGO～～
嗚…
迴響所填寫的email和URI並不會顯示耶
我本想偷打廣告一下的
好可惜…
不過沒關係啦
對了, 前面討論到的LCS 在wiki有碼 可以參考看看
http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
URL沒有顯示，不過直接點選使用者ID可以連到URL所在的網頁。email我就不知道為什麼沒有顯示了。
說到LCS，這裡再提供一份教學講義：http://www.csie.ntnu.edu.tw/~ice_acm/course/08032003/LCS.doc。
版主 您好:
sorry 請教一下，小弟印象中你有很多不錯的文章，像是算 點到點，或是線到線的距離，或是算凸包的算法，可是新版中我沒找到，請問版主可否告知怎麼找到那些文章
以前發表過的文章都放在這裡：
http://www.csie.ntnu.edu.tw/~u91029/menu.html
你想找的點對點、線對線距離，以及凸包的演算法，
可以在此頁面最下方的Computational Geometry欄位中找到。
該連結也可以在網誌的右方選單找到：
友站連結
* 美麗 C 世界
* DJWS的網路日誌─主選單 ＜－－這裡
* Lucky貓的ACM園地
* Sagit’s C++ 程式設計
網址更動之後，因為沒有在新網誌上特別提醒過，所以不太好找。不好意思啦。 (^_^”)>
你好,你的網站資料很豐富XD
不過有小地方寫錯了
http://www.csie.ntnu.edu.tw/~u91029/EnumerateAllSubsets.html
最下面的演算法應該更正為
1. int array[5] = {6, 7, 13, 4, 2}; // 可自行調整列舉順序
2. int subset[5]; // 用來存放一組可能的答案
3.
4. void recursion(int n, int N) // n是現在正在列舉的數值
5. { // N用來記錄子集合的元素個數
6. print_solution(); // 目前湊出來的集合
7.
8. for (int i=n; i<5; ++i)
9. {
10. // 加入 array[i] 這個數字 //原本寫成加入 array[n] 這個數字
11. subset[N] = array[i]; //原本寫成subset[N] = array[n];
12.
13. // 然後繼續列舉後面的數字
14. recursion(i+1, N+1);
15. }
16. }
17.
18. int main()
19. {
20. recursion(0, 0);
21. }
不然跑出來不是正確解答
嗯嗯
這篇還有印象吧
http://online-judge.uva.es/board/viewtopic.php?f=40&t=42251&sid=4cc332703e149e0ad220315f3dbe5e31
我已經找到錯誤了
謝謝
感謝你！程式碼已經修正好囉。
你在討論板的那篇問題我也有看到了。
請問站長大：
http://www.csie.ntnu.edu.tw/~u91029/0-1KnapsackProblem.html中
“找出所有的配置物品的方式”的範例程式裡的find_path是不是少了跳出條件?
感謝m(_ _)m
對耶，竟然少了跳出條件。
我改好了。謝謝你啦！
http://www.concretevitamin.com.cn/informatics/Pack/Index.html
大陸網友寫的背包問題詳解
提供給站長參考:P
系統竟然把你的留言當成是廣告留言了。好家在有看到。
謝謝你提供的連結，有機會我會好好看看的。
DJWS大您在flow – Max-Flow Min-Cut Theorem 說道:
﹝
由源點側流入到匯點側的水流總流量，
一定會小於等於由源點側穿越到匯點側的管線總容量。反方向亦同。﹞
我覺得有點奇怪 源點側流入匯點側不就是源點側穿越匯點側嗎 還是有什麼不同@@?
(flow的圖超多的 辛苦辛苦 > <)
還有在Flow:Ford-Fulkerson Algorithm想法的附圖
出現兩個標示為One Little Flow的圖 , 應是筆誤吧:D
其實我用了「流入」和「穿越」這兩個詞，並不是要強調兩者有差別，只是希望文句能夠活潑一點。不管是「流入」和「穿越」，我選用這些詞，是想要指出那些管線位於Cut上面，而且有方向性，是由源點側到匯點側。既然會造成誤解，所以現在我把「穿越」二字改為「橫跨」二字，文意上應該會清楚許多。
圖片修正好了，確實是筆誤。謝謝提醒啦。
您好，其實我只想說，這是一個非常棒的網站XD
我剛開始接觸ACM沒多久，已經多次從Google上面搜尋到此站的片段資料，覺得寫的很清楚易懂。今天才發現，原來是這樣的一個豐富完整的網站。
謝謝你。希望這個網站對你有幫助。
我會努力讓這網站變得更豐富的。
http://www.csie.ntnu.edu.tw/~u91029/GreatestCommonDivisor.html
下面Binary GCD的最後一個程式的第9,10行和11,12行重複了，是故意的嘛？
http://en.wikipedia.org/wiki/Binary_GCD_algorithm#Implementation_in_C
這個版本有些其他的加速技巧。
http://www.csie.ntnu.edu.tw/~u91029/ArticulationVertex.html
最下面的程式，第七行的vant是va嘛？
另外，我認為va應該是不需要用陣列的。因為每個點只需要其相鄰節點的va值來比較，所以只要利用函式回傳值，就可不用儲存va。
Binary GCD Algorithm我已經修正好了。如果我的網站內容有錯，那絕對不是故意的。有時候寫文件寫久了常常會疲倦、分心，所以常會有莫名其妙的狀況（尤其是程式碼）。也請各位多多包涵。
Wikipedia所記載的Binary GCD Algorithm實作，我會再研究看看（我可能有看過但因為複雜而沒有收錄，要不然就是我寫的時候Wikipedia當時還沒有相關資訊），目前我已經將網頁超連結放在文件之中。
Articulation Vertex的程式碼是筆誤，已修正。很明顯地，這呼應了我剛剛所說的。 : p
要實作va的概念，的確可以不需要用到陣列，改用函數回傳值也是可以的。不過我不知道哪一種會比較快、比較好就是了。感謝你提供這個想法。過一會兒，我會補上改用函數回傳值的程式碼，供大家參考。
最後，我不知道為什麼擋廣告留言的程式又把你的留言給擋住了。看來WordPress對於廣告防治有點太積極了。
我猜是因為有連結的關係，因為廣告幾乎都是有連結的。
WordPress管理介面有個選項可以調，我把它調成要出現五個連結以上才封鎖，結果還是常有踰矩攔截的問題。我猜可能他還有另外一種判定廣告的機制，再加上WordPress是英文系統，不認得中文字的關係吧。當然也有可能是擋廣告系統特別喜歡你的緣故。 : )
http://www.csie.ntnu.edu.tw/~u91029/Flow.html
從中找出一個最小割的程式中第20行的p是不是應該是visit?
你說的沒錯，是visit才對。謝謝你的提醒。
你好
因為最近修課的關係開始寫一些比較popular的C++問題
但因為自己程度很弱= =”
所以上網看到你這個很棒的網站!!!
可以請你在TSP(Travelling Salesman Problem)
的註解多寫一點嗎? 動規的方法我看不太懂
所以我想要只用Brute Force search寫
但Brute Force Search 最下面那段for我不大能理解= =”
感謝你
你提到的這個問題大約在半年前有人就跟我提起過了。我是很想把它寫得更詳細一點，但是目前沒有辦法馬上完成這件事情，因為我手上還有很多正等著要寫出來的主題。非常抱歉。
如果一切順利的話，一旦我完成了目前正在編纂的網路流（flow）問題之後，接下來會是匹配（matching）問題，然後會補上Optimal Assignment Problem、Chinese Postman Problem、Travelling Salesman Problem的動態規劃解法。然後會轉向著手編寫一些特殊資料結構的文章，以及字串比對演算法的文章。不過我想這時候我應該已經被徵招入伍了。
至於Travelling Salesman Problem的其他解法，像是基因演算法、螞蟻演算法，至少要等到退伍之後才有辦法寫。
最後是回應你的問題：如何用暴力法解TSP？你可以嘗試使用回溯法（backtracking）來解，只要把所有可能的路徑都列出來就可以了。回溯法是一個眾所皆知的TSP解法，網路上應該有不少資料，你可以試著多找找看，說不定連程式碼也都能找到。: )
非常感謝你的回答
你這個網站很棒!!
幫助我非常多
要繼續加油唷!!!!!
我會的。
m(_ _)m
http://www.csie.ntnu.edu.tw/~u91029/GreatestCommonDivisor.html
請問這裡面的擴充”歐基里德法”裡的”Iterative”的範例程式碼是不是要改成
1. int gcd(int a, int b, int& i, int& j)
2. {
3. int i_ = 1, j_ = 0, c = a, d = b;
# i = 0, j = 1;
4. while (true)
5. {
6. int q = c / d, r = c % d, t;
7. if (r == 0) break;
8. c = d; d = r;
9. t = i_; i_ = i; i = t – q * i;
10. t = j_; j_ = j; j = t – q * j;
11. }
12. return d;
13. }
不然會重複宣告
已修正。謝謝。 : )
提供一下GCD(a,b)=ax+by的迴圈解
由
int gcd(int a, int b) {
int r;
while (b) {
r = a%b;
a = b;
b = r;
}
return a;
}
得到
int gcd(int a, int& x, int b, int& y) {
int r, d; int A[2]={1,0}, B[2]={0,1}, R[2];
while (b) {
d = a/b;
r = a – b*d;
R[0] = A[0] – B[0]*d;
R[1] = A[1] – B[1]*d;
a = b;
A[0] = B[0]; A[1] = B[1];
b = r;
B[0] = R[0]; B[1] = R[1];
}
x = A[0];
y = A[1];
return a;
}
對不起冒泡了XD
剛剛才注意到
請不要理會上面那篇
呵呵，了解。
Bonjour
我是在找最小生成樹而發現你的blog
謝謝你 讓我了解 我上課都在上什麼
(因為都講法文 老師講話超快的)
請你繼續努力 幫助更多無助的人
真的是佛心來的
您好, 請問你會補 huffman compression algorithm 的 CODE嗎?
謝謝..
To karen,
謝謝。等我退伍之後我會繼續努力的！
To Cowardz,
一年內不會。
這應該是我認識的 DJWS 沒錯吧?
對呀就是我！
大大您好
因為最近修課正好在修演算法
遇到問題的時候上網看了一些您的解法感覺收穫真的很多
最近卻在銷售員問題上卡住了(Travelling Salesman Problem)
看到上面也有人提到
不過卻找不到資料在哪
可以請大大在提供一下借小女子參考嗎
我都是去書店和圖書館找書，以及用google找資料的。用google找資料是最方便的，關鍵字打進去，從第一個連結開始點進去找，找過三、四十個連結之後，資料差不多就齊全了。至於看不看得懂又是另一回事了。
hello, 你大概已經回部隊了, 在PTT上的文章 – 10290
我用取巧的方式AC了, 詳情可以上PTT看一下
Maximum Consecutive Sum的演算法是不是就是Kadane’s Algorithm？這可以推廣到二維n*n矩陣，我覺得蠻有趣的。
如果輸入的是0-1矩陣，在找maximum submatrix，似乎也存在有類似解Largest Empty Rectangle的算法。
看起來是的！最大連續和的演算法就是 Kadane’s Algorithm，不過我是現在才知道這演算法原來有個名字。
我記得UVa有一、二、三維的題目，我會把相關的資料整理一下，然後放到網頁上。另外我決定把 Maximum Consecutive Sum 改成 Maximum Subarray，後者應是正式的名稱。
感謝你提供的資訊，實在是惠我良多。:)
Maximum 0-1 submatrix的線性算法：
http://www.ddj.com/184410529?pgno=1
似乎跟Largest Empty Rectangle有點像？
我想應該會非常像。因為Largest Empty Rectangle其實就是Maximum 2D Subarray的特例。至於Maximum 0-1 Submatrix根本就是Largest Empty Rectangle了。
等到有長假時再來補充一下吧！
關於Josephus problem應該有不少有效率的方法吧，像是用搜尋樹或是遞迴公式。
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.5.177
Josephus problem
N個人 用DP解決只要O(N)很快了阿
搜尋樹或是遞迴公式 也要 >= O(N)
搜尋樹是怎麼個作法？
類似下面這兩個連結的做法
http://tclab.kaist.ac.kr/~otfried/cs206/notes/ranktrees.pdf
http://www.imt.ro/romjist/Volum12/Number12_1/pdf/02-MCosulschi.pdf
我粗略看了一下，這兩篇所提的方法的時間複雜度都是O(nlogn)。於是我猜這些方法應該類似於：把1到N的數字丟進binary search tree，然後進行N-1次的刪除動作。如此也是O(nlogn)。
可以請問版主未來的動向嗎?
我本來想走純軟,精進演算法則,
但是台灣科技業現階段的生態還是偏硬,
所以莫名其妙又走到韌體…
等我退伍之後會找份寫程式的工作，產品不胡搞瞎搞，工時合理，薪水足夠養家活口，就可以了。再老一點的時候，會弄個個人工作室，開發一些自己有興趣的軟體。再老一點的時候，應該會去擺小吃攤，賣好吃的，吃好吃的。再老一點的時候，打算讓小孩養，自己則是做點公益活動。以上是目前我所做的工作規畫。
你好:
我最近再找可以貼code的nopaste,但是都找不到我想要的style, 想請問你網頁上的code, 是用別人提供的nopaste還是自己寫的, 我覺得看起來滿好看的, 謝謝
我是拿這原始碼來改的：http://alexgorbatchev.com/wiki/SyntaxHighlighter
您好:
在Bitmask in Dynamic Programming主題中提到的TSP作法
某一行code為if (!dp[ss][i] || dp[s][i] + adj[i][j] < dp[ss][j])
其中!dp[ss][i] 是不是該改為 !dp[ss][j]
指的是還沒紀錄到j的最短路徑
我想應是如此 我已經測過uva的題目了
你說的沒錯！我修正它了，謝謝你。:)
您好
最近寫到UVa 10181 – 15 puzzle problem，並參考了您的網頁
http://www.csie.ntnu.edu.tw/~u91029/8PuzzleProblem.html
發現在判斷solvable的情況有點問題
http://mathworld.wolfram.com/15Puzzle.html
這裡算inversion時應該已經假設空白是在右下角
所以偶數為solvable
而初始盤面的空白不一定在右下角
如果自行移動到右下角在測試沒有問題
但如果要直接套用該函數，必須在最後結果加上空白的ow number
然後其sum為奇數為solvable，偶數為不可解
這個編程理論在以下的網頁
http://bal4u.dip.jp/mt/program/2006/05/uva-10181-15puzzle-problem-2.html
可以看到前面還是一樣算inversion，後面有加上r0，最後才判定
r0的意思就是0這個數字的row number
附帶一提，如果直接套用該函數而不加上空白的row number判定
UVa 10181的範例測資第一個就會是無解了
感謝你詳細的說明！是我搞錯了，現在已經修正囉。