Re: [問題]找錢問題 不知道能不能在這邊問～
實際程式化的話是這樣，以{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
推
04/18 02:17, , 1F
04/18 02:17, 1F
推
04/18 02:33, , 2F
04/18 02:33, 2F
※ 編輯: ddavid 來自: 140.112.31.182 (04/18 02:35)
推
04/18 11:53, , 3F
04/18 11:53, 3F
推
04/18 18:16, , 4F
04/18 18:16, 4F
推
04/19 07:40, , 5F
04/19 07:40, 5F
推
04/19 11:03, , 6F
04/19 11:03, 6F
推
04/20 03:54, , 7F
04/20 03:54, 7F
推
04/27 14:20, , 8F
04/27 14:20, 8F
推
04/29 11:22, , 9F
04/29 11:22, 9F
討論串 (同標題文章)
Inference 近期熱門文章
3
13
PTT遊戲區 即時熱門文章
37
48
17
19