2010年11月8日 星期一

Problem 4：排列組合的應用(99模擬)

子題1（11%）：一個菜販有「肉」、「菜」、「蛋」、「果」4 類商品，在菜攤上「分類」排列出
售，各項商品可由輸入檔讀入其「每公斤利潤」。有一天，菜販忘了商品在菜攤的排列方式，
只知道今天各類商品由左至右出售的「公斤數」，其資料選手也可由輸入檔讀入。在不知道今
天商品排列的情況下，請選手將所有的排列方式逐一代入計算，依總利潤之高低順序，由高
而低，輸出所有排列方式及其總利潤。
輸入說明：
第1 行有4 組數字，以逗號隔開，分別表示「肉」、「菜」、「蛋」、「果」每公斤的利潤。
第2 行有4 組數字，以逗號隔開，表示今天菜攤由左至右各類商品出售之公斤數。
輸出說明：
依總利潤之高低順序，每1 行輸出1 組排列方式及其總利潤，資料間至少以1 個空白隔開。
若有總利潤相同者，其前後輸出順序不拘。
輸入範例：【檔名：in-4-1.txt】
70, 32, 18, 42
43, 24, 21, 39
輸出範例：【檔名：out-4-1.txt】
肉菜蛋果 5794
肉蛋菜果 5752
果菜蛋肉 5682
肉果蛋菜 5644
果蛋菜肉 5640
肉蛋果菜 5572
菜果蛋肉 5492
菜蛋果肉 5420
肉果菜蛋 5392
肉菜果蛋 5362
蛋果菜肉 5184
蛋菜果肉 5154
果肉蛋菜 5112
菜肉蛋果 5072
果蛋肉菜 4956
菜蛋肉果 4916
果肉菜蛋 4860
蛋肉菜果 4764
果菜肉蛋 4746
蛋菜肉果 4650
菜肉果蛋 4640
蛋肉果菜 4584
菜果肉蛋 4556
蛋果肉菜 4500


子題2（11%）：如果有一個客人來買這個菜攤的n 項商品，每類商品只能買1 項或不買，請
選手列出所有可能的購買組合。輸出之順序，應依照購買之總金額由高而低依序輸出。
輸入說明：
第1 行有1 個數字，代表n 的值。
第2 行有4 組數字，以逗號隔開，分別表示「肉」、「菜」、「蛋」、「果」每項商品的購買金額。
輸出說明：
每列輸出一組購買組合及其購買總金額，並至少以1 個空白隔開。其輸出方式為：每列均輸
出「肉菜蛋果」字串，但客人「購買」之商品名稱以「小括號」括起來。輸出之順序依購買
之總金額由高而低依序輸出，若有總金額相同者則不限順序。
輸入範例：【檔名：in-4-2.txt】
2
140, 64, 36, 84
輸出範例：【檔名：out-4-2.txt】
(肉)菜蛋(果) 224
(肉)(菜)蛋果 204
(肉)菜(蛋)果 176
肉(菜)蛋(果) 148
肉菜(蛋)(果) 120
肉(菜)(蛋)果 100
張貼者： 於
標籤：

2 則留言:

  1. 寫寫程式2010年11月9日 上午8:36

    4-1

    Dim m
    Dim item
    Dim mon
    Dim q As Integer
    Dim ans(999) As String
    Dim mans(999) As Long
    Public Sub Form_Load()
    Me.Hide
    Open App.Path & "\in-4-1.txt" For Input As #1
    Open App.Path & "\out-4-1.txt" For Input As #2
    Line Input #1, step
    Line Input #1, nstep
    m = Split(step, ",")
    w = Split(nstep, ",")
    monn = "肉 菜 蛋 果"
    mon = Split(monn)
    monn = Replace(monn, " ", "")
    For i = 0 To UBound(mon)
    m(i) = Trim(m(i))
    w(i) = Trim(w(i))
    Next i
    Call check("")
    For i = 0 To q - 1
    kk = ans(i): Money = 0
    For j = 1 To 4
    Money = Money + m(InStr(monn, Mid(kk, j, 1)) - 1) * w(j - 1)
    Next j
    mans(i) = Money
    Next i
    For i = 0 To q - 2
    For j = i + 1 To q - 1
    If mans(j) > mans(i) Then
    step = mans(j): mans(j) = mans(i): mans(i) = step
    step = ans(j): ans(j) = ans(i): ans(i) = step
    End If
    Next j
    Next i
    For i = 0 To q - 1
    Print #2, ans(i), mans(i)
    Next i
    Close #2
    Close #1
    End
    End Sub

    Public Sub check(ByVal st)
    If Len(st) = 4 Then
    ans(q) = st
    q = q + 1
    Else
    For i = 0 To UBound(mon)
    If InStr(st, mon(i)) = 0 Then Call check(st & mon(i))
    Next i
    End If

    End Sub

    by Yung

    回覆刪除
  2. 寫寫程式2010年11月9日 上午9:12

    4-2
    Dim m
    Dim c
    Dim y
    Dim q As Integer
    Dim ans(999) As String
    Dim mans(999) As Long
    Public Sub Form_Load()
    Me.Hide
    Open App.Path & "\in-4-2.txt" For Input As #1
    Open App.Path & "\out-4-2.txt" For Input As #2
    Line Input #1, c
    Line Input #1, step
    m = Split(step, ",")
    x = "肉 菜 蛋 果"
    y = Split(x)
    x = Replace(x, " ", "")

    For i = 0 To UBound(y)
    m(i) = Trim(m(i))
    Next i
    q = 0
    Call check("", 0)

    For i = 0 To q - 1
    kk = ans(i): Money = 0
    For j = 1 To c
    Money = Money + m(InStr(x, Mid(kk, j, 1)) - 1)
    Next j
    mans(i) = Money
    Next i
    For i = 0 To q - 2
    For j = i + 1 To q - 1
    If mans(j) > mans(i) Then
    step = mans(j): mans(j) = mans(i): mans(i) = step
    step = ans(j): ans(j) = ans(i): ans(i) = step
    End If
    Next j
    Next i
    For i = 0 To q - 1
    For j = 0 To 3
    If InStr(ans(i), y(j)) <> 0 Then Print #2, "(" & y(j) & ")"; Else Print #2, y(j);
    Next j
    Print #2, , mans(i)
    Next i

    Close #2
    Close #1
    End
    End Sub

    Public Sub check(ByVal st, ByVal n)
    If Len(st) = 2 Then
    ans(q) = st
    q = q + 1
    Else
    For i = n To UBound(y)
    If InStr(st, y(i)) = 0 Then Call check(st & y(i), n)
    n = n + 1
    Next i
    End If
    End Sub

    BY Yung

    回覆刪除

訂閱： 張貼留言 (Atom)