最長遞增子序列(4)承接最長遞增子序列(3), 改寫火車法, 讓程式碼可以Print出所有最長遞增數列C版本請至最長遞增子序列(4) (C語言版) Private Type typ_r value As Integer link_count As Integer link_point() As Integer '為了記錄多個可能的下一節車廂, 這邊使用陣列宣告 link_pnt_count As Integer '紀錄總共可能勾了幾個車廂End Type'increase progressively SeriesPrivate Sub sub_IPS(Optional PrintAll As Boolean = False) Dim s() As String Dim p As Integer Dim r() As typ_r Dim i As Integer, j As Long Dim maxLink_index As Integer Dim maxLink_Len As Integer s = Split(sq) p = UBound(s) ReDim r(p) maxLink_Len = 1 maxLink_index = p For i = p To 0 Step -1 With r(i) .value = s(i) .link_count = 1 .link_pnt_count = 0 '設定起始值0代表沒有勾上其他車廂 For j = i + 1 To p If .value < r(j).value Then If .link_count < (r(j).link_count + 1) Then .link_count = r(j).link_count + 1 ReDim .link_point(0) '重設車廂指標 .link_point(0) = j .link_pnt_count = 1 '勾了一個 If .link_count > maxLink_Len Then maxLink_Len = .link_count maxLink_index = i End If ElseIf .link_count = (r(j).link_count + 1) Then '當新長度=現在的長度時 ReDim Preserve .link_point(.link_pnt_count) .link_point(.link_pnt_count) = j .link_pnt_count = .link_pnt_count + 1 '增加勾上的可能性並記錄 End If End If Next End With Next If PrintAll Then For i = 0 To p If r(i).link_count = maxLink_Len Then'檢查每個數, 檢查鏈結長度是否為最大長度, 若是... Erase s 's拿來儲存字串用 Call SubLink(r, i, s) '利用遞迴的函數傳回所有子遞增數列字串 For j = 0 To UBound(s) Print s(j) '把字串全部Print出來 Next End If Next End If Print "須刪除:"; p - maxLink_Len + 1; "組"End SubPrivate Function SubLink(ByRef r() As typ_r, ByVal index As Integer, ByRef returnStr() As String) As String'列出r數列內index的位置的數字, 其子遞增數列, 並存入returnStr Dim i As Long, j As Long, k As Long Dim nStr() As String With r(index) If .link_pnt_count = 0 Then ReDim returnStr(0) returnStr(0) = .value '若沒有任何下一個聯結的數字, 則傳回自己 Exit Function End If For i = 0 To .link_pnt_count - 1 Call SubLink(r, r(index).link_point(i), nStr) '取得第(i)個連結的子遞增數列字串, 並存入nStr ReDim Preserve returnStr(k + UBound(nStr)) '加大returnStr的空間, 新大小=原始大小+nStr的大小 For j = 0 To UBound(nStr) '將所有子字串與自己串接, 存入returnStr returnStr(k + j) = r(index).value & " " & nStr(j) Next k = k + j '記錄一下現在的returnStr大小 Next End WithEnd Function至此結束遞迴的部份有點難以講解, 不明白的部份就請自行領悟了typ_r的link_point很像C的鏈結串列如果用C寫應該會更順!把link_point直接宣告成指標指向下一個車廂的位置就好了利用VB6.0測試演算法效能測試環境: AMD K7 XP3200測試條件: 長度100的不重複亂數，範圍1~1000測試次數: 隨機不同數列重複10000次花費時間: 226.999999629334秒平均時間: 0.0227秒(將Form不顯示以忽略Print的時間)速度極快最初的演算法跑長度100的不重複亂數，跑一次我都不願意...(唯一的一次是睡前按下去的)測試了一下超長數列的速度測試條件: 長度1000的不重複亂數，範圍0~1000僅測試一次PrintAll, 因為很花時間 [ sub_IPS(Ture)花費時間: 445秒由於可能性眾多, PrintAll堆疊極大, 非常花時間與記憶體同樣的條件下不PrintAll [ sub_IPS(False)執行1000次僅需122秒由此可知列舉眾多子數列才是最花時間的部份 .msgcontent .wsharing ul li { text-indent: 0; } 分享 Facebook Plurk YAHOO! .
