解題觀念：
《這題的觀念好難打阿....不知道該怎麼打才能讓讀者看得懂！所以我盡力解釋！如果還有不懂在留言問我^^。》
這題的題意就是要算出一個數字用1、5、10、25、50去組合的話，總共有幾種組合方式。
比如6，它可以用6個1，也可以用一個5加一個1，總共有2種組成方式。
數字範圍則是0～3000，所以陣列大小可以很明確去定義。
那這題我的解法是，個別拆開計算。什麼意思呢？
舉例來說......
6，能用六個1組成，也能用一個5加一個1，但是不夠用25和50去搭配，所以共有2種方式。
這樣懂我意思嗎？？ 就是個別去計算它能用幾次1，幾次5，幾次25和幾次50。
沒關係，不懂的話等等看下面的EX。
所以這題不是輸入後去算答案，而是要使用者輸入數字後去找答案。
解題步驟：
這題用陣列解是最簡單的方法。
先宣告一個coin陣列和一個大小30001的money陣列。
並將 money[0]的初始值設為1。（因為數字1只有一種組合方式）
設一個for迴圈去跑coin陣列，在設一個內for迴圈去跑money陣列，要計算每個數字的組合方法有幾種。
內迴圈會從0～3000跑完後，外迴圈才會在進入下一個迴圈（coin[1])喔！！
也就是將所有數字1的組合、5的組合、10的組合、25的組合、50的組合都算過一遍 。
每個數字的組合方式都算好存在個別陣列中，使用者輸入數字後再去從陣列中尋找答案。
後面要設個判斷式，判斷輸入的數字是否為1，如果是的話直接印出只有一種方式。
不是的話，再去陣列找答案。
EX：
1
進入外層迴圈，coin陣列[0]＝1，進入內層迴圈money陣列[1]，
進入判斷式 1>= 1，符合 ＝＞money[1]+=money[1-coin[0]]
money[1]+=money[0]=1 （剛剛在前面已經把money[0]初始值設為1。）
所以當使用者輸入1時，進入判斷式money[1]==1，符合，印出....。
6
進入外層迴圈，coin陣列[0]＝1，進入內層迴圈money陣列[1]，
進入判斷式 6>= 1，符合 ＝＞money[6]+=money[6-coin[0]]＝1
（內層迴圈已經從1跑到5，所以money[5]=1）
＝＝＝＝＝當內層迴圈跑完3000了＝＝＝＝＝
再進入外層迴圈，coin陣列[1]=5，進入內層迴圈money陣列[6]，
（前面1～5就略過直接進入6吧）
進入判斷式6>=5，符合 ＝＞money[6]+=money[6-coin[1]]=1+1=2
（剛剛跑第一次迴圈的時候，money[6]的值已經有加1所以在加1為2。）
下次有在進入迴圈，coin[2]=25時，判斷式6>=25已經不符合所以不會再做計算，
（※前面1～4也是如此）
因此money[6]的值就是2，之後印出。
By 小K
沒有留言:
張貼留言