作者查詢 / springman

總覽項目：發文 | 留言 | 暱稱

作者 springman 在 PTT [ Prob_Solve ] 看板的留言(推文), 共89則

限定看板：Prob_Solve

看板排序：

全部Stock19551Gossiping9970Christianity1835ChangHua1760car1751nCoV20191329Lifeismoney1319HatePolitics1305EZsoft786NBA734MobileComm708Tennis705Browsers586VoIP554LaTeX544Disabled511Office454Google433AfterPhD428biker384IME381Broad_Band350Jeremy_Lin296IA293Windows241JesusLove206Instant_Mess150DYU148C_and_CPP147Free_box146Linux143study133AntiVirus130swim115Federer96Math96Badminton95Android93ONE_PIECE89Prob_Solve89Tech_Job87Teacher71Education61Golf50sky44Nets41PhD40Law-Service39ask-why37Programming37NetRumor32FITNESS31Fix-Network24iOS24MLB20Blog19Brethren19teaching16RegExp14AVEncode13AudioPlayer12Chiayi12Hornets11ask10DV10Kaohsiung10Lakers10BigPeitou9BigShiLin9ChungLi9Gov_owned9Hawks9Hsinchu9Keelung9Web_Design9WomenTalk9WorldCup9Ecophilia8Editor8Ajax7Bunco7Japan_Travel6java6JinYong6StockPicket6DSLR5Football5Knicks5GossipPicket4home-sale4joke4L_TalkandCha4LAW4Miaoli4specialman4Test4TW-F-Tennis4CD-R3Insurance3movie3NSwitch3Option3Rockets3SYSOP3tabletennis3UTAH-JAZZ3Wizards3Baseball2Celtics2ChicagoBulls2Facebook2Finance2MenTalk2NTUT_Talk2PHP2Siam-Star2Storage_Zone2Ang_Lee1Conan1Database1Donate-Blood1FCU_COOP1FCU_Talk1gay1HsinTien1Hualien1hwai1I-Lan1MAC1Mavericks1MdnCNhistory1money1MuscleBeach1Nadal1Nangang1NCU_Talk1PACERS1PingTung1Python1Salary1Tainan1TamShui1TW-history1TW-M-Tennis1WorkinChina1WorldCupGG1YoungArtist1<< 收起看板(147)

首頁

尾頁

[問題] 20 個數字分三堆使得最大的堆為最小

[ Prob_Solve ]7 留言, 推噓總分: +3

作者: singlovesong - 發表於 2012/01/07 13:36(12年前)

1^F推springman:這好像是 NP-complete 的問題吧01/07 20:44

6^F推springman:只是好像可以將 subset-sum 的問題 reduce 成這個問題01/08 18:59

7^F→springman:若沒想錯的話，應該是 NP-complete 沒錯01/08 19:00

[問題] 時間複雜度比較

[ Prob_Solve ]4 留言, 推噓總分: +1

作者: s97610017 - 發表於 2011/12/31 16:15(12年前)

1^F推springman:假設 n = 2^k，則 (lg n)! = k!，而 n^3 = 2^{3k}12/31 16:46

2^F→springman:k! 當然比 2^{3k} 大，都取 lg 的話12/31 16:46

3^F→springman:lg k! = k lg k，而 lg(2^{3k}) = 3k12/31 16:47

[問題] directed graph找shortest path

[ Prob_Solve ]16 留言, 推噓總分: +4

作者: mqazz1 - 發表於 2011/12/22 19:17(12年前)

1^F推springman:BFS 可以直接在 directed graph 上做，不必轉12/22 19:52

2^F→springman:將長度為 i 的 edge 轉成 i 條 edges 可能就可以12/22 19:52

3^F→springman:是 multistage graph 不是 multigraph ...12/22 19:54

4^F→springman:看起來 shortest path 與 longest path 的做法類似12/22 19:54

5^F→springman:有長度為負數的邊時應該也可以，因為沒有 cycle12/22 19:55

9^F推springman:因為每條邊的長度最多是 5，所以將長度為 i 的邊12/23 05:32

10^F→springman:轉成 i 條邊之後，邊數最多是 5|E| 條12/23 05:32

11^F→springman:代入 BFS 一樣是 O(V+E) 的時間內可以做完12/23 05:33

[問題] MST跟direction

[ Prob_Solve ]17 留言, 推噓總分: +5

作者: mqazz1 - 發表於 2011/12/22 19:11(12年前)

4^F推springman:不是biconnected的圖形似乎也可能是strongly connected12/23 05:36

5^F→springman:我想用 DFS 找 cycles 應該真的做得到，只是要想清楚12/23 05:37

[問題] 何謂 bottleneck spanning tree ?

[ Prob_Solve ]16 留言, 推噓總分: +3

作者: woody3724 - 發表於 2011/12/19 19:48(12年前)

10^F推springman:若 T 是 MBST 的話，其他 spanning tree 的最大邊都不會12/20 04:35

11^F→springman:比 T 的最大邊小。12/20 04:35

[問題] unbounded search

[ Prob_Solve ]6 留言, 推噓總分: +2

作者: mqazz1 - 發表於 2011/12/10 20:39(12年前)

1^F推springman:k 是最後找到 v 的位置吧，a[k] = v，對嗎？12/11 03:16

Fw: [問題] 如何實做一個不會重複的"六進位"?

[ Prob_Solve ]5 留言, 推噓總分: +1

作者: wa007123456 - 發表於 2011/11/11 18:11(12年前)

19^F推springman:這讓我想到大一時在寫八皇后的問題，怎麼都想不出來11/11 20:33

20^F→springman:後來有人提到用遞迴，將所有情形都找出來11/11 20:33

21^F→springman:然後每一種檢查是否符合條件11/11 20:33

22^F→springman:原以為只能這麼做，結果後來看到一位天才的同學11/11 20:34

23^F→springman:用八層迴圈一樣很快就跑出來，真的很天才。11/11 20:34

[問題] second shortest path

[ Prob_Solve ]28 留言, 推噓總分: +5

作者: singlovesong - 發表於 2011/09/18 09:18(12年前)

15^F推springman:找到 shortest path 之後，刪掉 shortest path 的一邊09/18 14:59

16^F→springman:再找 shortest path，有可能就是 second shortest path09/18 14:59

17^F→springman:shortest path 上每條邊刪掉一次、找 shortest path09/18 14:59

18^F→springman:照理說應該有答案，只是萬一所得到的答案都跟原來一樣長09/18 15:00

19^F→springman:怎麼辦呢？sorry，可能是我沒想清楚。09/18 15:00

21^F推springman:每條邊的長度若都是正的的話09/19 08:42

22^F→springman:可以先寫一個不限制simple path的shortest path的演算法09/19 08:43

23^F→springman:然後找起點的每個鄰居到終點的 shortest path09/19 08:44

24^F→springman:再加上前面的做法，好像會包含 second shortest path09/19 08:45

25^F→springman:不過不太確定...09/19 08:45

26^F→springman:最近好像都只在想 heuristic 的方法，沒有好的證明...09/19 08:46

首頁

尾頁