Евклидов алгоритм (для нахождения наибольшего общего делителя)

22

Соревнование

Напишите программу или функцию, которая принимает два входных целых числа iи jвыводит их наибольший общий делитель; рассчитывается с использованием евклидова алгоритма (см. ниже).

вход

Входные данные могут быть приняты в качестве пространства , разделенных строковым представлением iи jили в виде двух отдельных целых чисел. Вы можете предположить, что целые числа будут меньше или равны 10000. Вы также можете предположить, что входные целые числа не будут взаимно простыми.

Евклидово расстройство

Большее число между iи jделится на меньшее как можно больше раз. Затем остаток добавляется. Этот процесс повторяется с остатком и предыдущим номером, пока остаток не станет 0.

Например, если вход был 1599 650:

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

Последнее число 13является наибольшим общим делителем двух входных целых чисел. Это можно представить так:

Выход

Ваш вывод должен быть разбит на форму выше, за которой следует перевод строки и GCD. Он может быть выведен через любой носитель.

Примеры

входные

18 27
50 20
447 501
9894 2628

Выходы

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

Примечание. Выходы не обязательно должны располагаться так, как указано выше. Интервал только для ясности. Скобки обязательны.

бонус

Если ваш вывод находится в интервале, как указано выше, вы можете добавить бонус -10% к вашему счету.

code-golf math Зак Гейтс
источник
1. Можем ли мы предположить, что наибольшее число дается первым? 2. Для бонуса вы имеете в виду, что ширина поля должна быть постоянной и достаточной, чтобы оставить один пробел перед наибольшим числом? (с пробелами перед левой круглой скобкой во втором столбце чисел.) Следует избегать неоднозначных фраз, таких как «как они есть выше», когда выходные данные являются переменными. Это нормально, если требуемый вывод зафиксирован.
Уровень Река St
Хорошо, я вижу, что некоторые примеры имеют наибольшее число секунд
Level River St.
Ваше первоначальное название было в порядке, я прокомментировал то, что произошло на meta.codegolf.stackexchange.com/q/7043/15599 . Однако фраза «наибольший общий знаменатель» была неправильной. «Знаменатель» относится к дробям. Поиск в Google «наибольший общий знаменатель» дает результаты только для «наибольший общий делитель / фактор».
Уровень Река Св
Я думал, что название было в порядке, но я изменил его на «The», чтобы никого не вызывать недовольство. Спасибо за редактирование в "делителе", кстати. @steveverrill
Зак Гейтс,

Ответы:

4

Pyth, 33 байта

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

Попробуйте онлайн: демонстрация или тестовый набор

Объяснение:

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
Jakube
источник
7

CJam, 46 43 39 байт

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

Попробуйте онлайн в интерпретаторе CJam .

Как это работает

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.
Деннис
источник
6

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`

Рекурсивная функция, которая возвращает многострочную строку. Функция создает первую строку, а затем добавляет ее к рекурсивному результату со следующей парой чисел в евклидовом алгоритме. Если второе число равно нулю, мы берем строку другого числа в качестве базового случая, в результате чего она будет напечатана в отдельной строке в конце.

Форматирование выполняется путем подстановки строк с использованием целочисленного деления для получения мультипликатора.

Один сбой нужно начинать с большего числа, взятого с меньшего числа. Удобно, если числа находятся в неправильном порядке, первый шаг евклидова алгоритма переворачивает их. Чтобы этот шаг не отображался, добавляйте текущую строку только в том случае, если первое число равно, по крайней мере, второму (например, необходимо равенство f(9,9)).

XNOR
источник
5

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

Сортировка входных данных по размеру занимает много байтов: /
Это сводится к следующему:

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

Выход

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

Просто для удовольствия я также сделал правильно расставленную версию, получив оценку 233 * 0,9 == 209,7 байта.

Обновление Я смог сократить это с 285 байтов, и теперь он работает для произвольно длинных чисел, если вызвать gawk4 с -Mопцией.

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

Но у меня все еще было чувство, что я где-то столкнулся с каким-то ментальным блоком ...

Выход (gawk4 вызывается с awk -M -f code.awk)

6837125332653632513763 18237983363879361 (вход)
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

Добавлено несколько новых строк и вкладок

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

Я могу сохранить длины начальных значений для x, y и x% y в начале, потому что они могут становиться только короче с каждым шагом. Но для фактора я должен определить максимальную длину, прежде чем что-либо печатать, потому что ее длина может варьироваться. Я использую $iв качестве массива здесь, потому что он сохраняет два символа по сравнению с использованием [i] каждый раз.

Cabbie407
источник
4

C ++, компилятор GCC, 171 байт (-10%, поэтому 154 байт)

хорошо, так что моя первая попытка .. 

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

Советы по кодированию в гольф приветствуются.

PS Нужно ли подсчитывать байты стандартных заголовочных файлов и int main при использовании c ++? Исключая это уменьшает 50 байтов

Деванг Джаячандран
источник
Примечание: я исключил пробел, используемый для создания красивого кода.
Деванг Джаячандран
3

T-SQL (2012+), 268 байт

Реализуется как встроенная табличная функция, которая выполняет рекурсивный CTE. Возможно, стоит попытаться использовать форматирование для получения бонуса в 10%, но это должно подождать.

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

Объяснение и использование:

--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
MickyT
источник
2

Ред. 1: Рубин, 86

Рекурсивный алгоритм, благодаря совету от 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)}

Ред. 0: Рубин, 93

Это действительно не сработало вообще. whileЦикл занимает слишком много символов, особенно с end. Я не вижу способа избежать этого. Рекурсия потребовала бы именованной функции вместо лямбды, которая также потребляла бы много символов.

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

Назовите это так:

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)
Уровень реки St
источник
Вы можете использовать рекурсию через a=->i,j{...}и вызывать aчерез a[1,2]- хотя вы не уверены, что это спасет ваших персонажей.
Дверная ручка
@ Doorknob спасибо за совет, я не знал о том синтаксисе для вызова лямбда-функций (см. Мое использование f.call.) На самом деле он немного короче, но все еще далеко от Python.
Уровень Река St
2

PowerShell, 84

Блок рекурсивного кода, хранящийся в переменной. Вызвать его & $e num1 num2, например:

$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

В более читаемой форме он выполняет следующие действия (для более ясного кода, я поместил полные имена командлетов, больше пробелов в строке и сделал явными выходные команды конвейера):

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

Одно раздражение с точки зрения Codegolf; В PoSh нет целочисленного деления, 10/3 возвращает Double, но приводит результат к целому числу, и оно не всегда округляется в меньшую сторону, оно округляет N.5 до ближайшего четного числа - вверх или вниз. Так [int](99/2) == 50.

Это оставляет два неловких выбора: 

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

# or, worse

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

Вот почему я должен сжечь некоторых персонажей, делая:

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

Кроме того, это число

и отсутствие троичного оператора, который действительно причиняет боль.

У меня также есть итеративная версия, которая, как ни странно, также состоит из 84 символов:

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

Полностью анонимный кодовый блок, поэтому запустите его с

& {*codeblock*} 1599 650
TessellatingHeckler
источник
2

PHP, 118 байт

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

Попробуйте онлайн!

PHP, 131 байт

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

Попробуйте онлайн!

-4 байта заменить list(,$n,$m)=$argvна [,$n,$m]=$argvпотребности PHP> = 7.1

Йорг Хюльсерманн
источник
2

Japt , 43 42 41 байт

Кажется, что мои вновь обретенные «навыки» Джапта становятся хуже, а не лучше!

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

Попробуйте онлайн

мохнатый
источник
2

JavaScript (ES6), 74 50 62 61 55 байт

f=(x,y)=>y?y>x?y:x+`=(${y}*${x/y|0})+${x%=y}
`+f(y,x):x
  • Пожертвовано 12 байт, позволяющих передавать целые числа в любом порядке, а не по величине в первую очередь.

Попытайся

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>
Развернуть фрагмент

объяснение

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.
мохнатый
источник
1

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;}}
кораблик
источник
1

C 83 байта

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

тест и результаты

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
RosLuP
источник
0

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

Это не делает обычный евклидов алгоритм. Вместо этого он использует модуль, а затем вычисляет 2-е число для умножения на время его распечатки. Вы также можете сделать это короче, превратив его в лямбда-выражение, но я не знаю как.

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);
}
светящийся
источник
Я знаю, что прошло более 1,5 лет, но вы можете удалить public , изменить второй printlnна printи изменить d!=0на d>0. Кроме того, в настоящее время он дает неправильный вывод для первых строк. Это можно исправить, добавив if(d!=i)перед System.out.println(i+"=("+j+"*"+((i-d)/j)+")+"+d);. Итого всего: void z(int i,int j){for(int d=1;d>0;i=j,j=d){d=i%j;if(d!=i)System.out.println(i+"=("+j+"*"+((i-d)/j)+")+"+d);}System.out.print(i);}( 131 байт и исправлена ​​ошибка)
Кевин Круйссен