給2 個字串，請你輸出他們的最長共同子序列（longest common subsequence）的長度。
也就是說，在這兩個字串各自所有的子序列之中，內容相同而且長度最長的那個子序列。舉
例來說有兩個字串abcdgh 和aedfhr，它們的最長共同子序列為adh，長度為3。
輸入說明：
輸入檔含有多筆測試資料，每筆測試資料為二行字串，每行最多有 1000 個字元。
輸出說明：
對輸入的每筆測試資料，輸出它們最長共同子序列的長度。
輸入範例：
a1b2c3d4e
zz1yy2xx3ww4vv
abcdgh
aedfhr
輸出範例：
4
3
Dim s1(1000) As String
回覆刪除Dim s2(1000) As String
Private Sub Form_Load()
Open App.Path & "\in.txt" For Input As #1
Open App.Path & "\out.txt" For Output As #2
Do Until EOF(1)
ans = 0
Line Input #1, x
Line Input #1, y
Call qwe(x, y)
For i = 1 To Len(x)
For j = 1 To Len(y)
If s1(i) = s2(j) Then
ans = ans + 1
Exit For
End If
Next j
Next i
Print #2, ans
Loop
Close #2
Close #1
End Sub
Public Function qwe(a, b)
For i = 1 To Len(a)
s1(i) = Mid(a, i, 1)
Next i
For i = 1 To Len(b)
s2(i) = Mid(b, i, 1)
Next i
End Function
阿揚好，
回覆刪除1.分不清楚什麼是函數、副程式?
Public Function qwe(a, b)
依你的程式，呼叫了這兒，只是去做一段事情，並不需要傳回值。所以用，副程式就好了。
sub qwe(a,b)
2.Let X be "XMJYAUZ" and Y be "MZJAWXU". The longest common subsequence between X and Y is "MJAU"
也就是說，你的程式，錯誤。
這題可以參考這個wiki，如果看不懂，是不容易解出來這題的。
回覆刪除http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
function LCSLength(X[1..m], Y[1..n])
回覆刪除C = array(0..m, 0..n)
for i := 0..m
C[i,0] = 0
for j := 0..n
C[0,j] = 0
for i := 1..m
for j := 1..n
if X[i] = Y[j]
C[i,j] := C[i-1,j-1] + 1
else:
C[i,j] := max(C[i,j-1], C[i-1,j])
return C[m,n]
......| 0 1 2 3 4 5 6 7
.......| M Z J A W X U
-----|-----------------
0 . . | 0 0 0 0 0 0 0 0
1 .X | 0 0 0 0 0 0 1 1
2 .M| 0 1 1 1 1 1 1 1
3 .J | 0 1 1 2 2 2 2 2
4 .Y | 0 1 1 2 2 2 2 2
5 .A | 0 1 1 2 3 3 3 3
6 .U | 0 1 1 2 3 3 3 4
7 .Z | 0 1 2 2 3 3 3 4
Dim x As String
回覆刪除Dim y As String
Dim sum(100) As Integer
Private Sub Form_Load()
Open App.Path & "\in.txt" For Input As #1
k = 1
Do While Not EOF(1)
Input #1, x
Input #1, y
sumXY = sumXY + 1
For i = 1 To Len(x)
For j = 1 To Len(y)
a = Mid(x, i, 1)
b = Mid(y, j, 1)
If a = b Then
sum(k) = sum(k) + 1
End If
Next j
Next i
k = k + 1
maxK = k - 1
Loop
Close #1
Open App.Path & "\out.txt" For Output As #1
For i = 1 To maxK
Print #2, sum(i)
Next i
Close #1
End Sub
Private Sub Form_Load()
回覆刪除Open App.Path & "\in.txt" For Input As #1
Open App.Path & "\out.txt" For Output As #2
While Not EOF(1)
ReDim a(1000, 1000) As Integer
Input #1, x, y
n = Len(x): m = Len(y)
For i = 1 To n
X1 = Mid(x, i, 1)
For j = 1 To m
Y1 = Mid(y, j, 1)
If a(i, j - 1) > a(i - 1, j) Then
a(i, j) = a(i, j - 1)
Else
a(i, j) = a(i - 1, j)
End If
If X1 = Y1 Then
a(i, j) = a(i - 1, j - 1) + 1
End If
Next j
Next i
Print #2, a(n, m)
Wend
Close #2
Close #1
End Sub
Dim x(1000, 1000) As Integer
回覆刪除Dim sum(100) As Integer
Private Sub Form_Load()
Open App.Path & "\in.txt" For Input As #1
k = 1
a = ""
b = ""
Do While Not EOF(1)
Input #1, x1
Input #1, y1
sumXY = sumXY + 1
For i = 0 To 1
x(i, i) = 0
Next i
For i = 1 To Len(x1)
a = Mid(x1, i, 1)
For j = 1 To Len(y1)
b = Mid(y1, j, 1)
If a = b Then
x(i, j) = x(i - 1, j - 1) + 1
Else
If x(i, j - 1) > x(i - 1, j) Then
x(i, j) = x(i, j - 1)
Else
x(i, j) = x(i - 1, j)
End If
sum(k) = x(i, j)
End If
Next j
Next i
k = k + 1
sumk = k - 1
Loop
Close #1
Open App.Path & "\out.txt" For Output As #1
For i = 1 To sumk
Print #1, sum(i)
Next i
Close #1
End Sub
Private Sub Form_Load()
回覆刪除Open App.Path & "/in.txt" For Input As #1
Open App.Path & "/out.txt" For Output As #2
Do While Not EOF(1)
Input #1, strN, strM
ReDim a(1000, 1000) As Integer
N = Len(strN): M = Len(strM)
For i = 1 To N
x = Mid(strN, i, 1)
For j = 1 To M
y = Mid(strM, j, 1)
If x <> y Then
a(i, j) = a(i - 1, j)
If a(i, j - 1) > a(i - 1, j) Then a(i, j) = a(i, j - 1)
Else
a(i, j) = a(i - 1, j)
If a(i, j - 1) > a(i - 1, j) Then a(i, j) = a(i, j - 1)
a(i, j) = a(i, j) + 1
End If
Next j
Next i
Print #2, a(N, M)
Loop
Close #2
Close #1
End Sub
Private Sub Form_Load()
回覆刪除Open App.Path & "/in.txt" For Input As #1
Open App.Path & "/out.txt" For Output As #2
Do Until EOF(1)
Line Input #1, q1
Line Input #1, q2
ReDim st(Len(q1) + 1, Len(q2) + 1) As String
st(1, 0) = 0: st(0, 1) = 0: st(0, 0) = 0
For i = 1 To Len(q1)
st(i + 1, 0) = Mid(q1, i, 1)
st(i, 1) = 0
Next i
For i = 1 To Len(q2)
st(0, i + 1) = Mid(q2, i, 1)
st(1, i) = 0
Next i
Print
For i = 2 To Len(q1) + 1
For j = 2 To Len(q2) + 1
If st(i, 0) = st(0, j) Then
st(i, j) = st(i - 1, j - 1) + 1
Else
w1 = st(i - 1, j): w2 = st(i, j - 1)
If w1 > w2 Then
st(i, j) = w1
Else
st(i, j) = w2
End If
End If
Next j
Next i
Print #2, st(Len(q1) + 1, Len(q2) + 1)
Loop
Close #1
Close #2
End Sub
小白好，
回覆刪除1. 第一次的程式，當然是錯誤的。
2. 第二次的程式中，設第0列，全是0，與設第0欄，全是0，的寫法，是錯誤的。
(雖然程式是正常執行，那是因為，沒有設的值，會容錯地假設是0)
3. 你設了一個sumXY，可是卻全然沒用到。
4. 題目只是要求將那個值給寫入檔案，沒必要再用一個陣列來存它，做了一堆沒用的事。
在 sum(k)=x(i,j) 的地方，直接 print #1, x(i,j) 就好了。(當然，開檔要在這個的前方做好)
5. 這題中，你還是再一次用了
k=k+1
sumk = k -1
下次記得要「對調」。
高仔好，
回覆刪除1. ReDim a(1000,1000) 這一行，沒有必要。你是想要每重新讀入一組字串時，將陣列a的值，給重新歸0，但是，這個沒必要。因為，第0列的所有值，還是0。第0欄的，也是0。
然後，每個數都會重新給，上一次的值，並不會影響到這一次。
2. 這幾行寫的亂亂的。(應該也是錯的)
If x <> y Then a(i, j) = a(i - 1, j) If a(i, j - 1) > a(i - 1, j) Then a(i, j) = a(i, j - 1) Else a(i, j) = a(i - 1, j) If a(i, j - 1) > a(i - 1, j) Then a(i, j) = a(i, j - 1) a(i, j) = a(i, j) + 1 End If
---->
if x=y then
a(i,j) = a(i-1,j-1)+1
else
if a(i-1,j) > a(i,j-1) then
a(i,j)=a(i-1,j)
else
a(i,j)=a(i,j-1)
end if
end if
阿瑋好，
回覆刪除你的程式是對的。
good job.
阿揚好，
1.你的reDim那一行，一樣沒必要。
2.你的歸0，也是錯的，照說會有兩個字串的長度的和再加1個的0，你總共只設了3個0。
(那還不如就算了，不要設了，反正，vb容錯中，初始值也是0)
3.哦，原來你的陣列又當字串，又當數字的，這樣子，什麼時候出錯，自己也抓不出來哦。
要很小心。你這題st陣列，就拿來用數字就好了，不好嗎?
4. 但是，即便如此，你的程式的結果是正確的吧。(?)，但是，怪怪的漏洞太多，小心些。