Startseite / Tipps / VB.NET-Tipp 0004: Den Binomialkoeffizienten berechnen

VB.NET-Tipp 0004: Den Binomialkoeffizienten berechnen

 von Herfried Wagner

' Dieser Quellcode stammt von http://www.activevb.de
' und kann frei verwendet werden. Für eventuelle Schäden
' wird nicht gehaftet.

' Um Fehler oder Fragen zu klären, nutzen Sie bitte unser Forum.
' Ansonsten viel Spaß und Erfolg mit diesem Source!

' Projektversion:   Visual Studio 2002/2003
' Option Strict:    An
' Option Explicit:  An
'
' Referenzen: 
'  - System
'

' ##############################################################################
' ############################### BinomCoeff.vb ################################
' ##############################################################################
Option Explicit On 
Option Strict On
Option Compare Binary

Imports System

' <remarks>
'   Stellt Methoden zum Berechnen des Binomialkoeffizienten 
'   n über k bereit.
' </remarks>
Public Class BinomCoeff

    ' <summary>
    '   Gibt <paramref name="n"/> über <paramref name="k"/> zurück. 
    '   Die Berechnung erfolgt über ein iteratives Verfahren.
    ' </summary>
    '
    ' Berechnet n über k nach der Formel 
    '    B(n, k) = n! / k! * (n - k)!.
    '
    Public Shared Function BiFac( _
      ByVal n As Integer, _
      ByVal k As Integer) As Integer
        If n < k Then
            Throw New Exception("n must not be smaller than k.")
        Else
            Return FacIterative(n) \ (FacIterative(k) * (FacIterative(n - k)))
        End If
    End Function

    Private Shared Function FacIterative( _
      ByVal i As Integer) As Integer
        Dim j As Integer, k As Integer = 1
        For j = 1 To i
            k = k * j
        Next j
        Return k
    End Function

    ' <summary>
    '   Gibt <paramref name="n"/> über <paramref name="k"/> zurück. 
    '   Die Berechnung erfolgt über ein iteratives Verfahren.
    ' </summary>
    '
    ' Definition: B(n, k) = n! / (n - k)! * k!.
    ' Obige Formel kann gekürzt werden, wenn k < n ist, was immer zutrifft.
    '
    Public Shared Function BinomialCoeff( _
      ByVal n As Integer, _
      ByVal k As Integer) As Integer
        If n < k Then
            Throw New Exception("n must not be smaller than k.")
        Else
            Dim i As Integer
            Dim n1 As Integer = 1
            For i = (n - k + 1) To n
                n1 = n1 * i
            Next i
            Dim n2 As Integer = 1
            For i = 1 To k
                n2 = n2 * i
            Next i
            Return CInt(n1 / n2)
        End If
    End Function

    ' <summary>
    '   Gibt <paramref name="n"/> über <paramref name="k"/> zurück. 
    '   Die Berechnung erfolgt über ein rekursives Verfahren.
    ' </summary>
    '
    ' Berechnen des Binomialkoeffizienten über das herkömmliche 
    ' rekursive Verfahren. Also über die Rekursionsformel
    '   B(n, k) = B(n - 1, k - 1) + B(n - 1, k).
    ' Dieses Verfahren ist wegen seiner exponentiellen Laufzeit 
    ' für grössere Instanzen nicht verwendbar.
    '
    Public Shared Function BiRecursive( _
      ByVal n As Integer, _
      ByVal k As Integer) As Integer
        If n < k Then
            Throw New Exception("n must not be smaller than k.")
        Else
            Return BiRec(n, k)
        End If
    End Function

    Private Shared Function BiRec( _
      ByVal n As Integer, _
      ByVal k As Integer) As Integer
        If k = 0 Or n = k Then
            Return 1
        Else
            Return BiRec(n - 1, k - 1) + BiRec(n - 1, k)
        End If
    End Function

    ' <summary>
    '   Gibt <paramref name="n"/> über <paramref name="k"/> zurück. 
    '   Die Berechnung erfolgt über ein Verfahren, das auf 
    '   dynamischer Programmierung beruht.
    ' </summary>
    '
    ' Berechnung des Binomialkoeffizienten über einen Algorithmus, 
    ' der auf dem Prinzip der dynamischen Programmierung beruht.
    ' Dadurch kann die Laufzeit wesentlich verringert werden. 
    ' Durch Ausnützen der Tatsache, dass n über k gleich n über n - k ist,
    ' kann man den Aufwand zur Berechnung noch einmal reduzieren.
    '
    ' Die Idee zu diesem Algorithmus basiert auf dem Aufbau 
    ' des Pascalschen Dreiecks, das wie folgt aussieht:
    '
    '       1
    '      1 1
    '     1 2 1
    '    1 3 3 1
    '   1 4 6 4 1
    '
    ' Der Wert von n über k lässt sich dabei leicht ablesen, 
    ' indem man n "Ebenen" nach unten geht und dann k
    ' "Ebenen" nach rechts. Diese Pyramide wird im Datenfeld B 
    ' abgebildet, es werden allerdings nur die für die
    ' Berechnung erforderlichen Werte der Pyramide berechnet. 
    ' Die Pyramide ist für n über k, n > k immer n Stufen
    ' hoch und muss auf k Elemente "Breite" berechnet werden. 
    ' Diese Version des Algorithmus berechnet wirklich nur
    ' genau jene Felder, die man benötigt, es werden keine 
    ' Doppelberechnungen durchgeführt und die Matrix braucht
    ' nicht initialisiert zu werden. Laufzeit ist Theta((n - k) * k). 
    ' Ein weiterer Vorteeil des Verfahrens ist, dass
    ' keine Multiplikationen und Divisionen erforderlich sind.
    '
    Public Shared Function BiDynprog( _
      ByVal n As Integer, _
      ByVal k As Integer) As Integer
        If n < k Then
            Throw New Exception("n must not be smaller than k.")
        Else
            If n - k < k Then
                k = n - k
            End If
            Dim B(n, k) As Integer
            GoUpLeft(B, n, k)
            Return B(n, k)
        End If
    End Function

    Private Shared Sub GoUpLeft( _
      ByRef B(,) As Integer, _
      ByVal n As Integer, _
      ByVal k As Integer)

        ' Es wurde der obere Rand der Matrix erreicht oder 
        ' wir befinden uns auf der Diagonale. In diesem Fall
        ' setzen wir die Rekursion nicht fort, sondern beenden 
        ' sie und geben 1 zurück. Der obere Rand entspricht
        ' der rechten "Seite" des Pascalschen Dreiecks, der linke 
        'Rand der Diagonale. Man muss sich also oben
        ' angegebene Zeichnung um 90 Grad nach rechts rotiert vorstellen.
        If k = 0 Or k = n Then
            B(n, k) = 1

        ' Wir befinden uns "im Feld" und setzen die Rekursion fort.
        Else
            GoUpLeft(B, n - 1, k - 1)
            If k = 1 Then
                GoUpLeft(B, n - 1, k)
            Else
                GoLeft(B, n - 1, k)
            End If
            B(n, k) = B(n - 1, k - 1) + B(n - 1, k)
        End If
    End Sub

    Private Shared Sub GoLeft( _
      ByRef B(,) As Integer, _
      ByVal n As Integer, _
      ByVal k As Integer)
        If k = n Then
            B(n, k) = 1
        Else
            GoLeft(B, n - 1, k)
            B(n, k) = B(n - 1, k - 1) + B(n - 1, k)
        End If
    End Sub
End Class
' ##############################################################################
' ################################## Main.vb ###################################
' ##############################################################################
Option Explicit On 
Option Strict On
Option Compare Binary

Imports System

' <remarks>
'   Stellt den Einsprungspunkt der Anwendung bereit.
' </remarks>
Public Class Main

    ' <summary>
    '   Der Einsprungspunkt der Anwendung.
    ' </summary>
    Public Shared Sub Main()

        ' Iterative Version mit Fakultät.
        Console.WriteLine("Berechnung läuft, bitte warten...")
        Dim intStart As Integer = Environment.TickCount
        Console.WriteLine("BiFac: {0}", BinomCoeff.BiFac(12, 6))
        Console.WriteLine("Zeit: {0} ms", Environment.TickCount - intStart)

        ' Verbesserte iterative Version.
        Console.WriteLine("Berechnung läuft, bitte warten...")
        intStart = Environment.TickCount
        Console.WriteLine("BinomialCoeff: {0}", BinomCoeff.BinomialCoeff(12, 6))
        Console.WriteLine("Zeit: {0} ms", Environment.TickCount - intStart)

        ' Einfache Rekursion.
        Console.WriteLine("Berechnung läuft, bitte warten...")
        intStart = Environment.TickCount
        Console.WriteLine("BiRecursive: {0}", BinomCoeff.BiRecursive(12, 6))
        Console.WriteLine("Zeit: {0} ms", Environment.TickCount - intStart)

        ' Dynamische Programmierung.
        Console.WriteLine("Berechnung läuft, bitte warten...")
        intStart = Environment.TickCount
        Console.WriteLine("BiDynprog: {0}", BinomCoeff.BiDynprog(12, 6))
        Console.WriteLine("Zeit: {0} ms", Environment.TickCount - intStart)
    End Sub
End Class

Archivierte Nutzerkommentare 

Klicken Sie diesen Text an, wenn Sie die 4 archivierten Kommentare ansehen möchten.
Diese stammen noch von der Zeit, als es noch keine direkte Forenunterstützung für Fragen und Kommentare zu einzelnen Artikeln gab.
Aus Gründen der Vollständigkeit können Sie sich die ausgeblendeten Kommentare zu diesem Artikel aber gerne weiterhin ansehen.

n2 = 1
For i = 1 To k
    n2 = n2 * (n - i + 1) / i
Next i