Cours VB.NETDate de mise à jour : 05/12/2010
V-T. Les nombres aléatoires
V-T-1. Avec la classe 'Random' du Framework
V-T-2. Avec les instructions Rnd() et Randomize() de Visual Basic.Net
V-T-3. En cryptographie avec le Framework
V-T-4. Un peu de théorie
V-U. La 'Récursivité'
V-U-1. Règles fondamentales d'une fonction récursive
V-U-2. Exemple 1 : Inversion de chaînes
V-U-3. Exemple 2 : Calcul de 'Factorielle'
V-U-4. Exemple 3 : Calcul d'une expression avec parenthèses multiples
V-U-5. Exemple 4 : PGCD
V-U-6. Exemple 5 : Tri récursif
V-U-7. Exemple 6 : Parcours de répertoires et de sous répertoires
V-U-8. Exemple 7 : Évaluation d'un nombre écrit en chiffres romains
V-U-9. Exemple 8 : Suite de Fibonacci
V-U-10. Exemple 9 : Fractales
V-U-11. Autre
V-V. Faut-il oublier le GoTo ?
V-V-1. Le 'Goto'
V-V-2. Pourquoi éviter le 'GoTo'
V-V-3. Quand utiliser le 'GoTo'
V-W. Les bases binaires, hexadécimales, l'algèbre de Boole
V-W-1. Introduction
V-W-2. Notions théoriques
V-W-3. Pratique en Visual Basic
V-W-4. Viewer hexadécimal
V-W-5. Éditeur hexadécimal
V-T. Les nombres aléatoires
Comment obtenir un nombre aléatoire?
V-T-1. Avec la classe 'Random' du Framework
Il existe une classe (faisant partie de System ) nommée Random.
La méthode Next() retourne un Integer positif entre 0 et 2 147 483 647
La méthode NextDouble() retourne un Double entre 0 et 1.
La méthode NextBytes() retourne un Byte (octet)
On peut surcharger ces méthodes pour définir des bornes.
Exemple:
J'instancie une objet à partir de la classe.
L'objet Al est initialisé avec une valeur probablement liée au temps, à l'horloge interne, aussi l'initialisation est 'aléatoire'.
Pour obtenir un nombre (un double) entre 0 et 1 (toujours inférieur à 1)j'écris:
MonNombrealeatoire=Al.NextDouble
|
Ensuite chaque NextDouble génère le nombre aléatoire suivant (à partir d'une formule)
Noter bien que dans ce qui précède, si on fait plusieurs fois Dim Al As New Random , le nombre obtenu par NextDouble n'est jamais le même.
Par contre si on fait:
Dim Al As New Random(1)
MonNombrealeatoire=Al.NextDouble
MonNombrealeatoire=Al.NextDouble
|
On obtient toujours:
'0.248668584157093'
'0.110743977181029'
On obtient donc la même série car on a imposé avec Random(1) une valeur de départ qui est fonction de (1) et non du temps.
Pour obtenir un nombre aléatoire entre 0 et 10, on utilise Next:
Dim Al As New Random()
MonNombrealeatoire=Al.Next(10)
MonNombrealeatoire=Al.Next(10)
|
On obtient la série: 2, 1, 4, 7, 6, 4, 3, 9
On travaille sur des 'Integer'
Pour obtenir un nombre aléatoire entre 5 et 10 (mais < à 10), on utilise Next:
Dim Al As New Random()
MonNombrealeatoire=Al.Next(5,10)
MonNombrealeatoire=Al.Next(5,10)
|
La série comportera les nombres integers 5, 6, 7, 8, 9 (pas 10)
Pour remplir un tableau d'octets avec des octets aléatoires, on utilise NextBytes:
Dim rnd As New Random()
Dim b(10) As Byte
rnd.NextBytes(b)
|
V-T-2. Avec les instructions Rnd() et Randomize() de Visual Basic.Net
On peut utiliser les instructions VB. Ne faut-il pas mieux utiliser le Framework?
Rnd() fournit un nombre aléatoire entre 0 et 1 (sans jamais atteindre 1):valeur inférieure à 1 mais supérieure ou égale à zéro; ce nombre aléatoire est un Single.
En fait ,si on fait des Rnd() successifs, le nombre aléatoire précédemment généré est utilisé pour le calcul du nombre aléatoire suivant (avec une formule mathématique complexe), ce qui fait que la suite de nombres aléatoires est toujours la même et qu'elle est périodique (au bout d'un grand nombre de tirage, on recommence la même suite).
Randomize() initialise le générateur de nombres aléatoires. Si on ne donne pas d'argument, Randomize utilise la valeur de l'horloge interne pour initialiser; cette valeur est dû au hasard, aussi le Rnd qui suit va être dû au hasard.
Si on n'utilisait pas Randomize() avant Rnd(), la fonction Rnd() fournirait toujours les mêmes nombres aléatoires dans le même ordre.
En résumé:
Rnd , si il n'y a pas d'argument, fournit une suite de nombre pseudo aléatoire (le suivant étant calculé à partir du précédent), la suite est toujours la même, seule le premier change et est initialisé par Randomize qui est basé soit sur l'horloge système (et qui à priori initialise à une valeur toujours différente) s'il n'y a pas d'argument soit sur un argument.
Pour obtenir plusieurs fois les mêmes séries de nombres , utiliser Randomize avec un argument numérique puis appelez Rnd() avec un argument négatif.
Simuler un jeu de lancé de dé.
Comment obtenir un nombre entier entre un et six au hasard?
Dim MyValue As Integer
Randomize
MyValue = CInt(Int((6 * Rnd()) + 1))
|
Rnd() fournissant un nombre aléatoire entre 0 et 1, je le multiplie par 6 et j'ajoute 1 pour qu'il soit entre 1 et 7 sans atteindre 7 (il peut être entre 1 et 6,999), je prend sa valeur entière: il est maintenant entre 1 et 6, enfin je le transforme en Integer.
V-T-3. En cryptographie avec le Framework
Pour remplir un tableau d'octets avec des octets aléatoires forts d'un point de vue cryptographique (pour générer un mot de passe par exemple), on utilise plutôt la classe RNGCryptoServiceProvider()
L'exemple suivant crée une séquence aléatoire de 100 octets de long et la stocke dans ra.
Imports System.Security.Cryptography
Dim ra() As Byte = New Byte(100) {}
Dim rng As New RNGCryptoServiceProvider()
rng.GetBytes(ra)
|
Il existe aussi GetNonZeroBytes pour ne pas avoir d'octet=0.
V-T-4. Un peu de théorie
Un nombre aléatoire est obtenu par tirage au sort à égalité des chances, il est impossible de prévoir le tirage suivant.
Il existe des procédures physiques permettant de générer des nombres aléatoires: comptage de désintégration par compteur Geiger, analyse de bruit..
En informatique, on utilise les nombres pseudo aléatoires générés par des algorithmes.
L'implémentation actuelle de la classe Random est basée sur l'algorithme du générateur de nombres aléatoires soustractif de Donald E. Knuth. Pour plus d'information, consultez D. E. Knuth. « The Art of Computer Programming, volume 2: Seminumerical Algorithms. » Addision-Wesley, Reading, MA, deuxième édition, 1981.
Soit un nombre de départ x (nommé' graine'ou seed en anglais)
Le nombre est utilisé pour le calcul du nombre aléatoire suivant (avec une formule mathématique complexe), ce qui fait que la suite de nombre aléatoire est toujours la même pour une même graine et qu'elle est périodique.
La formule, dite générateur à congruence linéaire, pour trouver le nombre suivant, est de la forme:
Xn+1 = (aXn+b) mod m
xn+1 = (1 664 525 xn + 1 013 904 223) mod 232 (générateur de Knuth & Lewis)
Voir l'excellent article sur les nombres pseudo aléatoires:Article de P larbier:http://www.alrj.org/docs/algo/random.php
et l'excellent site de D. Müller: www.apprendre-en-ligne.net/random/index.html
On a vu que le générateur est périodique: au bout d'un certain nombre de tirage pseudo aléatoire, dès qu'un nombre apparaît la seconde fois, on recommence la même série. En théorie, la période maximale serait m de mod m dans la formule soit 232.
Quelle est la période de la Classe Random en pratique?
Période: 81 672 063 avec Next (Integer)
Période: 562 183 903 avec NextDouble (Double)
C'est un ordre de grandeur car en fonction de la graine (valeur de départ), la série et la période sont différentes (j'ai essayé!).
Tout l'art est de choisir la graine (le premier nombre) aléatoirement!!Cela est effectué par Randomize en VB ou l'instanciation d'un objet Random. Randomize utilise par exemple la valeur de l'horloge interne pour initialiser; cette valeur serait dû au hasard
Amélioration :
Comment générer des nombres plus aléatoires que les pseudo aléatoires?
1- Solution créée par le programmeur:
Le nombre aléatoire est la combinaison d'un nombre pseudo aléatoire et d'un nombre probablement aléatoire par exemple:
-Position de la souris
Temps entre 2 pressions sur des touches.
-Statistique d'activité du disque dur.
-Temps écoulé depuis.. (Ce que fait randomize).
Exemple:
Le nombre aléatoire est le produit d'un nombre pseudo aléatoire et du nombre de seconde écoulé depuis une date:
Dim pAlea As Double
Dim second As Double
Dim Alea As Double
Randomize
pAlea = Int((1000000 * Rnd) + 1)
second = DateDiff("s", "12/30/96", Now)
Alea = second *pAlea
|
Il y a des biais, en particulier, si on utilise régulièrement cette routine, le nombre de seconde est régulièrement croissant. On pourrait améliorer en utilisant second Mod quelque chose.
2- Solution proposée par le Framework:
Méthode utilisée dans la classe System.Security.Cryptography
Le générateur doit être capable de produire des nombres aléatoires résistant à des attaques ou à des analyses statistiques qui permettraient de prédire la suite.
Les méthodes courantes pour générer des nombres aléatoires en cryptographie consistent à utiliser diverses sources disponibles sur un ordinateur: temps entre deux accès au disque, taille de la mémoire, mouvements du pointeur de la souris... et à faire passer le résultat dans une fonction de hachage cryptographique comme MD5 ou SHA-1 puis à utiliser cette valeur comme graine puis...
V-U. La 'Récursivité'
La récursivité c'est quoi?
Exemple trouvé sur developpeur.journaldunet.com :
"C'est l'histoire d'un petit garçon qui ne voulait pas dormir et dont la mère lui raconte l'histoire de la petite grenouille qui ne voulait pas dormir et dont la mère lui raconte l'histoire de l'ourson qui ne voulait pas dormir et dont la mère lui raconte l'histoire du bébé écureuil qui s'est endormi, et l'ourson s'endormi, et la petite grenouille s'endormi, et le petit garçon s'endormi."
Cette histoire, permet de mieux voir ce qui se produit lors de la récursivité: la procédure (le petit qui ne dort pas et à qui on raconte une histoire) appelle, la même procédure (le petit qui ne dort pas et à qui on raconte une histoire) qui appelle la même procédure..... on passe au "niveau" suivant puis au suivant tant qu'on n'a pas atteint la condition d'arrêt (ici, l'endormissement). Celle-ci atteinte, la récursion se termine pour les autres niveaux en sens inverse en remontant.
 |
Une procédure est récursive si elle peut s'appeler elle même.
|
VB accepte les procédures récursives:
Sub Calcul()
..
Calcul()
..
End Sub
|
On voit ici que la procédure Calcul() s'appelle elle même: la ligne centrale appelle de nouveau la procédure Calcul() avec nouveaux paramètres, nouvelles variables locales, à la sortie de la procédure (après End Sub), retour à la 'version' précédente de la procédure Calcul() ou on retrouve les variables de la précédente version.
|
Une procédure non récursive appelle, elle, d'autres procédures.
|
Pourquoi utiliser la récursivité?
Une procédure récursive découpe le problème en morceaux plus petits et s'appelle elle-même pour résoudre chacun des plus petits morceaux, elle résout une petite partie du problème elle même.
Sub Calcul(Gros)
If..
Résout petit problème
Else
Découpe
Calcul(Petit)
End If
End Sub
|
Ici 'Résout petit problème' s'appelle le point terminal ou le point d'arrêt, c'est la branche qu'une condition qui n'appelle pas de nouveau la fonction Calcul(). C'est indispensable.
Ou bien elle découpe le problème en plus petits morceaux et pour chaque morceau on appelle de nouveau le procédure:
Sub Calcul(Gros)
If..
Découpe
Calcul(Petit)
End If
End Sub
|
A un moment donné, la condition n'est pas remplie, cela correspond au point terminal.
On se rend compte qu'une bouche For Next peut être transformée en procédure récursive:
Exemple :
Créons une procédure qui ajoute N éléments par ordre décroissant (ajoute l'élément N puis N-1 puis ... 2 puis 1)
On l'appelle avec Calcul(10) par exemple:
Avec For:
Function Calcul(N As Integer)
Dim total As Integer
For i= N to 1 Step-1
total=total + i
Next i
Calcul=total
End Function
Function Calcul(N As Integer)
Dim total As Integer
If N>0 Then
total= N+ Calcul (N-1)
End If
Calcul= total
End Fonction
|
On l'appelle avec Calcul(10)
Mais la récursivité ne sert pas seulement à cela, elle sert à résoudre aussi des problèmes qui seraient extrêmement complexes en programmation non récursive.
V-U-1. Règles fondamentales d'une fonction récursive
1-La récursivité doit s'arrêter à un moment donné.
Il doit y avoir un point terminal (ou point d'arrêt);
Il doit y avoir dans la fonction récursive, une expression conditionnelle dont au moins un des cas conduit à une expression évaluable.
Il doit donc y avoir un chemin non récursif (chemin ou la fonction ne s'appelle pas de nouveau).
Il doit y avoir un test qui survient obligatoirement et qui arrête le fonctionnement récursif sinon la fonction tourne sans fin (ou du moins, elle plante quand la pile est pleine).
2- A aucun moment les paramètres appelant de nouveau la fonction doivent être les mêmes que l'appel précédent.
Sinon cela tournera indéfiniment.
3-Le nombre d'appel récursif ne doit pas être très grand.
Sous peine de 'StackOverflow': la pile des appels qui stocke les adresses de retour de chaque appel récursif est pleine, elle dépasse ses capacités.
Certains ajoutent dans le code de la fonction récursive 'un compteur de sécurité':
Sub Calcul(ByRef Compteur As Long)
If Compteur> LIMITE Then Exit Sub
Compteur= Compteur+1
..
Calcul(Compteur)
..
End Sub
|
Noter que le compteur est un paramètre ByRef, ce qui permet de toujours incrémenter la même variable.
Voir exemple sur les fractales.
4-La fonction récursive ne doit pas déclarer un grand nombre de variables ou d'objets.
Sous peine d'occuper une place trop importante en mémoire.
5-Limiter les fonctions récursives à une seule procédure, éviter plusieurs fonctions récursives imbriquées.
Sinon cela devient vite trop complexe.
6- Chaque fois qu'elle est appelée de manière récursive (par elle-même, donc), un ou plusieurs des arguments qui lui sont transmis doivent se rapprocher de la condition d'arrêt.
Sinon il n'y aura pas d'arrêt.
7- La complexité du problème doit être réduite à chaque nouvel appel récursif.
8- Ne peut-on pas faire plus simple avec une boucle For Next?
Parfois une boucle simple remplace avantageusement une fonction récursive. Dans ce cas utiliser la boucle!!
C'est le cas de la fonction factorielle!!
V-U-2. Exemple 1 : Inversion de chaînes
Soit une chaîne de caractères, on veut une fonction qui inverse cette chaîne: dernier caractère en premier, avant dernier en second...
Exemple: "abcd" retournera "dcba"
Principe de la fonction 'inverse' récursive:
La fonction 'inverse' met le dernier caractère au début et appelle la fonction 'inverse' avec comme paramètre la chaîne moins le dernier caractère.
Exemple "abcd", on met "d" au début et rappelle la fonction inverse avec comme paramètre "abc"
Point d'arrêt: si la chaîne est vide, plus d'appel récursif, on retourne une chaîne vide.
Function inverse(ByVal st As String) As String
If st = "" Then
inverse = ""
Else
inverse = st.Substring(st.Length() - 1, 1) + inverse(st.Substring(0, st.Length() - 1))
End If
End Function
|
V-U-3. Exemple 2 : Calcul de 'Factorielle'
On rappelle que N! (factorielle N)= 1*2*3*...*(N-2)*(N-1)*N
Exemple Factorielle 3 =1*2*3
Dim R As Long
R=Factorielle(3)
|
Cette fonction n'est pas fournie par VB, créons une fonction Factorielle SANS récursivité:
Function Factorielle (ByVal N as Long) As Long
Dim i As Long
Resultat=1
For i= 1 to N
Resultat=i* Resultat
Next i
Return Resultat
end Function
|
Cela crée une fonction recevant le paramètre N et retournant un long.
La boucle effectue bien 1*2*3...*N-1*N.
Factorielle avec 'Récursivité':
Une autre manière de calculer une factorielle est d'utiliser la récursivité.
Comment faire?
On sait que N!= N * (N-1) * (N-2).... 3 * 2 * 1
on remarque donc que Factorielle N!= N * Factorielle(N-1)
N!= N*(N-1)! : en sachant que 1!=1
Créons la fonction:
Si N=1 la fonction retourne 1 sinon elle retourne N* factorielle(N-1)
Function Factorielle (ByVal N as Long) As Long
If N=1 then
Return 1
Else
Return N* Factorielle(N-1)
End If
end Function
|
Dans la fonction Factorielle on appelle la fonction Factorielle, c'est bien récursif.
Pour N=4:
La fonction 'descend' et appelle chaque fois la factorielle du nombre inférieur.
La fonction Factorielle est appelée 4 fois :
Factorielle (4) appelle Factorielle(3) qui appelle Factorielle(2) qui appelle Factorielle (1)
Puis la fonction remonte en retournant le résultat de chaque factorielle.
Factorielle (1) retourne 1
Factorielle (2)retourne 2 '2*factorielle(1)
Factorielle (3)retourne 6 '3*factorielle(2)
Factorielle (4) retourne 24 '4*factorielle(3)
Vb gère cela avec une pile des appels. il met dans une pile les uns aux dessus des autres les appels, quand il remonte, il dépile de haut en bas (Dernier rentré, premier sortie)
 |
Attention: La pile a une taille maximum, si N est trop grand, on déclenche une erreur de type StackOverflow.
|
V-U-4. Exemple 3 : Calcul d'une expression avec parenthèses multiples
Comment calculer la valeur de la chaîne "(4+2(2*8)-(5/(8+1)))"
Une partie du code nommée Calculsimple sait calculer une chaîne de type "8+1" ou "4+2" sans parenthèses.
Il faut gérer les parenthèses: la sub découpe ce qui est entre parenthèse et s'appelle elle-même pour calculer ce qui est entre parenthèses:
La sub calcul fait 2 choses:
S'il y a des parenthèses: appelle Calcul() avec comme paramètre la chaîne entre parenthèse puis remplace la chaîne entre parenthèse par sa valeur
Si il n'y a pas de parenthèses calcule l'expression simple (= - * /).
Voici l'algorithme:
Sub Calcul(Chaine As String) As String
Si Chaine contient "("
Decouper ValeurEntreParenthese
Resultat=Calcul (ValeurEntreParenthese)
Remplacer (ValeurEntreParenthese) par Resultat
Sinon
CalculSimple
Fin Si
End Sub
|
V-U-5. Exemple 4 : PGCD
On rappelle que le PGCD est le 'Plus Grand Commun Diviseur'.
Soit a et b 2 nombres:
Si b divise a => PGCD=b. sinon, PGCD(a,b) = PGCD(b, a mod b)
Function PGCD(ByVal P As Long, ByVal Q As Long) As Long
If Q Mod P = 0 Then
Return P
Else
Return PGCD(Q, P Mod Q)
End If
|
V-U-6. Exemple 5 : Tri récursif
Tri récursif
Le principe est que la fonction récursive scinde le tableau en 2 et pour chaque partie appelle de nouveau le tri récursif, la condition d'arrêt survient quand le dernier élément est < ou = au premier.
Dans un premier temps on range le tableau de telle sorte que tous les éléments inférieurs à l'élément d'indice pivot se trouvent placés à la gauche de celui-ci et donc tous les éléments supérieurs à sa droite. Ensuite on appelle à nouveau (récursivement) la procédure QuickSort pour chacun des deux sous-tableaux.
Cette méthode de tri récursif qui se nomme QuickSort est proportionnellement efficace au désordre du tableau à trier. Cette méthode mettra plus de temps (qu'une autre méthode) à trier un tableau qui est déjà en parti trié qu'un tableau rangé au hasard... Mais en cas de désordre intégral, c'est certainement la plus rapide.
Sub QuickSort(debut As Integer, fin As Integer)
Dim pivot, gauche, droite, temp As Integer
pivot = debut
gauche = debut
droite = fin
do
if t(gauche) >= t(droite) then
temp = t(gauche)
t(gauche) = t(droite)
t(droite) = temp
pivot = gauche + droite - pivot
End If
if pivot = gauche then droite=droite-1 else gauche=gauche+1
loop until gauche = droite
if debut < gauche - 1 then QuickSort(debut, gauche - 1)
if fin > droite + 1 then QuickSort(droite + 1, fin)
End Sub
|
Comment l'utiliser:
On crée un tableau Public d'integer contenant les valeurs à trier:
Public t() As Integer = {10, 2, 7, 4, 1, 3, 12, 6}
|
Dim i As Integer
Call QuickSort(0, 7)
|
Affichage du tableau trié dans une texteBox1
For I = 0 To 7
TextBox1.Text = TextBox1.Text + ControlChars.CrLf + t(i).tostring
Next
|
V-U-7. Exemple 6 : Parcours de répertoires et de sous répertoires
On veut afficher dans une ListBox les noms des répertoires, sous-répertoires et fichiers:
On crée une routine AfficheTree qui affiche:
-Le nom du répertoire courant.
-Le nom des fichiers du répertoire courant.
-Qui parcourt les sous-répertoires et pour chacun d'eux appelle AfficheTree
Imports System.IO
Sub AfficheTree ( ByVal myDir As String, ByVal Optional Niveau As Integer =0)
List1.Items.Add(New String (" ", niveau *2) & myDir)
For Each fichier As String In Directory.GetFiles( myDir)
List1.Items.Add(New String (" ", niveau *2+2) & fichier)
Next
For each sousRepertoire As String In Directory.GetDirectories( myDir)
AfficheTree (sousRepertoire, niveau+1)
Next
End Sub
|
V-U-8. Exemple 7 : Évaluation d'un nombre écrit en chiffres romains
On veut taper III et voir s'afficher 3
taper M et voir s'afficher 1000
taper XLVIII et voir s'afficher 48
On remarque (je l'ai pas fait tout seul!!) que:
Chaque caractère romain a une valeur (I=1, V=5, X=10, L=50, C=100, D=500, M=1000)
Pour deux caractères, on compare leurs valeurs:
Si le premier est plus petit, on le soustrait au second: IX = 10 - 1 = 9
Si le premier est plus grand, on l'ajoute au second: VI = 5 + 1 = 6
Pour une suite de n caractères: en partant de la gauche, si le premier chiffre a une valeur inférieure au deuxième, alors on le soustrait de la valeur de tout le reste, sinon on l'additionne à la valeur de tout le reste..
Le programme va donc comparer la valeur des 2 caractères de gauche; il va ajouter (si la valeur du premier est plus grande) ou soustraire (si la valeur du premier est plus petite) la valeur du premier caractère à la valeur de la chaîne raccourcie du premier caractère.
Exemple: pour XLVIII
X plus petit que L donc -10 +valeur de (LVIII)
L plus grand que V donc -10 +50 + valeur de (VIII)
V plus grand que I donc -10 +50 + 5 + valeur de (III)
...
|
Il faut créer un routine nommée valeur qui calcule la valeur d'un caractère.
Et la routine Eval qui calcule l'expression
S'il y a un caractère dans la chaîne c passée en paramètre, on retourne sa valeur, s'il y en a plusieurs, on compare les 2 premiers caractères, et on additionne ou soustrait à la valeur du premier caractère l' Eval (appel récursif) du reste de la chaîne.
Function valeur(ByVal c As Char) As Integer
Select Case c
Case "M"c : valeur = 1000
Case "D"c : valeur = 500
Case "C"c : valeur = 100
Case "L"c : valeur = 50
Case "X"c : valeur = 10
Case "V"c : valeur = 5
Case "I"c : valeur = 1
End Select
End Function
Function eval(ByVal s As String) As Integer
Dim n As Integer
If s.Length = 1 Then
eval = valeur(s.Chars(0))
Else
n = valeur(s.Chars(0))
If n < valeur(s.Chars(1)) Then n = -n
eval = n + eval(s.Substring(1, s.Length - 1))
End If
End Function
|
Si on veut tester: créer dans une form 2 texteBox: TextDecimal, TextRomain et un bouton Button1
Private Sub Button1_Click
TextDecimal.Text = eval(TextRomain.Text).ToString
End Sub
|
V-U-9. Exemple 8 : Suite de Fibonacci
« Possédant initialement un couple de lapins, combien de couples obtient-on en douze mois si chaque couple engendre tous les mois un nouveau couple à compter du second mois de son existence ? »
On suppose que :
- le premier mois, il y a juste une paire de lapins ;
- les lapins ne sont pubères qu'à partir du deuxième mois ;
- chaque mois, toute paire susceptible de procréer engendre effectivement une nouvelle paire de lapins ;
- les lapins ne meurent jamais (donc la suite de Fibonacci est strictement croissante).
Sont notés en gras, les couples productifs.
En janvier : 1 couple
En février : 1 couple
En mars : 1 + 1 = 2 couples
En avril : 1 + 2 = 3 couples
En mai : 2 + 3 = 5 couples
En juin : 3 + 5 = 8 couples
En juillet : 5 + 8 = 13 couples
En août : 8 + 13 = 21 couples
En septembre : 13 + 21 = 34 couples
En octobre : 21 + 34 = 55 couples
En novembre : 34 + 55 = 89 couples
En décembre : 55 + 89 = 144 couples
Les réponses constituent les nombres de la suite de Fibonacci : 1 - 1 - 2 - 3 - 5 - 8 - 13 - 21 - ..., dont chaque terme à partir du 3ème est la somme des deux précédents.
Function Fibonacci(ByVal n As Integer)
Dim result As Long = 0
If n < = 2 Then
result = 1
Else
result = Fibonacci(n - 1) + Fibonacci(n - 2)
End If
Return result
End Function
|
Programme itératif correspondant:
Function Fibonacci2(ByVal n As Integer)
Dim u, v, w, i As Long
If n <= 0 Then Return 0
If n = 0 Then Return 1
u = 0
v = 1
For i = 2 To n
w = u + v
u = v
v = w
Next
Return v
End Function
|
V-U-10. Exemple 9 : Fractales
Calculs de fractales
Les fonctions fractales sont des fonctions récursives théoriquement infinies...
Le Flocon de Koch, du nom du mathématicien suédois Helge Von Koch (1870-1924), est une courbe fermée, reproduisant un triangle équilatéral à des échelles de plus en plus petites. En répétant ce processus une infinité de fois, la courbe obtenue possède alors un périmètre infini mais une aire limitée. Pour ce faire, chaque segment formant un triangle équilatéral est lui-même décomposé en un triangle équilatéral dont la base mesure un tiers du segment, centrée et confondue à ce segment.
On va donc créer une fonction récursive nommée 'flocon' qui décompose un segment en ajoutant un triangle puis qui pour chaque segment appelle la fonction 'flocon.
Comme on ne peut pas afficher des points infiniment petits, on va ajouter une condition d'arrêt qui est déclenchée par le nombre d'appel récursif. Si la condition d'arrêt est remplie, on dessine le segment.
Voici la fonction récursive:
Private Sub Flocon(ByRef gh As Graphics, ByVal a As Point, ByRef b As Point, ByRef n As Integer)
Dim d, c, e As Point
Dim Couleur As Color = Color.Aqua
If n = 0 Then
gh.DrawLine(New Pen(Color.Red), a.X, a.Y, b.X, b.Y)
Else
c = Tiers(a, b)
d = Tiers(b, a)
e = Sommet(c, d)
Flocon(gh, a, c, n - 1)
Flocon(gh, c, e, n - 1)
Flocon(gh, e, d, n - 1)
Flocon(gh, d, b, n - 1)
End If
End Sub
|
Pour que cela fonctionne, il faut les deux routines suivantes:
Private Function Sommet(ByRef a As Point, ByRef b As Point) As Point
Sommet.x = (b.x + a.x) / 2 + (b.y - a.y) * Racine3Sur2
Sommet.y = (b.y + a.y) / 2 - (b.x - a.x) * Racine3Sur2
End Function
Private Function Tiers(ByRef a As Point, ByRef b As Point) As Point
Tiers.x = (b.x - a.x) / 3 + a.x
Tiers.y = (b.y - a.y) / 3 + a.y
End Function
|
Pour utiliser cet exemple il faut dans un formulaire un PictureBox nommé PictureBox1 pour afficher la fractale, un TextBox1 permettant de saisir le nombre d'appel récursif( ne pas dépasser 9 en pratique), et un bouton command1 exécutant le calcul et l'affichage.
Mettre en haut du module:
Const Racine3Sur2 As Double = 0.866025404
|
Private Sub Command1_Click(ByVal eventSender As System.Object, ByVal eventArgs As System.EventArgs) Handles Command1.Click
Dim newBitmap As Bitmap = New Bitmap(400, 400)
Dim g As Graphics = Graphics.FromImage(newBitmap)
Dim t As Integer
Dim a(2) As Point
Dim b(2) As Point
a(0).X = 164
a(0).Y = 10
b(1).X = 20
b(1).Y = 260
b(0) = Sommet(a(0), b(1))
a(1) = b(0)
a(2) = b(1)
b(2) = a(0)
For t = 0 To 2
Flocon(g, a(t), b(t), Val(TextBox1.Text))
Next t
PictureBox1.Image = newBitmap
End Sub
|
Code issu d'un code VB6 situé sur CodeS-SourceS VBFrance.com écrit par D. Thuler et transcrit par moi en VB.Net.Merci David.
V-U-11. Autre
Recherche de chemin dans un labyrinthe.
Le principe est que la fonction récursive teste le déplacement à droite, à gauche, en haut, en bas. La condition d'arrêt se produit quand on a trouvé la sortie; les endroits où on est déjà passé sont notés.
L'article http://recursivite.developpez.com/ donne des exemples et des explications extraordinaires de programmes récursifs EN PASCAL. Si vous avez le courage de les traduire en VB , envoyez les moi!!
V-V. Faut-il oublier le GoTo ?
 Et hop!! On saute..
Le Goto c'est quoi?
Faut-il utiliser le GoTo ?
V-V-1. Le 'Goto'
L'instruction GoTo permet de transférer le contrôle à l'emplacement d'une étiquette (on dit parfois un label) locale.
Une étiquette permet de localiser un endroit du code Les étiquettes sont toujours terminées par deux points(:).
Goto permet un saut non conditionnel : aller à, sauter vers une étiquette:
...
GoTo FIN
A=2
B=A+2
FIN:
|
FIN: est une étiquette, un mot en début de ligne qui désigne un endroit du code; pour créer une étiquette, taper en début de ligne un mot suggestif de l'endroit, puis ajouter ":".
Le programme saute de la ligne GoTo FIN à l'étiquette FIN: puis se poursuit après FIN (Les instructions entre Goto FIN et FIN: ne sont pas exécutées :
Le GoTo est souvent utilisé avec une instruction If (pour rendre le saut conditionnel):
If A=0 Then GoTo FIN
..
FIN:
|
V-V-2. Pourquoi éviter le 'GoTo'
L'utilisation du GoTo est peu élégante et à éviter:
Cela casse la structure du code qui se déroule de haut en bas, le cheminement du programme est moins évident, moins visible; s'il y a plusieurs GoTo le programme devient vite illisible.
On parle dans ce cas de "code spaghetti"  ou de "code kangourou" (à cause des sauts).
Dans la programmation structurée il faut bannir le 'GoTo'. On le remplacera avantageusement par des If..Then et des boucles.
Exemple:
On peut remplacer avantageusement la ligne:
If A=0 Then GoTo FIN
B=1
FIN:
|
par:
Autre exemple:
Saisir à l'aide d'une InPutBox un nombre. S'il n'est pas entre 1 et 31, ressaisir.
Avec GoTo:
Dim reponse As String
Question:
reponse= InPutBox ("Donner un nombre entre 1 et 31")
If Val(Reponse)<1 Or Val(Reponse) >31 Then GoTo Question
|
Sans GoTo:
Dim reponse As String
While Val(Reponse)<1 Or Val(Reponse) >31
reponse= InPutBox ("Donner un nombre entre 1 et 31")
Wend
|
V-V-3. Quand utiliser le 'GoTo'
Il est cependant parfois utilisé pour la clarté du code, car il permet de sortir de plusieurs blocs de code qui se suivent.
Exemple: détection d'erreur avant l'écriture sur une fichier:
If Not Exit(File) Then
errorState=File.NotExist
GoTo FIN
End if
If Not Open(File) Then
errorState=File.NotOpen
GoTo FIN
End if
If Not Overwrite(File) Then
errorState=File.NotOverwrite
GoTo FIN
End if
FIN:
|
C'est propre.
Là aussi on aurait pu utiliser des If imbriqués:
If Exit(File) Then
If Open(File) Then
If Overwrite(File) Then
errorState=File.Ok
Else
errorState=File.NotOverwrite
End if
Else
errorState=File.NotOpen
End if
Else
errorState=File.NotExit
End if
|
La solution avec les GoTo à l'avantage d'être plus lisible.
Pour info, il existe une autre solution élégante et originale utilisant un Select Case: Les "Case" peuvent contenir n'importe quelle expression.
Select Case true
Case len(File) = 0
msgbox "Pas de nom de fichier"
Case Not Exit(File)
errorState=File.NotExist
Case Not Open(File)
errorState=File.NotOpen
Case Not Overwrite(File)
errorState=File.NotOverwrite
Case else
End Select
|
V-W. Les bases binaires, hexadécimales, l'algèbre de Boole
 Mr Georges Boole 1805-1864
On étudie dans ce chapitre les différentes bases (binaire, hexadécimale..) en approfondissant. Ce chapitre n'est pas à lire de suite pour les débutants.
Voici ce que nous allons voir:
Le Bit, poids d'un bit.
Conversion décimal binaire.
L'octet, Kilo, Méga, Téra-Octet
Opération: L'addition, la multiplication binaire, les nombres négatifs.
Table de vérité.
Fonction logique. Or And, Not, Xor...
Notation.
Ordre des évaluations.
Loi de composition.
Déplacement de bit.
Hexadécimale.
Intérêts en Visual Basic.
A notre disposition Boolean, Integer Byte..
Conversion binaire, décimale, hexadécimale.
Cas particulier: If A then
Les masques de bit
Cryptage par Xor
Travail sur les couleurs, graphiques..
Viewer hexadécimal.
V-W-1. Introduction
L'algèbre de Boole est la partie des mathématiques, de la logique de l'électronique et de l'informatique qui s'intéresse aux opérations et aux fonctions sur les variables logiques. En logique propositionnelle, une expression est soit vraie soit fausse. (le vrai (1) et le faux (0)).
Georges Boole (1815-1864), physicien Anglais définit en 1847 un algèbre qui est applicable au raisonnement logique, qui traite des fonctions à variables binaires (deux valeurs). Mais il ne s'applique pas aux systèmes à plus de deux états d'équilibre.
Une variable booléenne, ou logique, ou binaire ne prend que deux valeurs (elle est généralement stockée sous la forme d'un bit).
Vers la fin des années 30, Claude Shannon démontra qu'à l'aide d'interrupteurs fermés pour « vrai » et ouverts pour « faux » il était possible d'effectuer des opérations logiques en associant le nombre 1 pour « vrai » et 0 pour « faux ».
Ce codage de l'information est nommé base binaire. C'est avec ce codage que fonctionnent les ordinateurs. Il consiste à utiliser deux états (représentés par les chiffres 0 et 1) pour coder les informations.
Il permet d'étudier les circuits logiques.
V-W-2. Notions théoriques
Notion de base:
On utilise diverses bases dans la vie courante:
Pour les heures, minutes, secondes on utilise sans le savoir une base 'soixante':
60 secondes= 1 minute
60 minutes = 1 heure
Si je compte : 1 s, 2s, 3s,...59s, 1mn, 1mn+1 s.....1mn+59s, 2 minutes....59 mn+ 59s, 1h...
En base décimale, on a à notre disposition les caractères 1 2 3 4 5 6 7 8 9.
Si on veut représenter le nombre au-dessus de 9, comme on n'a plus de caractère, on recommence avec 1 mais en le décalant vers la gauche pour signifier qu'il s'agit d'une dizaine. On obtient '10'. Le nombre suivant est '11' puis "12'.. Idem pour 100, 1000..
En base binaire, on n'a que le caractère 1 (et le zéro), 1 binaire= 1 décimal.
Si on veut écrire en binaire le nombre au dessus de 1, comme on n'a plus de caractère, on procède de même en décalant vers la gauche le 1:
10 binaire= 2 décimal.
Le nombre suivant est 11 binaire (3 en décimal).
Puis 100 (4 en décimal) car il faut de nouveau décaler.
En base hexadécimale, on a à notre disposition les caractères 1 2 3 4 5 6 7 8 9 A B C D E F.
Aussi 10 décimal = A en hexadécimal
...
15 décimal = F en hexadécimal
16 décimal = 10 en hexadécimal
Si on veut représenter le nombre au-dessus de 15, comme on n'a plus de caractères, on recommence avec 1 mais en le décalant vers la gauche pour signifier qu'il s'agit d'une 'seizaine'. On obtient '10' hexadécimal qui correspond à 16 décimal . Le nombre suivant est '11' puis "12' jusqu'a 1F puis 100... 1000..
Utilisons l'analogie des allumettes et des paquets d'allumettes:
En décimal on a des paquets de 10 allumettes.
On compte 1 ,2 ,3..9, 1 paquet de 10, puis 1 paquet + 1 allumette...
On a des gros paquets de 100, des énormes paques de 1000 allumettes..
En binaire on a des paquets de 2 allumettes et des gros paquets de 4 allumettes.
On compte 1 , 1 paquet de 2, puis 1 paquet + 1 allumette, puis 1 gros paquet de 4...
Donc pour compter en binaire: Binaire Décimal
1 allumette. 1 1
1 paquet de 2 10 2
1 paquet de 2 + 1 allumette 11 3
1 gros paquet de 4 100 4
1 gros paquet de 4 +1 allumette 101 5
1 gros paquet de 4 +1 paquet de 2 110 6
....
Le nombre d'allumette qu'il y a dans un paquet se nomme le poids.
En hexadécimal, les paquets sont de 16 allumettes:
On compte 1, 2, 3 ..jusqu'a 15 allumettes puis 1 paquet de 16 puis 1 paquet plus une allumette..
Base binaire:
Soyons maintenant un peu plus scientifique:
Le bit:
Le terme bit (b avec une minuscule) signifie « binary digit », c'est-à-dire 0 ou 1 en numérotation binaire. Il s'agit de la plus petite unité d'information manipulable par un ordinateur.
Physiquement cette information binaire correspond à:
* un signal électrique ou magnétique. (pas de signal=0, au-delà d'un certain seuil de +5V, valeur 1).
* des trous ou pas de trous sur un CD.
* l'état de bistables, c'est-à-dire des composants électroniques contenus dans les circuits intégrés qui ont deux états d'équilibre (état 1, état 0).
Avec un bit il est donc possible d'avoir deux états :
soit 1.
soit 0.
Grâce à 2 bits, il est possible d'obtenir quatre états différents (2*2) :
On peut avec 2 bits , avoir les valeurs: 0, 1, 10, 11 soit 0,1, 2, 3 en décimal.
Avec 3 bits, il est possible d'obtenir huit états différents (2*2*2) de 0 à 7 en décimal:
Avec 4 bits, il est possible d'obtenir huit états différents (2*2*2*2) de 0 à 15 en décimal:
Pour un groupe de n bits, il est possible de représenter 2n valeurs ( de 0 à 2n-1 ).
Avec 8 bits =256 valeurs.
Avec 16 bits=65536 valeurs.
Avec 32 bits=4294967296 valeurs.
Avec 64 bits=18446744073709551616 valeurs.
Avec 8 bits (un octet) on peut représenter un nombre qui peut avoir 256 valeurs différentes:
de 0 à 255
Poids des bits:
Chaque bits a un poids, qui dépend de la position du bit en partant de la droite. Comme les dizaines, les centaines et les milliers pour un nombre décimal, le poids d'un bit croît d'une puissance de deux en allant de la droite vers la gauche:
Remarque : cela est valable pour toutes les bases:
Soit un nombre 'mno' en base b
Le premier chiffre à droite a la valeur: o x b1
Le deuxième chiffre à droite a la valeur: n x b2
Le troisième chiffre à droite a la valeur: m x b3
En allant de la droite vers la gauche le poids croît d'un puissance de b.
Le nombre total est la somme de toutes les valeurs:
o x b1 + n x b2 + m x b3
Conversion:
Pour convertir un nombre binaire en nombre décimal:
Il faut multiplier la valeur de chaque bit par son poids, puis d'additionner les résultats.
Ainsi, le mot binaire 10101 vaut en décimal :
24x1 + 23x0 + 22x1 + 21x0 + 20x1
= 16x1 + 8x0 + 4x1 + 2x0 + 1x1
= 21
Pour convertir un nombre décimal en nombre binaire:
-Méthode des poids:
Soit 21 en décimal.
Il faut connaître les poids (puissance de 2): 2, 4, 8, 16 ,32..
Trouver le premier poids (la première puissance de 2) inférieur au nombre décimal 21 :c'est 16
16 donne en binaire 10000
Faire 21-16 =5
Trouver le premier poids inférieur au nombre 5, c'est 4.
4 donne en binaire 100
Faire 5-4= 1
Quand on atteint 1 (ou 0) on s'arrête.
On additionne 10000
+ 100
+ 1
_____
10101
-Méthode des divisions par 2:
21 /2 = 10 reste 1
10 /2 = 5 reste 0
5 /2 = 2 reste 1
2 /2 = 1 reste 0
1 /2 = 0 reste 1
On prend les restes en commençant par la fin: 10101
Y a t-il une solution plus élégante?
La calculette Windows permet les conversions.
1. Dans le menu Affichagede la calculette, cliquez sur Scientifique.
2. Tapez le nombre décimal que vous souhaitez convertir.
3. Cliquez sur le RadioButton 'Bin' .
Octet, Kilo méga Téra Octet.
L'octet (en anglais Byte ou B) est une unité d'information composée de 8 bits ( 256 valeurs possibles). Il permettait par exemple de stocker le code d'un caractère (une lettre ou un chiffre: 65 indiquant 'A' dans le code ASCII). Il y a quelques années les ordinateurs fonctionnaient avec des octets puis ils ont utilisé 16 bits , 32 bits et maintenant 64 bits. On voit que plus l'unité d'information contient de bits, plus elle pourra contenir des grands nombres.
En informatique, si 8 bits correspondent à un octet (Byte), 16 bits est généralement appelée mot (en anglais word), 32 bits correspond à un mot double (en anglais double word, d'où l'appellation dword).
En Visual Basic.Net, les entiers (Integer) sont codés sur 32 bits, les Long sur 64 bits. Les valeurs sont signées (positive ou négative), un bit est donc utilisé pour le signe. Par contre UInteger est un entier non signé codé sur 32 bits pouvant donc prendre les valeurs 0 à 4 294 967 295.
Ko, Mo, Go, To ( kB, MB, GB, TB en anglais)
Pour indiquer la capacité d'une mémoire, on utilisait:
* Un kilooctet (Ko) = 210 octets = 1024 octets
* Un Mégaoctet (Mo) = 220 octets = 1024 ko = 1 048 576 octets
* Un Gigaoctet (Go) = 230 octets = 1024 Mo = 1 073 741 824 octets
* Un Téraoctet (To) = 240 octets = 1024 Go = 1 099 511 627 776 octets
Cela correspondait bien à des puissances de 2, de plus c'était en accord avec les circuits intégrés de mémoire qui avaient bien 1024 octets dans un Ko.
Il parait que depuis 1998 l'IEC a décidé:
* Un kilooctet (Ko ou KB) = 1000 octets
* Un Mégaoctet (Mo ou MB) = 1000 Ko = 1 000 000 octets
* Un Gigaoctet (Go ou GB) = 1000 Mo = 1 000 000 000 octets
* Un Téraoctet (To) = 1000 Go = 1 000 000 000 000 octets
Hors de France, on utilise le nom de « byte » plutôt que le terme « octet ». Cela donne les kilobyte, mégabyte, gigabyte et terabyte : (kB, MB, GB, TB avec un B majuscule)
Ne pas confondre Byte B (octet) et bit (bit ou binary digit).
Opérations:
Addition binaire:
L'addition en binaire se fait comme en décimale :
0+1 = 1
1+0 = 1
0+0 = 0
1+1 =10
Pour plusieurs digits, on additionne en commençant par les bits de droite. On a des retenues lorsque la somme de deux bits de même poids dépasse la valeur de l'unité la plus grande (dans le cas du binaire : 1), cette retenue est reportée sur le bit de poids plus à gauche...
C'est ce qui se passe avec 1+1= 10
Autre exemple:
0 1 1 0 0
+ 0 1 1 1 0
- - - - - -
1 1 0 1 0
Soustraction binaire:
La soustraction en binaire se fait comme cela :
100
- 010
_____
010
Mais pour les processeurs il est plus facile d'additionner le complément à 2.
Le complément à 1 c'est le fait d'inverser tous les bits du nombre sur toute sa longueur.
010 donne le complément à 1 suivant: 11111101
(si on travaille sur des octets, on inverse les huit bits)
Le complément à 2, c'est le complément à 1 +1: 11111101+1=11111110
Ajoutons 00000100 à 11111110 cela donne bien 00000010
(la dernière retenue tombe dans le vide)
La table de multiplication en binaire est très simple :
* 0x0=0
* 0x1=0
* 1x0=0
* 1x1=1
La multiplication se fait en formant un produit partiel pour chaque digit du multiplicateur (seuls les bits non nuls donneront un résultat non nul). Lorsque le bit du multiplicateur est nul, le produit partiel est nul, lorsqu'il vaut un, le produit partiel est constitué du multiplicande décalé du nombre de positions égal au poids du bit du multiplicateur.
Par exemple :
1 1 0 1 multiplicande
x 0 0 1 0 multiplicateur
- - - - - -
0 0 0 0
1 1 0 1
0 0 0 0
- - - - - -
1 1 0 1 0
On constate que pour multiplier un nombre par 2, il faut le décaler d'un bit à gauche.
10 binaire multiplié par 2 est égal à 100 (2 x 2=4 en décimal)
Nombres négatifs
On peut utiliser des nombres non signés (contenant une valeur absolue), dans un octet il peut y avoir 256 valeurs (0 à 255)
On peut utiliser des nombres signés (positif ou négatif), on 'code' les nombres négatifs en complément à 2:
Le complément à 1 c'est le fait d'inverser tous les bits du nombre sur toute sa longueur.
010 donne le complément à 1 suivant: 11111101 sur un octet
(si on travaille sur des octets, on inverse les huit bits)
Le complément à 2, c'est le complément à 1 +1: 11111101+1=11111110
On se rend compte que le premier bit à gauche est à 1 pour les nombres négatifs. Dans ce cas on ne peut plus coder que 128 valeurs (sur 7 bits) pour un octet signé.
Table de vérité:
Une table de vérité est un tableau permettant de décrire toutes les possibilités de sorties en fonction des entrées. On place donc les variables d'entrées dans les colonnes de gauche en les faisant varier. La colonne (ou les colonnes si la fonction a plusieurs sorties) de droite décrit le résultat.
Exemple de table de vérités de la multiplication.
L'expression logique correspondante est S= A X B
On retrouve bien par exemple: si les 2 entrées sont 1 et 1 la sortie est 1: en d'autres termes 1 X 1 =1
Exemple des tables de vérités des fonctions logiques:
Pour la fonction And par exemple, l'expression logique correspondante est S= A AND B si les 2 entrées sont 1 et 1 la sortie est 1: en d'autres termes 1 And 1 =1
Comment écrire une fonction logique à partir d'une table de vérité:
Il est possible à partir de la table de vérité d'une fonction d'écrire l'expression algébrique de celle-ci.
Exemple 1:Soit la table de vérité suivante:
La sortie vaut 1 lorsque A vaut 1 et B vaut 0, l'expression logique de cette fonction est donc:
S=A AND NOT B
Exemple 2: Soit la table de vérité suivante:
La sortie vaut 1 lorsque A vaut 1 et B vaut 0 ou lorsque A et B sont à 0, l'expression logique de cette fonction est donc:
S=(A And Not B) Or (Not A And Not B)
En conclusion:
On écrit donc les expressions pour chaque sortie à 1 (avec des And), on les combine avec des Or
Fonction logique:
La loi AND, dite conjonction
Elle est définie de la manière suivante : a And b est égal à 1 si et seulement si a est égal à 1 et b est égal à 1.
On peut construire la table.
« l'un et l'autre »
La loi OR, dite disjonction ou disjonction inclusive
Elle est définie de la manière suivante : a Or b est égal à 1 si et seulement si a est égal à 1 ou b est égal à 1. (notons que si a est égal à 1 et que b est égal à 1 aussi, alors a OU b est égal à 1.)
On peut construire la table:
« l'un ou l'autre ou les deux »
Le contraire, dite négation
Le contraire de "a" égal à 1 si et seulement si a est égal à 0. Le contraire de a est noté Not a
La loi XOR, dite disjonction exclusive
Elle est définie de la manière suivante : a Xor b est égal à 1 si et seulement si a est égal à 1 ou b est égal à 1 mais pas les deux. (notons que si a est égal à 1 et que b est égal à 1 aussi, alors a Xor b est égal à 0.)
On peut construire la table:
« l'un ou l'autre mais pas les deux ».
a Xor b équivalent à (a Or b) And Not( a And b)
a Xor b Xor b = a : si on applique sur a 2 fois Xor b, on retrouve a. C'est une propriété très utilisée.
L'opérateur Équivalence
L'équivalence (notée =) est vraie si les deux entrées ont la même valeur et faux sinon. Elle se compose comme suit :
a=b est égal à Not( a Or b) Or ( a And b)
On peut aussi dire que :
a=b est égal à Not (a Xor b)
Notons la notation utilisée dans les traités d'algèbre de Boole:
+ (addition) équivalent à Or
. (produit) équivalent à And
- au dessus (négation) équivalent à Not
Ordre des évaluations:
Les opérations seront soumises aux même règles que les opérations « de tous les jours », la fonction Not est prioritaire par rapport à And qui est prioritaire par rapport à la fonction Or, enfin on trouve Xor ; on peut, pour s'aider, placer des parenthèses dans les opérations pour forcer l'ordre des opérations.
Exemple :
Dim a As Boolean = 0
Dim b As Boolean = 1
Dim c As Boolean 1
On cherche a And b Or c
a And b = 0
(0 And 1 = 0)
0 Or c = 1
(O Or 1 = 1)
|
Le résultat est donc:
Les parenthèses modifient l'ordre des opérations: elles sont prioritaires sur tous:
En VB, compte tenu que les opérateurs logiques et de bits ont une priorité inférieure à celle des opérateurs arithmétiques et relationnels, toutes les opérations au niveau du bit doivent être mises entre parenthèses afin de garantir une exécution précise.
Sur un groupe de bit les opérations s'effectuent bit à bit:
Exemples:
15 décimal 00001111
4 décimal 00000100
15 And 4 = 00000100 --->4 décimal
4 décimal 00000100
2 décimal 00000010
4 Or 2 = 00000110 --->6 décimal
Les lois de composition:
Ce sont des règles logiques qui permettent de simplifier l'écriture des expressions algébriques.
Associativité:
* (A And B)And C est équivalent à A And (B And C) et A And B And C
* (A Or B) Or C est équivalent à A Or (B Or C) et A Or B Or C
Absoption:
* A And (A Or B) est équivalent à A
* A Or A And B est équivalent à A
Commutativité:
* A And B est équivalent à B And A L'ordre est sans importance
* A Or B est équivalent à B Or A
Distributivité:
* A Or(B And C) est équivalent à (A Or B) And (A Or C)
* A And (B Or C) est équivalent à A And B Or A And C
Mais aussi:
* A Or A est équivalent à A
* A And A est équivalent à A
Identité:
* 1 And A est équivalent à A
* 0 Or A est équivalent à A
Inversion:
* A And Not A est équivalent à 0 'A ne peut pas être vrai et faux
* A Or Not A est équivalent à 1
Nullité:
* 0 And A est équivalent à 0
* 1 Or A est équivalent à 1
Théorème de De Morgan
Not (a Or b) est équivalent à Not a And Not b
Dans les deux cas, l'expression ne sera égale à 1 que si a et b sont = 0.
Not( a And b)équivalent à Not a Or Not b
Dans les deux cas, l'expression ne sera =1 que si a ou b sont =0.
Les expressions complexes peuvent donc être simplifiées en utilisant des transformations:
Il existe aussi plusieurs autres opérateurs qui n'ont pas d'équivalent en Visual Basic Net:
Ils existaient en VB6!!
Implication
L'implication (notée IMP) qui n'existe pas en VB.Net s'écrit de la manière suivante :
a IMP b peut s'écrire en VB: Not(a) Or b
Cette opération n'est pas commutative a est une condition suffisante pour b, qui, elle, est une condition nécessaire pour a.
Inhibition
L'inhibition (notée INH) n'existe pas en VB.Net, elle se compose comme suit :
a INH b peut s'écrire en VB: a And Not(b)
Cette opération n'est pas commutative.
Déplacement de bit:
Les opérateurs binaires << et >> effectuent des opérations de déplacement de bits.
L'opérateur << décale à gauche les bits du premier opérande du nombre de positions spécifié. Les bits de poids fort situés en dehors de la plage du type de résultat sont éliminés, et les positions libérées par les bits de poids faible sont remplies par des zéros.
L'opérateur >> décale à droite les bits du premier opérande du nombre de positions spécifié. Les bits de poids faible sont éliminés et, si l'opérande de gauche est positif, les positions libérées par les bits de poids fort sont mises à zéro ; s'il est négatif, elles sont mises à un. Si l'opérande de gauche est de type Byte, les bits de poids fort disponibles sont remplis par des zéros.
A quoi cela sert?
Exemple décaler à gauche un Byte revient à faire une multiplication par 2.
3 en décimal= 11
Je décale à gauche, j'obtient 110 , c'est 3*2=6 en décimal.
Revenons sur la base hexadécimale:
En hexadécimal:
On a 16 caractères: 0, 1, 2, 3 ,4 ...8, 9, A, B, C, D, E, F.
Quand on compte et qu'on arrive à F (15 décimal), on passe à 10 (16 décimal) puis 11...
Voyons la correspondance décimale, hexadécimale, binaire:
Pour un nombre hexadécimal à plusieurs chiffres le poids de chaque chiffre est:
1C en base 16 c'est donc 10+C en hexadécimal = en décimal c'est 161 + 12x 160 = 16 + 12 = 28
Le nombre 28 (en base 10) vaut en base 16 : 1*161 + 12*160 = 1*161 + C*160
c'est-à-dire 1C en base 16.
Le nombre FB4 (en base 16) vaut en base 10 : F*162 + B*161 + 4*160 = 3840 + 176 + 4 = 4020
A quoi sert la base hexadécimale?
C'est une représentation plus imagée de la représentation binaire:
Pour convertir un octet en hexadécimale, on le partage en 2 groupes de 4 bits, qui correspondent chacun à un chiffre hexadécimal.
00101010 c'est un octet en binaire; impossible à retenir en binaire (en décimal on ne voit pas du tout ce qu'il représente en bits). Cet octet, on le coupe en 2 , chaque demi-octet représente 4 bits dont la valeur est comprise entre 0 (0000 en binaire) et F (1111 en binaire, 15 en décimal)
00101010 en binaire= 2A en hexadécimal.
Il suffit de se souvenir des nombres de 1 à 15 en binaire pour se représenter rapidement 2A.
Autre exemple:
HFF = 255 décimal
HFFFF=65535 décimal
Notons que pour signifier qu'on a affaire à un nombre hexadécimal, on ajoute H devant.
L'hexadécimal est donc une manière rapide et mnémotechnique de se représenter des nombres binaires.
Les viewers et éditeurs permettant de voir et modifier les octets contenues dans un fichier affichent les octets en hexadécimal. (voir plus bas)
V-W-3. Pratique en Visual Basic
En Visual Basic.Net, on a à notre disposition
Les Boolean qui peuvent prendre les valeurs True ou False..
Les entiers: Byte contient 8 bits (non signé) pouvant prendre les valeurs 0 à 255: il existe aussi en VB 2005, SByte contenant un octet signé dont les valeurs varient de moins 128 à plus 127.
Les Short 16 bits, les Integer sont codés sur 32 bits, les Long sur 64 bits. Ces valeurs sont signées (positives ou négatives), un bit est donc utilisé pour le signe.
Par contre en VB 2005, UInteger est un entier non signé codé sur 32 bits pouvant donc prendre les valeurs 0 à 4 294 967 295. Ushort et ULong existent aussi. (U comme Unsigned)
Il existe aussi les nombres en virgule flottante ou fixe ( Single, Double, Decimal), ceux là, on ne les utilisera pas pour travailler sur les bits.
Littéral
Un littéral est censé être en base décimal .
Dim A As Integer = 12 (12 est en base décimale)
On peut forcer un littéral a être un hexadécimal ou un octal: Un nombre hexadécimal est noté avec le préfixe &H , exemple :
A=&HFF
(&O pour octal)
Il n'est pas possible de saisir un littéral en binaire.
Bien comprendre que, en interne, les entiers sont codés en binaire: c'est normal, la mémoire de l'ordinateur et les registres des processeurs sont composés d'octets de 8 bits de Dword de 16 bits et maintenant de 32 et 64 bits contenant des bits positionnés à 0 ou 1.
Dim A As Integer = 12
c'est 12 est en base décimale, c'est notre manière de l'utiliser.
mais c'est 0000000000001100 en mémoire physique, représentation binaire.
c'est 000C en hexadécimal, mais dans une autre base plus pratique, "plus imagée".
C'est toujours le même nombre!!
And Or Xor AndAlso, OrElse
En VB, en plus de And, Or, Xor, existent AndAlso et OrElse qui testent la première valeur puis, si nécessaire, la seconde. Si la seconde valeur n'a pas à être évaluée, est ne le sera pas, c'est un gain de temps.
Pourquoi Xor n'a pas d'équivalent?
Car pour évaluer Xor, il faut d'emblée utiliser les 2 valeurs.
Comment réagit VB avec les booléens, les entiers?
* Si A et B sont des expressions booléennes (valeur True ou False uniquement):
IF A>=2 And A<=5 Then..
Les expressions booléennes sont évaluées et on a comme résultat True ou False.
* Si A et B sont des nombres entiers (Integer= 32 bits, Long=64 bits, Short=16 bits, Byte=8 bits par exemple):
L'opération est effectuée sur chaque bit de l'équivalent binaire, le résultat binaire est affiché en décimal.
A = 7 'en décimal ( 0111 en binaire)
B = 12 'en décimal( 1100 en binaire)
A And B = 4 'en décimal( 0100 en binaire)
* Si A et B sont des nombres en virgule flottante (Single, Double par exemple), ils sont codés sous la forme de mantisse plus exposant, une opération logique devrait produire un résultat aberrant. Ils sont convertis en Long avant évaluation si Option Strict= Off:
Dim a As Single = 7
Dim b As Single = 12
Dim c As Boolean = True
MsgBox(a And b) 'affiche '4' car 7 et 12 sont transformés en Long (si Option Strict=Off)
si Option Strict=On Levée d'une exception.
Un conseil: utiliser des Booléens quand vous voulez effectuer des opérations logiques, des entiers quand vous travaillez sur les bits.
Conversion Binaire, hexadécimale, décimal:
L'affichage d'un entier se fait en décimal par défaut si on utilise la méthode ToString:
Dim a As Integer =&HFF Littéral en hexadécimal
MsgBox (a.ToString) Affiche
|
On peut surcharger la méthode et afficher en hexadécimal:
Dim a As Integer = 255
MsgBox(a.ToString("X")) Affiche
|
On peut afficher en hexadécimal et décider le nombre de digit affiché:
Dim a As Integer = 255
MsgBox(a.ToString("X4")) Affiche
|
En utilisant la classe Convert, on peut même afficher en base binaire, octale, décimal, hexadécimal.
Convert.ToString(Int64, base) Convertit la valeur d'un entier signé 64 bits en sa représentation String équivalente dans une base 'base' spécifiée (base 2, 8, 10, 16).
Dim d As Long = 3
Dim r As String
r= Convert.ToString(d, 2)) 'convertit la valeur Long de "d" en base 2
d= 3 donne r="11" binaire
Si on avait eu une String "3" on l'aurait convertie en Long grâce à CLng(d)
Convert.ToInt64(s, base) 'convertit en type int64(long en base 10) la valeur de la String 's' à partir d'une base 'base'.
Dim d As String = "111"
Dim r As Long
r= Convert.ToInt64(d, 2)) 'convertit d (string représentant un binaire) en Long
cela donne r=7
Enfin dans l'espace Visual Basic l'instruction Hex donne la représentation hexadécimale d'un nombre , ( Oct existe aussi)
str=Hex(456) retourne 1C8
Conversion String en Byte:
Conversion String en Bytes:
Dim str As String= ".."
Dim encoding As New System.Text.ASCIIEncoding()
Dim Bytes() As Byte()= encoding.GetBytes(str)
|
Conversion Bytes en String:
Dim Bytes As Byte() = ...
Dim str As String
Dim enc As New System.Text.ASCIIEncoding()
str = enc.GetString(Bytes)
|
Enregistrement d'un tableau de Bytes:
1 - En mémoire: (dans un mémoryStream)
Imports System.IO
...
Dim dataArray(1000) As Byte
Dim randomGenerator As New Random
randomGenerator.NextBytes(dataArray)
|
Ecriture
Dim binWriter As New BinaryWriter(New MemoryStream())
binWriter.Write(dataArray)
|
Lecture
Dim binReader As New BinaryReader(binWriter.BaseStream)
binReader.BaseStream.Position = 0
Dim verifyArray() As Byte = binReader.ReadBytes(dataArray.Length)
|
2 - Dans un fichier:
...
Dim fs As New FileStream(FILE_NAME, FileMode.CreateNew)
Dim w As New BinaryWriter(fs)
w.Write(datArray)
w.Close()
fs.close
|
Le Framework 2 permet une écriture encore plus simple pour lire écrire les octets d'un fichier:
Lire et mettre dans un tableau les octets d'un fichier? (Framework 2)
Dim myBytes() As Byte =File.ReadAllBytes("c:\monText.txt")
Il existe aussi WriteAllByte.
Précision sur 'If a Then'
Avec des valeurs numériques si
* a=0, a est évalué comme False le programme se poursuit après Then;
* si a est différent de 0 (1, -1, 45,...) a est considéré comme True et le programme se poursuit après Then.
Donc
Dim a As Integer =15
If a Then..
|
C'est une mauvaise méthode!! Il vaut mieux écrire:
Dim a As Integer =15
If a <>0 Then..
|
Avec une expression Booléenne par contre, on peut écrire:
Dim a As Boolean= True
If a = True Then..
If a Then..
|
Exemple:
If (x=15)=True Then..
If x=15 Then...
|
Avec une expression booléenne, et uniquement avec une expression booléenne, il est possible de se passer du = True après un If car de toutes façons , l'expression est évaluée.
Masque de bit:
Or permet d'écrire un bit à 1:
Soit un entier, on veut forcer un des bits à 1 , la solution est de faire un Or avec un entier ayant ce seul bit à 1.
Exemple : Mettre le deuxième bit de 00000100 (4 en décimal) à 1
Il faut faire un Or avec 00000010.
Le poids du deuxième bit est 2, c'est le 'mask bit'.
4 Or 2 = 6
00000100 Or 00000010 = 00000110
En faisant Or 2, on a bien mis le deuxième bit à 1.
Le masque est toujours une puissance de 2.
Or 8 met le quatrième bit à 1
And permet de tester un bit
A And 1 indique si le bit le moins significatif (le plus à droite) est a 1
Exemple: si A = 7 'en décimal ( 0111 en binaire) A And 1 retourne 1
A And 8 indique si le quatrième bit est a 1 (8 est le poids du quatrième bit).
Exemple: si A = 7 'en décimal ( 0111 en binaire) A And 8 retourne 0
8 c'est le 'mask bit' (00001000) du quatrième bit.
A And 8 peut ensuite être évalué comme une expression booléenne:
If A and 8 Then ' Si le quatrième bit de A est à 1 alors,
And permet aussi de forcer à 0 une partie des bits et de ne conserver que la valeur de certains bits:
Soit une couleur codée sur 24 bits; les 8 bits à droite codent la composante bleue, Je veux conserver uniquement ces 8 bits de droite (l'octet de droite):
myColor And &HFF conserve le premier octet mais met les 2 autres à 0:
MyColor=0010 0100 1000 0010 0010 0110
And 0000 0000 0000 0000 0000 1111
= 0000 0000 0000 0000 0000 0110
Le masque correspond au bits à conserver.
Xor permet de forcer un bit à 0
Pour mettre le 4eme bit à 0:
Il faut faire un Xor avec 00001000.
Le poids du deuxième bit est 2, c'est le 'mask bit'.
12 Xor 8 = 4
00001100 Or 00001000 = 00000100
Exemple pratique:
Comment stocker plusieurs valeurs dans une variable en utilisant un masque.
Souvent, plutôt que de coder une information par octet, on peut coder une information par bit et ainsi coder 8 informations par octet.
Le paramètre d'une fonction est, par exemple, composé d'un entier ou chaque bit à une signification.
Exemple fictif :
00000001 le premier bit à 1 signifie gras (1 en décimal)
00000010 le deuxième bit à 1 signifie l'italique (2 en décimal)
00000100 le troisième bit à 1 signifie le soulignage. (4 en décimal)
Si je veux envoyer les paramètres gras et souligné, j'enverrais le paramètre 1 Or 4 qui correspond a 00000101. Les bits 1 et 3 sont bien à 1.
On note bien que chaque paramètre doit être une puissance de 2.
C'est plus clair de créer une énumération:
<Flags()> Enum Car
Normal=0
Gras= 2
Italique= 4
Souligne= 8
End Enum
|
Si je veux envoyer les paramètres gras et souligné, j'enverrais le paramètre Car.Gras Or Car.Souligne
<Flags()> indique qu'on travaille bien sur des bits.
Souvent les valeurs sont proposées par VB, comme par exemple quand on utilise MsgBox; le deuxième paramètre qui indique le style peut comporter plusieurs indications séparées par des Or:
reponse= MsgBox(msg, MsgBoxStyle.DefaultButton2 Or MsgBoxStyle.Critical Or MsgBoxStyle.YesNo, Title)
|
Pour lire un bit en retour d'une fonction, on utilisera And:
Si reponse And Car.Italique =1
|
c'est que le second bit de reponse est à 1.
Bien que ce soit une opération sur les bits on écrit souvent:
If reponse And Car.Italique Then...
|
Cryptage simple par Xor
La technique la plus simple est d'appliquer un « OU exclusif » (XOR) entre le texte à chiffrer et la clé.
Pour obtenir le message crypté on effectue Message Xor Cle (si la clé fait x octets on effectue le Xor entre le premier octet du message et le premier de la clé, puis le deuxième.. quand on arrive à x+1 caractère du message, on recommence au premier caractère de la clé).
Comme Message Xor Cle Xor Cle =Message, pour déchiffrer le message codé, il suffit de faire de nouveau un Xor avec la clé.
La clé est donc la même pour coder et décoder, on appelle cela une clé symétrique.
Bien sur, si on utilise un texte comme clé et comme message, c'est le code du caractère qui est utilisé.
Travail sur les couleurs:
Les valeurs RVB (couleurs) sont stockées dans trois octets de 8 bits, conduisant à une couleur à 24 bits, chaque octet correspondant respectivement au rouge, au vert et au bleu.
rrrr rrrr vvvv vvvv bbbb bbbb
Comment récupérer la composante rouge verte ou bleue?
Dim myColor As Integer = 15963245
Dim R, V, B As Byte
|
Pour le rouge:
On décale de 16 bits vers la droite: 0000 0000 0000 0000 rrrr rrrr
Pour le vert:
V = (myColor And &HFF00) >> 8
|
On fait un And &HFF00 ce qui met le premier et le troisième octet à 0 0000 0000 vvvv vvvv 0000 0000
On décale de 8 bits vers la droite: 0000 0000 0000 0000 vvvv vvvv
Pour le bleu:
On fait un And &HFF ce qui met le premier et le second octet à 0
0000 0000 0000 0000 bbbb bbbb
(En Vb on peut faire plus simple)
Travail sur les graphiques:
Un mode souvent utilisé pour la réalisation d'interfaces est le mode XOR. Ce mode permet d'effacer facilement un cadre de sélection en le redessinant une seconde fois à la même position.
Si l'on a un écran noir et blanc pour lequel 1 = noir et 0 = blanc et que l'on affiche une forme en noir, chaque pixel appartenant à la forme est inversé à l'écran puisque 1 xor p = not p. Donc si l'on dessine la forme deux fois, chaque pixel est inversé deux fois et revient donc dans son état initial.
Par contre, sur un écran couleur, les résultats sont imprévisibles. Si le noir est représenté par la valeur de pixel 1111 et que l'on dessine en xor sur un pixel de valeur 1001, le résultat est un pixel de valeur 1111 xor 1001 = 0110. La couleur résultante est alors imprévisible : on obtient un effet "technicolor".
En VB on a d'autres fonctions sur les graphiques.
V-W-4. Viewer hexadécimal
Comment voir le contenu d'un fichier en hexadécimal?
C'est très simple et VB 2005:
On utilise un composant ByteViewer
Charger la référence System.design.Dll
Puis entrer le code dans Form_Load:
Private Sub Form1_Load() Dim viewer As New System.ComponentModel.Design.ByteViewer()
Dim viewer As New System.ComponentModel.Design.ByteViewer
Me.Controls.Add(viewer)
viewer.Dock = DockStyle.Fill
Dim ofd As New OpenFileDialog
If ofd.ShowDialog() = Windows.Forms.DialogResult.OK Then viewer.SetFile(ofd.FileName)
End Sub
|
Si vous avez déjà un tableau de bytes, utilisez sa méthode SetBytes .
Vous pouvez même choisir son mode d'affichage (Ansi, Unicode, Hexadump ou automatique) avec sa méthode SetDisplayMode.
Second exemple:
Ouvrir un fichier image .jpg le charger dans un tableau de Bytes et l'afficher:
Dim viewer As New System.ComponentModel.Design.ByteViewer
Me.Controls.Add(viewer)
viewer.Dock = DockStyle.Fill
Dim ofd As New OpenFileDialog
ofd.ShowDialog()
Dim img As Image = Image.FromFile(ofd.FileName)
Dim mstImage As IO.MemoryStream = New IO.MemoryStream
img.Save(mstImage, System.Drawing.Imaging.ImageFormat.Jpeg)
Dim bytImage As Byte() = mstImage.GetBuffer
viewer.SetBytes(bytImage)
|
V-W-5. Éditeur hexadécimal
On peut écrire en VB.Net un éditeur hexadécimal de fichier (lecture du fichier, visualisation en hexa et ascii, modification d'un octet:
Voir le lien suivant:
Pour que le source marche , ne pas oublier de générer puis mettre les fichiers vb dans MyProjet et les fichiers ressources dans le répertoire de ressources.
Les sources présentés sur cette page sont libres de droits,
et vous pouvez les utiliser à votre convenance. Par contre cette page de présentation de ces sources constitue une oeuvre intellectuelle protégée par les droits d'auteurs. Copyright © .
Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu :
textes, documents, images, etc sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à 3 ans de prison et jusqu'à 300 000 E de dommages et intérêts.
Cette page est déposée à la SACD.
|
