› 看板 C_and_CPP 關於我們 聯絡資訊
作者wa007123456 (大笨羊)
看板C_and_CPP
標題[問題] C和組合
時間Wed Oct 12 08:09:20 2011
最近遇到一個問題 =============================== 如果手上有50,10,5,1元可以使用 使用者隨便輸入一個數字當作金額 試問有多少種組合? =============================== 還滿有趣的! 一開始我在想程式要怎麼學會分堆@@ 後來想法是先數學化 50x+10y+5z+a=輸入的數字 很像我高一學的一個題目 "求非負整數解個數" 但是因為係數不同... 加上電腦的數字有限制範圍 必須要用到大數的乘法... 一整個囧! 希望有大大能夠解答! 感謝:) -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 125.226.15.183 ※ 編輯: wa007123456 來自: 125.226.15.183 (10/12 08:10)
→ diabloevagto:如果要用到大數的，網路有一堆寫好的... 10/12 08:14
推 ericinttu:為什麼要用大數乘法? 10/12 08:27
推 Bencrie:怕階乘爆掉吧 XD 10/12 08:47
→ tropical72:希望你對這題也有興趣 http://ppt.cc/apkB 建議先不考 10/12 13:31
→ tropical72:慮大數問題去做.. 10/12 13:31
這個的話..因為他有辦法用數學導出一個出每項未知數的係數都為1的做法 但是我的係數有50 10 5 1 如果係數都是1 那直接使用 C(n+k-1,k) 來完成 瞬間秒殺 n=n個事物 ex:我舉的例子有4個事物 k=選取k個的組合 例如說有三個未知數 x+y+z=7 可以把他想成把7個單位物件 分給三個未知數 我們可以想像如下: 假設這裡有7顆球 我用兩條線來分成三組 例如 OO|OOOO|O 代表第一個人有兩顆球 第二個人有4顆 第三個人1顆 把他做排列的話就是 9! 在除以相同物排列 2! 和 7! 所以9!/(2!*7!)=36種分法 我想要用組合的方法解決他 或許我應該去數學版問問看@@ 不過真的謝謝你:)
→ x000032001:這不就DP嗎 10/12 13:48
推 tropical72:是 dp 沒錯,所以才丟個範例,大數先不考慮為佳。 10/12 13:50
※ 編輯: wa007123456 來自: 125.226.15.183 (10/12 14:20)
推 tropical72:不好意思,我錯了,我以為你要找所有解,其實是找幾個解. 10/12 14:23
→ loveme00835:這的確去Prob_Solve比較合適, 不是任何問題都來C++板 10/12 14:33
→ firejox:假如你要大數 建議換個語言寫... 10/12 18:18
推 bigpigbigpig:基本上把 next_permutation 改一下就可以解決了！ 10/13 11:37