Terinspirasi oleh Murah, Cepat, Bagus , kita akan menerapkan algoritma yang memiliki tepat dua di antaranya.

Matematika

Dengan dua bilangan nol bukan a dan b , GCF d adalah bilangan bulat terbesar yang membagi a dan b tanpa sisa. Koefisien Bézout adalah pasangan bilangan bulat (x, y) sedemikian rupa sehingga ax + by = d . Koefisien Bézout tidak unik. Misalnya, diberikan:

a = 15, b = 9

Kita punya

d =  3
x =  2
y = -3

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

Cara umum untuk menghitung GCF dan sepasang koefisien Bézout adalah menggunakan Algoritma Euclid , tetapi itu bukan satu-satunya cara.

Kode

Program Anda harus mengambil dua bilangan bulat sebagai input. Ini akan menghasilkan / mengembalikan faktor umum terbesar dan sepasang koefisien Bézout.

Input contoh:

15 9

contoh output

3 (2, -3)

Outputnya bisa dalam urutan dan format apa pun, tetapi harus jelas yang mana adalah GCF dan yang merupakan koefisien.

Si curang

Program Anda berpotensi menjadi murah, cepat, dan bagus. Sayangnya, itu hanya dua.

• Saat itu tidak murah , program harus menggunakan sumber daya sistem dalam jumlah yang berlebihan.
• Saat itu tidak cepat , program harus menghabiskan banyak waktu.
• Jika tidak bagus , output program harus salah.

Program harus dapat melakukan (well, not do) ketiganya. Yang dilakukan saat terserah Anda- bisa berdasarkan waktu, kompiler, input mana yang lebih besar, dll. Beberapa catatan tambahan:

• Program Anda seharusnya tidak curang dan harus lulus inspeksi sepintas. Saya akan sedikit curiga jika Anda menerapkan tiga algoritma terpisah.
• Dalam kasus murah , "jumlah sumber daya sistem yang berlebihan" adalah segala sesuatu yang akan memperlambat program lain. Bisa jadi memori, bandwidth, dll.
• Dalam kasus cepat , "waktu berlebihan" berarti relatif terhadap cara kerjanya dalam kasus murah dan bagus . Program masih harus selesai. Semakin dekat Anda bisa "sangat frustasi tetapi tidak cukup frustasi untuk menghentikan program" yang (lebih lucu dan) lebih baik.
• Dalam kasus yang baik , hasilnya tidak seharusnya salah dan harus lulus inspeksi sepintas. Saya akan sangat curiga jika itu memberi saya GCF "2 anna setengah".

Ini adalah kontes popularitas, jadi kebanyakan orang yang menang menang!

EDIT

Untuk memperjelas, saya mencari program yang bisa "cepat dan murah" dan "murah dan bagus" dan "cepat dan bagus" dalam kasus yang berbeda, bukan yang hanya melakukan salah satunya.

C

Murah dan cepat. Anda mendapatkan gcd dalam sekejap mata. Namun pria yang melakukannya tidak tahu tentang "Bézier co-something" jadi dia hanya membagi a dan b dengan gcd. (Untuk membuat segalanya lebih buruk, pada saat itu a dan b cukup jauh dari nilai awal mereka karena algoritma yang ia pilih dengan bijak)

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 #

Ini menghitung koefisien Bézout. Saya menggunakan algoritma Extended Euclidean .

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__

Tidak murah: main () disebut rekursif (mengisi tumpukan) sampai peringatan "rekursi dalam" dipecat oleh perl yang akan keluar dari aplikasi karena handler __WARN__.

Tidak cepat: Ketika algoritma gcf () mengembalikan hasil yang benar, kode hanya hang selama beberapa detik (pilih () di main ()).

Tidak bagus: Semua hasil di atas 99 (atau di bawah -99) salah.

Semuanya tidak begitu kreatif; menantikan jawaban yang lebih elegan.

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

Ini murah dan cepat tetapi buruk pada kenyataan bahwa kisaran dibatasi pada input terbesar sehingga mungkin tidak menemukan sepasang koefisien.

Teka-teki yang bagus.

Javascript

Tidak murah

Menggunakan banyak sumber daya sistem.

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

Tidak cepat

Gunakan panggilan balik, sama seperti failafe ekstra.

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

Tidak baik

Batas ketat gcf(10, 10), hanya untuk ruang disk yang aman.

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