Billig, schnell, gut - Common Factor (Größter) [geschlossen]

10

Inspiriert von Cheap, Fast, Good werden wir einen Algorithmus implementieren, der genau zwei davon enthält.

Die Mathematik

Bei zwei Ganzzahlen ungleich Null a und b ist der GCF d die größte Ganzzahl, die a und b ohne Rest teilt . Bézout-Koeffizienten sind Paare von ganzen Zahlen (x, y), so dass ax + by = d ist . Bézout-Koeffizienten sind nicht eindeutig. Zum Beispiel gegeben:

a = 15, b = 9

Wir haben

d =  3
x =  2
y = -3

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

Eine übliche Methode zur Berechnung des GCF und eines Paares von Bézout-Koeffizienten ist die Verwendung des Euklid-Algorithmus , aber keineswegs die einzige.

Der Code

Ihr Programm sollte zwei Ganzzahlen als Eingaben verwenden. Es sollte den größten gemeinsamen Faktor und ein Paar Bézout-Koeffizienten ausgeben / zurückgeben.

Beispieleingabe:

15 9

Beispielausgabe

3 (2, -3)

Die Ausgabe kann in beliebiger Reihenfolge und in beliebigem Format erfolgen, es sollte jedoch klar sein, welches der GCF und welche die Koeffizienten sind.

Die Hinterhältigen

Ihr Programm hat das Potenzial, billig, schnell und gut zu sein. Leider können es nur zwei davon gleichzeitig sein.

  • Wenn es nicht billig ist , sollte das Programm eine übermäßige Menge an Systemressourcen verwenden.
  • Wenn es nicht schnell ist , sollte das Programm zu lange dauern.
  • Wenn es nicht gut ist , sollte die Programmausgabe falsch sein.

Das Programm sollte in der Lage sein, alle drei zu erledigen (naja, nicht zu tun). Was ist, wenn es nach Ihnen geht - es könnte auf der Zeit, dem Compiler, der größeren Eingabe usw. basieren. Einige zusätzliche Hinweise:

  • Ihr Programm sollte nicht offensichtlich hinterhältig sein und eine flüchtige Prüfung bestehen. Ich wäre etwas misstrauisch, wenn Sie drei separate Algorithmen implementieren würden.
  • Im billigen Fall ist "übermäßige Menge an Systemressourcen" alles, was andere Programme verlangsamen würde. Es kann Speicher, Bandbreite usw. sein.
  • Im schnellen Fall bedeutet "übermäßige Zeit" relativ dazu, wie es in den billigen und guten Fällen läuft . Das Programm sollte noch beendet sein. Je näher man "unglaublich frustrierend, aber nicht frustrierend genug, um das Programm zu stoppen" kommen kann, desto (lustiger und) besser.
  • Im guten Fall sollte die Ausgabe nicht offensichtlich falsch sein und eine flüchtige Prüfung bestehen. Ich wäre sehr misstrauisch, wenn es mir einen GCF von "2 anna half" geben würde.

Dies ist ein Beliebtheitswettbewerb, daher gewinnen die meisten Upvotes!

BEARBEITEN

Zur Verdeutlichung suche ich nach Programmen, die in verschiedenen Fällen "schnell und billig" und "billig und gut" und "schnell und gut" sein können, nicht nach Programmen, die nur eines davon ausführen.

Hovercouch
quelle
1
Es ist schön, eine originelle Herausforderung wie diese zu haben. :)
Ypnypn
Muss das Programm genau zwei auf einmal sein oder ist es in Ordnung, wenn es nur in einigen Fällen gut und in anderen billig und schnell (aber nicht gut) ist?
Dennis
1
Ich suche drei Fälle mit jeweils genau zwei.
Hovercouch
Wenn das Programm nicht gut ist, sollte die Ausgabe falsch sein? Was bringt es dann, etwas richtig zu berechnen?
Ricardo A
4
Ich stimme dafür, diese Frage als nicht zum Thema gehörend zu schließen, da es sich um eine [hinterhältige] Herausforderung handelt, die vor einem Jahr zum Thema gehörte, jetzt aber im Konsens der Community nicht zum Thema gehört .
James

Antworten:

2

C.

Es ist billig und schnell. Sie erhalten gcd im Handumdrehen. Der Typ, der es tat, hatte jedoch keine Ahnung von diesem "Bézier-Co-Etwas", also teilte er einfach a und b durch gcd. (Um die Sache noch schlimmer zu machen, sind a und b zu diesem Zeitpunkt aufgrund des von ihm mit Bedacht gewählten Algorithmus ziemlich weit von ihrem Anfangswert entfernt)

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;
}
bebe
quelle
0

C #

Dies berechnet die Bézout-Koeffizienten. Ich habe den Extended Euclidean Algorithmus verwendet .

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

    }
}
Bura Chuhadar
quelle
Wann ist das teuer, wann ist es langsam und wann ist es schlecht?
U-Bahn:
@undergroundmonorail Ich werde diese Werte setzen, wenn ich die Chance habe.
Bura Chuhadar
0

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__

Nicht billig: main () wird rekursiv aufgerufen (den Stapel füllen), bis eine Perl-Warnung "Deep Recursion" von Perl ausgelöst wird, die die Anwendung aufgrund des __WARN__ -Handlers beendet.

Nicht schnell: Wenn der gcf () -Algorithmus korrekte Ergebnisse zurückgibt, bleibt der Code nur einige Sekunden lang bestehen (select () in main ()).

Nicht gut: Alle Ergebnisse über 99 (oder unter -99) sind falsch.

Alles in allem nicht so kreativ; Ich freue mich auf elegantere Antworten.

Matthias
quelle
0

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

Dies ist billig und schnell, aber es ist schlecht, dass der Bereich auf den größten Eingang begrenzt ist, sodass möglicherweise kein Koeffizientenpaar gefunden wird.

Gutes Puzzle.

Ricardo A.
quelle
0

Javascript

Nicht billig

Verwendet viele Systemressourcen.

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

Nicht schnell

Verwenden Sie einen Rückruf als zusätzliche Ausfallsicherheit.

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

Nicht gut

Strikte Begrenzung von gcf(10, 10), nur um Speicherplatz zu sichern.

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]];
}
Kaliumion
quelle
Wann ist es billig und schnell, aber nicht gut?
Hovercouch
Diese Antwort ist billig, gut, aber nicht schnell.
Kaliumionen
Die Herausforderung besteht darin, ein Programm zu schreiben, das unter verschiedenen Umständen jeweils "nicht billig", "nicht schnell" und "nicht gut" ist.
Hovercouch
Antwort behoben ...
Kaliumion