BTS SIO - Notes de cours

Accueil > Première année > SI4-SI6 > Algorithmes sur les entiers

Algorithmes sur les entiers

jeudi 21 novembre 2013, par

Pour ces exercices, on suppose que l’on ne connaît que les opérations d’addition et de soustraction. On va réfléchir aux algorithmes en pseudo code et les implémenter ensuite, d’abord en Pascal puis en Python.

Algorithme de division

La division entre nombre entiers est appelée division euclidienne. Un algorithme permet de la calculer de façon peu efficace : c’est l’algorithme naïf. D’un point de vue général, le nom d’algorithme naïf est tooujours donné à l’algorithme le plus simple, celui qui met en œuvre l’idée la plus simple.

Ici, pour diviser a par b, on va soustraire b de a jusqu’à ce qu’on ait a inférieur à b. Le résultat est le nombre de soustractions effectuées, et a contient donc le reste de la division.

Multiplication Égyptienne

Cette méthode calcul utilisée dans l’Égypte antique est basée sur une décomposition en puissances de 2.

Dans un premier temps, on construit la décomposition en puissance de 2 du premier nombre de la multiplication(a). On calcule les puissance de 2 jusqu’à dépasser a. La multiplication par 2 est une addition d’un nombre par lui même.

On a ainsi, par exemple pour 25 : 1, puis 2, puis 4, puis 8, puis 16, puis 32.
32 étant trop grand, on l’abandonne, on garde 16.

On va maintenant soustraire les puissance de 2 successivement de a, lorsque c’est possible. Dans l’exemple : 25-16=9, puis 9-8=1, puis 1-4 est impossible, ainsi 1-2, et 1-1=0. On a donc 25=16+8+1. Les puissance de 2 utilisées sont : 0, 3,4

On construit ensuite le tableau des puissance de 2 multipliées par le second argument. Par exemple 13. On aura : 13, 26, 52, 104, 208.

Il reste maintenant à additionner les termes de la seconde série qui sont utilisée dans la première : 13+104+208=325.

C’est bien le résultat de 25*13.

Un message, un commentaire ?

Qui êtes-vous ?
Votre message

Pour créer des paragraphes, laissez simplement des lignes vides.