IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Téléchargez Discussion :

Algorithme d'Euclide et "plus grand commun diviseur"


Sujet :

Téléchargez

  1. #1
    Rédacteur/Modérateur

    Avatar de Jerome Briot
    Homme Profil pro
    Freelance en conception mécanique et prototypage
    Inscrit en
    novembre 2006
    Messages
    20 175
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Freelance en conception mécanique et prototypage

    Informations forums :
    Inscription : novembre 2006
    Messages : 20 175
    Points : 54 326
    Points
    54 326
    Par défaut Algorithme d'Euclide et "plus grand commun diviseur"


    codons l'algorithme de Euclide permettant de déterminer le plus grand commun diviseur entre deux nombres entiers

    Le code suivant détermine le plus grand commun diviseur ("greatest common divisor" en anglais) entre une liste d'entiers contenus dans deux tableaux :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    function gcd = findgcd(a,b)
    %FINDGCD
    %
     
    % Author : Jerome Briot (Dut)
    % Contact : dutmatlab#yahoo#fr -or- briot#cict#fr
    % Profil : www.mathworks.com/matlabcentral/newsreader/author/94805
    %        : www.developpez.net/forums/u125006/dut/
    %
    % Version : 1.0 - 04 Sep 2009
    %
     
    % MATLAB : 7.6.0.324 (R2008a)
    % System : Linux 2.6.24-24-generic
    %
     
    error(nargchk(2,2,nargin));
     
    if ndims(a)~=ndims(b)
        error('A and B must have the same number of dimensions');
    end
     
    if numel(a)~=numel(b)
        error('A and B must have the same number of elements');
    end
     
    gcd = ones(size(a))*-1;
    idx = (a & b);
    gcd(idx) = 2*(~bitget(a(idx),1) & ~bitget(b(idx),1));
     
    idx = ~gcd;
     
    if ~any(idx)
        return
    end
     
    gcd(idx) = euclidalgo(a(idx),b(idx));
     
    function g = euclidalgo(aa,bb)
     
    for n=1:numel(aa)
     
        if aa(n)<bb(n)
            m = bb(n);
            g(n) = aa(n);
        else
            g(n) = bb(n);
            m = aa(n);
        end
     
        r = mod(m,g(n));
        while r>0
            m = g(n);
            g(n) = r;
            r = mod(m,g(n));
        end
    end
    Voici un fichier démo :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    function demofindgcd
    %DEMOFINDGCD
    %
     
    % Author : Jerome Briot (Dut)
    % Contact : dutmatlab#yahoo#fr -or- briot#cict#fr
    % Profil : www.mathworks.com/matlabcentral/newsreader/author/94805
    %        : www.developpez.net/forums/u125006/dut/
    %
    % Version : 1.0 - 04 Sep 2009
    %
     
    % MATLAB : 7.6.0.324 (R2008a)
    % System : Linux 2.6.24-24-generic
    %
     
    a = [6 27 8 2 0 1268  462];
    b = [35 6 0 4 0 1254 1071];
     
    gcd = findgcd(a,b);
     
    sprintf('%5d %5d %5d %5d %5d %5d %5d\n',[a;b;gcd].')
    Qui renvoie ceci :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
        6    27     8     2     0  1268   462
       35     6     0     4     0  1254  1071
        1     3    -1     2    -1     2    21
    La troisième ligne contient le plus grand commun diviseur entre chaque élément de la première ligne et celui de la seconde lui correspondant.

    La valeur -1 est retournée si au moins une des deux valeurs est 0.

    Voila... si vous avez des remarques, des questions ou des suggestions, n'hésitez pas

    Mais rappelez-vous que je ne suis pas un spécialiste dans ce domaine

    Note : Ne sachant pas si ces codes sont justes, je ne les ai pas optimisés (et donc pas commentés)
    Fichiers attachés Fichiers attachés
    Ingénieur indépendant en conception mécanique et prototypage :
    • conception mécanique 3D (Autodesk Fusion 360)
    • impression 3D (Ultimaker)
    • développement informatique (Python, MATLAB, C)
    • programmation de microcontrôleur (Microchip PIC, Arduino…)

    « J'étais le meilleur ami que le vieux Jim avait au monde. Il fallait choisir. J'ai réfléchi un moment, puis je me suis dit : "Tant pis ! J'irai en enfer" » (Saint Huck)

Discussions similaires

  1. Calcul du Plus Grand Commun Diviseur (PGCD)
    Par hpalpha dans le forum Contribuez
    Réponses: 0
    Dernier message: 13/02/2011, 18h21
  2. quel algorithme pour trouver le plus grand sous arbres commun à des arbres?
    Par iwky911 dans le forum Algorithmes et structures de données
    Réponses: 0
    Dernier message: 20/05/2009, 22h08
  3. Algorithme de plus grand sous-mot commun
    Par nicolas66 dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 28/11/2006, 14h24

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo