[生活趣事/生活週記]3/1-讀馬太二章&程式設計能力檢定(初級)

今天早上上完數位邏輯，
我跟著聖別學長到邵弟兄加吃飯讀經，
今日是讀馬太2章，
我藉著這次讀經才總算懂這個星象家原來是先走錯路，
之後才藉著聖經走回正確的路上，
之前這段好像看過去只覺得是星象家找到耶穌而已，
好深的含意在裡面都沒發現呀>_<
感謝主，今天的內容我得著了很多！

下午跟著聖別學長回到分部，
我就到PC室繼續解ACM～XD
解的差不多，
順應3月的到來，
我也順便把Blog背景換成春季綠意盎然的樣子了～
希望各位會喜歡！

晚上就是程式設計能力檢定(初級)，
有三題，
我都是硬爆XD"""
然後在快到8點的時候解完了，
接著我就回家了。

今天看來幻想迷宮是沒什麼進度就是了～XD

[UVa]357:Let Me Count The Ways

這題是DP的找零錢問題。

有幾種組合的算法，
由於可能會有重覆算到的關係，
所以要先加入最小的零錢(此題是1cent)進去，
看看各個值(小於等於30000)假設最後一枚硬幣為此零錢能用幾種方法(其實是dp[該值-加入的零錢價值]種)找出來，
接著再把次小的零錢(此題是5cents)放進去，
看看各個值(小於等於30000)假設最後一枚硬幣為此零錢能用幾種方法(其實是dp[該值-加入的零錢價值]種)找出來，
這樣以此類推到最大的零錢，
這樣我在算最後一個零錢是5cents的組合的時候，
我只會找出1cent跟5cents的組合，
不會找出配上10cents啦...25cents啦...或是50cents之類的組合。
等到我在算最後一個零錢是10cents的組合的時候，
我只會找出10cents跟5cents跟1cent的組合，
不會找出配上25cents啦...或是50cents之類的組合。
(如果看不懂以上內容，可以翻閱關於DP找零錢問題的教學文章。)

P.S. 這題要用long long Orz...

[C](0.020)

[UVa]147:Dollars

這題是DP的找零錢問題。

有幾種組合的算法，
由於可能會有重覆算到的關係，
所以要先加入最小的零錢(此題是5c)進去，
看看各個值(小於等於300.00)假設最後一枚硬幣為此零錢能用幾種方法(其實是dp[該值-加入的零錢價值]種)找出來，
接著再把次小的零錢(此題是10c)放進去，
看看各個值(小於等於300.00)假設最後一枚硬幣為此零錢能用幾種方法(其實是dp[該值-加入的零錢價值]種)找出來，
這樣以此類推到最大的零錢，
這樣我在算最後一個零錢是10c的組合的時候，
我只會找出5c跟10c的組合，
不會找出配上20c啦...50c啦...或是1元之類的組合。
等到我在算最後一個零錢是20c的組合的時候，
我只會找出5c跟10c跟20c的組合，
不會找出配上50c啦...或是1元之類的組合。
(如果看不懂以上內容，可以翻閱關於DP找零錢問題的教學文章。)

再來應該要建dp表，我們不可能用小數當索引值，
所以我們可以把該值乘上100在對應dp的那格為其答案，
但是浮點數乘法再配上轉成整數是避不開誤差的Orz...
因此請善用兩個整數來存值XD

[C](0.020)

[UVa]136:Ugly Numbers

這題要算第1500個Ugly Number是誰，
假設我現在要算第N項，
那麼我就找前面這N-1項中找出：
「乘2會大於第N-1項的那項」以及「乘3會大於第N-1項的那項」還有「乘5會大於第N-1項的那項」。
找出來後比較他們三個的大小，
最小的就是第N項。

接著要找N+1項，
我再從前N項中一樣找出：
「乘2會大於第N項的那項」以及「乘3會大於第N項的那項」還有「乘5會大於第N項的那項」。
那其實你再找「乘2會大於第N項的那項」，
你可以從「乘2會大於第N-1項的那項」開始往後搜，
就不用再從第0項開始搜。
找「乘3會大於第N項的那項」還有「乘5會大於第N項的那項」也可以比照辦理、以此類推。

這樣就可以很快速的找到第1500個Ugly Number了。^^

[C](0.020)

[UVa]102:Ecological Bin Packing

新站連結於http://knightzone.org/?p=1465