递归法提升密码穷举算法性能

   在Google中查询“密码穷举算法”，可以得到大约5千个的结果，提供了一个C的算法实例。本文不想再重复拷贝这些实例代码，如果需要的兄弟可以在Google上搜索获得。本人在研读这些代码后，觉得可以使用递归以提升该算法的性能。

    惭愧的紧，本人对C代码就好像对上海话一样，能听懂一点，却说不溜。一句话，半调子。因此本文使用了VB.NET语言，希望大家可以理解。VB嘛，更好懂。

    下面提供了两段代码，使用了相同的声明。

    Friend Delegate Sub CallBack(ByVal Password As String)                              ' 密码输出回调

    Private Const PStartLen As Integer = 1
    Private Const PMaxLen As Integer = 6                                                ' 生成密码的最大长度
    Private PDict() As Char = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz".ToCharArray        ' 密码词典 
    

    第一段是C代码的一个VB.NET翻版：

    ' 翻版

    Friend Sub MakePass_General(ByVal Cnn As CallBack)
        Dim PDictLen As Long = Len(PDict)                                               ' 获得密码词典长度
        Dim CPass(PMaxLen - 1) As String                                                ' 将生成的密码
        Dim PLen As Integer

        For PLen = PStartLen To PMaxLen                                                 ' 密码长度
            Dim Array(PMaxLen - 1) As Integer                                           ' 密码词典下标
            Dim bNext As Boolean = True

            While bNext
                Dim i, j As Integer

                For i = 0 To PLen - 1
                    CPass(i) = PDict(Array(i))
                Next

                Cnn.Invoke(String.Join("", CPass))                                      ' 密码输出

                For j = PLen - 1 To 0 Step -1                                           ' 密码指针进位
                    Array(j) += 1

                    If Array(j) < PDictLen Then
                        Exit For
                    Else
                        Array(j) = 0
                        If (j = 0) Then bNext = False
                    End If
                Next
            End While
        Next
    End Sub

    第二段代码，使用了递归法进行了优化：

    ' 递归法密码穷举算法
    Friend Sub MakePass_Recursion(ByVal Cnn As CallBack)
        Dim PLen As Integer
        For PLen = PStartLen To PMaxLen                                                 ' 密码长度
            Dim CPass(PLen - 1) As String                                               ' 将生成的密码

            MakePass_Recursion(Cnn, CPass)
        Next
    End Sub
    Private Sub MakePass_Recursion(ByVal Cnn As CallBack, ByRef CPass() As String, Optional ByVal ID As Integer = 0)
        Dim i As Integer
        For i = 0 To PDict.Length - 1
            CPass(ID) = PDict(i)

            If ID = CPass.Length - 1 Then
                Cnn.Invoke(String.Join("", CPass))                                      ' 密码输出
            Else
                MakePass_Recursion(Cnn, CPass, ID + 1)
            End If
        Next
    End Sub

    代码很简单，勿虚多言。对两段代码进行了测试，使用递归法优化后的密码穷举算法较常规的算法提高了大约1倍的速度。

    班门弄斧，让高手们见笑了。请多指教。

本文地址：http://com.8s8s.com/it/it41601.htm