Zainspirowani tanią, szybką, dobrą , zaimplementujemy algorytm, który ma dokładnie dwa z nich.

Matematyka

Biorąc pod uwagę dwie niezerowe liczby całkowite a i b , GCF d jest największą liczbą całkowitą, która dzieli zarówno i b bez reszty. Współczynniki Bézouta to pary liczb całkowitych (x, y) takie, że ax + by = d . Współczynniki Bézouta nie są unikalne. Na przykład biorąc pod uwagę:

a = 15, b = 9

Mamy

d =  3
x =  2
y = -3

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

Powszechnym sposobem obliczania GCF i pary współczynników Bézouta jest użycie algorytmu Euclida , ale w żadnym wypadku nie jest to jedyny sposób.

Kod

Twój program powinien przyjąć dwie liczby całkowite jako dane wejściowe. Powinien generować / zwracać największy wspólny współczynnik i jedną parę współczynników Bézouta.

Przykładowe dane wejściowe:

15 9

przykładowe wyjście

3 (2, -3)

Dane wyjściowe mogą być w dowolnej kolejności i formacie, ale powinno być jasne, która jest GCF, a które są współczynnikami.

Podstępni

Twój program może być tani, szybki i dobry. Niestety mogą to być tylko dwa z nich jednocześnie.

• Jeśli nie jest tani , program powinien zużywać nadmierną ilość zasobów systemowych.
• Gdy nie jest to szybkie , program powinien zająć zbyt dużo czasu.
• Jeśli nie jest dobrze , wynik programu powinien być nieprawidłowy.

Program powinien być w stanie zrobić (dobrze, nie rób) wszystkie trzy. Co dzieje się, kiedy zależy od Ciebie - może być oparte na czasie, kompilatorze, którego dane wejściowe są większe itp. Kilka dodatkowych uwag:

• Twój program nie powinien być oczywiście podstępny i powinien przejść pobieżną kontrolę. Byłbym trochę podejrzliwy, jeśli zaimplementujesz trzy osobne algorytmy.
• W taniej sytuacji „nadmierna ilość zasobów systemowych” to wszystko, co spowolniłoby inne programy. Może to być pamięć, przepustowość itp.
• W szybkim przypadku „nadmierny czas” oznacza w stosunku do tego, jak przebiega w tanich i dobrych przypadkach. Program powinien się jeszcze zakończyć. Im bliżej „niesamowicie frustruje, ale nie jest wystarczająco frustrujące, aby zatrzymać program”, tym lepiej (zabawniej i).
• W dobrym przypadku wynik nie powinien być oczywiście nieprawidłowy i powinien przejść pobieżną kontrolę. Byłbym bardzo podejrzliwy, gdyby dał mi GCF „2 anna half”.

To konkurs popularności, więc większość entuzjastów wygrywa!

EDYTOWAĆ

Aby to wyjaśnić, szukam programów, które mogą być „szybkie i tanie” oraz „tanie i dobre” oraz „szybkie i dobre” w różnych przypadkach, a nie takie, które wykonują tylko jeden z nich.

do

Jest tani i szybki. Dostajesz gcd w mgnieniu oka. Jednak facet, który to zrobił, nie miał pojęcia o tym „czymś Béziera”, więc po prostu podzielił aib przez gcd. (co gorsza, w tym momencie aib są dość dalekie od ich początkowej wartości z powodu algorytmu, który mądrze wybrał)

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;
}

DO#

Oblicza to współczynniki Bézouta. Użyłem rozszerzonego algorytmu euklidesowego .

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__

Nie tanie: main () jest wywoływany rekurencyjnie (zapełnianie stosu), dopóki perl nie wyśle ​​ostrzeżenia o „głębokiej rekurencji”, który opuści aplikację z powodu obsługi __WARN__.

Nie szybko: gdy algorytmy gcf () zwracają poprawne wyniki, kod po prostu zawiesza się na kilka sekund (select () w main ()).

Niezbyt dobrze: wszystkie wyniki powyżej 99 (lub poniżej -99) są nieprawidłowe.

W sumie nie tak kreatywne; czekam na bardziej eleganckie odpowiedzi.

Pyton

#!/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))

Jest to tanie i szybkie, ale złe jest to, że zakres jest ograniczony do największego wejścia, więc może nie znaleźć pary współczynników.

Dobra łamigłówka.

JavaScript

Nie tanie

Zużywa wiele zasobów systemowych.

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];
}

Nie szybko

Użyj oddzwaniania, tak jak dodatkowe zabezpieczenie w razie awarii.

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);
}

Niedobrze

Ścisły limit gcf(10, 10), tylko do bezpiecznego miejsca na dysku.

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]];
}