7月 2017 ~ 二信資處程式

Z2A 7/12 試題參考解

F4P12 樂透

F5P22 最大公約數計算

M4P12 N! 尾數的0

M4P21 計程車費率計算

M4P42 數字反轉後相加

M6P01 大數三則運算

M6P02 階乘化成質因數

M6P03 求兩數之間的質數個數

M6P04 二進位～廿進位的轉換

M6P01 大數三則運算

正整數的加+ 減- 乘* ，但數字超過 Long 型別哦，需以字串輸入

輸入檔第1列為n，接著有n列，

輸入說明：兩個輸入檔in1.txt in2.txt

輸入資料檔第一列為正整數 n { 1<=n<=5 }，接著n列，

每列三部份a op b 以空格隔開，其中1<=a,b<10^60，而op為以上3個符號之一

將每列的a , b兩數依 op 算出後輸出， a 、 op 、 b 以空格隔開，減號算出後有可能為負數

輸出說明：一個輸出檔 out.txt

對應每一列輸入，輸出一列 , 為a+b、或a-b、或a*b 後的計算結果

【in1.txt】

2222222222222222222222222 + 1111111111111111111111111

2222222222222222222222222 - 1111111111111111111111111

2222222222222222222222222 * 1111111111111111111111111

99999 – 100000

【in2.txt】

1234567 + 987654321

1234567 * 987654321

1234567 - 9876543212345678

【out.txt】

3333333333333333333333333

1111111111111111111111111

2469135802469135802469135308641975308641975308642

-1

988888888

1219325432114007

-9876543211111111

M6P01參考程式碼
Public Class Form1
'大整數三則(加減乘) 兩整數 + - 或乘
'每列三部份a op b 以空格隔開，其中1<=a,b<10^60，而op為以上3個符號之一
'將每列的a , b兩數依 op 算出後輸出， a 、 op 、 b 以空格隔開，減號算出後有可能為負數
' 題意規定只輸出計算結果，本參考題多印題目以方便查看
Const MaxN As Integer = 60
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)
Dim a(MaxN) As Integer
Dim b(MaxN) As Integer
Dim c(MaxN + MaxN) As Integer
For fn = 1 To 2
If fn = 2 Then PrintLine(3) 'in2之前印空白列
Dim n As Short = LineInput(fn)
For i = 1 To n
Dim line As String = LineInput(fn)
Dim dat() = line.Split(" ") '將輸入列分成三個部份 dat(0)、dat(1)、dat(2)
Dim an = ston(dat(0), a) ' bprt(a, an) ' 轉成整數陣列 a() 且長度為 an
Dim bn = ston(dat(2), b) ' bprt(b, bn) ' 轉成整數陣列 b() 且長度為 bn
Dim cn As Integer ' 運算結果的長度將為 cn
Select Case dat(1) ' 根是符號 + , - , * 執行不同運算
Case "+"
Print(3, "加:" & line & " = ")
cn = badd(a, an, b, bn, c) '呼叫大數加法
bprt(c, cn)
Case "-"
Dim neg = False
If Not bcmp(a, an, b, bn) Then '若判斷 b較大，兩數互換，並加負號
neg = True
an = ston(dat(2), a)
bn = ston(dat(0), b)
End If
Print(3, "減:" & line & " = " & IIf(neg, "-", " ")) '是否加負號
cn = bsub(a, an, b, bn, c) '呼叫大數減法
bprt(c, cn)
Case "*"
Print(3, "乘:" & line & " = ")
cn = bmul(a, an, b, bn, c) '呼叫大數乘法
bprt(c, cn)
End Select
Next
Next
End
End Sub

Function ston(ByVal s As String, ByRef x() As Integer)
Dim n = s.Length
' Debug.Print(s & "," & n)
For i = 0 To n - 1
x(i) = Val(Mid(s, n - i, 1))
Next
For i = n To MaxN '未讀入部份清為 0 ，避免上一資料殘餘值
x(i) = 0
Next
Return n
End Function
Function badd(ByVal a() As Integer, ByVal an As Integer, ByVal b() As Integer, ByVal bn As Integer, ByRef c() As Integer) As Integer
Dim cn As Integer = Math.Max(an, bn)
For i = 0 To cn
c(i) = a(i) + b(i)
Next
For i = 0 To cn - 1
If c(i) >= 10 Then
c(i + 1) += 1
c(i) = c(i) Mod 10
End If
Next
If c(cn) <> 0 Then cn += 1
Return cn
End Function
Function bmul(ByVal a() As Integer, ByVal an As Integer, ByVal b() As Integer, ByVal bn As Integer, ByRef c() As Integer) As Integer
Dim cn As Integer = an + bn
For i = 0 To cn '先清為0, 避免上一資料殘留
c(i) = 0
Next
For i = 0 To an - 1
For j = 0 To bn - 1
c(i + j) += a(i) * b(j)
Next
Next
For i = 0 To cn - 1
If c(i) >= 10 Then
c(i + 1) += c(i) \ 10
c(i) = c(i) Mod 10
End If
Next
If c(cn - 1) = 0 Then cn -= 1
Return cn
End Function
Function bcmp(ByVal a() As Integer, ByVal an As Integer, ByVal b() As Integer, ByVal bn As Integer) As Boolean
bcmp = True '若a>=b為True
If an <> bn Then Return (an > bn)
For i = an - 1 To 0 Step -1
If a(i) < b(i) Then Return False
Next
End Function
Function bsub(ByVal a() As Integer, ByVal an As Integer, ByVal b() As Integer, ByVal bn As Integer, ByRef c() As Integer)
Dim cn As Integer = Math.Max(an, bn)
For i = 0 To cn - 1
c(i) = 9 + a(i) - b(i)
Next
c(0) += 1 : c(cn) = -1
For i = 0 To cn - 1
If c(i) >= 10 Then
c(i + 1) += 1
c(i) = c(i) Mod 10
End If
Next
Do Until c(cn) <> 0
cn -= 1
Loop
cn += 1
Return cn
End Function
Sub bprt(ByVal x() As Integer, ByVal xn As Integer)
For i = xn - 1 To 0 Step -1
Print(3, x(i) & "")
Next
PrintLine(3)
End Sub
End Class

M6P02 階乘化成質因數 (時限：10秒， 註： x最大32767，方法若不佳可能跑很久)

輸入檔第1列為n {1<=n<=5}，接著有n列，每列只有一個正整數 x ， 2<= x <=32767

求 x! 由幾個質數相乘所得，例 5! = 2 x 3 x 2x2 x 5 共5個質數，故輸出 5；

又 10! = 2 x 3 x 2x2 x 5 x 2x3 x 7 x2x2x2 x 3x3 x2x5 共 15個，故輸出 15

輸入說明：兩個輸入檔in1.txt in2.txt

輸入資料檔第一列為正整數 n { 1<=n<=5 }，接著n列，每列有1個數字x

輸出說明：一個輸出檔 out.txt

對應每一列輸入，輸出一列 , 為x! 的質因數個數

【in1.txt】

【in2.txt】

100

1000

9999

19999

32767

【out.txt】

239

2877

31977

65524

109050

M6P02參考程式碼
Public Class Form1
Const maxp As Integer = 32767
Dim p As New ArrayList
Dim q(maxp) As Integer
Dim pcnt As Integer
Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
genp(maxp) '建質數表
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 k = 1 To n
' Dim s As String = LineInput(fn) '讀入一整列
'PrintLine(3, fxx(s)) '呼叫 fxx(s) 印出傳回值
Dim x As Integer = LineInput(fn)
PrintLine(3, f1(x)) '呼叫 f1(x) 印出傳回值
Next
Next
End
End Sub
Sub genp(ByVal maxp As Integer)
For i = 2 To maxp
If isp(i) Then p.Add(i)
Next
pcnt = p.Count
' Debug.Print(pcnt & "," & p(pcnt - 1)) '3512,32749 ' 6542 , 65521
End Sub
Function isp(ByVal k As Integer) As Boolean
If k < 2 Then Return False
isp = True
For i = 2 To Math.Sqrt(k)
If k Mod i = 0 Then Return False
Next
End Function
Function f1(ByVal x As Integer) As Integer
f1 = 0
For i = 2 To x
Dim y As Integer = i
Dim yq As Integer = Math.Sqrt(y)
For j = 0 To pcnt - 1
If p(j) > yq Then Exit For
Do While y Mod p(j) = 0
f1 += 1
y \= p(j)
Loop
If y = 1 Then Exit For
Next
If y > 1 Then f1 += 1
Next
End Function

Function fxx(ByVal s As String) As String
fxx = ""
' 處理後傳回 fxx的值
End Function
End Class

M6P03

求兩數之間的質數個數

給兩個正整數 a,b { 0<a,b<2*10⁹ ，且|a-b|<10⁴ } 求[a,b]之間(含) 共有幾個質數

輸入說明：兩個輸入檔in1.txt in2.txt

輸入資料檔第一列為正整數 n { 1<=n<=5 }，接著n列，每列有2個數字a b 以空白隔開

輸出說明：一個輸出檔 out.txt

對應每一列輸入，輸出一列 , 為[a,b]間的質數個數

【in1.txt】

1 2

20 10

100000000 100009999

【in2.txt】

2 97

10000 19999

1999999999 1999990000

【out.txt】

551

1033

441

M6P03參考程式碼
Public Class Form1
Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
genp() '建質數表
'M6P03 兩數間的質數個數
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, pxx(s) & "")
Next i
Next fn
End
End Sub

Function pxx(ByVal s As String) As Integer
pxx = 0
Dim dat() = s.Split(" ") '依空白分
Dim a As Integer = dat(0), b As Integer = dat(1), c As Integer
If a > b Then
c = a : a = b : b = c
End If
For x = a To b
If isp(x) Then pxx += 1
Next
End Function
Dim MaxN As Integer = 2147483647
Dim p As New ArrayList
Dim pcnt As Integer
Sub genp()
Dim q As Integer = Math.Sqrt(MaxN)
p.Add(2) : p.Add(3)
Dim gap = 2
Dim x As Integer = 5
Do Until x > q
If isp(x) Then p.Add(x)
x += gap
gap = 6 - gap
Loop
pcnt = p.Count
' Debug.Print(" tot: " & pcnt & " ," & p(pcnt - 1)) ' tot: 4792 ,46337
' Label1.Text &= Now & vbNewLine
End Sub
Function isp(ByVal x As Integer) As Boolean
If x < 2 Then Return False
Dim q As Integer = Math.Sqrt(x)
Dim i As Integer = 0
Do While i < p.Count AndAlso p(i) <= q
If x Mod p(i) = 0 Then Return False
i += 1
Loop
Return True
End Function
End Class

M6P04 二進位～廿進位的轉換

二進位只有0,1、十進位有0~9，十一進位～廿進位以ABCDEFGHIJ代表10~19

輸入說明：兩個輸入檔in1.txt in2.txt

輸入資料檔第一列為正整數 n { 1<=n<=5 }，接著n列，每列有2個數字1個字串，

以空格隔開 x y s，代表將x進位的s字串轉為y進位

S字串的數值大小若轉為十進位的值為非負整數 0~10⁷ 。

輸出說明：一個輸出檔 out.txt

對應每一列輸入，輸出一列 y進位的字串

輸入、輸出範例檔

【in1.txt】

16 8 D5F4

2 10 1101101

3 13 1212120

【in2.txt】

20 19 2JIHGF

10 16 999999

12 10 4027BA

【out.txt】

152764

109

810

3GB64B

F423F

999934

M6P04參考程式碼
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 t = 1 To n
Dim s As String = LineInput(fn)
PrintLine(3, pxx(s))
Next
Next
End
End Sub
Function pxx(ByVal s As String) As String
Dim dat() = s.Split(" ")
Dim x As Integer = dat(0), y As Integer = dat(1)
Dim d As Integer = x2d(x, dat(2))
pxx = d2y(d, y) 'd & "," & d2y(d, y)
End Function
Dim d20 As String = "0123456789ABCDEFGHIJ"
Function x2d(ByVal x As Integer, ByVal xs As String) As Integer
x2d = 0
For i = 1 To xs.Length
Dim c As Char = Mid(xs, i, 1)
x2d = x2d * x + (InStr(d20, c) - 1)
Next
End Function
Function d2y(ByVal d As Integer, ByVal y As Integer) As String
d2y = ""
Do Until d = 0
d2y = Mid(d20, d Mod y + 1, 1) & d2y
d \= y
Loop
If d2y = "" Then Return "0"
End Function
End Class

F4P12參考程式碼
Public Class Form1

Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
'104正式題-P12 樂透(104版：六選五) 不固定後使用組合，
'固定 6選5 簡單寫可迴圈 6次各排除1個元素即可
' 另補充 c75由7個選5呼叫 comb 完成
FileOpen(1, "in1.txt", OpenMode.Input)
FileOpen(2, "in2.txt", OpenMode.Input)
FileOpen(3, "out.txt", OpenMode.Output)
Call c75()
For fn = 1 To 2
Dim n As Integer = LineInput(fn)
Dim dat() = LineInput(fn).Split(",")
Dim a(4) As Integer '中獎號
For j = 0 To 4
a(j) = dat(j)
Next
Array.Sort(a)
Erase dat '刪除了，
' Dim dat(5) As String '再宣告仍是錯
For i = 1 To n
Dim da2() = LineInput(fn).Split(",")
Dim b(5) As Integer '投注號 6個
For j = 0 To 5
b(j) = da2(j)
Next
' 迴圈六次，各排除1個，只留5個
Dim vi, v(4) As Integer
Dim cnt(5) As Integer ' 各對幾個
For j = 0 To 5
vi = 0
For k = 0 To 5
If j <> k Then
v(vi) = b(k) : vi += 1
End If
Next
' 產生一組 5 個數字在 v 與 a 比
cnt(lotto(a, v)) += 1 '每一組各中幾個號碼，累加至 cnt陣列
Next
' 六組個累加完一起印出
PrintLine(3, cnt(2) & "," & cnt(3) & "," & cnt(4) & "," & cnt(5))
Next i
If fn = 1 Then PrintLine(3)
Next fn
End

End Sub
Function lotto(ByVal a() As Integer, ByVal v() As Integer)
Dim ai = 0, vi = 0
lotto = 0
Do Until ai >= 5 Or vi >= 5
If a(ai) = v(vi) Then
ai += 1 : vi += 1
lotto += 1 ' 中獎號個數
ElseIf a(ai) > v(vi) Then
vi += 1
Else
ai += 1
End If
Loop
End Function
Dim combI = 0, combout(5040) As String
Sub comb(ByVal b() As Integer, ByRef u() As Boolean, ByVal p As Integer, ByVal k As Integer)
' 從b陣列m個元素中選 n 個, 遞迴位置 p , 還要挑 k 個
Dim m As Integer = b.Length
If k = 0 Then
' 產生一組，列出，若要存至陣列中，需另宣告例如 combout( )
Dim ostr As String = ""
For j = 0 To m - 1
If u(j) Then ostr &= b(j)
Next
combout(combI) = ostr
combI += 1
PrintLine(4, ostr)
Return
End If
If p + k > m Then Return '第p個位置還需挑k個，不可能的不用再遞迴
u(p) = True
Call comb(b, u, p + 1, k - 1)
u(p) = False
Call comb(b, u, p + 1, k)
End Sub
Sub ttrim(ByRef s As String, ByVal a As String, ByVal b As String)
Do While InStr(s, a) > 0
s.Replace(a, b)
Loop
End Sub

Private Sub c75()
Dim b() = {2, 4, 7, 8, 6, 1, 3} '假設 7 選5
Dim u(7) As Boolean '是否選到
FileOpen(4, "o4.txt", OpenMode.Output)
' Array.sort(b) '不排序則使用原陣列序
comb(b, u, 0, 5)
Close()
End Sub
End Class

二信資處程式

2017年7月15日星期六

Z2A 7/12試題

Recent Posts

Categories

Blog Archive

著作人

2017年7月15日 星期六

Recent Posts

Categories

Blog Archive

著作人

訂閱

2017年7月15日星期六