錢幣的組合

程式設計

120131511 2012-03-30 11:42:53 ‧ 5255 瀏覽

分享至

演算法挑戰，假設某國有1到30元各不同的錢幣
問題一：
如果要組成27元，請問有幾種組合方式(非排列)
問題二：
如果要組成37元，請問有幾種組合方式(非排列)

krarm iT邦好手 1 級 ‧ 2012-03-30 23:26:14 檢舉

可以用排列組合!
也可以用dynamic programming!

登入發表討論

直播研討會

{{ item.channelVendor }} {{ item.webinarstarted }} |

直播中

1 個回答

wiseguy

iT邦超人 1 級 ‧ 2012-03-30 15:05:22

最佳解答

問題一：3010 種
問題二：21607 種
以下是 php 程式：

&lt;pre class="c" name="code">$kind=0;
ccc(30,27);
echo "27 kind={$kind}\n";
$kind=0;
ccc(30,37);
echo "37 kind={$kind}\n";

function ccc($max, $value)
{
	global $kind;

	if ($max > 0 && $value > 0)
	{
		$a = $value % $max;
		$b = (int)floor($value / $max);

		if ($max > 1 && $a > 0)
			ccc($max-1, $a);
		else
			$kind++;

		for ($i=$b-1; $i>=0; $i--)
		{
	        $d[$max] = $i;
			ccc($max-1, $value-($i*$max));
		}
	}
}

回應 14
分享
檢舉

看更多先前的回應...收起先前的回應...

120131511 iT邦研究生 4 級 ‧ 2012-03-30 16:07:18 檢舉

if ($max > 0 && $value > 0)
{

您的算法好像變成排列，而非組合
如1-3元錢幣要算3元有幾總組合
其組合有
111
12
3
三種，但您的演算法會有6種，變成排列了。

wiseguy iT邦超人 1 級 ‧ 2012-03-30 16:39:52 檢舉

樓主有 run 我的程式嗎？
ccc(3,3) 是 3 種沒錯啊。

php.exe -n ccc.php
3元幣=1個
2元幣=1個, 1元幣=1個
1元幣=3個
total=3

120131511 iT邦研究生 4 級 ‧ 2012-03-31 01:12:38 檢舉

抱歉 $kind++ 沒歸零，所以驗證有誤

120131511 iT邦研究生 4 級 ‧ 2012-03-31 02:04:31 檢舉

是否有其他演算法，如樹狀或統計函數，讓執行效率提高？

krarm iT邦好手 1 級 ‧ 2012-03-31 09:35:20 檢舉

dynamic programming

wiseguy iT邦超人 1 級 ‧ 2012-03-31 20:24:46 檢舉

沒錯，用 dp 可以加快百倍以上的速度，樓主可以試試將小弟的 function 改為 dp 版本，即可知效果。

wiseguy iT邦超人 1 級 ‧ 2012-03-31 22:22:45 檢舉

我自己以 dp 改寫後，測試 ccc(30,27)到ccc(30,77) 的結果。
原始函式的時間遞增得相當快，而動態規劃則變動很小。

&lt;pre class="c" name="code">ccc(30, 27)原始函式：quantity=3010  time:0.01195502281189
ccc(30, 27)動態規劃：quantity=3010  time:0.0011961460113525

ccc(30, 37)原始函式：quantity=21607  time:0.09086799621582
ccc(30, 37)動態規劃：quantity=21607  time:0.001121997833252

ccc(30, 47)原始函式：quantity=123839  time:0.54752492904663
ccc(30, 47)動態規劃：quantity=123839  time:0.0013818740844727

ccc(30, 57)原始函式：quantity=602422  time:2.803258895874
ccc(30, 57)動態規劃：quantity=602422  time:0.0016791820526123

ccc(30, 67)原始函式：quantity=2580573  time:12.635329008102
ccc(30, 67)動態規劃：quantity=2580573  time:0.0019540786743164

ccc(30, 77)原始函式：quantity=9974703  time:51.097416877747
ccc(30, 77)動態規劃：quantity=9974703  time:0.0023171901702881

120131511 iT邦研究生 4 級 ‧ 2012-04-01 02:00:22 檢舉

小弟用C#照 wiseguy大大的函式去跑，
ccc(12, 12)要35秒，
ccc(47, 47)超過30分鐘後都沒反應，只好中止，
還在找瓶頸在哪，原先想說用Threading去跑個別遞迴....
dp是不錯的解決方式
PS.電腦是ASUS B121平板/RAM 4G/OS windows 8 / VS 2010

wiseguy iT邦超人 1 級 ‧ 2012-04-01 09:35:06 檢舉

樓主是不是弄錯了什麼了？我用 php 跑，不管 ccc(12,12) 還是 ccc(47,47) 都不到一秒，C# 怎麼可能比 php 這種 script 語言還慢？我的電腦也只是 Core Duo E7200 2.53GHz + 3GB RAM，平板有差這麼多嗎？

&lt;pre class="c" name="code">ccc(12, 12)原始函式：quantity=77  time:0.019269943237305
ccc(12, 12)動態規劃：quantity=77  time:0.00022411346435547
ccc(47, 47)原始函式：quantity=124754  time:0.51868987083435
ccc(47, 47)動態規劃：quantity=124754  time:0.0037131309509277

120131511 iT邦研究生 4 級 ‧ 2012-04-01 16:27:21 檢舉

我也覺得很納悶。

120131511 iT邦研究生 4 級 ‧ 2012-04-01 16:39:54 檢舉

抓出兇手了，因一個紀錄顯示變數值的TextBox造成的問題，拿掉後就正常了，
只是時間還有點長ccc(50, 50)跑了21秒，不過比之前要快太多了。

wiseguy iT邦超人 1 級 ‧ 2012-04-01 19:56:36 檢舉

齁~ 原來樓主用 GUI 啊~ 難怪我說奇怪，C# 怎麼可能是這種速度？
這種演算法的東西，用 console 模式寫比較準啦~
要不然光是 GUI 處理就耗掉不少時間了

carl830 iT邦研究生 5 級 ‧ 2012-04-03 01:51:30 檢舉

我覺得加上GUI也不應該那麼慢吧
我用C寫(50, 50)也是瞬間出來 GUI有吃那麼重嗎@@?
複雜度也只有(coin數*目標值)而已吧

是說這題我覺得dp還比較簡單遞迴我反而還要想0.0"

wiseguy iT邦超人 1 級 ‧ 2012-04-03 10:15:05 檢舉

對啊！加上GUI也不應該那麼慢。別說用 C 了，我用 javascript 在網頁跑遞迴，(50,50)也是瞬間就跑完了。要超過10秒的，至少得算 70 元以上。不過這是不做 dp 的結果。改成 dp 跑 (70,70) 也花不到 0.1 秒。

這種題目用遞迴解，只需不到20行程式就解完了，dp是避免它重覆遞迴已經遞迴過的改善措施。所以小弟不明白 carl830 所言《dp還比較簡單遞迴我反而還要想》，意思是您不是用遞迴解的嗎？不用遞迴的話，程式碼不少喔？

登入發表回應

我要發表回答

立即登入回答

參賽組數

1064 組

團體組數

40 組

累計文章數

22205 篇

完賽人數

600 人

15th鐵人賽 16th鐵人賽 13th鐵人賽 14th鐵人賽 12th鐵人賽 11th鐵人賽鐵人賽 2019鐵人賽 javascript 2018鐵人賽 python 2017鐵人賽 windows php c# windows server linux css react vue.js

IT邦幫忙

錢幣的組合

1 個回答

樓主有 run 我的程式嗎？ ccc(3,3) 是 3 種沒錯啊。

我要發表回答

標記使用者

樓主有 run 我的程式嗎？
ccc(3,3) 是 3 種沒錯啊。