VB的”最長遞增子序列” 是什麼意思??

Question

VB的\"最長遞增子序列\" 是什麼意思??
VB的\"最長遞增子序列\" 是什麼意思??
希望可以附上一小段的程式碼好理解...謝謝......

To: W.J.S. 大大
可否說明一下你的思考邏輯
如何寫出這段程式的...感激不盡!!

Answer 1

TO:Liu-Liu
這一題看起來好像挺有挑戰性,不知道您有沒有解出來?

2006-01-23 19:21:34 補充：
跟月大討論的結果還是用全組合去找,不知道答案對不對XD
Private Sub Command1_Click()
Dim S, S1 As String, Y() As Integer, I As Integer, T As Integer, B As Boolean
Dim L As Integer, P As Integer, MAX As Integer

S = Array(6, 11, 8, 15, 5, 13, 3, 10, 1, 4, 16, 12, 9, 17, 7, 2, 14)
P = UBound(S): L = P
Do
ReDim Y(L)
For I = 0 To L
Y(I) = I
Next
Do
S1 = "": T = S(Y(0)) - 1: B = True
For I = 0 To L
If T >= S(Y(I)) Then B = False: Exit For
T = S(Y(I)): S1 = S1 & S(Y(I)) & " "
Next
If B Then
T = UBound(Split(S1))
If T = L + 1 And T >= MAX Then Print S1: MAX = T
End If
If I > L Then I = L
For T = I To 0 Step -1
If Y(T) < P Then Y(T) = Y(T) + 1: Exit For
Next
If T < 0 Then Exit Do
For I = T + 1 To L
If Y(I - 1) + 1 <= P Then Y(I) = Y(I - 1) + 1
Next
Loop
L = L - 1
Loop Until L = 0
Print "最大長度為:"; MAX
End Sub

2006-01-23 21:39:58 補充：
TO:Liu-Liu
不知道全型空格能做資料縮排!今天又學了一招,謝謝您.

2006-01-24 18:11:20 補充：
利用組合,如123可組合成1,2,3,12,13,23,以此題共有17個數字可組合成6,11>6,8>...6,11,8>6,11,15...等再判斷每組中的數字是否遞增後再取出長度最大的那幾組就可.

2006-01-24 18:11:51 補充：
程式中Y陣列是為旗標;若以ABC為題做組合1個字組:ReDim Y(0)Y(0)=1>A,Y(0)=Y(0)+1=2>B,Y(0)=Y(0)+1=3>C已經到ABC的長度3,換計算2個字組2個字組:ReDim Y(1)Y(0)=1;Y(1)=Y(0)+1=2>AB,Y(0)=1;Y(1)=Y(1)+1=3>AC,已經到ABC的長度3,換 Y(0)進位Y(0)=Y(0)+1=2;Y(1)=Y(0)+1=3>BC3個字組:ReDim Y(2)Y(0)=1;Y(1)=Y(0)+1=2;Y(2)=Y(1)+1=3>ABC..收工文筆不好不知道你看得懂嗎?

2006-01-24 18:21:00 補充：
程式有再做修改,除去一些不必要的過程,放在以下網址:http://s56.yousendit.com/d.aspx?id=09QED18J3IJXD24OJ6DVTXG4WN

Answer 2

這一題如果只是要一組解和長度..O(nlogn)就可以辦到!<使用二分法加速!>

Liu-Liu 說的方法可以把LIS->(轉化成)LCS問題.

step1:先做O(nlogn)之sort
step2:做DP O(n^2)

總題時間複雜度O(n^2)

2006-09-29 09:14:28 補充：
二分法-->指二分搜尋法!

Answer 3

看不懂？

Answer 4

　先回答你的問題,再附上程式.
　何謂"子序列",就是從某數列中挑出部份元素,組成一個新數列,挑選時,位置順序不能亂對調,則新數列為原數列的"子序列",假如位置亂對調,則新數列為原數列的"子數列",而不是"子序列".
　舉個例子:A數列為 5,2,7,9,8,4,3,6 B數列為 7,8,4,6 C數列為 8,9,2,3,4 則 B 為 A 的子序列,而 C 只是 A 的"子數列",而不是"子序列".
　所有的"子序列"裏,屬於遞增的(右,後比左,前大的),且長度最大的(元素個數最多的),就是"最長遞增子序列",然而"最長遞增子序列"可能不只一個.
　舉個生活的例子:有8個石頭,排成一列,每個石頭有編號,由左往右編號為 5,2,7,9,8,4,3,6 現在你要從中挑出石頭,
條件是:由左往右,每次挑的編號要越來越大,這樣最多可挑幾個,要怎樣挑,答案是最多可挑 3 個,有 6 種挑法 5,7,9 及 5,7,8 及 2,7,9 及 2,7,8 及 2,4,6 及 2,3,6
　附上的程式,可以求出"最長遞增子序列"的長度,且可列出"最長遞增子序列"其中之一個,請在 Text1 輸入數列長度,再按 Command1,參考長度 3,10,500,1000.
注意: Vb6 可使用中文變數,中文程序名稱,中文函數,中文物件...等等.
以下是程式.
Option Explicit: DefLng A-Z
Dim 數列(), 列長(), 連接(), 數列長, 原數列$, 最長遞增子序列$
Private Sub Command1_Click()
　Call 準備: Call 處裡: Call 秀出
End Sub
Sub 準備(): Dim 數
　數列長 = Val(Text1): ReDim 數列(數列長 + 1), 列長(數列長 + 1), 連接(數列長 + 1)
　Randomize: For 數 = 1 To 數列長: 數列(數) = Rnd * 100: Next
　數列(0) = -1000000: 數列(數列長 + 1) = 1000000: 列長(數列長 + 1) = 1
End Sub
Sub 處裡(): Dim 指標, 搜尋
　For 指標 = 數列長 To 0 Step -1
　　For 搜尋 = 指標 + 1 To 數列長 + 1
　　　If 數列(搜尋) >= 數列(指標) And 列長(搜尋) > 列長(指標) Then
　　　　列長(指標) = 列長(搜尋): 連接(指標) = 搜尋
　　　End If
　　Next
　　列長(指標) = 列長(指標) + 1
　Next
End Sub
Sub 秀出(): Dim 數
　Cls
　原數列 = "": 最長遞增子序列 = ""
　For 數 = 1 To 數列長
　　原數列 = 原數列 + "," + Str(數列(數))
　Next
　數 = 連接(0)
　Do Until 數 = 數列長 + 1
　　最長遞增子序列 = 最長遞增子序列 + "," + Str(數列(數))
　　數 = 連接(數)
　Loop
　Print "原數列為:", Mid(原數列, 2)
　Print "最長遞增子序列為:", Mid(最長遞增子序列, 2)
　Print "最長遞增子序列長度為:", 列長(0) - 2
End Sub

Answer 5

...程式碼這麼長阿......
那我可能要花一點時間來看他了...
(因為本人不是很厲害,初學者)

Answer 6

最長遞增子序列：就是從一些數所組成的數列中，找出一個遞增的子序列，而且所包含的元素是最多的。
例如：
　6、11、8、15、5、13、3、10、1、4、16、12、9、17、7、2、14
　其最長遞增子序列長度為5 （如6、8、10、12、14 ，答案可能不唯一，但最大長度是5）
如果用電腦直接一個一個找，可能要找 2^n 次，如果用動態規劃來處理頂多是 n^2 次，電腦在 n=400 時瞬間就可算出來，可見動態規劃在解題時，有其很高的價值與幫助。

2006-01-23 08:50:01 補充：
to:W.J.S.
本人可沒這麼厲害，若有高手會解，則歡迎發表。

2006-01-23 19:28:58 補充：
給 W.J.S. 小小的建議：
建議利用全型空格來做資料縮排的動作。