Problem
Donald Knuth, auteur de “
The Art of Programming", considère l'algorithme d'Euclide comme le tout premier. Parce que, malgré le fait que l'algorithme ait été inventé et utilisé avant même
Euclid, qui a vécu aux IV-III siècles . J.-C. (il est déjà mentionné par
Aristote, qui a vécu un siècle plus tôt), Euclide décrit le processus de manière itérative, c'est-à-dire compatible avec le sens moderne du mot "algorithme".
"Remplacez le plus grand des deux nombres par la différence entre le plus grand et le plus petit jusqu'à ce qu'ils soient égaux. C'est GCD."
L'algorithme d'Euclide lui-même est familier à tous les écoliers modernes. La description mathématique peut être consultée
ici. Mettre en œuvre
classique Algorithme d'Euclide et formatez-le comme une fonction
nod(a, b) qui prend 2 nombres en entrée et renvoie le plus grand commun diviseur de ces deux nombres.
Aucune entrée ou sortie requise ! Il vous suffit d'implémenter la fonction.
Запрещенные операторы: gcd;%