[VB.NET] Compteur en binaire réfléchi (code Gray)

Voir le sujet précédent Voir le sujet suivant Aller en bas

[VB.NET] Compteur en binaire réfléchi (code Gray)

Message par Skynyrd777 le Ven 27 Aoû 2010 - 10:30

Bonjour,

Cet algorithme permet de compter en code Gros-Gray (ou binaire réfléchi) ; ce code qui permet d'incrémenter en binaire en ne modifiant qu'un seul bit par itération. Ce code peut être nécessaire dans certains dispositifs électroniques et intéressant dans certains problèmes algorithmiques tels les tours de Hanoï.

Les règles d'incrémentation sont :
- si le nombre de 1 dans le registre est pair, alors inverser le bit de poids faible (le dernier à droite).
- si le nombre de 1 est impair, alors inverser le bit à gauche du 1 le plus à droite. (sinon)

Algorithme en VB.NET
Code:
    Sub Main()

        ' Création du registre
        Dim lgreg As UInteger = 8
        Dim reg As String = ""
        reg = reg.PadLeft(lgreg, "0")
        Dim m As UInteger = 0
        Dim p As UInteger ' position du dernier 1

        ' Compteur itératif
        Do While reg <> "1".PadRight(lgreg, "0")
            Console.Out.WriteLine(reg) ' affichage
            m = 0
            For j As UInteger = 1 To lgreg ' compte les 1
                If Mid(reg, j, 1) = "1" Then
                    m += 1
                    p = j
                End If
            Next j
            ' inversion d'un bit
            If parite(m) Then
                reg = Mid(reg, 1, reg.Length - 1) & (Val(Mid(reg, reg.Length, 1)) Xor 1).ToString
            Else
                reg = Mid(reg, 1, p - 2) & (Val(Mid(reg, p - 1, 1)) Xor 1).ToString & Mid(reg, p, reg.Length)
            End If
        Loop

        Console.Out.WriteLine("1".PadRight(lgreg, "0"))
        Console.In.ReadLine()

    End Sub

    Function parite(ByVal x As Decimal) As Boolean
        Return Not ((x And 1) = 1)
    End Function

Notes : Le code est théoriquement censé revenir à 0 une fois atteint la valeur maximale du registre, ce que cet algorithme ne gère pas. Exemple : sur un registre de 5 bit, 0 se code "00000" en Gray et 31 (2^5-1) se code "10000" (valeur maximale du registre). On modifie la taille du registre dans la variable lgreg dans les déclarations (le registre est initialement à la taille d'un octet).
avatar
Skynyrd777
Admin

Messages : 216
Date d'inscription : 02/06/2010

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Voir le sujet précédent Voir le sujet suivant Revenir en haut

- Sujets similaires

 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum