2018/8/30 更新 p11
用VB10寫在Form_Load，讀檔統一如下，然後呼叫fxx，每題讀檔就不重複
讀檔寫檔
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", 1)
FileOpen(2, "in2.txt", 1)
FileOpen(3, "out.txt", 2)
For fn = 1 To 2
If fn = 2 Then PrintLine(3)
Dim n As Short = LineInput(fn)
For k = 1 To n
Dim s As String = LineInput(fn)
PrintLine(3, fxx(s))
Next
Next
End
End Sub
．．．
每一題 解題部份
Function fxx( s as ... ) as ...
．．．
End Class
P11 質因數分解
x質因數分解， x<65536 ，先建 sqrt(65535)之內的質數表 pr(0)=2,~ pr(53)=251x被pr(i)整除的個數，>0才印，直到 x =1 或質數用完 x<>1則只有1次方
建質數表，所以在讀檔前呼叫Gen_Pr() 產生 Pr()質數表
Dim pr(60) As Integer '質數表 54個: 最大251
Dim pcnt As Integer ' 個數
Function fxx(ByVal s As String) As String
Dim x As Integer = s
fxx = ""
For i = 0 To pcnt - 1
If x Mod pr(i) = 0 Then
Dim cnt As Integer = 0
Do While x Mod pr(i) = 0
cnt += 1
x \= pr(i)
Loop
If fxx <> "" Then fxx &= " "
fxx &= pr(i) & "^" & cnt
If x = 1 Then Exit For
End If
Next
If x > 1 Then
If fxx <> "" Then fxx &= " "
fxx &= ( x & "^1" ) '8/30更新, 因少 ^1
End If
End Function
Sub Gen_pr()
pr(0) = 2 : pcnt = 1
For k = 3 To 255 Step 2
If isp(k) Then
pr(pcnt) = k
pcnt += 1
End If
Next
' Return pcnt & " , " & pr(pcnt - 1)
End Sub
Function isp(ByVal k As Integer) As Boolean
If k < 2 Then Return False
For i = 2 To Math.Sqrt(k)
If k Mod i = 0 Then Return False
Next
Return True
End Function
P12 N!尾0個數
2*5才會有0，5比2少，只要算5的個數即可
Function fxx(ByVal s As String) As String
Dim x As Integer = s
Dim cnt As Integer = 0
For i = 5 To x Step 5
Dim k As Integer = i
Do While k Mod 5 = 0
cnt += 1
k \= 5
Loop
Next
Return cnt
End Function
P21 計程車費
Function fxx(ByVal s As String) As String
Dim k As Integer = s * 1000 '所有的數乘 1000化成公尺
Dim p = 85 '一上車 85元
k -= 1500 '可走 1500公尺
p += ((k + 249) \ 250) * 5 '每 250 公尺 5 元
Return p
End Function
Function fxx(ByVal s As String) As String
Dim k As Integer = s.Length
For j = 1 To k \ 2
If Mid(s, j, 1) <> Mid(s, k + 1 - j, 1) Then Return "N"
Next
Return "Y"
End Function
P31 是否為樹
同 103 年模擬題P31
Const MaxN As Integer = 20 '編號 0~20
Dim adj(MaxN, MaxN) As Boolean '相鄰矩陣
Dim nds(MaxN) As Boolean '是否為節點
Dim vst(MaxN) As Boolean '是否訪過
Sub dfs(ByVal u As Integer) '由 u深訪
vst(u) = True
For v = 0 To MaxN
If adj(u, v) And Not vst(v) Then dfs(v) '相鄰且 v 未訪過
Next
End Sub
Function fxx(ByVal s As String) As String
s = Trim(s) : ttrim(s, " ", " ") : ttrim(s, ", ", ",") : ttrim(s, " ,", ",")
Dim st As Integer ' 起點
Dim egs() = s.Split(" ") '邊
Dim egcnt As Integer = egs.Length '邊數
Array.Clear(adj, 0, (MaxN + 1) * (MaxN + 1))
Array.Clear(nds, 0, MaxN + 1)
For i = 0 To UBound(egs)
Dim xy() = egs(i).Split(",") '分成 x,y
Dim x As Integer = xy(0), y As Integer = xy(1)
adj(x, y) = True : adj(y, x) = True
nds(x) = True : nds(y) = True
st = x
Next
Dim ndcnt As Integer = 0 '節點數
For i = 0 To MaxN
If nds(i) Then ndcnt += 1
Next
If ndcnt <> egcnt + 1 Then Return "F" '點、邊的數不符 樹的規定
Array.Clear(vst, 0, MaxN + 1)
dfs(st)
For i = 0 To MaxN '是節點，但未訪過，不連通就不是樹
If nds(i) And Not vst(i) Then Return "F"
Next
Return "T"
End Function
Sub ttrim(ByRef s As String, ByVal a As String, ByVal b As String)
Do While (InStr(s, a) > 0)
s = s.Replace(a, b)
Loop
End Sub P32 二元搜尋樹高
用陣列模擬左鏈及右鏈
因每個檔案只有一組資料，n是節點數，每點一列，在讀檔時一次讀入a()，再給fxx用
．．．
Dim n As Integer = LineInput(fn)
For k = 0 To n - 1
a(k) = LineInput(fn)
lt(k) = -1 : rt(k) = -1
Next
PrintLine(3, fxx(n))
．．．
Dim a(30), lt(30), rt(30) As Integer '節點值、左鏈、右鏈
Function fxx(ByVal n As Integer) As String
' n節點數 ：最多 30個節點 a()資料、 lt()左鏈、 rt()
Dim p, pp, h As Integer '目前位置、父、高
Dim mh As Integer = 0 '高度
For i = 1 To n - 1
p = 0 : pp = 0 : h = 0
Do Until p = -1 '走到 末端，插入點
pp = p : h += 1
If a(i) > a(p) Then '大：往右
p = rt(p)
ElseIf a(i) < a(p) Then '小：往左
p = lt(p)
End If
Loop
If a(i) > a(pp) Then '父節點的右樹
rt(pp) = i
ElseIf a(i) < a(pp) Then '父節點的左樹
lt(pp) = i
End If
If h > mh Then mh = h
Next
fxx = mh
End Function
P41 加減問題
只有三個數，2^3八種 + - 組合，用 8*3的陣列存 -1及1 ，八種各跑1次即可
可直接打表 pm()={}八種組合，也可以跑Gen_Pm產生{在讀檔前呼叫一次}
'Dim pm(,) As Integer = {{-1, -1, -1}, {-1, -1, 1}, {-1, 1, -1}, {-1, 1, 1}, {1, -1, -1}, {1, -1, 1}, {1, 1, -1}, {1, 1, 1}}
Dim pm(31, 4) As Integer '假設有 3個數、 4個數、 5個數 三種情形，所以最多 2^5=32種正負狀態
Sub Gen_pm(ByVal n As Integer)
For i = 0 To 2 ^ n - 1
Dim x = i
For j = 0 To n - 1
pm(i, j) = IIf(x Mod 2 = 0, -1, 1)
x \= 2
' Debug.Print(i & "," & j & ":" & pm(i, j))
Next
Next
End Sub
Function fxx(ByVal s As String) As String
Dim dat() = s.Split(" ")
Dim a(2) As Integer
a(0) = dat(0) : a(1) = dat(1) : a(2) = dat(2)
For j = 0 To 7
If a(0) * pm(j, 0) + a(1) * pm(j, 1) + a(2) * pm(j, 2) = 0 Then Return "T"
Next
Return "F"
End Function
' 使用 Strings.StrReverse 函式
Function fxx(ByVal s As String) As String
Dim dat() = s.Split(",")
Dim a As Integer = Strings.StrReverse(dat(0))
Dim b As Integer = Strings.StrReverse(dat(1))
Dim sum As Integer = Strings.StrReverse(a + b)
Return sum ' Strings.StrReverse(a + b) X:若未存入整數，字串的前導0仍會保留
End Function
' 解法2：使用 自訂函式 Rev
Function Rev(ByVal k As Integer) As Integer
Rev = 0
Do While k > 0
Rev = Rev * 10 + k Mod 10
k \= 10
Loop
End Function
Function fxx2(ByVal s As String) As String
Dim dat() = s.Split(",")
Dim n0 As Integer = dat(0)
Dim n1 As Integer = dat(1)
Return Rev(Rev(n0) + Rev(n1))
End Function
Rev = 0
Do While k > 0
Rev = Rev * 10 + k Mod 10
k \= 10
Loop
End Function
Function fxx2(ByVal s As String) As String
Dim dat() = s.Split(",")
Dim n0 As Integer = dat(0)
Dim n1 As Integer = dat(1)
Return Rev(Rev(n0) + Rev(n1))
End Function
發表文章
0 意見:
張貼留言