2017年10月27日 星期五

2017年10月23日 星期一

106商業技藝競賽程式模擬題參考解

           , ,      No comments   
106年度 程式設計模擬題 參考解_陳俊華  2017/10/20 {p22,p31會另重寫}

 P11 計算字元數
Public Class Form1
    Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
        Me.Hide()
        FileOpen(1, "in1.txt", OpenMode.Input)
        FileOpen(2, "in2.txt", OpenMode.Input)
        FileOpen(3, "out.txt", OpenMode.Output)
        For fn = 1 To 2
            If fn = 2 Then PrintLine(3)
            Dim n As Integer = LineInput(fn)
            For i = 1 To n
                Dim s As String = LineInput(fn)
                PrintLine(3, fnxx(s))
            Next
        Next
        End
    End Sub
    Function fnxx(ByVal s As String) As String
        fnxx = ""
        Dim cnt As Integer = 0
        For i = 1 To s.Length
            If (Mid(s, i, 1) <> " ") Then cnt += 1
        Next
        Return fnxx & cnt
    End Function
End Class



P12 前綴字串(Prefix) and 後綴字串(Postfix)
Public Class Form1
    Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
        Me.Hide()
        FileOpen(1, "in1.txt", OpenMode.Input)
        FileOpen(2, "in2.txt", OpenMode.Input)
        FileOpen(3, "out.txt", OpenMode.Output)
        For fn = 1 To 2
            If fn = 2 Then PrintLine(3)
            Dim n As Integer = LineInput(fn)
            For i = 1 To n
                Dim p As String = LineInput(fn)
                Dim q As String = LineInput(fn)
                PrintLine(3, fnxx(p, q))
            Next
        Next
        End
    End Sub
    Function fnxx(ByVal p As String, ByVal q As String) As String
        fnxx = ""
        Dim pn As Integer = p.Length, qn As Integer = q.Length
        Dim rn As Integer = Math.Min(pn, qn)
        Dim i As Integer
        For i = rn To 1 Step -1
            If Mid(p, 1, i) = Mid(q, qn + 1 - i, i) Then Exit For
        Next
        Return fnxx & i
    End Function
End Class

P21 身分證
Public Class Form1
    Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
        Me.Hide()
        FileOpen(1, "in1.txt", OpenMode.Input)
        FileOpen(2, "in2.txt", OpenMode.Input)
        FileOpen(3, "out.txt", OpenMode.Output)
        For fn = 1 To 2
            If fn = 2 Then PrintLine(3)
            Dim n As Integer = LineInput(fn)
            For i = 1 To n
                Dim s As String = LineInput(fn)
                PrintLine(3, fnxx(s))
            Next
        Next
        End
    End Sub
    Function fnxx(ByVal s As String) As String
        fnxx = ""
        Dim n2() = {10,11,12,13,14,15,16,17,34,18,19,20,21,22,35,23,24,25,26,27,28,29,32,30,31,33}
        Dim c As Char = Mid(s, 1, 1)
        If c < "A" Or c > "Z" Then Return "F"
        If Mid(s, 2, 1) < "1" Or Mid(s, 2, 1) > "2" Then Return "F"
        Dim k As Integer = n2(Asc(c) - Asc("A"))
        Dim sum As Integer = k \ 10 + (k Mod 10) * 9
        For i = 2 To 9
            c = Mid(s, i, 1)
            If c < "0" Or c > "9" Then Return "F"
            sum += Val(c) * (10 - i)
        Next
        c = Mid(s, 10, 1)
        If c < "0" Or c > "9" Then Return "F"
        sum += Val(c)
        If sum Mod 10 = 0 Then Return "T" Else Return "F"
    End Function
End Class
P22 羅馬數字符號
Public Class Form1
    Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
       Me.Hide()
        FileOpen(1, "in1.txt", OpenMode.Input)
        FileOpen(2, "in2.txt", OpenMode.Input)
        FileOpen(3, "out.txt", OpenMode.Output)
        For fn = 1 To 2
            If fn = 2 Then PrintLine(3)
            Dim n As Integer = LineInput(fn)
            For i = 1 To n
                Dim s As String = LineInput(fn)
                PrintLine(3, fnxx(s))
            Next
        Next
        End
    End Sub
    Dim rom() As String = {"I", "V", "X", "L", "C", "D", "M"}
    Dim dnum() = {1, 5, 10, 50, 100, 500, 1000, 4000}
    Function fnxx(ByVal s As String) As String
        fnxx = ""
        Dim x As Integer = s
        For i = 6 To 0 Step -2
            If x < dnum(i) Then Continue For
            If x \ dnum(i) = 9 Then
                fnxx &= rom(i) & rom(i + 2)
                x -= (dnum(i) * 9)
            ElseIf x \ dnum(i) = 4 Then
                fnxx &= rom(i) & rom(i + 1)
                x -= (dnum(i) * 4)
            ElseIf x >= dnum(i + 1) Then
                fnxx &= rom(i + 1)
                x -= dnum(i + 1)
            End If
            Do While x >= dnum(i)
                fnxx &= rom(i)
                x -= dnum(i)
            Loop
        Next
    End Function
End Class

P31 解一元一次方程式
Public Class Form1
    Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
       Me.Hide()
        FileOpen(1, "in1.txt", OpenMode.Input)
        FileOpen(2, "in2.txt", OpenMode.Input)
        FileOpen(3, "out.txt", OpenMode.Output)
        For fn = 1 To 2
            If fn = 2 Then PrintLine(3)
            Dim n As Integer = LineInput(fn)
            For i = 1 To n
                Dim s As String = LineInput(fn)
                PrintLine(3, fnxx(s))
            Next
        Next
        End
    End Sub
    Dim x(1), v(1) As Integer  ' 0:左、 1:右式
    Function fnxx(ByVal s As String) As String
        fnxx = ""
        Dim dat() = s.Split("=")
        x(0) = 0 : x(1) = 0 : v(0) = 0 : v(1) = 0 '清空
        For i = 0 To 1
            eval(i, dat(i))
        Next
        Dim x2 = x(0) - x(1), v2 = v(1) - v(0)
        If x2 = 0 Then
            If v2 = 0 Then Return "IS" Else Return "NS"
        Else
            fnxx &= (v2 / x2)
        End If
    End Function
    Sub eval(ByVal i As Integer, ByVal f As String)
        Dim si = 1
        Dim p1 As Integer = 1
        If Mid(f, 1, 1) = "x" Then f = "1" & f
        For j = 1 To f.Length
            Dim c As Char = Mid(f, j, 1)
            If c = "+" Then
                xv(p1, si, i, j, f) '加減號之間的數值
                si = 1
                p1 = j + 1
            ElseIf c = "-" Then
                xv(p1, si, i, j, f) '加減號之間的數值
                si = -1
                p1 = j + 1
            End If
        Next
        xv(p1, si, i, f.Length + 1, f) '加減號之間的數值
    End Sub
    Sub xv(ByVal p1 As Integer,ByVal si As Integer,ByVal i As Integer,ByVal j As Integer,ByVal f As String)
        Dim num As Integer = Val(Mid(f, p1))
        If (Mid(f, j - 1, 1) = "x") Then
            If num = 0 Then num = 1
            x(i) += num * si
        Else
            v(i) += num * si
        End If
    End Sub
End Class
P32 將一個數字每個位數相加，直到剩個位數為止
Public Class Form1
    Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
       Me.Hide()
        FileOpen(1, "in1.txt", OpenMode.Input)
        FileOpen(2, "in2.txt", OpenMode.Input)
        FileOpen(3, "out.txt", OpenMode.Output)
        For fn = 1 To 2
            If fn = 2 Then PrintLine(3)
            Dim n As Integer = LineInput(fn)
            For i = 1 To n
                Dim s As String = LineInput(fn)
                PrintLine(3, fnxx(s))
            Next
        Next
        End
    End Sub
    Function fnxx(ByVal s As String) As String
        fnxx = ""
        Dim x As Integer = s
        Do Until x < 10
            x = dsum(x)
        Loop
        Return fnxx & x
    End Function
    Function dsum(ByVal x As Integer) As Integer
        dsum = 0
        Do While x > 0
            dsum += x Mod 10
            x \= 10
        Loop
        Return dsum
    End Function
End Class

P41 樹(是否為樹，造成迴圈的邊)
Public Class Form1
    Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
       Me.Hide()
        FileOpen(1, "in1.txt", OpenMode.Input)
        FileOpen(2, "in2.txt", OpenMode.Input)
        FileOpen(3, "out.txt", OpenMode.Output)
        For fn = 1 To 2
            If fn = 2 Then PrintLine(3)
            Dim n As Integer = LineInput(fn)
            For i = 1 To n
                Dim s As String = LineInput(fn)
                PrintLine(3, fnxx(s))
            Next
        Next
        End
    End Sub
    Const MaxN As Integer = 20  '最大的編號
    Dim egcnt As Integer '邊數
    Dim ndcnt As Integer '節點數
    Dim nds(MaxN) As Boolean ' 是否節點編號
    Dim rt(MaxN) As Integer '各點的根
    Dim ht(MaxN) As Integer '各根的高
    Function sam(ByVal x As Integer, ByVal y As Integer) As Boolean  'uni-find 樹是否迴圈
        Return fdrt(x) = fdrt(y)
    End Function
    Function fdrt(ByVal x As Integer) As Integer  'uni-find 樹的找根
        If x = rt(x) Then Return x
        rt(x) = fdrt(rt(x))
        Return rt(x)
    End Function
    Sub uni(ByVal x As Integer, ByVal y As Integer) 'uni-find 樹的合併
        x = fdrt(x) : y = fdrt(y)
        If ht(x) < ht(y) Then
            rt(x) = y
        Else
            rt(y) = x
            If ht(x) = ht(y) Then ht(x) += 1
        End If
    End Sub
    Function fnxx(ByVal s As String) As String
        For i = 0 To MaxN  '清陣列
            nds(i) = False
            ht(i) = 0
            rt(i) = i
        Next
        fnxx = ""
        s = ttrim(s) '清多餘空白
        Dim egs() = s.Split(" ")
        egcnt = egs.Length
        For i = 0 To egcnt - 1
            Dim xy() = egs(i).Split(",")
            Dim x As Integer = xy(0), y As Integer = xy(1)
            If sam(x, y) Then fnxx &= egs(i) & " " '有迴圈
            uni(x, y)
            nds(x) = True : nds(y) = True
        Next
        ' 沒迴圈，且 節點數 = 邊數+1
        ndcnt = 0
        For i = 0 To MaxN
            If nds(i) Then ndcnt += 1
        Next
        If fnxx <> "" Then Return Trim(fnxx)
        If ndcnt = egcnt + 1 Then
            Return "T"
        Else
            Return "F"
        End If
    End Function
    Function ttrim(ByVal s) As String  '清中間多個空白為1個
        s = Trim(s)
        Do While InStr(s, "  ") > 0
            s = Replace(s, "  ", " ")
        Loop
        Return s
    End Function
End Class


P42 樹葉至根的路徑
Public Class Form1
    Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
       Me.Hide()
        FileOpen(1, "in1.txt", OpenMode.Input)
        FileOpen(2, "in2.txt", OpenMode.Input)
        FileOpen(3, "out.txt", OpenMode.Output)
        For fn = 1 To 2
            If fn = 2 Then PrintLine(3)
            Dim n As Integer = LineInput(fn)
            For i = 1 To n
                If i > 1 Then PrintLine(3)
                Print(3, fnxx(fn))
            Next
        Next
        End
    End Sub
    Const MaxN As Integer = 99 '編號最大 99,根的父
    Dim far(MaxN) As Integer
    Dim chi(MaxN) As Boolean
    Function fnxx(ByVal fn As Integer) As String
        fnxx = ""
        For i = 0 To MaxN
            chi(i) = False
        Next
        Dim m As Integer = 0
        Do
            Dim s As String = LineInput(fn)
            If s = "0" Then Exit Do
            Dim xy() = s.Split(",")
            Dim x As Integer = xy(0), y As Integer = xy(1)
            far(x) = y   'x的父是 y
            chi(y) = True ' y 有兒子
            m += 1 '節點的個數
        Loop

        far(99) = 99
        For i = 0 To m - 1 '沒有 chi的即葉節點
            If chi(i) Then Continue For '有兒子跳過
            Dim p As String = ""
            Dim c As Integer = far(i) '從 i 往上至 99為止
            Dim fst As Boolean = True

            Do Until far(c) = 99
                If fst Then fst = False Else p &= ","
                p &= c
                c = far(c)
            Loop
            If p = "" Then
                fnxx &= i & ":N" & vbNewLine
            Else
                fnxx &= i & ":{" & p & "}" & vbNewLine
            End If
        Next

    End Function

End Class

 第１版檔案下載   第2版檔案下載

部份題第２版
106 程式 – 模擬題 P12 前綴、後綴字串 – 參考解-2                                陳俊華2017/10/21
  Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
        Me.Hide()
        FileOpen(1, "in1.txt", OpenMode.Input)
        FileOpen(2, "in2.txt", OpenMode.Input)
        FileOpen(3, "out.txt", OpenMode.Output)
        For fn = 1 To 2
            If fn = 2 Then PrintLine(3)
            Dim n As Integer = LineInput(fn)
            For i = 1 To n
                Dim s1 As String = LineInput(fn)
                Dim s2 As String = LineInput(fn)
                PrintLine(3, fnxx(s1, s2))
            Next
        Next
        End
    End Sub
    Function fnxx(ByVal s1 As String, ByVal s2 As String) As String
        For w = Math.Min(s1.Length, s2.Length) To 1 Step -1
            If chk(s1, s2, w) Then Return w & ""
        Next
        Return "0"
    End Function
    Function chk(ByVal s1 As String, ByVal s2 As String, ByVal w As Integer) As Boolean
        ' 檢查 (s1 前w個字元) 與 (s2 後w個字元)  是否相同
        Dim sn2 = s2.Length - w  ' s2 位移量
        For j = 1 To w
            Dim k = sn2 + j
            If Mid(s1, j, 1) <> Mid(s2, k, 1) Then Return False
        Next
        Return True
    End Function

106 程式 – 模擬題 P22 羅馬數字 – 參考解-2                                              陳俊華2017/10/21
  Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
        Me.Hide()
        FileOpen(1, "in1.txt", OpenMode.Input)
        FileOpen(2, "in2.txt", OpenMode.Input)
        FileOpen(3, "out.txt", OpenMode.Output)
        For fn = 1 To 2
            If fn = 2 Then PrintLine(3)
            Dim n As Integer = LineInput(fn)
            For i = 1 To n
                Dim s As String = LineInput(fn)
                PrintLine(3, fnxx(s))
            Next
        Next
        End
    End Sub
    Dim nt() As Integer = {1, 5, 10, 50, 100, 500, 1000}
    Dim rt() As String = {"I", "V", "X", "L", "C", "D", "M"}
    Dim nt2() As Integer = {4, 9, 40, 90, 400, 900, 4000}
    Dim rt2() As String = {"IV", "IX", "XL", "XC", "CD", "CM", "M?"}

    Function fnxx(ByVal s As String) As String
        fnxx = ""
        Dim x As Integer = s
        For i = 6 To 0 Step -1
            If x >= nt2(i) Then
                x -= nt2(i)
                fnxx &= rt2(i)
            End If
            Do While x >= nt(i)
                x -= nt(i)
                fnxx &= rt(i)
            Loop
        Next
    End Function

106 程式 – 模擬題 M6P32_數字每位數和，直到剩個位數                                     陳俊華2017/10/21
  Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
        Me.Hide()
        FileOpen(1, "in1.txt", OpenMode.Input)
        FileOpen(2, "in2.txt", OpenMode.Input)
        FileOpen(3, "out.txt", OpenMode.Output)
        For fn = 1 To 2
            If fn = 2 Then PrintLine(3)
            Dim n As Integer = LineInput(fn)
            For i = 1 To n
                Dim s As String = LineInput(fn)
                PrintLine(3, fnxx(s))
            Next
        Next
        End

    End Sub
    Function fnxx(ByVal s As String) As String
        Dim x As Integer = s
        Do Until x < 10
            x = dsum(x)
        Loop
        Return x & ""
    End Function
    Function dsum(ByVal x As Integer) As Integer
        dsum = 0
        Do While x > 0
            dsum += x Mod 10
            x \= 10
        Loop
    End Function

106 程式 – 模擬題 P31解一元一次方程式– 參考解-2                                       陳俊華2017/10/21
  Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
        Me.Hide()
        FileOpen(1, "in1.txt", OpenMode.Input)
        FileOpen(2, "in2.txt", OpenMode.Input)
        FileOpen(3, "out.txt", OpenMode.Output)
        For fn = 1 To 2
            If fn = 2 Then PrintLine(3)
            Dim n As Integer = LineInput(fn)
            For i = 1 To n
                Dim s As String = LineInput(fn)
                PrintLine(3, fnxx(s))
            Next
        Next
        End
    End Sub
    Dim x, v As Integer          ‘共用變數
    Function fnxx(ByVal s As String) As String
        Dim dat() = s.Split("=")
        eval(dat(0))
        Dim xa = x, va = v
        eval(dat(1))
        xa -= x : v -= va
        If xa = 0 Then
            Return IIf(v = 0, "IS", "NS")
        Else
            Return (v / xa)
        End If
    End Function
    Sub eval(ByVal s As String)
        Dim si = 1 '正負號
        Dim num As Integer = 0
        x = 0 : v = 0
        For i = 1 To s.Length
            Dim c As Char = Mid(s, i, 1)
            If c >= "0" And c <= "9" Then
                num = num * 10 + Val(c)
            Else  '可能是 x , + , -
                If c = "x" Then
                    If num = 0 Then num += 1
                    x += num * si
                Else
                    v += num * si
                    si = IIf(c = "+", 1, -1)
                End If
                num = 0
            End If
        Next
        v += num * si
    End Sub