• A) Calculs élémentaires avec des nombres binaires.
• B) Addition et soustraction de nombres binaires.
• C) Calculs utilisant la multiplication par 11 (3 en décimal).
• D) Calculs utilisant la division par 11 (3 en décimal).
  

A) Calculs élémentaires avec des nombres binaires.

Nous utiliserons le terme «binaire» ou «nombre binaire» pour désigner un nombre écrit dans le système binaire.

Ajouter 1 à un nombre binaire

Et voici quelques exemples :

Pour pouvoir enchaîner des calculs, il est préférable de bien gérer la position de la tête de lecture/écriture.
Voir l’exemple dans l’article : La machine de Turing (1).

Exercice 1

Ajouter 1 à un nombre binaire, la tête étant sous le chiffre de droite et ramener la tête sous ce chiffre de droite

Exercice 2

Soustraire 1 à un binaire strictement supérieur à 0, la tête étant sous le chiffre de droite.

Les deux exercices précédents montrent que :

Un seul état suffit pour ajouter 1 ou soustraire 1 à un nombre binaire.

Si on ajoute 1 ou si on retranche 1 au deuxième chiffre en partant de la droite d’un nombre binaire, on obtient l’ajout de 10 ou le retrait de 10.

Exercice 3

Ajouter 10 à un binaire, la tête étant sous le chiffre de droite, et ramener la tête sous ce chiffre de droite à la fin du calcul.
On pouvait aussi ajouter 1 à deux reprises.

Exercice 4

Soustraire 10 à un binaire supérieur à 10, la tête étant sous le chiffre de droite, et ramener la tête sous ce chiffre de droite à la fin du calcul.
On pouvait aussi retirer 1 à deux reprises.

Pour la suite, notons que :

L’écriture en binaire d’un nombre pair se termine par un 0.
Un binaire dont l’écriture se termine par un 0 est un nombre pair.

Exercice 5

Diviser par 2 un nombre binaire qui se termine par un 0, la tête étant sous le chiffre de droite.

Exercice 6

Calculer le quotient entier dans la division par 2 d’un nombre binaire quelconque, la tête étant sous le chiffre de droite.

Pour terminer ce paragraphe, nous allons voir dans l’exercice suivant le passage de l’écriture en unaire à l’écriture en binaire (l’opération inverse sera proposée dans l’exercice 14).

Exercice 7

Transcrire un unaire en binaire, la tête étant sous le chiffre de droite de l’unaire.
Laisser un blanc entre l’emplacement de la réponse en binaire et l’unaire. On prévoira de remplacer les 1 par des 0 dans l’unaire, de façon à pouvoir reconstituer l’unaire à la fin des calculs.

B) Addition et soustraction de nombres binaires.

Les algorithmes de déplacement vus dans l’article : La machine de Turing (1) seront bien utiles ici !

Addition de deux nombres binaires X et Y séparés par un b, la tête étant sous le chiffre de droite de Y.

Nous avons présenté plusieurs méthodes de calcul de la somme de deux nombres écrits en unaire dans l’article : La machine de Turing (2).
Avec le prototype présenté, l’utilisation des nombres binaires permet des calculs sur des nombres plus grands.

Exercice 8

Calculer la différence X-Y de deux nombres binaires tels que X > Y, la tête étant sous le chiffre de droite de Y.

Voir un exemple de soustraction avec des nombres écrits en unaire dans l’article :
La machine de Turing (2).

C) Calculs utilisant la multiplication par 11 (3 en décimal).

Pour multiplier par 11 (3 en décimal) un nombre n, on pourrait utiliser : 3n = 2n + n. Mais, cela ne sera pas possible avec le prototype car, si un état suffit pour calculer 2n, il faut neuf états pour recopier n et cinq états pour calculer 2n + n.

La division d’un nombre binaire pair par 2 et le calcul de 3n + 1 nous permettront, dans le prochain article, d’étudier la suite de Collatz.

Multiplier un nombre binaire par le binaire 11, la tête étant sous le chiffre de droite du binaire.

Trois états suffisent pour effectuer la multiplication par 11 (3 en décimal).

Exercice 9:

Un nombre binaire n est écrit sur le ruban, la tête étant sous le chiffre de droite.
Établir un algorithme pour calculer 3 x n + 1.

Exercice 10:

Un nombre binaire n est écrit sur le ruban, la tête étant sous le chiffre de droite.
Établir un algorithme pour calculer 3 x n + 2.

D) Calculs utilisant la division par 11 (3 en décimal).

Algorithme pour effectuer la division par 11 d’un multiple de 3.

Un entier, multiple de 3, est écrit sur le ruban dans le système binaire, la tête étant sous le chiffre de droite.

Pour tester l’efficacité de cet algorithme à trois états, voici la division de 1011110100 par 11 en binaire soit, en décimal, la division de 756 par 3.
Un 4ème état a été ajouté simplement pour supprimer les 0 muets à gauche de la réponse.

La division par 11 (3 en décimal) peut se faire avec uniquement 3 états.

Algorithme pour tester la divisibilité par 11

Un nombre est écrit sur le ruban dans le système binaire, la tête étant sous le chiffre de droite.
La tête doit parcourir ce nombre, se déplacer d’une case à gauche et écrire :

• 0 si le binaire n’est pas divisible par 11
• 1 si le binaire est divisible par 11

Vérification de la divisibilité de 1110011001 par 11 soit, en décimal, la divisibilité de 921 par 3.

Exercice 11:

Un nombre binaire n est écrit sur le ruban, la tête étant sous le chiffre de droite.
Établir un algorithme pour :

Étudier la divisibilité de n par 11.
Écrire 0 si n n’est pas divisible par 11 et s’arrêter.
Écrire 1 si n est divisible par 11 et, dans ce cas, calculer le quotient de n par 11.
Effacer les 0 muets.

Division, après avoir fait le test, de 1011111101 par 11 soit, en décimal, la division de 765 par 3.

Vous pouvez terminer la lecture de cet article, en jouant au jeu des différences avec les graphes de la multiplication et de la division par 11 !

Solutions des exercices du mois précédent

Exercice 12 :

Trouver des situations dans lesquelles on obtient un 0 muet à gauche du résultat quand on soustrait 1 à un nombre binaire et comment supprimer ce 0 muet ?

Exercice 13:

Calculer la différence X-Y de deux nombres binaires tels que X > Y, la tête étant sous le chiffre de droite de Y et supprimer les 0 inutiles : les 0 restant de Y et les 0 muets de X-Y.

Exercice 14 :

Transcrire en unaire un nombre écrit en binaire, la tête étant sous le chiffre de droite du binaire.
Laisser un blanc entre le binaire et l’emplacement de la réponse en unaire.

Exercice 15

Ajouter 11 à un binaire, la tête étant sous le chiffre de droite et ramener la tête sous ce chiffre de droite à la fin du calcul.

Prochain article :

Des algorithmes intéressants comme : traitements de chaînes de caractères, le codage Gray, calculer un PGCD, la conjecture de Collatz, un castor affairé, etc.