Tantangan

Tulis program atau fungsi yang mengambil dua bilangan bulat input, idan j, dan hasilkan pembagi umum terbesar mereka; dihitung dengan menggunakan algoritma Euclidean (lihat di bawah).

Memasukkan

Input dapat diambil sebagai representasi string dengan batasan ruang idan jatau sebagai dua bilangan bulat terpisah. Anda dapat mengasumsikan bahwa bilangan bulat akan kurang dari atau sama dengan 10.000. Anda juga dapat mengasumsikan bahwa bilangan bulat input tidak akan menjadi prima satu sama lain.

Kerusakan Euclidean

Jumlah yang lebih besar antara idan jdibagi dengan yang lebih kecil sebanyak mungkin. Kemudian, sisanya ditambahkan. Proses ini diulangi dengan sisa dan nomor sebelumnya, sampai sisa menjadi 0.

Misalnya, jika inputnya adalah 1599 650:

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

Angka terakhir 13,, adalah pembagi umum terbesar dari dua bilangan bulat input. Dapat divisualisasikan seperti ini:

Keluaran

Output Anda harus berupa rincian dalam formulir di atas, diikuti oleh baris baru dan GCD. Ini bisa menjadi output melalui media apa pun.

Contohnya

Input

18 27
50 20
447 501
9894 2628

Keluaran

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

Catatan: Output tidak harus diberi spasi seperti di atas. Spasi hanya untuk kejelasan. Diperlukan tanda kurung.

Bonus

Jika output Anda diberi spasi seperti di atas, Anda dapat menambahkan bonus -10% untuk skor Anda.

Pyth, 33 byte

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

Cobalah online: Demonstrasi atau Test Suite

Penjelasan:

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 byte

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

Cobalah online di juru bahasa CJam .

Bagaimana itu bekerja

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`

Fungsi rekursif yang mengembalikan string multiline. Fungsi menciptakan baris pertama, kemudian menambahkannya ke hasil rekursif dengan pasangan angka berikutnya dalam algoritma Euclidean. Setelah angka kedua adalah nol, kita mengambil string dari angka lainnya sebagai alas, menyebabkannya dicetak pada barisnya sendiri di bagian akhir.

Pemformatan dilakukan melalui substitusi string, menggunakan divisi integer untuk mendapatkan multiplicand.

Satu cegukan harus dimulai dengan jumlah yang lebih besar yang diambil dengan jumlah yang lebih kecil. Mudahnya, jika angkanya salah, langkah pertama dari algoritma Euclidian membaliknya. Untuk mencegah langkah ini ditampilkan, hanya tambahkan baris saat ini jika angka pertama setidaknya yang kedua (kesetaraan diperlukan untuk, katakanlah 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

Menyortir input berdasarkan ukuran membutuhkan banyak byte: /
Turun ke ini:

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

Keluaran

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

Hanya untuk bersenang-senang saya membuat versi spasi juga, memberi saya skor 233 * 0,9 == 209,7 byte.

Pembaruan Saya dapat mempersingkat ini dari 285 byte dan sekarang berfungsi untuk nomor panjang sewenang-wenang jika memanggil gawk4 dengan -Mopsi.

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

Tapi aku masih punya perasaan aku berlari ke beberapa blok mental di suatu tempat ...

Output (gawk4 disebut dengan awk -M -f code.awk)

6837125332653632513763 18237983363879361 (masukan)
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

Beberapa baris dan tab baru ditambahkan

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

Saya bisa menyimpan panjang nilai awal untuk x, y dan x% y di awal, karena mereka hanya bisa mendapatkan lebih pendek setiap langkah. Tetapi untuk faktor saya harus menentukan panjang maksimum sebelum mencetak apa pun, karena panjangnya bisa bervariasi. Saya menggunakan $isebagai array di sini, karena menghemat dua karakter dibandingkan dengan menggunakan [i] setiap kali.

C ++, kompiler GCC, 171 byte (-10%, jadi 154 byte)

oke jadi coba pertama saya ..

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

tips untuk kode golf dihargai.

PS Apakah perlu untuk menghitung byte dari file header standar dan int main saat menggunakan c ++? Tidak termasuk itu mengurangi 50 byte

T-SQL (2012+), 268 byte

Diimplementasikan sebagai fungsi tabel inline yang mengeksekusi CTE rekursif. Mungkin bermanfaat untuk mencoba memformat bonus 10%, tetapi itu harus menunggu.

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

Penjelasan dan penggunaan:

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

Algoritma rekursif, terima kasih untuk tip dari 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

Ini benar-benar tidak berhasil sama sekali. The whileLoop memakan terlalu banyak karakter, terutama dengan end. Saya tidak bisa melihat cara untuk menghindarinya. Rekursi akan membutuhkan fungsi bernama alih-alih lambda, yang juga akan memakan banyak karakter.

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

Sebut saja seperti ini:

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

Blok kode rekursif, disimpan dalam variabel. Aktifkan dengan & $e num1 num2, misalnya:

$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

Dalam bentuk yang lebih mudah dibaca, ia melakukan hal berikut (nb. Untuk kode yang lebih jelas, saya telah memasukkan nama commandlet lengkap, lebih banyak spasi dalam string, dan membuat perintah output pipa eksplisit):

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

Satu gangguan dari sudut pandang codegolf; PoSh tidak memiliki divisi integer, 10/3 mengembalikan Double, tetapi membuang hasilnya ke integer dan tidak selalu bulat, membulatkan N.5 ke bilangan genap terdekat - naik atau turun. Jadi [int](99/2) == 50.

Itu menyisakan dua pilihan aneh:

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

# or, worse

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

Itulah sebabnya saya harus membakar beberapa karakter:

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

Terlepas dari itu, ini adalah jumlah

Saya juga memiliki versi berulang yang, agak bagus, juga 84 karakter:

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

Codeblock sepenuhnya anonim, jadi jalankan dengan

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

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

Cobalah online!

-4 Bytes diganti list(,$n,$m)=$argvdengan [,$n,$m]=$argvkebutuhan PHP> = 7.1

Japt , 43 42 41 byte

"Keterampilan" yang baru saya temukan tampaknya semakin buruk, tidak lebih baik!

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

Cobalah online

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

• Mengorbankan 12 byte yang memungkinkan bilangan bulat diteruskan dalam urutan apa pun, bukan yang terbesar terlebih dahulu.

Cobalah

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>

Penjelasan

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 byte

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

tes dan hasil

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

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

Itu tidak melakukan algoritma Euclidean biasa. Sebagai gantinya, ia menggunakan modulus dan kemudian menghitung angka ke-2 untuk dikalikan dengan kapan itu dicetak. Anda juga dapat membuat ini lebih pendek dengan mengubahnya menjadi ekspresi lambda, tapi saya tidak yakin bagaimana caranya.

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