Re: [問題]找錢問題 不知道能不能在這邊問～

[ddavid (星舞絃獨角獸神話憶)]

    實際程式化的話是這樣，以{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
推 allen65535:專業的來了，我看不懂 XD
推 ddavid:補加上註解說明了。
※ 編輯: ddavid          來自: 140.112.31.182       (04/18 02:35)
推 weiluner:雖然我不是資工系的 但我已經有點了解 感謝大大們的回答딠
推 teves:你不是資工系的還要寫資工作業? 跑去修資工的課?
推 darkbuffoon:請問簽名檔的由來？
推 weiluner:我是生科系的 這是資工系開的生物資訊課程~
推 ddavid:簽名檔是自己的作品XD
推 tdk4:看原Po的簽名檔就知道你沒有研究魔術XD
推 SantaLucas:好奇學過魔術的人會怎麼改寫這句話？