2018年12月24日 星期一
P1 期末 Ch4 + Ch5-1
課內題目及學習手冊(75%左右) ←下載
補充題目_選擇40題(15%左右) ←下載
另(10%左右)課文內重點、中英對照
選擇模擬測驗
qe.fisp.com.tw
老師：jafachen@yahoo.com.tw
密碼：學號
P2 期末Ch12
課內題目及學習手冊(65%左右) ←下載
補充題目_選擇25題(20%左右) ←下載
另(15%左右)課文內重點、中英對照
選擇模擬測驗
qe.fisp.com.tw
老師：jafachen@yahoo.com.tw
密碼：學號
2018年12月19日 星期三
篩法、陣列的應用
篩法400.xlsx
找 2~n(<10^7)的所有質數 虛擬碼
動態陣列 p 、靜態陣列 c(n) 初值 false設為質數、true被刪記(非質數)
push (2)
for i= 3 ~ n jump 2
if not c(i) then
'//這是質數，將所有 i 的倍數刪掉
push( i ) '將 i 加入 p 陣列
for j=i*i ~ n jump i
c(j) = true ' j 被刪記
end for
end if
end for
應用題連結
1220-0 ~ 1220-3 參考解
找 2~n(<10^7)的所有質數 虛擬碼
動態陣列 p 、靜態陣列 c(n) 初值 false設為質數、true被刪記(非質數)
push (2)
for i= 3 ~ n jump 2
if not c(i) then
'//這是質數，將所有 i 的倍數刪掉
push( i ) '將 i 加入 p 陣列
for j=i*i ~ n jump i
c(j) = true ' j 被刪記
end for
end if
end for
應用題連結
1220-0 ~ 1220-3 參考解
2018年12月15日 星期六
商競程式107正式題
讀檔部份省略，假設每組一列S或多列S()傳入fxx，傳回結果
F107_P11_計算含S字數
Function fnxx(ByVal s As String) As String
fnxx = ""
s = Trim(s) : ttrim(s, " ", " ")
Dim dat() = s.Split(" ")
Dim cnt = 0
For i = 0 To UBound(dat)
If InStr(dat(i), "s") > 0 Or InStr(dat(i), "S") > 0 Then cnt += 1
Next
Return dat.Length & "," & cnt
End Function
'若資料以空格隔開，可能需要將多個空白 取代為 單空白
Sub ttrim(ByRef s As String, ByVal a As String, ByVal b As String)
While (InStr(s, a) > 0)
s = s.Replace(a, b)
End While
End Sub
' 107年 正式題 P12 井字棋
' 不會有兩人同時連線，分別判斷1及2有沒有連、否則都沒連3
' 一次傳S陣列 3列
Dim a(2, 2) As Integer
Function fxx(ByVal s$()) As String
fxx = "3"
For i = 0 To 2
For j = 0 To 2
a(i, j) = Mid(s(i), j + 1, 1)
Next
Next
If chk(1) Then Return 1
If chk(2) Then Return 2
End Function
Function chk(ByVal p As Integer) As Boolean
' 列
Dim cnt As Integer
For i = 0 To 2
cnt = 0
For j = 0 To 2
If a(i, j) = p Then cnt += 1
Next
If cnt = 3 Then Return True
Next
' 行
For i = 0 To 2
cnt = 0
For j = 0 To 2
If a(j, i) = p Then cnt += 1
Next
If cnt = 3 Then Return True
Next
If p = a(0, 0) AndAlso a(0, 0) = a(1, 1) AndAlso a(1, 1) = a(2, 2) Then Return True '\
If p = a(0, 2) AndAlso a(0, 2) = a(1, 1) AndAlso a(1, 1) = a(2, 0) Then Return True '/
Return False
End Function
' 107年 正式題 P21 快樂數字
' 最大 100000 宣告一陣列，檢查是否出現過
Const MaxN As Integer = 100000 '最大的數字
Function fxx(ByVal s$) As String
fxx = ""
Dim x% = s
Dim mk(MaxN) As Boolean
mk(x) = True
Do Until x = 1
x = ss(x)
If mk(x) Then Exit Do
mk(x) = True
Loop
If x = 1 Then Return "T" Else Return "F"
End Function
Function ss(ByVal x As Integer) As Integer
ss = 0
Dim d%
Do Until x = 0
d = x Mod 10
ss += (d * d)
x \= 10
Loop
End Function
' 107年 正式題 P22 排列
' 最多5個數字，全排列，由小至大問第 k 個的值
Dim plst As New ArrayList
Function fxx(ByVal s$) As String
fxx = ""
Dim dat() = s.Split(",")
Dim N% = dat(0)
Dim a(N - 1) As Integer '最多 5 個數
For i = 0 To N - 1
a(i) = dat(i + 1)
Next
Dim k% = dat(N + 1)
plst.Clear()
perm(a, 0, N)
plst.Sort()
Return plst(k - 1)
End Function
Sub perm(ByVal a%(), ByVal p%, ByVal N%)
If p = N Then '產生一組
Dim num = ""
For i = 0 To N - 1
num &= a(i)
Next
plst.Add(num)
Return
End If
' 換 p ~ N-1 , 遞迴
Dim t As Integer
For x = p To N - 1
t = a(p) : a(p) = a(x) : a(x) = t ' p換 成其它的數字
perm(a, p + 1, N)
t = a(p) : a(p) = a(x) : a(x) = t ' p 換回來
Next
End Sub
' 107年 正式題 P31 大數乘冪運算 M^K { 1 <= M,K <= 999 }
' 可 用 BigInteger 類別，應也可以使用 Log10吧
' 專案 需加入 參考，再 Imports, 不確定BigInteger的位數上限，需另查
Imports System.numerics
Function fxx(ByVal s As String) As String
Dim dat() = s.Split(",")
Dim m% = dat(0), k% = dat(1)
' 算 m^k
Dim Pow As BigInteger = BigInteger.Pow(m, k)
fxx = Len(Pow.ToString) '& "," & Pow.ToString
End Function
方法2 使用Log10： Return Math.Floor(Math.Log10(M)*K)+1
' 107年 正式題 P41 樹最遠的2節點長度
' 因最多 127個節點，父子為相鄰，建adj(,) 以 floyd找任2點最短路{樹沒迴路,
2點只有一種距離}, 所有2節點距中最長即是
Const MaxN% = 127
Const inf% = 99
Dim a(MaxN, MaxN) As Integer
Function fxx(ByVal s$) As String
s = Mid(s, 2)
Dim bt(MaxN) As Boolean
Dim sep() As Char = {",", "，"}
Dim dat() = s.Split(sep)
Dim m% = dat.Length '最後 node
Dim p%, v%
For k = 0 To UBound(dat)
v% = Val(dat(k))
If v% > 0 Then bt(k + 1) = True Else bt(k + 1) = False
Next
For i = 1 To m
For j = 1 To m
a(i, j) = inf 'inf
Next
Next
'建相鄰矩陣
For p = m \ 2 To 1 Step -1
Dim lch% = p * 2 '左子
Dim rch% = lch% + 1 ' 右子
If bt(lch) Then '有左子 連
a(p, lch) = 1 : a(lch, p) = 1
End If
If bt(rch) Then '有右子 連
a(p, rch) = 1 : a(rch, p) = 1
End If
Next
floyd(m) '最短路 {樹沒有迴圈，兩點距只有一個值}
v = 0
For i = 1 To m
For j = i + 1 To m
If a(i, j) < inf Then
v = Math.Max(v, a(i, j))
End If
Next
Next
fxx = v
End Function
Sub floyd(ByVal m%)
For k = 1 To m
For i = 1 To m
For j = 1 To m
a(i, j) = Math.Min(a(i, j), a(i, k) + a(k, j))
Next
Next
Next
End Sub
' 107年 正式題 P42 循環排列
' 因最多 k=20 , 數字 1~k 找循環
Const MaxN% = 20 '最多20個 1~20
Dim a(MaxN) As Integer
Dim vst(MaxN) As Boolean
Dim cyc As New ArrayList
Function fxx(ByVal s$) As String
s = Mid(s, 2)
Dim sep() As Char = {",", "，"}
Dim dat() = s.Split(sep)
Dim k% = dat.Length 'k個數
Dim v%
fxx = ""
For i = 1 To k
v% = Val(dat(i - 1))
a(i) = v ' 第 i 個 接 第 v 個
Next
fxx &= "["
Dim fst As Boolean = True
Array.Clear(vst, 0, vst.Length)
For i = 1 To k
If vst(i) Then Continue For
If fst Then fst = False Else fxx &= ","
fxx &= "["
If a(i) = i Then
fxx &= i '自己接自己
Else
cyc.Clear()
dfs(i)
fxx &= cyc(0)
For j = 1 To cyc.Count - 1
fxx &= "," & cyc(j)
Next
End If
fxx &= "]"
Next
fxx &= "]"
End Function
Sub dfs(ByVal u%)
If vst(u) Then Return
cyc.Add(u) : vst(u) = True
dfs(a(u))
End Sub
F107_P11_計算含S字數
Function fnxx(ByVal s As String) As String
fnxx = ""
s = Trim(s) : ttrim(s, " ", " ")
Dim dat() = s.Split(" ")
Dim cnt = 0
For i = 0 To UBound(dat)
If InStr(dat(i), "s") > 0 Or InStr(dat(i), "S") > 0 Then cnt += 1
Next
Return dat.Length & "," & cnt
End Function
'若資料以空格隔開，可能需要將多個空白 取代為 單空白
Sub ttrim(ByRef s As String, ByVal a As String, ByVal b As String)
While (InStr(s, a) > 0)
s = s.Replace(a, b)
End While
End Sub
' 107年 正式題 P12 井字棋
' 不會有兩人同時連線，分別判斷1及2有沒有連、否則都沒連3
' 一次傳S陣列 3列
Dim a(2, 2) As Integer
Function fxx(ByVal s$()) As String
fxx = "3"
For i = 0 To 2
For j = 0 To 2
a(i, j) = Mid(s(i), j + 1, 1)
Next
Next
If chk(1) Then Return 1
If chk(2) Then Return 2
End Function
Function chk(ByVal p As Integer) As Boolean
' 列
Dim cnt As Integer
For i = 0 To 2
cnt = 0
For j = 0 To 2
If a(i, j) = p Then cnt += 1
Next
If cnt = 3 Then Return True
Next
' 行
For i = 0 To 2
cnt = 0
For j = 0 To 2
If a(j, i) = p Then cnt += 1
Next
If cnt = 3 Then Return True
Next
If p = a(0, 0) AndAlso a(0, 0) = a(1, 1) AndAlso a(1, 1) = a(2, 2) Then Return True '\
If p = a(0, 2) AndAlso a(0, 2) = a(1, 1) AndAlso a(1, 1) = a(2, 0) Then Return True '/
Return False
End Function
' 107年 正式題 P21 快樂數字
' 最大 100000 宣告一陣列，檢查是否出現過
Const MaxN As Integer = 100000 '最大的數字
Function fxx(ByVal s$) As String
fxx = ""
Dim x% = s
Dim mk(MaxN) As Boolean
mk(x) = True
Do Until x = 1
x = ss(x)
If mk(x) Then Exit Do
mk(x) = True
Loop
If x = 1 Then Return "T" Else Return "F"
End Function
Function ss(ByVal x As Integer) As Integer
ss = 0
Dim d%
Do Until x = 0
d = x Mod 10
ss += (d * d)
x \= 10
Loop
End Function
' 107年 正式題 P22 排列
' 最多5個數字，全排列，由小至大問第 k 個的值
Dim plst As New ArrayList
Function fxx(ByVal s$) As String
fxx = ""
Dim dat() = s.Split(",")
Dim N% = dat(0)
Dim a(N - 1) As Integer '最多 5 個數
For i = 0 To N - 1
a(i) = dat(i + 1)
Next
Dim k% = dat(N + 1)
plst.Clear()
perm(a, 0, N)
plst.Sort()
Return plst(k - 1)
End Function
Sub perm(ByVal a%(), ByVal p%, ByVal N%)
If p = N Then '產生一組
Dim num = ""
For i = 0 To N - 1
num &= a(i)
Next
plst.Add(num)
Return
End If
' 換 p ~ N-1 , 遞迴
Dim t As Integer
For x = p To N - 1
t = a(p) : a(p) = a(x) : a(x) = t ' p換 成其它的數字
perm(a, p + 1, N)
t = a(p) : a(p) = a(x) : a(x) = t ' p 換回來
Next
End Sub
' 107年 正式題 P31 大數乘冪運算 M^K { 1 <= M,K <= 999 }
' 可 用 BigInteger 類別，應也可以使用 Log10吧
' 專案 需加入 參考，再 Imports, 不確定BigInteger的位數上限，需另查
Imports System.numerics
Function fxx(ByVal s As String) As String
Dim dat() = s.Split(",")
Dim m% = dat(0), k% = dat(1)
' 算 m^k
Dim Pow As BigInteger = BigInteger.Pow(m, k)
fxx = Len(Pow.ToString) '& "," & Pow.ToString
End Function
方法2 使用Log10： Return Math.Floor(Math.Log10(M)*K)+1
' 107年 正式題 P32 模數
' 應該有公式解(數論？待查) 但 a,b,m皆 1~99 ： 99^3 應可以暴力解
Function fxx(ByVal s$) As String
fxx = ""
s = Strings.Trim(s) : ttrim(s, " ", " ")
Dim dat() = s.Split(" ")
' fxx = s & "," & dat.Length
Dim ai% = dat(0), ax% = dat(1)
Dim bi% = dat(2), bx% = dat(3)
Dim mi% = dat(4), mx% = dat(5)
Dim cnt = 0
For k = mi To mx
Dim md = k * 100
For i = ai To ax
For j = bi To bx
If (i + j) Mod k = (i - j + md) Mod k Then cnt += 1
Next
Next
Next
Return cnt
End Function
Sub ttrim(ByRef s$, ByVal a$, ByVal b$)
Do While InStr(s, a) > 0
s = s.Replace(a, b)
Loop
End Sub
' 因最多 127個節點，父子為相鄰，建adj(,) 以 floyd找任2點最短路{樹沒迴路,
2點只有一種距離}, 所有2節點距中最長即是
Const MaxN% = 127
Const inf% = 99
Dim a(MaxN, MaxN) As Integer
Function fxx(ByVal s$) As String
s = Mid(s, 2)
Dim bt(MaxN) As Boolean
Dim sep() As Char = {",", "，"}
Dim dat() = s.Split(sep)
Dim m% = dat.Length '最後 node
Dim p%, v%
For k = 0 To UBound(dat)
v% = Val(dat(k))
If v% > 0 Then bt(k + 1) = True Else bt(k + 1) = False
Next
For i = 1 To m
For j = 1 To m
a(i, j) = inf 'inf
Next
Next
'建相鄰矩陣
For p = m \ 2 To 1 Step -1
Dim lch% = p * 2 '左子
Dim rch% = lch% + 1 ' 右子
If bt(lch) Then '有左子 連
a(p, lch) = 1 : a(lch, p) = 1
End If
If bt(rch) Then '有右子 連
a(p, rch) = 1 : a(rch, p) = 1
End If
Next
floyd(m) '最短路 {樹沒有迴圈，兩點距只有一個值}
v = 0
For i = 1 To m
For j = i + 1 To m
If a(i, j) < inf Then
v = Math.Max(v, a(i, j))
End If
Next
Next
fxx = v
End Function
Sub floyd(ByVal m%)
For k = 1 To m
For i = 1 To m
For j = 1 To m
a(i, j) = Math.Min(a(i, j), a(i, k) + a(k, j))
Next
Next
Next
End Sub
' 107年 正式題 P42 循環排列
' 因最多 k=20 , 數字 1~k 找循環
Const MaxN% = 20 '最多20個 1~20
Dim a(MaxN) As Integer
Dim vst(MaxN) As Boolean
Dim cyc As New ArrayList
Function fxx(ByVal s$) As String
s = Mid(s, 2)
Dim sep() As Char = {",", "，"}
Dim dat() = s.Split(sep)
Dim k% = dat.Length 'k個數
Dim v%
fxx = ""
For i = 1 To k
v% = Val(dat(i - 1))
a(i) = v ' 第 i 個 接 第 v 個
Next
fxx &= "["
Dim fst As Boolean = True
Array.Clear(vst, 0, vst.Length)
For i = 1 To k
If vst(i) Then Continue For
If fst Then fst = False Else fxx &= ","
fxx &= "["
If a(i) = i Then
fxx &= i '自己接自己
Else
cyc.Clear()
dfs(i)
fxx &= cyc(0)
For j = 1 To cyc.Count - 1
fxx &= "," & cyc(j)
Next
End If
fxx &= "]"
Next
fxx &= "]"
End Function
Sub dfs(ByVal u%)
If vst(u) Then Return
cyc.Add(u) : vst(u) = True
dfs(a(u))
End Sub
2018年12月4日 星期二
107模(二信自訂)
二信高中自訂107模擬題 (題目文字檔) (測資檔)
M107a_p01 春夏秋冬
阿華和阿俊玩一個遊戲叫做「春夏秋冬」有四種牌，夏吃春、秋吃夏、冬吃秋、春吃冬，吃到的得1分，其餘不計分
我們以 PMAW分別代表春夏秋冬，阿華和阿俊各發六張牌，阿華的a1~a6、阿俊的b1~b6
a1與b1比、a2與b2比…a6與b6比，問阿華與阿俊各得幾分？
in1.txt
3
AMPWAP MWWPMW
PPMMWA MWAAPW
WMAWPM AWMPWW
in2.txt
3
AMWPWP WMWPMW
PAPMMW AMWAAP
PWMAWP MAWMPW
out.txt
4 1
1 5
3 1
1 1
2 3
3 2
參考解1
M107a_p02 小三數學
每列2個數字，第1個數字k：10~2147483647，第2個數字m：-2147483648~2147483647，
若k的每位數之間可插入1或2個運算符號使結果等於 m ，則輸出YES，否則輸出NO
可插入的符號為{ + , - , * , / }四種}可使用相同的符號，先乘除或加減
假設計算過程，除法需整除才算， 例如 9/6*4=6 不算，因9/6非整數不可以先*4再/6
in1.txt
5
123 4
234 14
24015 16
862 4
22 4
in2.txt
3
1357924680 -626963
334 5
543 345
out.txt
YES
YES
YES
YES
YES
YES
YES
NO
-------輸出註解
12/3
2+3*4
240/15
8-6+2
2+2 或 2*2
1357-924*680
3*3-4 或 3/3+4
NO
參考解2
M107a_p03 組合排列
有一個m位數數字X，最少3位,不含0不重複，選n個{2~m}，所有的組合全排列後，由小至大的第k個是多少
若m=4,x=1357，n=3，則全排列為
(1) 135 (2) 137 (3) 153 (4) 157 (5) 173 (6) 175 (7) 315 (8) 317 (9) 351 (10)357 (11)371 (12)375
(13)513 (14)517 (15)531 (16)537 (17)571 (18)573 (19)713 (20)715 (21)731 (22)735 (23)751 (24)753
輸入每列三個數 x,n,k、輸出全排列的第k個數，如上例x=1357,n=3,k=10則輸出357
in1.txt
2
1357,3,10
1357,3,19
in2.txt
3
543,2,3
123,2,5
2468,3,11
out.txt
357
713
43
31
482
參考解3
M107a_p04 十轉五四三
每列2個數 x,k，其中x為十進位 0<x<1000000，且有可能有小數，若有小數最多3位數；k為3,4,5之一，代表k進位
請將x轉為 k進位，若沒有小數則不印，若有小數最多3位，小數部份的尾0不印
in1.txt
3
123.456 5
2345.678 4
345678 3
in2.txt
3
987654.321 3
87653.125 4
6789 5
out.txt
443.212
210221.223
122120011220
1212011210210.022
111121211.02
204124
參考解4
M107a_p01 春夏秋冬
阿華和阿俊玩一個遊戲叫做「春夏秋冬」有四種牌，夏吃春、秋吃夏、冬吃秋、春吃冬，吃到的得1分，其餘不計分
我們以 PMAW分別代表春夏秋冬，阿華和阿俊各發六張牌，阿華的a1~a6、阿俊的b1~b6
a1與b1比、a2與b2比…a6與b6比，問阿華與阿俊各得幾分？
in1.txt
3
AMPWAP MWWPMW
PPMMWA MWAAPW
WMAWPM AWMPWW
in2.txt
3
AMWPWP WMWPMW
PAPMMW AMWAAP
PWMAWP MAWMPW
out.txt
4 1
1 5
3 1
1 1
2 3
3 2
參考解1
M107a_p02 小三數學
每列2個數字，第1個數字k：10~2147483647，第2個數字m：-2147483648~2147483647，
若k的每位數之間可插入1或2個運算符號使結果等於 m ，則輸出YES，否則輸出NO
可插入的符號為{ + , - , * , / }四種}可使用相同的符號，先乘除或加減
假設計算過程，除法需整除才算， 例如 9/6*4=6 不算，因9/6非整數不可以先*4再/6
in1.txt
5
123 4
234 14
24015 16
862 4
22 4
in2.txt
3
1357924680 -626963
334 5
543 345
out.txt
YES
YES
YES
YES
YES
YES
YES
NO
-------輸出註解
12/3
2+3*4
240/15
8-6+2
2+2 或 2*2
1357-924*680
3*3-4 或 3/3+4
NO
參考解2
M107a_p03 組合排列
有一個m位數數字X，最少3位,不含0不重複，選n個{2~m}，所有的組合全排列後，由小至大的第k個是多少
若m=4,x=1357，n=3，則全排列為
(1) 135 (2) 137 (3) 153 (4) 157 (5) 173 (6) 175 (7) 315 (8) 317 (9) 351 (10)357 (11)371 (12)375
(13)513 (14)517 (15)531 (16)537 (17)571 (18)573 (19)713 (20)715 (21)731 (22)735 (23)751 (24)753
輸入每列三個數 x,n,k、輸出全排列的第k個數，如上例x=1357,n=3,k=10則輸出357
in1.txt
2
1357,3,10
1357,3,19
in2.txt
3
543,2,3
123,2,5
2468,3,11
out.txt
357
713
43
31
482
參考解3
M107a_p04 十轉五四三
每列2個數 x,k，其中x為十進位 0<x<1000000，且有可能有小數，若有小數最多3位數；k為3,4,5之一，代表k進位
請將x轉為 k進位，若沒有小數則不印，若有小數最多3位，小數部份的尾0不印
in1.txt
3
123.456 5
2345.678 4
345678 3
in2.txt
3
987654.321 3
87653.125 4
6789 5
out.txt
443.212
210221.223
122120011220
1212011210210.022
111121211.02
204124
參考解4
M107a_P05朋友(高中104北二區-3.b839)
問題描述:當我們到一個新環境時，常常會從和我們有相同個性、喜好或來自相同故鄉的人們開始結交，
我們也會對同姓交或名字相近的人感到熟悉或有好感。 在這道題目中，我們將假設朋友關係是這樣建立的：
(1)若兩個人的名字相似，則兩個人會結為朋友。
(2)若兩個人有共同朋友，則兩個人會結為朋友。
如何定義兩個人的名字相似呢？令兩個人的名字為 S 和 T ，我們說若S(長度為m)和T(長度為n)的
最長共同子字串(Longest common subsequene,LCS)長度不小於min(m,n)/2.0，則S和T相似。 {LCS的定義就省略}
根據上上述的朋友關係，我們可以將一群人分成一個或數個團體，每個團體中的任意兩個人都是朋友，而兩個不同團體中的人則都不是朋友。
現在，請你寫一個程式，輸出最大團體(人數最多)的人數個數。
輸入每列第1個數字k代表一群人共有k個人(最多20人)，接著有這k人的姓名{皆是小寫字母最多20字}，以空白隔開
in1.txt
3
5 abc adb xyzzzz zzzxop xompn
5 abc adb xyzzzz zzzxop xoapd
5 abc adb xyzzzz zzzxop xoape
in2.txt
3
6 abcd adb xyzzzz zzzxop xompn zzzab
6 abc adx xyzzzz zzzxop xoapd xyzaa
6 abdc adb xyzzzz zzzxop xoape xyzz
out.txt
3
5
3
6
5
4
M107a_p06霍夫曼編碼
一篇英數字的文章，若每個字元不壓縮最少一個字元需7位元，用霍夫曼編碼，較常用的字元使用較少的位元編碼，
可以使整個使用的位元數減少。例如「ABCABDABEACDABE」共15個字原使用7位元*15共105個位元，若將編碼改為
A00,B01,C10,D110,E1110,F1111，則只需使用36個位元即可。
每列皆為可列印的ASCII字元，最多100個字元，使用霍夫曼編碼，請問最少可用多少位元表示這列文字？
in1.txt
3
ABCABDABEACDABE
This is a Book.
TO BE OR NOT TO BE?
in2.txt
2
In computer science and information theory, a Huffman code is a particular type of optimal code
CAD,CAI,CAM,CIM,DOG,GOD,ACM,CAT,CAE,CAR,BOOK,DOOR.
out.txt
34
48
53
389
168
M107a_p07最少硬幣數
阿華商店使用阿華幣，其幣值是特定的，給一個正整數問換成最少阿華幣的個數？
例如有6種幣值：{1,2,3,5,15,18}要換48元可以是 18+18+5+5+2要五個硬幣，也可以 18+15+15要三個硬幣
每列給第1個數字k{5~12}代表有k種幣值，接著k個幣值，最後m代表要換m元(1~9999}，輸出最小硬幣數
in1.txt
3
6,1,2,3,5,15,18,48
7,1,3,5,8,12,20,35,100
7,1,3,5,8,12,20,35,123
in2.txt
3
10,1,2,3,10,15,20,25,30,55,88,234
12,1,2,5,8,13,25,40,60,99,123,250,511,9876
8,1,5,12,20,25,35,85,100,466
out.txt
3
5
6
4
22
7
M107a_p08最短路徑長
第1列為圖形各邊的資訊{2節點名及邊長}，節點編碼皆為1個大寫字母，邊長1~99，各邊以逗號隔開
第2列有數組詢問，以逗號隔開，每個詢問給兩節點名稱，問這兩節點之最短路徑的長度，輸出亦以逗號隔開
in1.txt
2
AB11,BC12,CD17,DE13,EA6,AF5,FB9,FD8,EF15,FG1,BG3
EB,CE
RN15,AB9,DR14,AE2,BE4,BF16,CF23,HR25,FG13,GH5,AJ17,JK7,FK12,EJ22,AS8,SM18,SP14,LG6,LF21,GM27,MN11,JL20,PN38
AN,BS,LC
in2.txt
2
AB11,BC12,CD7,DE23,EA6,AF5,FB9,CF13,FD8,EF15
ED,CE
RN15,AB9,BC39,CD41,DR53,AE2,BE4,BF16,CF23,CH43,HR25,FG13,GH5,AJ17,JK7,FK12,EJ22,AS8,SM18,SP14,LG6,LF21,GM27,MN11,JL20,PN38
AN,BS,LC
out.txt
15,27
37,14,42
19,24
37,14,42
M107a_p09最長遞增子序列(LIS)
給一串整數數列a1,a2,....am {m最大100} ，從中任選k個b1,b2,...bk使b1<b2<...<bk，
例: bj的順序仍維持ai的順序， 問最大的k為多少？
例：輸入為6,2,9,8,3,7,10,4,5
可以6,9,10、或6,8,10、 6,7,10、 2,7,9、 … 也可以 2,3,4,5 ：最長數列為 4個
輸入為6,2,9,8,3,10,7,4,13,5
可以6,9,10,13、… 也可以2,3,4,5 ：最長數列為 4個
輸入為6,2,9,8,3,10,7,4,13,5,11
可以 6,8,10,13、 也可以 2,3,4,5,11 ：最長數列為 5個
in1.txt
3
6,2,9,8,3,7,10,4,5
6,2,9,8,3,10,7,4,13,5
6,2,9,8,3,10,7,4,13,5,11
in2.txt
5
1,15,17,13,18,19,6,8,24,4,21,0,3,2,22
26,3,12,27,20,29,28,1,21,15,8,10,18,25,13
29,13,17,26,19,5,10,3,20,11,24,28,27,22,16,4,2,21,14,7
3,28,5,16,15,1,6,23,4,14,2,20,7,25,29,26,24,13,21,12
15,1,13,25,5,17,20,2,27,8,6,26,22,4,21,7,19,29,3,23,10,18,28,12,11
out.txt
4
4
5
7
5
6
7
7
=====註：若加印路徑 且有多個LIS相同，則先出現的優先
4:2,3,4,5
4:2,3,4,5
5:2,3,4,5,11
7:1,15,17,18,19,21,22
5:1,8,10,18,25
6:13,17,19,20,24,27
7:3,5,6,14,20,25,26
7:1,2,4,7,10,18,28
M107a_p10整理牌型
撲克牌的 「大老二」以2最大，然後AKQJT9876543,其中10點以T代表，給你6~13張牌，
請先依花色，每種花色再由大至小排列，花色先黑桃、紅心、方塊、再梅花。
每一列有 6~12個數字，中間以逗號隔開，代表撲克牌的編號：
0~12 spade 的 A234~9TJQK , 13~25 heart的 A234~9TJQK ,
26~38 diamond 的 A234~9TJQK , 39~51 club 的 A234~9TJQK
輸出：先S:,再H:,再D:,再C:，若沒有的花色則不印，請參考輸入輸出範例
in1.txt
2
0,1,2,7,9,13,24,25,32,36,50
12,14,15,22,23,3,39,48,6,8
in2.txt
2
11,16,17,18,20,26,30,31,33,5
19,21,27,28,29,34,35,37,40,45,46,47,49
out.txt
S:2AT83,H:AKQ,D:J7,C:Q
S:K974,H:2JT3,C:AT
S:Q6,H8654,D:A865
H:97,D:2QT943,C:2J987