Wyzwanie

Napisać program lub funkcję, która pobiera dwie liczby całkowite wejściowe, ia j, i wysyła ich największy wspólny dzielnik; obliczone przy użyciu algorytmu euklidesowego (patrz poniżej).

Wkład

Dane wejściowe można traktować jako ciąg znaków rozdzielany spacjami ii jlub jako dwie oddzielne liczby całkowite. Możesz założyć, że liczby całkowite będą mniejsze lub równe 10 000. Możesz także założyć, że wejściowe liczby całkowite nie będą względem siebie pierwszymi.

Podział euklidesowy

Im większa liczba z przedziału ii jjest podzielony przez mniejszą tyle razy, ile to możliwe. Następnie dodaje się resztę. Ten proces powtarza się z resztą i poprzednim numerem, aż reszta stanie się 0.

Na przykład, jeśli dane wejściowe to 1599 650:

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

Ostateczna liczba 13to największy wspólny dzielnik dwóch liczb całkowitych wejściowych. Można to wizualizować w następujący sposób:

Wydajność

Twój wynik musi być zestawieniem w powyższym formularzu, po którym następuje nowa linia i GCD. Może być wyprowadzany przez dowolny nośnik.

Przykłady

Wejścia

18 27
50 20
447 501
9894 2628

Wyjścia

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

Uwaga: Wyjścia nie muszą być rozmieszczane tak, jak są powyżej. Odstępy służą jedynie przejrzystości. Wymagane są nawiasy.

Premia

Jeśli twój wynik jest podzielony jak wyżej, możesz dodać -10% premii do swojego wyniku.

Pyth, 33 bajty

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

Wypróbuj online: pakiet demonstracyjny lub testowy

Wyjaśnienie:

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 bajtów

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

Wypróbuj online w interpretatorze CJam .

Jak to działa

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`

Funkcja rekurencyjna, która zwraca ciąg wielowierszowy. Funkcja tworzy pierwszy wiersz, a następnie dołącza go do wyniku rekurencyjnego z następną parą liczb w algorytmie euklidesowym. Gdy druga liczba jest równa zero, bierzemy ciąg drugiej liczby za przypadek podstawowy, powodując, że jest ona drukowana w swoim własnym wierszu na końcu.

Formatowanie odbywa się przez podstawienie łańcucha, przy użyciu dzielenia liczb całkowitych, aby uzyskać multiplicand.

Jeden czkawka musi zacząć się od przyjęcia większej liczby modów, tym mniejszej liczby. Dogodnie, jeśli liczby są w niewłaściwej kolejności, pierwszy krok algorytmu euklidesowego je odwraca. Aby zapobiec wyświetlaniu tego kroku, dodaj bieżący wiersz tylko wtedy, gdy pierwsza liczba to co najmniej druga (powiedzmy, że wymagana jest równość 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

Sortowanie danych wejściowych według rozmiaru zajmuje dużo bajtów: /
Sprowadza się do tego:

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

Wydajność

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

Dla zabawy stworzyłem też odpowiednio rozłożoną wersję, dającą mi wynik 233 * 0,9 == 209,7 bajtów.

Aktualizacja Byłem w stanie skrócić to z 285 bajtów, a teraz działa na dowolnie długie numery, jeśli wywołuje gawk4 z -Mopcją.

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

Ale wciąż mam wrażenie, że gdzieś wpadłem na jakiś mentalny blok ...

Wyjście (wywołanie gawk4 z awk -M -f code.awk)

6837125332653632513763 18237983363879361 (wejście)
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)

Dodano kilka nowych linii i kart

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

Na początku mogę zapisać długości początkowych wartości dla x, y i x% y, ponieważ mogą one być coraz krótsze z każdym krokiem. Ale dla współczynnika muszę określić maksymalną długość przed wydrukowaniem czegokolwiek, ponieważ jego długość może się różnić. Używam $itutaj jako tablicy, ponieważ zapisuje dwa znaki w porównaniu do używania [i] za każdym razem.

C ++, kompilator GCC, 171 bajtów (-10%, więc 154 bajty)

dobrze, więc moja pierwsza próba ...

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

mile widziane wskazówki do kodowania golfa.

PS Czy konieczne jest zliczanie bajtów standardowych plików nagłówkowych i int main podczas korzystania z c ++? Wykluczenie zmniejsza 50 bajtów

T-SQL (2012+), 268 bajtów

Zaimplementowano jako funkcję tabeli wbudowanej, która wykonuje rekurencyjną CTE. Być może warto spróbować sformatować bonus 10%, ale to będzie musiało poczekać.

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

Objaśnienie i użycie:

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

Algorytm rekurencyjny dzięki wskazówce od Klamki.

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

To naprawdę nie wyszło dobrze. whilePętla zajmuje zbyt wiele znaków, zwłaszcza z end. Nie widzę sposobu na uniknięcie tego. Rekurencja wymagałaby nazwanej funkcji zamiast lambda, która zjadłaby również wiele znaków.

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

Nazwij to tak:

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

Rekurencyjny blok kodu, przechowywany w zmiennej. Wywołaj go za pomocą & $e num1 num2np .:

$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

W bardziej czytelnej formie robi to następująco (nb. Dla jaśniejszego kodu umieściłem pełne nazwy komend, więcej spacji w łańcuchu i jawnie wydałem komendy wyjściowe potoku):

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

Jedna irytacja z punktu widzenia codegolfa; PoSh nie ma podziału na liczby całkowite, 10/3 zwraca Double, ale rzutuje wynik na liczbę całkowitą i nie zawsze zaokrągla w dół, zaokrągla N.5 do najbliższej parzystej liczby - w górę lub w dół. Tak [int](99/2) == 50.

To pozostawia dwie niezręczne opcje:

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

# or, worse

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

Dlatego muszę spalić niektóre postacie, wykonując:

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

Poza tym jest to liczba

Mam również wersję iteracyjną, która, całkiem ładnie, ma również 84 znaki:

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

Całkowicie anonimowy blok kodu, więc uruchom go

& {*codeblock*} 1599 650

PHP, 118 bajtów

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)."
":"";

Wypróbuj online!

PHP, 131 bajtów

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)."
":"";

Wypróbuj online!

-4 bajty wymienić list(,$n,$m)=$argvz [,$n,$m]=$argvpotrzebami PHP> = 7.1

Japt , 43 42 41 bajtów

Moje nowo odkryte „umiejętności” Japt wydają się coraz gorsze, a nie lepsze!

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

Wypróbuj online

JavaScript (ES6), 74 50 62 61 55 bajtów

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

• Poświęcono 12 bajtów, pozwalając na przekazywanie liczb całkowitych w dowolnej kolejności, a nie największej.

Spróbuj

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>

Wyjaśnienie

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 bajty

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 i wyniki

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

Nie wykonuje zwykłego algorytmu euklidesowego. Zamiast tego używa modułu, a następnie oblicza drugą liczbę do pomnożenia przez wydruk. Możesz także skrócić to, zmieniając je w wyrażenie lambda, ale nie jestem pewien, jak to zrobić.

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