Technique de multiplication

Chaque peuple a sa propre technique pour multiplier des nombres. Chez certains on pose la multiplication comme vous l'avez apprise à l'école, chez d'autres on utilise une représentation visuelle qui consiste à compter des points et chez d'autres encore on utilise une technique qui ne demande que de savoir multiplier et diviser par 2.

Cette technique est intéressante car multiplier ou diviser un nombre par 2 est quelque chose qu'il est très facile de faire de tête (et aussi dans un micro-processeur), voici le principe que nous allons découvrir sur la multiplication "37x15".

On commence par faire deux colonnes : dans la première on divise le nombre par 2 à chaque étape (en division entière, on élimine à chaque fois ce qui est après la virgule), dans la seconde on multiplie par 2 à chaque étape.

37  x  15
18  x  30
9   x  60
4   x  120
2   x  240
1   x  480

Ensuite, on barre les lignes ou le premier nombre est pair

37  x  15
18  x  30
9   x  60
4   x  120
2   x  240
1   x  480

Il ne reste plus qu'à sommer les nombre de la deuxième colonne :

37 x 15 = 15 + 60 + 480 = 555

Au lieu de tout sommer à la fin on peut aussi calculer le résultat au fur et à mesure :

37  x  15  ; résultat = 0
18  x  30  ; résultat = 15 = 0 + 15
9   x  60  ; résultat = 15
4   x  120 ; résultat = 75 = 15 + 60
2   x  240 ; résultat = 75
1   x  480 ; résultat = 75
0   x  960 ; résultat = 555 = 75 + 480

De manière plus courte on a le tableau suivant :

37	15	0
18	30	15
9	60	15
4	120	75
2	240	75
1	480	75
0	960	555

A vous de programmer cette méthode de division. Vous devrez afficher le tableau ci-dessus afin de bien montrer les étapes.

Entrée

Sur une ligne, deux entiers positifs et non nuls.

Sortie

Vous devez calculer le produit des deux entiers en utilisant la technique expliquée ci-dessus. Vous devez afficher le tableau comme expliqué ci-dessus, ainsi que le résultat final.

Les nombres doivent être séparés les uns des autres par des espaces.

Exemple

entrée :

37 15

sortie :

37 15 0
18 30 15
9 60 15
4 120 75
2 240 75
1 480 75
0 960 555
555

Source : https://www.france-ioi.org/