2018年12月24日 星期一

2018年12月19日 星期三

篩法、陣列的應用

           , ,      No comments   
篩法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 參考解

2018年12月15日 星期六

商競程式107正式題

           ,      No comments   
讀檔部份省略，假設每組一列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年 正式題 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

' 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








2018年12月11日 星期二

2018年12月4日 星期二

107模(二信自訂)

                No comments   
二信高中自訂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_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