O desafio

Escreva um programa ou função que use dois números inteiros de entrada, ie j, e emita seu maior divisor comum; calculado usando o algoritmo euclidiano (veja abaixo).

Entrada

A entrada pode ser tomada como uma representação de string delimitada por espaço ie / jou como dois números inteiros separados. Você pode assumir que números inteiros serão menores ou iguais a 10.000. Você também pode assumir que os números inteiros de entrada não serão primos um do outro.

Repartição Euclidiana

O número maior entre ie jé dividido pelo menor tantas vezes quanto possível. Em seguida, o restante é adicionado. Esse processo é repetido com o restante e o número anterior, até que o restante se torne 0.

Por exemplo, se a entrada foi 1599 650:

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

O número final,, 13é o maior divisor comum dos dois números inteiros de entrada. Pode ser visualizado assim:

Saída

Sua saída deve ser o detalhamento no formulário acima, seguido por uma nova linha e o GCD. Pode ser produzido através de qualquer meio.

Exemplos

Entradas

18 27
50 20
447 501
9894 2628

Saídas

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

Nota: As saídas não precisam ser espaçadas, pois estão acima. O espaçamento é apenas para maior clareza. Parênteses são obrigatórios.

Bônus

Se sua saída estiver espaçada como acima, você poderá adicionar um bônus de -10% à sua pontuação.

Pitão, 33 bytes

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

Experimente on-line: demonstração ou Test Suite

Explicação:

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

Experimente online no intérprete CJam .

Como funciona

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`

Uma função recursiva que retorna uma seqüência de linhas múltiplas. A função cria a primeira linha e a anexa ao resultado recursivo com o próximo par de números no algoritmo euclidiano. Quando o segundo número é zero, tomamos a sequência do outro número como o caso base, fazendo com que seja impresso em sua própria linha no final.

A formatação é feita através da substituição de cadeias, usando a divisão inteira para obter o multiplicando.

Um soluço está precisando começar com o número maior sendo modificado, o número menor. Convenientemente, se os números estão na ordem errada, o primeiro passo do algoritmo euclidiano os vira. Para impedir que essa etapa seja exibida, adicione a linha atual apenas se o primeiro número for pelo menos o segundo (é necessária igualdade para, por exemplo,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

A classificação da entrada por tamanho requer muitos bytes: /
Tudo se resume a isso:

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

Saída

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

Apenas por diversão, também fiz uma versão com espaçamento adequado, obtendo uma pontuação de 233 * 0,9 == 209,7 bytes.

Atualização Consegui reduzi-lo de 285 bytes e agora ele funciona para números arbitrariamente longos se chamar gawk4 com a -Mopção

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

Mas ainda tenho a sensação de que encontrei algum bloqueio mental em algum lugar ...

Saída (gawk4 chamado com awk -M -f code.awk)

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

Algumas novas linhas e guias adicionadas

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

Eu posso salvar os comprimentos dos valores iniciais para x, ye x% y no início, porque eles só podem diminuir a cada etapa. Mas para o fator eu tenho que determinar o comprimento máximo antes de imprimir qualquer coisa, porque ele pode variar. Eu uso $icomo uma matriz aqui, porque ele salva dois caracteres em comparação ao uso de um [i] toda vez.

C ++, compilador GCC, 171 bytes (-10%, portanto, 154 bytes)

ok então minha primeira tentativa ..

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

dicas para codificar golfe apreciado.

PS É necessário contar bytes de arquivos de cabeçalho padrão e int main enquanto estiver usando c ++? Excluindo, reduz 50 bytes

T-SQL (2012+), 268 bytes

Implementado como uma função de tabela embutida que executa uma CTE recursiva. Pode valer a pena tentar colocar a formatação para o bônus de 10%, mas isso terá que esperar.

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

Explicação e uso:

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

Algoritmo recursivo, graças à dica da Maçaneta da porta.

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

Isso realmente não deu certo. O whileloop ocupa muitos caracteres, especialmente com o end. Não vejo uma maneira de evitá-lo. A recursão exigiria uma função nomeada em vez de uma lambda, que também consumiria muitos caracteres.

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

Chame assim:

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

Um bloco de código recursivo, armazenado em uma variável. Invoque-o com & $e num1 num2, por exemplo:

$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

De uma forma mais legível, ele faz o seguinte (por exemplo, para um código mais claro, coloquei os nomes completos dos comandos, mais espaços na sequência e expliquei os comandos de saída do pipeline):

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

Um aborrecimento do ponto de vista do codegolf; O PoSh não possui divisão inteira, 10/3 retorna um Duplo, mas converte o resultado em um inteiro e nem sempre arredonda para baixo. arredonda N.5 para o número par mais próximo - para cima ou para baixo. Então [int](99/2) == 50.

Isso deixa duas opções embaraçosas:

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

# or, worse

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

É por isso que eu tenho que gravar alguns personagens fazendo:

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

Além disso, é o número de

Eu também tenho uma versão iterativa que, bastante bem, também possui 84 ​​caracteres:

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

Codeblock completamente anônimo, então execute-o com

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

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

Experimente online!

-4 bytes substituídos list(,$n,$m)=$argvpelas [,$n,$m]=$argvnecessidades PHP> = 7.1

Japonês , 43 42 41 bytes

Minhas novas "habilidades" japonesas parecem estar piorando, não melhores!

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

Experimente online

JavaScript (ES6), 74 50 62 61 55 bytes

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

• 12 bytes sacrificados, permitindo que os números inteiros sejam transmitidos em qualquer ordem, em vez da maior primeiro.

Tente

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>

Explicaçã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.

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

teste e resultados

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

Não faz o algoritmo euclidiano regular. Em vez disso, ele usa o módulo e calcula o segundo número para multiplicar quando impresso. Você também pode tornar isso mais curto, transformando-o em uma expressão lambda, mas não sei como.

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