JWorld@TW the best professional Java site in Taiwan
      註冊 | 登入 | 全文檢索 | 排行榜  

» JWorld@TW » Java 技巧文件 » UVA(ACM)討論  

按列印兼容模式列印這個話題 列印話題    把這個話題寄給朋友 寄給朋友    訂閱主題
reply to topicthreaded modego to previous topicgo to next topic
本主題所含的標籤
作者 110 Meta-Loopless Sorts 解題技巧
秒殺



版主

發文: 131
積分: 2
於 2009-02-04 17:01 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
這一題的特色是要寫一個會自動寫程式的程式
而且最討厭的是 if 語法會用到 else if
所以沒有搞清楚題義的話有可能會 WA 很多次
解這一題的關鍵是 "最佳化氣泡排序法"
不過由於不是真得做氣泡排序
而是把氣泡排序的流程變成暴力程式碼
所以不是兩個迴圈就可以搞定的喔
這一題大致上需要一個 8x8 的矩陣或半矩陣, 以及一個遞迴
動動腦筋一定可以解出來的喔
如果不明白什麼是最佳化氣泡排序法
先去 G 一下會比較知道該如何解題


reply to postreply to post
作者 Re:110 Meta-Loopless Sorts 解題技巧 [Re:秒殺]
yahoo1234tw





發文: 668
積分: 0
於 2009-02-04 17:25 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
請問什麼叫"半矩陣" ?

reply to postreply to post
專業的職業演員不會站在路邊演白戲,但是這裡有很多以寫程式為業的人很喜歡作賤自己跟別人,沒事就免費幫一些懶學生寫作業。
作者 Re:110 Meta-Loopless Sorts 解題技巧 [Re:秒殺]
秒殺



版主

發文: 131
積分: 2
於 2009-02-04 17:33 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
矩陣可以用來表示很多東西的交叉關係
例如匯率表如果有三種貨幣
就會需要一個 3x3 的矩陣
有時候 a-b 與 b-a 的關係一模一樣
這時候就沒有必要浪費 NxN 的記憶體空間 (不過最近 RAM 很便宜 ^^)
例如換匯如果雙向沒有價差
台>美 x(1/34), 美>台 x34
這樣就不需要 a-b, b-a 兩個都紀錄
下列的說明表示單向與雙向的差別

雙向矩陣:
1
2
3
4
- a b c
a x x x
b x x x
c x x x


單向矩陣:
(右上型)
1
2
3
4
- a b c
a - x x
b - - x
c - - -

(左下型)
1
2
3
4
- a b c
a - - -
b x - -
c x x -


NxN 的半矩陣比起原矩陣省掉很多記憶體
記憶體空間為 (NxN-N)/2
省掉的記憶體空間其實還蠻可觀的
一些常見的應用有這些

1. RPG 的場景轉換點
2. 交友關係表 (對等的情況下)
3. 戰略遊戲的交戰狀況表
4. 車資表 (例如: 台北>高雄, 高雄>台北 來回車資相同)

還有很多狀況下都有半矩陣的應用, 動動腦筋吧 ^^


秒殺 edited on 2009-02-04 17:41
reply to postreply to post
作者 Re:110 Meta-Loopless Sorts 解題技巧 [Re:秒殺]
yahoo1234tw





發文: 668
積分: 0
於 2009-02-05 16:57 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
雙向矩陣? 線性代數或是資料結構是用這個詞嗎? 還是哪裡有定義這個詞?

yahoo1234tw edited on 2009-02-05 17:04
reply to postreply to post
專業的職業演員不會站在路邊演白戲,但是這裡有很多以寫程式為業的人很喜歡作賤自己跟別人,沒事就免費幫一些懶學生寫作業。
作者 Re:110 Meta-Loopless Sorts 解題技巧 [Re:秒殺]
秒殺



版主

發文: 131
積分: 2
於 2009-02-05 23:09 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
資料結構的講法叫做
有向圖: N x N 方陣
無向圖: 1+2+...+(N-2)+(N-1) 三角形 (就是我說的半矩陣)
講無向圖沒辦法圖形化思考
所以我喜歡說矩陣,半矩陣,這樣比較有助於消化
動點腦筋就知道囉 ^^


reply to postreply to post
作者 Re:110 Meta-Loopless Sorts 解題技巧 [Re:秒殺]
yahoo1234tw





發文: 668
積分: 0
於 2009-02-06 12:06 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
秒殺 wrote:
資料結構的講法叫做
有向圖: N x N 方陣
無向圖: 1+2+...+(N-2)+(N-1) 三角形 (就是我說的半矩陣)

有向圖跟無向圖的定義是這樣嗎 @__@
越扯越遠

不是應該叫對稱矩陣跟上(下)三角矩陣嗎


reply to postreply to post
專業的職業演員不會站在路邊演白戲,但是這裡有很多以寫程式為業的人很喜歡作賤自己跟別人,沒事就免費幫一些懶學生寫作業。
作者 Re:110 Meta-Loopless Sorts 解題技巧 [Re:秒殺]
秒殺



版主

發文: 131
積分: 2
於 2009-02-17 13:39 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
那就歡迎你用教課書上的說法多寫一些文章吧 ^^

reply to postreply to post
» JWorld@TW »  Java 技巧文件 » UVA(ACM)討論

reply to topicthreaded modego to previous topicgo to next topic
  已讀文章
  新的文章
  被刪除的文章
Jump to the top of page

JWorld@TW 本站商標資訊

Powered by Powerful JuteForum® Version Jute 1.5.8