9/16 完成 p11、p21 10/06 完成 p21、p22 、 p41 、 p42
10/19 完成 p31 10/22 完成 p32 另 p12也OK
用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)) '根據測資可能一次兩列或傳fn讀多行
' fxx(s1,s2) 或 fxx(fn,s)
Next
Next
End
End Sub
．．．
每一題 解題部份
Function fxx( s as ... ) as ...
．．．
End Class
P11 數學問題-質數
每檔n筆<=5， x<65536 ，直接呼叫 isp，可以不需建質數表
Function fxx(ByVal s As String) As String
Dim x As Integer = s
If isp(x) Then
Return "T" '是質數
Else
Return "F" '非質數
End If
End Function
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 數學問題-大數運算
A除B,求商 ：A,B<= 60位數的整數，B>0，A沒規定 {有可能<0},
以neg記錄正負，以正數處理，若為neg,印出才加印負號
form_load 每筆讀入2列:被除數s1及除數s2，傳入 fxx( s1,s2)
Const MaxN As Integer = 65 '最多 60位數
Dim A(MaxN), B(MaxN), C(MaxN) As Integer
Dim an, bn, cn As Integer
Function fxx(ByVal s1 As String, ByVal s2 As String) As String
'A 被除數，有可能為負數 、 B>0的正數 A÷B 求商
Dim neg As Boolean = False 'A是否為負數
s1 = Trim(s1) : s2 = Trim(s2)
If Mid(s1, 1, 1) = "-" Then
neg = True
s1 = Mid(s1, 2)
End If
s2n(s1, A, an) '將「被除數」s1轉成陣列 A
s2n(s2, B, bn) '將「除數」正數s2轉成陣列 B
If bn = 1 And B(0) = 1 Then ' 若B為1，直接印出S1
fxx = p2f(A, an)
Return IIf(neg, "-", "") & fxx
End If
bdiv() '呼叫大數除法 a÷b 存入 c
Return IIf(neg, "-", "") & p2f(C, cn) ' 印 c => fxx
End Function
Function p2f(ByVal x() As Integer, ByVal xn As Integer) As String
' 倒著印陣列 X()，元素個數 xn
If xn = 0 Then Return "0"
p2f = ""
For i = xn - 1 To 0 Step -1
p2f &= x(i)
Next
End Function
Sub s2n(ByVal xs As String, ByRef x() As Integer, ByRef xn As Integer)
' 將字串倒轉成 整數陣列
Dim i As Integer = 0
xn = xs.Length
For j = xn To 1 Step -1
x(i) = Mid(xs, j, 1)
i += 1
Next
x(xn) = 0
End Sub
Sub bdiv() '將 a÷b 存入 c
Dim aw As Integer = bn + 1
Dim i, cnt As Integer
For k = an - bn To 0 Step -1
cnt = 0
Do While ncmp(k, aw)
' Print(3, k & ":" & aw)
cnt += 1
bsub(k, aw)
Dim os1 As String = p2f(A, an), os2 As String = p2f(B, bn)
' PrintLine(3, " a,b " & os1 & " , " & os2)
Loop
C(k) = cnt
Next
For i = an - bn To 0 Step -1
If C(i) <> 0 Then Exit For
Next
cn = i + 1
End Sub
Function ncmp(ByVal ak As Integer, ByVal aw As Integer) As Boolean
ncmp = True ' A 陣列 a(ak+aw-1) ~ a(ak) 共 aw 位， 與 b 陣列比較大小
'先消去 a(ak+aw-1) 起的前導 0 、有需要?
Dim i As Integer
For i = aw - 1 To 0 Step -1
If A(i + ak) <> 0 Then Exit For
Next
aw = i + 1
If aw <> bn Then Return (aw > bn)
For i = bn - 1 To 0 Step -1
If A(i + ak) <> B(i) Then Return (A(i + ak) >= B(i))
Next
Return True
End Function
Function bsub(ByVal ak As Integer, ByVal aw As Integer) As Integer
' A 陣列 a(ak+aw-1) ~ a(ak) 共 aw 位， 減去 b 陣列, 去前導0 傳回新寬度
Dim i As Integer
For k = 0 To bn - 1
i = k + ak
If A(i) < B(k) Then '往前1位 借10
A(i + 1) -= 1
A(i) += 10
End If
A(i) -= B(k)
Next
'消去 a(ak+aw-1) 起的前導 0
Do While aw > 0 AndAlso A(aw + ak - 1) = 0
aw -= 1
Loop
bsub = aw
End Function
P21 字串-前綴字串(Prefix) and 後綴字串(Postfix)
一次讀兩列 s1,s2 再傳入 fxx
兩字串較小長度len起至1，分別判定左k個字是否等於右k個字
Function fxx(ByVal s1 As String, ByVal s2 As String) As String
Dim n1 As Integer = s1.Length, n2 As Integer = s2.Length
Dim len As Integer = Math.Max(n1, n2)
Dim k As Integer = len
For k = len To 1 Step -1
If Strings.Left(s1, k) = Strings.Right(s2, k) Then Exit For
Next
Return k
End Function
P22 字串-行、字數、字元數
因要讀多行，傳入 檔號fn，在fxx(fn) 讀檔處理
Function fxx(ByVal fn As Integer) As String
Dim a, b, c As Integer '列、字、字元
Do Until EOF(fn)
Dim line = LineInput(fn)
a += 1 '加1列
c += line.Length ' 這列的字元數
Dim dat() = line.Split(" ")
b += dat.Length ' 這列的 字數(word)以空白隔開
Loop
Return a & "," & b & "," & c
End Function
P31 樹-是否為堆積樹(Heap tree)
判斷是否為堆積樹 {Min_Heap、Max_Heap皆算}
Function fxx(ByVal s As String) As String
f = "T"
Dim dat() = s.Split(",")
Dim m As Integer = dat.Length
Dim a(m) As Integer
For i = 0 To UBound(dat)
a(i + 1) = dat(i)
Next
If Not h1(a, m) And Not h2(a, m) Then Return "F" '不是 Max_Heap 且 不是 Min_Heap 才傳回 F
End Function
Function h1(ByVal a() As Integer, ByVal m As Integer) As Boolean ' Max_Heap ?
h1 = True
For p = m \ 2 To 1 Step -1
If a(p) <= a(2 * p) Then Return False
If 2 * p + 1 <= m AndAlso a(p) <= a(2 * p + 1) Then Return False '有可能 沒有 2p+1
Next
End Function
Function h2(ByVal a() As Integer, ByVal m As Integer) As Boolean ' Min_Heap ?
h2 = True
For p = m \ 2 To 1 Step -1
If a(p) >= a(2 * p) Then Return False
If 2 * p + 1 <= m AndAlso a(p) >= a(2 * p + 1) Then Return False '有可能沒有 2p+1
Next
End Function
P32 樹-中序表示法
二元搜尋樹的中序表示法，每檔只有一組資料
Class bt '一個節點，內含三個資料 {註：也可以分開建三個陣列}
Public Property lt As Integer = -1 '左樹
Public Property dt As Integer '資料
Public Property rt As Integer = -1 '右樹
End Class
Dim nd(30) As bt '最多 30 個節點 ，編號 0~100
'註：二搜樹的中序其實就是 由小到大，偷工的做法就是排序即可
Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
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 m As Short = LineInput(fn) '共有 m 個節點
'一個檔只有一組資料
PrintLine(3, fxx(m, fn)) '傳 m 個節點, 檔號fn
Next ' fn
End
End Sub
Function fxx(ByVal m As Integer, ByVal fn As Integer) As String
nd(0) = New bt '要記得 需 New bt 才可使用
nd(0).dt = LineInput(fn) '第1個 root
For j = 1 To m - 1
nd(j) = New bt
Dim k As Integer = LineInput(fn)
nd(j).dt = k
Dim p = 0
Do While True
If k < nd(p).dt Then '往左
If nd(p).lt = -1 Then
nd(p).lt = j
Exit Do
Else
p = nd(p).lt
End If
Else '往右
If nd(p).rt = -1 Then
nd(p).rt = j
Exit Do
Else
p = nd(p).rt
End If
End If
Loop
Next j
fxx = ""
'For j = 0 To m - 1 '印出參考 ( 左、值、右 )
' PrintLine(3, j & " " & nd(j).lt & ":" & nd(j).dt & ":" & nd(j).rt)
'Next
fxx = ""
fst = True : ino_t(0, fxx) '印中序
' fst = True : pre_t(0,fxx) '印前序
' fst = True : pos_t(0,fxx) '印後序
End Function
Dim fst As Boolean '是否印出的第1個節點, 不加，號
Sub ino_t(ByVal p As Integer, ByRef fxx As String) '中序
If nd(p).lt <> -1 Then ino_t(nd(p).lt, fxx)
If fst Then fst = False Else fxx &= ","
fxx &= nd(p).dt
If nd(p).rt <> -1 Then ino_t(nd(p).rt, fxx)
End Sub
Sub pre_t(ByVal p As Integer, ByRef fxx As String) '前序
If nd(p).lt <> -1 Then pre_t(nd(p).lt, fxx)
If fst Then fst = False Else fxx &= ","
fxx &= nd(p).dt
If nd(p).rt <> -1 Then pre_t(nd(p).rt, fxx)
End Sub
Sub pos_t(ByVal p As Integer, ByRef fxx As String) '後序
If nd(p).lt <> -1 Then pos_t(nd(p).lt, fxx)
If nd(p).rt <> -1 Then pos_t(nd(p).rt, fxx)
If fst Then fst = False Else fxx &= ","
fxx &= nd(p).dt
End Sub
P41 其他-尋找對稱字串
若字串長度為 k , 只需判別 k\2次 { (1,k),(2,k-1)…(k\2,k-k\2+1) } 是否皆相同
Function fxx(ByVal s As String) As String
fxx = ""
Dim sn As Integer = s.Length
' 從最長開始 取一段 長度k = lt~rt 是否為迴文
For k = sn To 1 Step -1 '長度從 sn開始至1 各試有沒有迴文
For lt = sn - k + 1 To 1 Step -1
Dim rt As Integer = k - lt + 1
If padr(Mid(s, lt, k), k) Then Return k
Next
Next
End Function
Function padr(ByVal s As String, ByVal k As Integer) As Boolean
'長度為 k 的字串 s 是否迴文
For i = k \ 2 To 1 Step -1 '前後 各1字元比較
If Mid(s, i, 1) <> Mid(s, k + 1 - i, 1) Then Return False
Next
Return True
End Function
P42 其他-十進制數轉成二進制數
可使用內建函數轉二、八、十六進位，也可自寫函數
str = Convert.ToString( d, x ) '將十進位d轉為x進位{x為2、8、16)傳回字串
d = Convert.ToInt32(str, x) ' 將x進位字串str轉為十進位 傳回數值
Function fxx(ByVal s As String) As String
Dim dat() = s.Split(",") '需注意 原始資料的 逗號左右 是否有空白
Dim a As Integer = StrReverse(Trim(dat(0)))
Dim b As Integer = StrReverse(Trim(dat(1)))
Dim sum As Integer = StrReverse((a + b) & "")
' Debug.Print(3, sum & ":") '十進位的結果
fxx = d2b(sum) '自訂轉換函數
'fxx = Convert.ToString(sum, 2) '也可用Convert，但好像只有2,8,16可以
End Function
Function d2b(ByVal sum As Integer) As String
d2b = ""
If sum = 0 Then Return "0"
Do Until sum = 0
d2b = sum Mod 2 & d2b
sum \= 2
Loop
End Function
發表文章
0 意見:
張貼留言