作者ddavid (星舞絃獨角獸神話憶)
看板Inference
標題Re: [問題]找錢問題 不知道能不能在這邊問～
時間Wed Apr 18 02:14:08 2007
實際程式化的話是這樣，以{25, 20, 10, 5, 1}來說：
// 隔這個define去取data[a]的值只不過預防取到a < 0，其中MAX_INT是個很大的值
// ，使得如果取到a < 0時給出很大的值，就會直接被min捨棄掉
#define DATA(a) ((a >= 0) ? (data[a]) : (MAX_INT))
// 價值0時用的硬幣數為0
data[0] = 0;
// 從價值1開始跑到MAX_NUM
for(i = 1; i < MAX_NUM; i++)
{
// 某價值所需最少硬幣，就是扣掉各個幣值後的各個價值中，選用幣數最少的那個
// 加上1
data[i] = 1 + min(DATA(i - 25), DATA(i - 20), DATA(i - 10), DATA(i - 5),
DATA(i - 1));
}
主程式這樣就搞定了，跑完data[x]就是代表x這個價值需要多少硬幣。
令m為錢幣種類數、n為要算的最大價值的話，這程式時間複雜度是O(mn)，會遠
比用多層迴圈硬幹的O(n^m)好上太多。
--
「去質疑親眼所見的事是最愚昧的行為。這又分為兩種－－質疑自己所見是不是
真的，或是用見到的事去質疑沒見到的事。呵。」
－－芙莉雅，謊言事務所實現使者
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.31.182
1F：推 allen65535:專業的來了，我看不懂 XD 04/18 02:17
2F：推 ddavid:補加上註解說明了。 04/18 02:33
※ 編輯: ddavid 來自: 140.112.31.182 (04/18 02:35)
3F：推 weiluner:雖然我不是資工系的 但我已經有點了解 感謝大大們的回答딠 04/18 11:53
4F：推 teves:你不是資工系的還要寫資工作業? 跑去修資工的課? 04/18 18:16
5F：推 darkbuffoon:請問簽名檔的由來？ 04/19 07:40
6F：推 weiluner:我是生科系的 這是資工系開的生物資訊課程~ 04/19 11:03
7F：推 ddavid:簽名檔是自己的作品XD 04/20 03:54
8F：推 tdk4:看原Po的簽名檔就知道你沒有研究魔術XD 04/27 14:20
9F：推 SantaLucas:好奇學過魔術的人會怎麼改寫這句話？ 04/29 11:22