2010年8月6日 星期五

排列組合三-零錢問題

 假設某國的硬幣的面值有 1、5、10、50 元四種,輸入一個金額 N (正整數,N<=1000),印出符合該金額的硬幣組合有多少種。
 輸入1:100
 輸出1:158
 輸入2:999
 輸出2:72800

(網路參考:http://www.tcgs.tc.edu.tw/~sagit/cpp/q12.htm)

6 則留言:

  1. 老師 那個C++ 有點看不懂說@@

    方法 大致上是理解,不過老師是要讓我們練習遞迴還是迴圈呢?

    回覆刪除
  2. 寫得出來再說啊。
    怎麼樣都可以,先做出來了,再說其它的啊。
    熊掌
    哦,那個C++不用理它啦。

    回覆刪除
  3. Dim c(4) As Integer
    Private Sub Form_Load()
    Open App.Path & "\in.txt" For Input As #1
    Open App.Path & "\out.txt" For Output As #2
    Input #1, x
    c(1) = 1: c(2) = 5: c(3) = 10: c(4) = 50
    Print #2, abc(x, 4)
    Close #2
    Close #1
    End Sub
    Function abc(ByVal i As Integer, ByVal j As Integer) As Long
    If j = 1 Then
    abc = 1
    Else
    If i < c(j) Then
    abc = abc(i, j - 1)
    Else
    abc = abc(i, j - 1) + abc(i - c(j), j)
    End If
    End If
    End Function

    回覆刪除
  4. 作者已經移除這則留言。

    回覆刪除
  5. 把握解題方法,快些完成吧。
    阿揚說不能回應,再試試吧。

    回覆刪除
  6. Dim c(4) As Integer
    Dim money(1000) As Long
    Private Sub Form_Activate()
    c(2) = 5: c(3) = 10: c(4) = 50
    Open App.Path & "\in.txt" For Input As #1
    Open App.Path & "\out.txt" For Output As #2
    Input #1, x
    For i = 0 To x
    money(i) = 1
    Next i
    For i = 2 To 4
    For j = 1 To x
    If j >= c(i) Then
    money(j) = money(j) + money(j - c(i))
    End If
    Next j
    Next i
    Print #2, money(x)
    Close #1
    Close #2
    End
    End Sub

    回覆刪除