Inspiré par Cheap, Fast, Good , nous allons implémenter un algorithme qui en a exactement deux.

Les maths

Étant donné deux entiers non nuls a et b , le GCF d est le plus grand entier qui divise à la fois a et b sans reste. Les coefficients de Bézout sont des paires d'entiers (x, y) telles que ax + by = d . Les coefficients de Bézout ne sont pas uniques. Par exemple, étant donné:

a = 15, b = 9

On a

d =  3
x =  2
y = -3

Depuis 15*2 + 9*(-3) = 30 - 27 = 3.

Une façon courante de calculer le GCF et une paire de coefficients de Bézout est d'utiliser l'algorithme d'Euclide , mais ce n'est en aucun cas le seul moyen.

Le code

Votre programme doit prendre deux entiers en entrée. Il doit produire / renvoyer le plus grand facteur commun et une paire de coefficients de Bézout.

Exemple d'entrée:

15 9

exemple de sortie

3 (2, -3)

La sortie peut être dans n'importe quel ordre et format, mais il doit être clair quel est le GCF et quels sont les coefficients.

Les sournois

Votre programme a le potentiel d'être bon marché, rapide et bon. Malheureusement, il ne peut y en avoir que deux à la fois.

• Lorsqu'il n'est pas bon marché , le programme doit utiliser une quantité excessive de ressources système.
• Lorsqu'il n'est pas rapide , le programme devrait prendre trop de temps.
• Quand ce n'est pas bon , la sortie du programme devrait être fausse.

Le programme devrait être capable de faire (enfin, ne pas faire) les trois. C'est à vous de décider - cela peut être basé sur l'heure, le compilateur, quelle entrée est plus grande, etc. Quelques notes supplémentaires:

• Votre programme ne doit pas être visiblement sournois et doit passer une inspection superficielle. Je serais un peu méfiant si vous implémentiez trois algorithmes distincts.
• Dans le cas bon marché , «une quantité excessive de ressources système» est tout ce qui pourrait ralentir d'autres programmes. Il peut s'agir de mémoire, de bande passante, etc.
• Dans le cas rapide , «temps excessif» signifie par rapport à la façon dont il fonctionne dans les cas bon marché et bons . Le programme devrait encore se terminer. Plus vous vous rapprochez de "incroyablement frustrant mais pas assez frustrant pour arrêter le programme", mieux c'est (drôle et).
• Dans le bon cas, la sortie ne doit pas être manifestement fausse et doit passer une inspection superficielle. Je serais très méfiant si cela me donnait un GCF de "2 anna half".

Il s'agit d'un concours de popularité, donc la plupart des votes positifs gagnent!

ÉDITER

Pour clarifier, je suis à la recherche des programmes qui peuvent être « rapide et pas cher » et « bon et pas cher » et « rapide et bon » dans les différents cas, pas ceux qui ne seul d'entre eux.

C

C'est bon marché et rapide. Vous obtenez un gcd en un clin d'œil. Cependant, le gars qui l'a fait n'avait aucune idée de ce "co-quelque chose de Bézier" alors il a simplement divisé a et b par pgcd. (pour aggraver les choses, à ce point a et b sont assez loin de leur valeur initiale en raison de l'algorithme qu'il a judicieusement choisi)

int main(int argc, char **argv){
    unsigned int a, b, tmp;
    a = (unsigned int)atoi(argv[1]);
    b = (unsigned int)atoi(argv[2]);
    for (tmp = 0; ((a | b) & 1) == 0; ++tmp){
        a >>= 1;
        b >>= 1;
    }
    while ((a & 1) == 0) 
        a >>= 1;
    do {
        while ((b & 1) == 0)
            b >>= 1;
        if (a > b){
            unsigned int t = b; 
            b = a; 
            a = t;
        }  
        b = b - a;
    } while (b != 0);
    tmp = a << tmp;
    printf("%u, (%u,%u)", tmp, a/tmp, b/tmp);
    return 0;
}

C #

Ceci calcule les coefficients de Bézout. J'ai utilisé l' algorithme euclidien étendu .

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Enter your first number.");
            int firstNumber = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine("Enter your second number.");
            int secondNumber = Convert.ToInt32(Console.ReadLine());

            double max = Math.Max(firstNumber, secondNumber);
            double min = Math.Min(firstNumber, secondNumber);
            double s1 = 1;
            double s2 = 0;
            double t1 = 0;
            double t2 = 1;
            double quotient = 0;
            double remainder = 0;
            double[] remainders = new double[0];

            int i = 0;
            do
            {
                quotient = (int)(max / min);
                remainder = max - quotient * min;
                if (remainder > 0)
                {
                    Array.Resize(ref remainders, remainders.Length + 1);
                    remainders[i] = remainder;

                }
                if (i % 2 == 0)
                {
                    s1 = s1 - quotient * s2;
                    t1 = t1 - quotient * t2;
                }
                else
                {
                    s2 = s2 - quotient * s1;
                    t2 = t2 - quotient * t1;
                }

                if (i == 0)
                {
                    max = min;

                }
                else if (i >= 1)
                {
                    max = remainders[i - 1];
                }


                min = remainder;
                i++;
            } while (remainder > 0);

            Console.WriteLine((remainders[remainders.Length - 1]).ToString() + " " + (i % 2 == 0 ? "(" + s1 + "," + t1 + ")" : "(" + s2 + "," + t2 + ")"));
        }

    }
}

Perl 5

#!/usr/bin/perl
use strict;
use warnings;

$SIG{__WARN__} = sub { exit };

print(<<INTRO);
Greatest Common Factor

    goodbye           -- exit the application
    [number] [number] -- compute gcf of both numbers

INTRO

main();
sub main {
    print "> ";
    chomp(local $_ = <STDIN>);

    print "Have a good one.\n" and exit if /goodbye/;

    my @nums = /(-?\d+)/g;
    print "invalid input\n" and return main() if @nums != 2;

    my ($gcf, @coeff) = gcf(@nums);
    unless (grep abs($_) > 99, $gcf, @coeff) {
        select $\,$\,$\, rand for 1..10;
    }

    local $" = ", "; #"
    print "gcf(@nums) = $gcf\n";
    print "bezout coefficients: @coeff\n";
    main();
}

sub gcf {
    my ($x, $y) = @_;

    my @r = ($x, $y);
    my @s = (1, 0);
    my @t = (0, 1);

    my $i = 1;
    while ($r[$i] != 0) {
        my $q = int($r[$i-1] / $r[$i]);
        for (\@r, \@s, \@t) {
            $_->[$i+1] = $_->[$i-1] - $q * $_->[$i];
        }
        $i++;
    }

    return map int(1.01 * $_->[$i-1]), \@r, \@s, \@t;
}

__END__

Pas bon marché: main () est appelée récursivement (en remplissant la pile) jusqu'à ce qu'un avertissement de "récurrence profonde" soit déclenché par perl qui quittera l'application en raison du gestionnaire __WARN__.

Pas rapide: lorsque les algorithmes gcf () retournent des résultats corrects, le code se bloque pendant quelques secondes (select () dans main ()).

Pas bon: tous les résultats supérieurs à 99 (ou inférieurs à -99) sont incorrects.

Dans l'ensemble, pas si créatif; dans l'attente de réponses plus élégantes.

Python

#!/usr/bin/python
def gcd(x, y):
    l = 0
    if x < y:
        l = x
    else:
        l = y
    for g in reversed(range(l + 1)):
        if x%g == 0 and y%g == 0 and g > 1:
            return g
        else:
            if g == 1:
                return 1

def bezout(x,y,g):
    c1 = 0
    c2 = 0
    k = 0
    if x < y:
        k = y
    else:
        k = x
    for _k in range(k):
        tc = (gcd(x,y) - x*_k)%y
        if tc == 0:
            c1 = _k
            c2 = (gcd(x,y) - y*_k)/x
            return (c1, c2)

gc = gcd(15,9)
be, bf = bezout(9,15,gc)
print("%d (%d, %d)" % (gc, be, bf))

C'est bon marché et rapide, mais c'est mauvais dans le fait que la plage est plafonnée à l'entrée la plus grande, de sorte qu'il peut ne pas trouver une paire de coefficients.

Bon puzzle.

Javascript

Pas cher

Utilise beaucoup de ressources système.

function gcf(a, b) {
    var result = 1;
    for (var i = 1; i < 100000000 * a && i < 100000000/* Do it a few extra times, just to make sure */ * b; i++) {
        if (a % i == 0 && b % i == 0) {
            result = i;
        }
    }
    return [result, a / result, b / result];
}

Pas vite

Utilisez un rappel, tout comme une sécurité supplémentaire.

function gcf(a, b) {
    setTimeout(function() {
        var result = 1;
        for (var i = 1; i < 2 * a && i < 2 * b; i++) {
            if (a % i == 0 && b % i == 0) {
                result = i;
            }
        }
        alert(result.toString() + " (" + (a / result).toString() + ", " + (b/result).toString() + ")");
    }, 10000);
}

Pas bon

Limite stricte de gcf(10, 10), juste pour un espace disque sûr.

function gcf(a, b) {
    var gcfTable = [[1,1,1,1,1,1,1,1,1,1],[1,2,1,2,1,2,1,2,1,2],[1,1,3,1,1,3,1,1,3,1],[1,2,1,4,1,2,1,4,1,2],[1,1,1,1,5,1,1,1,1,5],[1,2,3,2,1,6,1,2,3,2],[1,1,1,1,1,1,7,1,1,1],[1,2,1,4,1,2,1,8,1,2],[1,1,3,1,1,3,1,1,9,1],[1,2,1,2,5,2,1,2,1,10]];
    return [gcfTable[a - 1][b - 1], a / gcfTable[a - 1][b - 1], b / gcfTable[a - 1][b - 1]];
}