VBCoding Статьи Visual Basic 6 Visual Basic Комбинаторика и переборные алгоритмы

Visual Basic 6
Комбинаторика и переборные алгоритмы

Введение

    В этой статье будут рассмотрены основные понятия комбинаторики и переборные алгоритмы.
    

Что такое комбинаторика?

    Вам наверняка встречались такие задачи, в которых нужно найти количество способов, которыми можно расположить некоторые предметы, сделать действие и т.д. Именно такие задачи и решает комбинаторика.
    Основные понятия комбинаторики – перестановка, размещение и сочетание. Также на важном месте находится факториал.
    

Факториал

    n! (n факториал) – это произведение всех натуральных чисел от 1 до n (n! = 1 * 2 * 3 * ... * n).
    Условились считать, что 0! = 1! = 1.
    Факториал вычисляется очень легко:
    
    Private Function fact (ByVal n As Integer) As Double
       Dim i As Integer
       
       Fact = 1
       For i = 1 To n ‘перемножаем все числа от 1 до n
          fact = fact * i
       Next
    End Function
    
    Факториал можно также вычислить с помощью рекурсивного алгоритма:
    
    Private Function fact (ByVal n As Integer) As Double
       If n <= 0 Then ‘проверяем условие выхода из рекурсии
          fact = 1
       Else
          fact = num * fact (n – 1) ‘перемножаем промежуточный результат и на единицу меньшее число
       End If
    End Function
    
    Заметьте, что возвращаемое значение должно иметь тип Double. Это сделано, потому что факториал растёт очень быстро и уже 13! не умещается в рамки типа Long. Тип Double позволяет вычислять факториалы чисел до 170.
    Лучше использовать нерекурсивный алгоритм вычисления факториала, так как этот способ быстрее и при использовании рекурсии возможно переполнение стека.
    

Последовательности

    Предположим, нам нужно вывести в Textbox все последовательности длины N из чисел 1, 2, 3, ..., M. Первая последовательность будет иметь следующий вид:
    
    1, 1, 1, ..., 1
    
    , а последняя:
    
    M, M, M, ..., M.
    
    Всего таких последовательностей будет M ^ N.
    Пусть последовательность находится в одномерном массиве X. Создадим процедуру NextS, которая будет генерировать последовательность. Её нужно будет вызвать M ^ N раз. В процедуре NextS нужно перебрать все N знаков последовательности, начиная с последнего. Если знак равен M, то присваиваем ему значение 1, в ином случае увеличиваем его на единицу и выходим из цикла.
    
    Dim M As Integer
    Dim N As Integer
    Dim X() As Integer
    
    Private Sub Sequences()
    Dim i As Integer
    Dim j As Integer
    
    M = CInt (InputBox (“Введите M”))
    N = CInt (InputBox (“Введите N”))
    ReDim X(N)
    
    txtOut.Text = ""
    
    For i = 1 To N
        X(i) = 1
    Next
    Yes = False
    For i = 1 To M ^ N
             For j = 1 To N
    txtOut.Text = txtOut.Text & CStr(X(j))
             Next
            txtOut.Text = txtOut.Text & vbCrLf
             NextS
    Next
    End Sub
    
    Private Sub NextS()
    Dim i As Integer
    
    i = N
    Do While (i > 0) And (X(i) = M)
    X(i) = 1
    i = i - 1
    Loop
    If i > 0 Then (i) = X(i) + 1
    End Sub
    
    Все последовательности можно найти также и рекурсивным алгоритмом:
    
    Dim M As Integer
    Dim N As Integer
    Dim X() As Integer
    
    Private Sub SequencesRecursion()
    M = 5
    N = 5
    ReDim X(N)
    
    txtOut.Text = ""
    
    SRGenerate 0
    End Sub
    
    Private Sub SRGenerate (ByVal K As Integer)
    Dim i As Integer
    Dim j As Integer
    
    If K = N Then
    For i = 1 To N
    txtOut.Text = txtOut.Text & CStr(X(i))
    Next
    txtOut.Text = txtOut.Text & vbCrLf
    Else
    For j = 1 To M
    X(K + 1) = j
    SRGenerate (K + 1)
    Next
    End If
    End Sub
    

Перестановки

    Число перестановок – это число различных способов, которыми можно упорядочить данное множество, состоящее из n элементов.
    Число перестановок n элементов равно n!. Его можно вычислить следующим образом:
    
    Private Function PereCount (ByVal n As Integer) As Double
       PereCount = fact (n)
    End Function
    
    Private Function fact (ByVal n As Integer) As Double
       Dim i As Integer
       
       Fact = 1
       For i = 1 To n ‘перемножаем все числа от 1 до n
          fact = fact * i
       Next
    End Function
    
    Предположим, нам нужно вывести в TextBox все перестановки чисел от 1 до N. Создадим для этого рекурсивный алгоритм, который будет выглядеть так:
    
    Dim N As Integer
    Dim X () As Integer
    
    Private Sub Perestanovki ()
       Dim i As Integer
    
       N = CInt (InputBox (“Введите N”))
       ReDim X (N)
       For i = 1 To N
          X (i) = i
       Next
       PRGenerate 0
    End Sub
    
    Private Sub PRGenerate (ByVal k As Integer)
       Dim i As Integer
    
       If k = N Then
          For i = 1 To N
             txtOut.Text = txtOut.Text & CStr (X (i))
          Next
          txtOut.Text = txtOut.Text & vbCrLf
       Else
          For i = k + 1 To N
             Swap X (k + 1), X (i)
             PRGenerate k + 1
             Swap X (k + 1), X (i)
          Next
       End If
    End Sub
    
    Private Sub Swap (ByRef a As Integer, ByRef b As Integer)
       Dim c As Integer
    
       c = a
       a = b
       b = c
    End Sub
    

Сочетания

    Сочетание – это произвольное k-элементное подмножество n-элементного множества. Порядок элементов в подмножестве не имеет значения.
    Пример сочетаний по 2 из 3:
    
    12
    13
    23
    
    Число сочетаний находится по следующей формуле:
    
    C (n, k) = n! / (k! * (n-k)!)
    
    Число сочетаний можно вычислить, используя следующий код:
    
    Private Function SochCount (ByVal n As Integer, ByVal k As Integer) As Double
       SochCount = fact (n) / (fact (k) * fact (n-k))
    End Function
    
    Private Function fact (ByVal n As Integer) As Double
       Dim i As Integer
       
       Fact = 1
       For i = 1 To n ‘перемножаем все числа от 1 до n
          fact = fact * i
       Next
    End Function
    
    Есть и другой способ вычисления количества сочетаний. Его Вы можете использовать, если n! или k! не умещаются в рамках типа Double (если n>170 или k>170). Этот способ заключается в использовании треугольника Паскаля (он же арифметический треугольник, он же золотой треугольник).
    В 1653 году Блез Паскаль опубликовал «Трактат об арифметическом треугольнике». Этот треугольник был известен ещё в Древней Индии (X век). В XVI веке он был вновь открыт Штифелем.
    Треугольник Паскаля строится очень легко. Его бёдра и вершина состоят из единиц, а остальные элементы получаются сложением двух элементов, стоящих непосредственно над ним. Количество сочетаний будет равным элементу k треугольника, находящемуся в строке n. n и k нумеруются от нуля.
    Алгоритм вычисления числа сочетаний с использованием треугольника Паскаля представлен ниже:
    
    Private Function SochTT (ByVal n As Integer, ByVal k As Integer) As Double
       Dim i As Integer
       Dim j As Integer
       Dim TT () As Double
    
       ReDim TT (n, k)
       For i = 0 To n
          TT (0, i) = 1
          TT (i, i) = 1
       Next
       For i = 2 To n
          For j = 1 To i – 1
             TT (i, j) = TT (i – 1, j – 1) + TT (i – 1, j)
          Next
       Next
       SochTT = TT (n, k)
    End Function
    
    Если Вам нужно вычислять число сочетаний много раз, то, возможно, будет удобнее один раз построить треугольник Паскаля, а затем получать из массива данные.
    
    Dim TT () As Double
    
    Private Sub CreateTT ()
       ReDim TT (0, 0)
       BuildTT 0, 0
    End Sub
    
    Private Function SochTT (ByVal n As Integer, ByVal k As Integer) As Double
       If n > Ubound (TT) Then BuildTT Ubound (TT) + 1, n
       SochTT = TT (n, k)
    End Function
    
    Private Sub TerminateTT ()
       ReDim TT (0, 0)
    End Sub
    
    Private Sub BuildTT (ByVal start As Integer, ByVal end As Integer)
       Dim i As Integer
       Dim j As Integer
    
       ReDim Preserve TT (end, end)
       For i = start To end
          TT (0, i) = 1
          TT (i, i) = 1
       Next
       If end < 2 Then Exit Sub
       If start < 2 Then start = 2
       For i = start To end
          For j = 1 To i – 1
             TT (i, j) = TT (i – 1, j – 1) + TT (i – 1, j)
          Next
       Next
    End Sub
    
    Сначала нужно вызвать процедуру CreateTT. Затем Вы можете получать число сочетаний с помощью функции SochTT. Когда треугольник станет Вам не нужен, вызовите процедуру TerminateTT. В вышеуказанном коде при вызове функции SochTT, если треугольник ещё не достроен до необходимого уровня, то он достраивается с помощью процедуры BuildTT. Затем функция получает нужный элемент массива TT и возвращает его.
    Допустим, нам нужно вывести в TextBox все сочетания из N по K. Создадим для этого рекурсивный алгоритм, который будет выглядеть так:
    
    Dim X () As Integer
    Dim Counter () As Integer
    Dim K As Integer
    Dim N As Integer
    
    Public Sub Soch()
    Dim i As Integer
    
    N = CInt(InputBox("Введите N"))
    K = CInt(InputBox("Введите K"))
    
    K = K + 1
    
    ReDim X(N)
    
    For i = 1 To N
           X(i) = i
    Next
    txtOut.Text = ""
    
    ReDim Counter(K)
    Counter(0) = 1
    
    SochGenerate 1
    End Sub
    
    Private Sub SochGenerate(ByVal c As Integer)
    Dim i As Integer
    Dim j As Integer
    Dim n1 As Integer
    Dim Out() As Integer
    Dim X1() As Integer
    
       If c = K Then
          ReDim Out(K)
          
          X1 = X
          
          For i = 1 To K - 1
             n1 = 0
             For j = 1 To N
                If X1(j) <> 0 Then n1 = n1 + 1
                If n1 = Counter(i) Then
                   Out(i) = X1(j)
                   X1(j) = 0
                   Exit For
                End If
             Next
             txtOut.Text = txtOut.Text & CStr(Out(i))
          Next
          txtOut.Text = txtOut.Text & vbCrLf
       Else
          For Counter(c) = Counter(c - 1) To N - c + 1
             SochGenerate c + 1
          Next
       End If
    End Sub
    

Размещения

    Размещение – это произвольное k-элементное подмножество n-элементного множества. Порядок элементов в подмножестве имеет значение.
    Пример размещений из 3 по 2:
    
    12
    21
    13
    31
    23
    32
    
    Число размещений находится по формуле:
    
    A (n, k) = n! / (n – k)!
    
    Число размещений можно вычислить, используя такой код:
    
    Private Function RazmCount (ByVal n As Integer, ByVal k As Integer) As Double
       RazmCount = fact (n) / fact (n – k)
    End Function
    
    Private Function fact (ByVal n As Integer) As Double
       Dim i As Integer
       
       Fact = 1
       For i = 1 To n ‘перемножаем все числа от 1 до n
          fact = fact * i
       Next
    End Function
    
    Допустим, нам нужно вывести в TextBox все размещения из N по K. Это можно сделать очень легко. Размещения – это все перестановки всех сочетаний. Мы уже знаем, как найти все сочетания и все перестановки. Создадим алгоритм нахождения всех размещений:
    
    Dim X () As Integer
    Dim Counter () As Integer
    Dim Out() As Integer
    Dim K As Integer
    Dim N As Integer
    
    Private Sub Razm ()
    Dim i As Integer
    
    N = CInt(InputBox("Введите N"))
    K = CInt(InputBox("Введите K"))
    
    K = K + 1
    
    ReDim X(N)
       ReDim Out(K)
    
    For i = 1 To N
           X(i) = i
    Next
    txtOut.Text = ""
    
    ReDim Counter(K)
    Counter(0) = 1
    
    RazmSochGenerate 1
    End Sub
    
    Private Sub RazmSochGenerate ()
    Dim i As Integer
    Dim j As Integer
    Dim n1 As Integer
    Dim X1() As Integer
    
       If c = K Then
          
          X1 = X
          
          For i = 1 To K - 1
             n1 = 0
             For j = 1 To N
                If X1(j) <> 0 Then n1 = n1 + 1
                If n1 = Counter(i) Then
                   Out(i) = X1(j)
                   X1(j) = 0
                   Exit For
                End If
             Next
          Next
          PRGenerate 0
       Else
          For Counter(c) = Counter(c - 1) To N - c + 1
             RazmSochGenerate c + 1
          Next
       End If
    End Sub
    
    Private Sub PRGenerate (ByVal k As Integer)
       Dim i As Integer
    
       If k = N Then
          For i = 1 To N
             txtOut.Text = txtOut.Text & CStr (Out (i))
          Next
          txtOut.Text = txtOut.Text & vbCrLf
       Else
          For i = k + 1 To N
             Swap Out (k + 1), Out (i)
             PRGenerate k + 1
             Swap Out (k + 1), Out (i)
          Next
       End If
    End Sub
    
    Private Sub Swap (ByRef a As Integer, ByRef b As Integer)
       Dim c As Integer
    
       c = a
       a = b
       b = c
    End Sub
    

Заключение

    В этой статье были рассмотрены переборные алгоритмы и основы комбинаторики.
    
Павел Сурменок
Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
http://vbnet.ru
 

Добавить комментарий


Защитный код
Обновить

 
VBCoding Статьи Visual Basic 6 Visual Basic Комбинаторика и переборные алгоритмы  
Powered by Exponenta -