Die Herausforderung

Schriebe ein Programm oder eine Funktion , die zwei Eingänge ganze Zahlen erfolgt, iund jund gibt ihren größten gemeinsamen Teiler; berechnet mit dem euklidischen Algorithmus (siehe unten).

Eingang

Die Eingabe kann als durch Leerzeichen getrennte Zeichenfolgendarstellung von iund joder als zwei separate Ganzzahlen erfolgen. Sie können davon ausgehen, dass ganze Zahlen kleiner oder gleich 10.000 sind. Sie können auch davon ausgehen, dass die Eingabe-Ganzzahlen keine Primzahlen zueinander sind.

Euklidischer Zusammenbruch

Die größere Zahl zwischen iund jwird so oft wie möglich durch die kleinere geteilt. Dann wird der Rest hinzugefügt. Dieser Vorgang wird mit dem Rest und der vorherigen Nummer wiederholt, bis der Rest wird 0.

Zum Beispiel, wenn die Eingabe war 1599 650:

1599 = (650 * 2) + 299
 650 = (299 * 2) +  52
 299 =  (52 * 5) +  39
  52 =  (39 * 1) +  13
  39 =  (13 * 3) +   0

Die letzte Zahl 13ist der größte gemeinsame Teiler der beiden Eingabe-Ganzzahlen. Es kann so visualisiert werden:

Ausgabe

Ihre Ausgabe muss die Aufschlüsselung in der obigen Form sein, gefolgt von einem Zeilenumbruch und der GCD. Es kann über jedes Medium ausgegeben werden.

Beispiele

Eingänge

18 27
50 20
447 501
9894 2628

Ausgänge

27 = (18 * 1) + 9
18 =  (9 * 2) + 0
9

50 = (20 * 2) + 10
20 = (10 * 2) +  0
10

501 = (447 * 1) + 54
447 =  (54 * 8) + 15
 54 =  (15 * 3) +  9
 15 =   (9 * 1) +  6
  9 =   (6 * 1) +  3
  6 =   (3 * 2) +  0
3

9894 = (2628 *  3) + 2010
2628 = (2010 *  1) +  618
2010 =  (618 *  3) +  156
 618 =  (156 *  3) +  150
 156 =  (150 *  1) +    6
 150 =    (6 * 25) +    0
6

Hinweis: Die Ausgänge müssen nicht wie oben angeordnet sein. Der Abstand dient nur der Übersichtlichkeit. Klammern sind erforderlich.

Bonus

Wenn Ihre Ausgabe wie oben angegeben verteilt ist, können Sie Ihrer Punktzahl einen Bonus von -10% hinzufügen.

Pyth, 33 Bytes

ASQWGs[H\=\(G\*/HG\)\+K%HG)A,KG)H

Probieren Sie es online aus: Demo oder Test Suite

Erläuterung:

ASQWGs[H\=\(G\*/HG\)\+K%HG)A,KG)H
  Q                                read the two numbers from input
 S                                 sort them
A                                  and assign them to G and H
   WG                              while G != 0:
                      K%HG           assign H mod G to K
     s[H\=\(G\*/HG\)\+K   )          join the following list items and print:
                                        H=(G*(H/G))+K
                           A,KG      assign K, G to G, H
                               )   end while
                                H  print H

CJam, 46 43 39 Bytes

q~]$3*~\{N5$"=("3$:G'*3$Gmd")+"\}h]7>NG

Probieren Sie es online im CJam-Interpreter aus .

Wie es funktioniert

q~]    e# Read all input, evaluate it and wrap the results in an array.
$3*    e# Sort the array and repeat it thrice.
~\     e# Dump the array and swap its last two elements.
{      e# Do:
  N    e#   Push a linefeed.
  5$   e#   Copy the sixth topmost element from the stack.
  "=(" e#   Push that string.
  3$:G e#   Copy the fourth topmost element from the stack. Save it in G.
  '*   e#   Push that character.
  3$   e#   Copy the fourth topmost element from the stack.
  Gmd  e#   Push quotient and remainder of its division by G.
  ")+" e#   Push that string.
  \    e#   Swap the string with the remainder.
}h     e#   If the remainder is positive, repeat the loop.
]7>    e# Wrap the stack in an array and discard its first seven elements.
NG     e# Push a linefeed and G.

Python 2, 70

f=lambda a,b:b and'%d=(%d*%d)+%d\n'%(a,b,a/b,a%b)*(a>=b)+f(b,a%b)or`a`

Eine rekursive Funktion, die eine mehrzeilige Zeichenfolge zurückgibt. Die Funktion erstellt die erste Zeile und hängt sie dann mit dem nächsten Zahlenpaar im euklidischen Algorithmus an das rekursive Ergebnis an. Sobald die zweite Zahl Null ist, nehmen wir die Zeichenfolge der anderen Zahl als Basisfall, sodass sie am Ende in einer eigenen Zeile gedruckt wird.

Die Formatierung erfolgt durch Zeichenfolgensubstitution unter Verwendung einer Ganzzahldivision, um den Multiplikanden zu erhalten.

Ein Schluckauf muss mit der größeren Zahl beginnen, die mod der kleineren Zahl genommen wird. Wenn sich die Zahlen in der falschen Reihenfolge befinden, werden sie zweckmäßigerweise im ersten Schritt des Euklidian-Algorithmus umgedreht. Um zu verhindern, dass dieser Schritt angezeigt wird, fügen Sie die aktuelle Zeile nur hinzu, wenn die erste Zahl mindestens die zweite ist (Gleichheit ist beispielsweise erforderlich für f(9,9)).

awk, 78 77

x=$1{for(x<$2?x+=$2-(y=x):y=$2;t=y;x=t)print x"=("y"*"int(x/y)")+",y=x%y}$0=x

Das Sortieren der Eingabe nach Größe erfordert viele Bytes
:

x=$1;
if(x<$2) x+=$2-(y=x); # add $2 subtract $1 and set y to $1
else y=$2;            # set y to $2

Ausgabe

650 1599 (Eingabe)
1599 = (650 × 2) + 299
650 = (299 · 2) + 52
299 = (52 * 5) + 39
52 = (39 * 1) + 13
39 = (13 · 3) + 0
13

Nur zum Spaß habe ich auch eine Version mit dem richtigen Abstand erstellt, die eine Punktzahl von 233 * 0,9 == 209,7 Bytes ergibt.

Update Ich konnte dies von 285 Bytes verkürzen und jetzt funktioniert es für beliebig lange Nummern, wenn gawk4 mit der -MOption aufgerufen wird .

x=$1{x<$2?x+=$2-(y=x):y=$2;a=length(x);b=length(y);for(d=length(x%y);t=y;x=t){$++i=x;$++i=y;if(c<l=length($++i=int(x/y)))c=l;$++i=y=x%y}while(j<NF)printf "%"a"d = %"b-length($(j+2))"s(%d * %"c"d) + %"d"d\n",$++j,_,$++j,$++j,$++j}$0=x

Aber ich hatte immer noch das Gefühl, dass ich dort irgendwo auf eine mentale Blockade gestoßen bin ...

Ausgang (mit gawk4 aufgerufen awk -M -f code.awk)

6837125332653632513763 18237983363879361 (Eingabe)
6837125332653632513763 = (18237983363879361 * 374883) + 15415252446024000
     18237983363879361 = (15415252446024000 * 1) + 2822730917855361
     15415252446024000 = (2822730917855361 * 5) + 1301597856747195
      2822730917855361 = (1301597856747195 * 2) + 219535204360971
      1301597856747195 = (219535204360971 * 5) + 203921834942340
       219535204360971 = (203921834942340 * 1) + 15613369418631
       203921834942340 = (15613369418631 * 13) + 948032500137
        15613369418631 = (948032500137 * 16) + 444849416439
          948032500137 = (444849416439 * 2) + 58333667259
          444849416439 = (58333667259 * 7) + 36513745626
           58333667259 = (36513745626 * 1) + 21819921633
           36513745626 = (21819921633 * 1) + 14693823993
           21819921633 = (14693823993 * 1) + 7126097640
           14693823993 = (7126097640 * 2) + 441628713
            7126097640 = (441628713 * 16) + 60038232
             441628713 = (60038232 * 7) + 21361089
              60038232 = (21361089 * 2) + 17316054
              21361089 = (17316054 * 1) + 4045035
              17316054 = (4045035 * 4) + 1135914
               4045035 = (1135914 * 3) + 637293
               1135914 = (637293 * 1) + 498621
                637293 = (498621 * 1) + 138672
                498621 = (138672 * 3) + 82605
                138672 = (82605 * 1) + 56067
                 82605 = (56067 * 1) + 26538
                 56067 = (26538 * 2) + 2991
                 26538 = (2991 × 8) + 2610
                  2991 = (2610 * 1) + 381
                  2610 = (381 · 6) + 324
                   381 = (324 * 1) + 57
                   324 = (57 · 5) + 39
                    57 = (39 * 1) + 18
                    39 = (18 * 2) + 3
                    18 = (3 · 6) + 0
3

Einige Zeilenumbrüche und Tabulatoren hinzugefügt

x=$1{
    x<$2?x+=$2-(y=x):y=$2;
    a=length(x);
    b=length(y);
    for(d=length(x%y);t=y;x=t)
    {
        $++i=x;
        $++i=y;
        if(c<l=length($++i=int(x/y)))c=l;
        $++i=y=x%y
    }
    while(j<NF)
        printf "%"a"d = %"b-length($(j+2))"s(%d * %"c"d) + %"d"d\n",
                                               $++j,_,$++j,$++j,$++j
}$0=x

Ich kann die Längen der Anfangswerte für x, y und x% y am Anfang speichern, weil sie bei jedem Schritt nur kürzer werden können. Aber für den Faktor muss ich die maximale Länge bestimmen, bevor ich etwas drucke, da die Länge variieren kann. Ich benutze es hier $ials Array, weil es zwei Zeichen speichert, verglichen mit der Verwendung eines [i] jedes Mal.

C ++, GCC-Compiler, 171 Bytes (-10%, also 154 Bytes)

Okay, also mein erster Versuch.

#include<iostream>
using namespace std;
int main()
{
    int a,b,c;
    cin>>a>>b;
    if(a<b)
    swap(a,b);
    while(b>0)
    {
        c=a;
        cout<<a<<" = ("<<b<<" * "<<a/b<<") + "<<a%b<<endl;
        a=b;
        b=c%b;
    }
    cout<<a;
}

Tipps zum Code Golf geschätzt.

PS Müssen bei Verwendung von c ++ die Bytes der Standardheaderdateien und von int main gezählt werden? Ausgenommen, es reduziert 50 Bytes

T-SQL (2012+), 268 Byte

Implementiert als Inline-Tabellenfunktion, die einen rekursiven CTE ausführt. Es könnte sich lohnen, den 10% -Bonus zu formatieren, aber das muss warten.

CREATE FUNCTION E(@ INT,@B INT)RETURNS TABLE RETURN WITH M AS(SELECT IIF(@<@B,@B,@)A,IIF(@>@B,@B,@)B),R AS(SELECT A,B,A/B D,A%B R FROM M UNION ALL SELECT B,R,B/R,B%R FROM R WHERE 0<>R)SELECT CONCAT(A,'=(',B,'*',D,')+',R)R FROM R UNION ALL SELECT STR(B)FROM R WHERE R=0

Erklärung und Verwendung:

--Create the function
CREATE FUNCTION E(@ INT,@B INT)RETURNS TABLE RETURN
WITH
    --Order the input correctly
    M AS (
          SELECT IIF(@<@B,@B,@)A,
                 IIF(@>@B,@B,@)B
          )
    --Recursive selection
    ,R AS (
          SELECT A,B,A/B D,A%B R FROM M -- Anchor query
          UNION ALL
          SELECT B,R,B/R,B%R FROM R     -- Recurse until R = 0
          WHERE 0<>R
          )
SELECT CONCAT(A,'=(',B,'*',D,')+',R)R   -- Concat results into output string
FROM R 
UNION ALL                               -- ALL required to maintain order
SELECT STR(B)                           -- Add final number
FROM R WHERE R=0

--Function Usage
SELECT * FROM E(447,501)

R
-----------------------------------------------------
501=(447*1)+54
447=(54*8)+15
54=(15*3)+9
15=(9*1)+6
9=(6*1)+3
6=(3*2)+0
3

Rev. 1: Ruby, 86

Rekursiver Algorithmus dank Tipp von Doorknob.

f=->i,j{j>i&&(i,j=j,i)
0<j ?(print i," = (#{j} * #{i/j}) + #{i%j}
";f[j,i%j]):puts(i)}

Rev. 0: Ruby, 93

Das hat wirklich nicht gut geklappt. Die whileSchleife nimmt zu viele Zeichen auf, insbesondere bei end. Ich kann keinen Weg finden, dies zu vermeiden. Eine Rekursion würde eine benannte Funktion anstelle eines Lambdas erfordern, was auch viele Zeichen verschlingen würde.

->i,j{j>i&&(i,j=j,i)
while j>0
print(i," = (#{j} * #{i/j}) + #{i%j}\n")
i,j=j,i%j
end
puts i}

Nenne es so:

f=->i,j{j>i&&(i,j=j,i)
while j>0
print(i," = (#{j} * #{i/j}) + #{i%j}\n")
i,j=j,i%j
end
puts i}

I=gets.to_i
J=gets.to_i

f.call(I,J)

PowerShell, 84

Ein rekursiver Codeblock, der in einer Variablen gespeichert ist. Rufen Sie es auf mit & $e num1 num2zB:

$e={$s,$b=$args|Sort;if(!$s){$b}else{$r=$b%$s;"$b=($s*$(($b-$r)/$s))+$r";&$e $s $r}}

PS D:\> & $e 9894 2628
9894=(2628*3)+2010
2628=(2010*1)+618
2010=(618*3)+156
618=(156*3)+150
156=(150*1)+6
150=(6*25)+0
6

In einer besser lesbaren Form macht es Folgendes (zur Verdeutlichung des Codes habe ich die vollständigen Commandlet-Namen und mehr Leerzeichen in die Zeichenfolge eingefügt und die Pipeline-Ausgabebefehle explizit gemacht):

function Euclid {
    $small, $big = $args|Sort-Object   #Sort argument list, assign to two vars.

    if (!$small) {                     #Recursion end, emit the last
        Write-Output $big              #number alone, for the last line.

    } else {                           #main recursive code

        $remainder = $big % $small
        Write-Output "$big = ( $small* $(($big-$remainder)/$small)) + $remainder"
        Euclid $small $remainder
    }
}

Ein Ärger aus Codegolf-Sicht; PoSh hat keine Ganzzahldivision, 10/3 gibt ein Double zurück, wandelt das Ergebnis jedoch in eine Ganzzahl um und rundet nicht immer ab, sondern rundet N.5 auf die nächste gerade Zahl - auf oder ab. Also [int](99/2) == 50.

Das lässt zwei schwierige Entscheidungen:

$remainder = $x % $y
$quotient = [Math]::Floor($x/$y)

# or, worse

$remainder=$null
$quotient = [Math]::DivRem($x, $y, [ref]$remainder)

Deshalb muss ich einige Charaktere brennen, um:

$remainder = $big % $small
($big - $remainder)/$small

Abgesehen davon ist es die Anzahl der

Ich habe auch eine iterative Version, die auch 84 Zeichen enthält:

{$r=1;while($r){$s,$b=$args|Sort;$r=$b%$s;"$b=($s*$(($b-$r)/$s))+$r";$args=$s,$r}$s}

Vollständig anonymer Codeblock, also starte ihn mit

& {*codeblock*} 1599 650

PHP, 118 Bytes

for(list(,$n,$m)=$argv,$g=max($n,$m),$l=min($n,$m);$g;$g=$l,$l=$m)
echo$g,$l?"=($l*".($g/$l^0).")+".($m=$g%$l)."
":"";

Probieren Sie es online!

PHP, 131 Bytes

for(list(,$n,$m)=$argv,$r=[max($n,$m),min($n,$m)];$r[+$i];)echo$g=$r[+$i],($l=$r[++$i])?"=($l*".($g/$l^0).")+".($r[]=$g%$l)."
":"";

Probieren Sie es online!

-4 Bytes ersetzen list(,$n,$m)=$argvbei [,$n,$m]=$argvBedarf PHP> = 7.1

Japt , 43 42 41 Bytes

Meine neu entdeckten Japt "Skills" scheinen sich zu verschlechtern, nicht zu verbessern!

?U>V?ßVU :[V'='(U'*V/U|0')'+V%=UR,ßVU]¬:V

Probieren Sie es online aus

JavaScript (ES6), 74 50 62 61 55 Byte

f=(x,y)=>y?y>x?y:x+`=(${y}*${x/y|0})+${x%=y}
`+f(y,x):x

• Opferte 12 Bytes, sodass die Ganzzahlen in beliebiger Reihenfolge übergeben werden konnten und nicht die größten zuerst.

Versuch es

f=(x,y)=>y?y>x?y:x+`=(${y}*${x/y|0})+${x%=y}
`+f(y,x):x
o.innerText=f(i.value=683712533265363251376,j.value=18237983363879361)
i.oninput=j.oninput=_=>o.innerText=f(+i.value,+j.value)

<input id=i type=number><input id=j type=number><pre id=o>

Erläuterung

f=          :Assign the function to variable f ...
(x,y)=>     :And take the two integer inputs as arguments via parameters x and y.
y?          :If y is greater than 0 then
y>x?        :    If y is greater than x then
f(y,x)      :        Call f again, with the order of the integers reversed.
            :        (This can only happen the first time the function is called.)
:           :    Else
x           :        Start building the string, beginning with the value of x.
+`=(        :        Append "=(".
${y}        :          The value of y.
*           :          "*"
${x/y|0}    :          The floored value of x divided by y
)+          :          ")+"
${x%=y}     :          The remainder of x divided by y, which is assigned to x
            :          (x%=y is the same as x=x%y.)
\n          :          A newline (a literal newline is used in the solution).
`+f(y,x)    :        Append the value f returns when y and the new value of x
            :        are passed as arguments.
:           :Else
x           :    Return the current value of x,
            :    which will be the greatest common divisor of the original two integers.

JS, 151

a=prompt("g","");b=prompt("l","");c=0;l=[a,b];for(var i=0;i<=1;i++){t=c;o=c+1;r=c+2;n=l[t]%l[o];if(n!==0){l[r]=n;c=c+1;i=0;}else{p=l[o];alert(p);i=2;}}

C 83 Bytes

g(x,y,z){y&&(printf("%u=(%u*%u)+%u\n",x,y,x/y,z=x%y),z)?g(y,z,0):printf("%u\n",y);}

Test und Ergebnisse

int main()
{g(18,27,0);
 g(50,20,0);
 g(447,501,0);
 g(9894,2628,0);
}

18=(27*0)+18
27=(18*1)+9
18=(9*2)+0
9
50=(20*2)+10
20=(10*2)+0
10
447=(501*0)+447
501=(447*1)+54
447=(54*8)+15
54=(15*3)+9
15=(9*1)+6
9=(6*1)+3
6=(3*2)+0
3
9894=(2628*3)+2010
2628=(2010*1)+618
2010=(618*3)+156
618=(156*3)+150
156=(150*1)+6
150=(6*25)+0
6

Java 133

public void z(int i,int j){for(int d=1;d!=0;i=j,j=d){d=i%j;System.out.println(i+"=("+j+"*"+((i-d)/j)+")+"+d);}System.out.println(i);}

Es funktioniert nicht mit dem regulären euklidischen Algorithmus. Stattdessen wird das Modul verwendet und die zweite Zahl berechnet, mit der beim Ausdruck multipliziert wird. Sie können dies auch verkürzen, indem Sie es in einen Lambda-Ausdruck umwandeln, aber ich bin mir nicht sicher, wie.

public void z(int i, int j)
{
    for(int d=1;d!=0;i=j,j=d)
    {
        d=i%j;
        System.out.println(i+"=("+j+"*"+((i-d)/j)+")+"+d);
    }
    System.out.println(i);
}