Lalgorithme dEuclide - univ-reunionfr
L'algorithme d'Euclide La scène peut être munie d'un ou plusieurs « arrière-plans », dont l'un représente un repère ; or l'algorithme d'Euclide peut être implémenté graphiquement en modifiant des coordonnées On peut simuler un point mobile en prenant le lutin « ball » et en le redimensionnant
Voici une méthode décrite dans un ouvrage
1 Voici une méthode décrite dans un ouvrage d'Euclide pour déterminer la profondeur d'un puits : en plaçant son oeil à 1m60 de hauteur et à 1m du bord d'un puits de 1,20m de diamètre, le bord du puits cache juste la ligne du fond 1,60m 1m 1,20m (a) Faire une gure et nommer les points qui représentent l'oeil et les pieds
Algorithmed’Euclide - CultureMath
où l’on a utilisé intensivement (à chaque fois que l’égalité est surmontée d’un ) le résultat ci-dessus Remarquons que l’on a arrêté le calcul à pgcd(15;45) = 15 parce que l’on a noté que 15 était un diviseur de 45, mais que l’on aurait pu continuer à appliquer la méthode
Euclide et la méthode axiomatique
Euclide (330-275 avant notre ère) Né à Alexandrie Euclide insistait toujours auprès de ses élèves pour dire que l’acquisition des connaissances ne doit pas se faire dans un but intéressé, mais pour le plaisir du savoir Un jour, un élève qui assistait depuis peu au cours d’Euclide, demanda : « Que puis-je gagner à écouter tout
Nombres entiers – rationnels - PGCD - Exercices
a 11592 et 9936 (divisions successives - méthode d’Euclide) b 357 et 721 (divisions successives - méthode d’Euclide) c 1312 et 2536 (divisions successives) d 1634 et 602 (soustractions successives) Exercice 9 Grâce à un tableur, déterminer le PGCD de deux nombres en utilisant l’algorithme d’Euclide
Multiples et Diviseurs (Fiches méthodes)
Méthode 8 Calculer le PGCD de deux nombres en utilisant l'algorithme d'Euclide Exemple de résolution Calculer le PGCD de 270 et 210 1ère étape : On commence par faire la division euclidienne de 270 par 210 : 270 = 1*210 + 60 2ème étape : On continue en divisant le diviseur par le reste obtenu 210 = 3*60 + 30 60 = 2*30 + 0
Exercices - pdfbibcom
Calcul du pgcd de 2 entiers (méthode Euclide) Objectif : On souhaite écrire un programme de calcul du pgcd de deux entiers non nuls, en C# à partir de l’algorithme de la méthode d'Euclide Voici une spécification de l'algorithme de calcul du PGCD de deux nombres (entiers strictement positifs) a et b, selon cette méthode :
Lycée Echebbi Tadhaman Devoir de contrôle N°1 Prof OUERGHI
1°) Déterminer le PGCD(1848; 1980 ) par la méthode d’algorithme d’Euclide Exercice 1 ( 5 pts ) 2°) Déduire le PPCM (1848; 1980 )
Euclide et GéoPlan - debart
Les éléments d’Euclide Page 1/9 Descartes et les Mathématiques Euclide et GéoPlan Démonstration des théorèmes de Thalès et Pythagore par la méthode des aires Sommaire 1 Triangle équilatéral 2 Reproduire un angle 3 Arithmétique : algorithme d'Euclide 4 Thalès : démonstration par la méthode des aires 5
[PDF] Méthode d'analyse critique d'un document d'histoire 1ère L
[PDF] méthode d'ératostere
[PDF] Méthode d'Eratosthène
[PDF] méthode d'alphabétisation pour adultes
[PDF] méthode d'amélioration des processus
[PDF] méthode d'analyse chimique
[PDF] méthode d'analyse de texte
[PDF] méthode d'analyse définition
[PDF] méthode d'analyse et de conception
[PDF] méthode d'analyse informatique
[PDF] methode d'analyse physico chimique
[PDF] méthode d'analyse qqoqcp
[PDF] méthode d'analyse qualitative
[PDF] méthode d'analyse swot
L"algorithme d"Euclide
Pierre Lescanne
derni`ere mise `a jour:18 janvier 2006 - 09: 07 Plan KnuthEuclide
Le plus grand commun diviseur
Source
Cete expos´e est inspir´e de
l"ouvrage de Don KnuthThe art of computer programming Vol.2 Knuth Sˆurement le plus grand scientifique informaticien contemporain. The art of computer programminga ´et´e d´esign´e parAmerican Scientist, parmi les douze meilleurs livres scientifiques du si`ecle. avec1.lam´ecanique quantiquede Dirac,
2.larelativit´ed"Einstein,
3.lesfractalesde Mandelbrot,
4.laliaison chimiquede Pauling,
5.lafondation des math´ematiquesde Russel et Withehead,
6.lath´eorie des jeuxde von Neumannn et Morgenstern,
7.lacybern´etiquede Wiener,
8.lasym´etrie orbitalede Woodward et Hoffmann,
9.l"´electrodynamique quantiquede Feynman,
10.larecherche de structurede Smith,
11.lesoeuvres compl`etesd"Einstein.
Plan KnuthEuclide
Le plus grand commun diviseur
Euclide
Euclide (n´e vers -325, mort vers -265 `a Alexandrie) ´etudia `a Ath`enes `a l"´Ecole des successeurs de Platon et il s"´etablit `a Alexandrie sur l"invitation de Ptol´em´ee II, roi d"´Egypte.Ses´
El´ementssont constitu´es de 13 livres :
?qui sont une synth`ese des math´ematiques connues `a son ´epoque,?auxquelles Euclide apporte des compl´ements, desd´emonstrations et de la rigueur,?qui traitent d"arithm´etique, d"alg`ebre et de g´eom´etrie.
L"algorithme d"Euclide
L"algorithme d"Euclide de calcul duplus grand commun diviseurse trouve dans lelivre 7 propositions 1 et 2.Il n"est pas probablement pas de lui.
Les experts pensent que la m´ethode ´etait d´ej`a connue 200 ans auparavant. Au moins dans sa forme soustractive, elle ´etait connue d"Eudoxe.Le plus vieil algorithme non trivial connu,
car il contient explicitement une it´eration. Plan KnuthEuclide
Le plus grand commun diviseur
Le plus grand commun diviseur
Le plus grand commun diviseurpgcd(m,n)demetnest le plus grand entier qui divise `a la foismetn.Sim= 2m23m35m57m711m11...=?
ppremierp mpalors pgcd(m,n) =? ppremierp min(mp,np).Cette formule est inapplicable en pratique, car elle n´ecessite de factoriser un nombre en facteurs premiers, ce que l"on se sait pas faire efficacement.L"algorithme d"Euclide annot´e (1/3)
Proposition.´
Etant donn´e deux entiers positifs, trouver leur plus grand commun diviseur.L"initialisation SoitAetCdeux entiers positifs; on doit trouver leur plus grand commun diviseur.SiCdiviseA, alorsCest un diviseur commun deCet Apuisqu"il se divise lui-mˆeme. Il est aussi clairement le plus grand puisqu"aucun entier plus grand queCne diviseC.L"it´eration SiCne divise pasA,alorsje soustrais de fa¸con continuele plus petit des nombresAouCdu plus grand, jusqu"`a ce qu"un nombre divise le pr´ec´edent. Ceci arrivera `a un moment ou `a un autre, puisque s"il reste une unit´e, il divise le nombre pr´ec´edent.L"algorithme d"Euclide annot´e (2/3)
Preuve que le r´esultat est un diviseur commun
SoitmaintenantEle reste deAdivis´e parC;soitFle reste deCdivis´e parE. Supposons queFest un diviseur deE.PuisqueFdiviseEetEdivise C-F,Fdivise aussiC-F; mais il se divise lui-mˆeme, donc il diviseC. PuisqueCdiviseA-EalorsFdiviseA-E. Mais il divise aussiEalors, il diviseA.Donc c"est un diviseur commun deAetC.L"algorithme d"Euclide (3/3)
Preuve que le r´esultat est le plus grand diviseur commun J"affirme maintenant que c"est le plus grand. En effet, siFn"est pas le plus grand diviseur commun deAetC, un nombre plus grand doit lesdiviser tous les deux.SoitGun tel nombre.Maintenant puisqueGdiviseCtandis queCdiviseA-E, alorsGdivise
A-E.GdiviseAtout entier, donc il doit diviser le resteE. MaisE diviseC-F; par cons´equent,GdiviseC-F. OrGdiviseCentier, donc il divise le resteF; c"est-`a-dire qu"un nombre plus grand divise un nombre plus petit.C"est impossible.Commentaires
L"algorithme a ´et´e simplifi´e.
Les Grecs ne consid`erent pas l"unit´e comme un"diviseur»d"un entier. Plus pr´ecis´ement,?l"unit´en"est pas un nombre, ?lez´eron"existe pas Etant donn´es deux entiers positifs,?ou bien il sont tous les deux ´egaux `a l"unit´e, ?ou plus il sont premiers entre eux, ?ou bien ils ont unpgcd.Commentaires
Euclide duplique ses explications et donne deux propositions s´epar´ees.Commentaires
En fait, Euclide fournit un algorithmefond´e sur des soustractions pgcd(m,n) =pgcd(m-n,n)sim>n pgcd(m,n) =pgcd(m,n-m)simcens´ee valoir pour le cas g´en´eral.1que le vingti`eme si`ecle a commenc´e seulement `a d´ecouvrir!