Calculer le pgcd de deux nombres

Soyez le premier à donner votre avis sur cette source.

Vue 10 946 fois - Téléchargée 487 fois

Description

Le code calcul le pgcd de deux nombres avec l'algorithme d'Euclide.

Source / Exemple :


unit pgcd;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    Label1: TLabel;
    Label2: TLabel;
    Label3: TLabel;
    Button1: TButton;
    Button2: TButton;
    Edit1: TEdit;
    Edit2: TEdit;
    Edit3: TEdit;
    procedure Button2Click(Sender: TObject);
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.Button2Click(Sender: TObject);
var a : Integer;
    b : Integer;
    r : Integer;
    temp : Integer;
begin
a := StrToInt(Edit1.Text);
b := StrToInt(Edit2.Text);

{début de la boucle while}
while (temp <> -1)  do
begin
temp := r; {Variable temporaire}

r := a mod b;
a := b;
b := r;

if r = 0
then
begin
Edit3.Text := IntToStr(temp);
temp := -1;
end;

if r = 1
then
begin
Edit3.Text := IntToStr(r);
temp := -1;
end;
end;
{fin de la boucle while}
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
close
end;

end.

Conclusion :


Tout dabord pgcd signifie plus grand commun diviseur.
Explication de l'algorithme d'Euclide:
Tout résulte dans une seule formule a=bq+r
Ci dessous a/b.
a |_b_
r | q
Prenons un exemple 72/40
72|_40
32| 1

-> on fait ensuite 40/32
40|_32_
8 | 1

-> puis 32/8
32|_8_
0| 4

Le pgcd est le dernier reste non nule de ces divisions donc pgcd(72,40)=8 car le reste de 32/8 est 0.

Dans le programme celà donne.
-On déclare 3 variables a,b,r (q est inutile), une variable temp
- Une boucle While qui s'execute tant que temp est différent de -1
- On demande à l'utilisateur les deux nombres a et b (StrToInt sert à convertir la valeur entrée en Integer)
- On stocke r dans temp. (Ce qui permet de garder le dernier reste non nul)
- on fait r := a mod b (stocke le reste de la division)
- On effectue deux conditions :
- si r=1 alors le pgcd est 1
- si r=0 alors le pgcd est le reste de la division d'avant (C'est la variable temp qui le contient)
- dans les deux boucles conditionnels on stocke -1 dans la variable temp pour quitter la boucle while.

Voilà, j'espère que mes explications sont assez clair sinon envoyez moi un petit message ou alors un commentaire dans ma source.

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

g0belin
Messages postés
155
Date d'inscription
jeudi 6 décembre 2001
Statut
Membre
Dernière intervention
19 avril 2010
-
A quand la suite avec le PPCM ???
cs_bouba
Messages postés
518
Date d'inscription
dimanche 2 décembre 2001
Statut
Membre
Dernière intervention
10 novembre 2007
1 -
j'ai créé le programme avec le PPCM, vous pouvez aller le voir sur le site.
cs_Warzak
Messages postés
1
Date d'inscription
lundi 11 novembre 2002
Statut
Membre
Dernière intervention
11 novembre 2002
-
Bah ppcm c juste :

ppcm(a;b) = (a*b)/pgcd(a;b)

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.