Desafio

Origami (papel dobrável) é uma forma criativa de arte. Tanto quanto eu sei, o mestre de Origami prefere papel quadrado. Vamos começar do começo - converta um papel retangular em um quadrado.

Então o papel é dividido em quadrados. Removemos o maior quadrado que compartilha uma aresta mais curta com a forma atual, passo a passo (veja a figura abaixo). E se a parte restante após uma etapa for menor ou igual a 0.001 * (area of the original paper), o papel não poderá mais ser dividido. É possível que nada permaneça finalmente.

Sua tarefa é calcular quantos quadrados são feitos durante o processo. O quadrado da última etapa que impossibilita a divisão do papel é contado na saída.

Exemplo (um papel de 1.350largura / altura), a saída é 10:

Entrada e saída

Entrada: proporção largura / altura do papel retangular, um decimal (ou um número inteiro sem o ponto) de 1.002para 1.999com uma etapa mínima de 0.001. Você também pode usar qualquer outro formato razoável que descreva a proporção. Apenas mencione isso na sua resposta.

Saída: contagem quadrada, um número inteiro.

Exemplo de E / S

Um formato de mapeamento é usado para manter a página organizada, enquanto seu código não precisa suportar uma entrada de lista nem ser uma função de mapeamento.

1.002 => 251
1.003 => 223
1.004 => 189
1.005 => 161
1.006 => 140
1.007 => 124
1.008 => 111
1.009 => 100

Lista de todas as respostas

Graças a @LuisMendo, aqui está o gráfico de respostas.

Observações

• Este é um código de golfe, então o código mais curto ganha
• Preste atenção às brechas padrão
• É sua liberdade decidir como lidar com entradas e saídas, mas elas devem seguir as restrições padrão.

A propósito...

• Comente se você tem alguma dúvida sobre o desafio
• Pessoalmente, sugiro que sua resposta contenha uma explicação se você estiver usando um idioma de golfe
• Graças a @GregMartin, leia sua resposta para obter uma boa explicação matemática para o desafio.

Código de exemplo

Aqui está uma versão simplificada do código C ++:

#include <iostream>
#include <utility>

int f (double m)
{
    double n = 1, k = 0.001;
    int cnt = 0;
    k *= m;                       // the target minimum size
    while(m*n >= k)
    {
        m -= n;                   // extract a square
        if(n > m)
            std::swap(n, m);      // keep m > n
        ++ cnt;
    }
    return cnt;
}

int main()
{
    double p;
    std::cin >> p;
    std::cout << f(p);
    return 0;
}

Todos os cálculos relacionados no código de exemplo precisam de uma precisão de 6 dígitos decimais, abrangidos float.

MATL , 19 bytes

`SZ}y-htG/p1e-3>}x@

A entrada é uma matriz com os dois números que definem a proporção original, como [1, 1.009]. (Não é necessário que os números sejam classificados ou que um deles seja 1.)

Experimente online!

Explicação

`        % Do...while loop
  S      %   Sort array. Takes 1×2 array as input (implicit) the first time
  Z}     %   Split array into its 2 elements: first the minimum m, then the maximum M
  y      %   Duplicate m onto the top of the stack. The stack now contains m, M, m
  -      %   Subtract. The stack now contains m, M-m
  h      %   Concatenate into [m, M-m]. This is the remaining piece of paper
  t      %   Duplicate
  G/     %   Divide by input, element-wise
  p      %   Product of array. Gives ratio of current piece's area to initial area
  1e-3>  %   True if this ratio exceeds 1e-3. In that case the loop continues
}        % Finally (execute after last iteration, but still within the loop)
  x      %   Delete last piece of paper
  @      %   Push current loop counter. This is the result
         % End (implicit)
         % Display (implicit)

Haskell , 71 70 65 63 62 61 58 56 bytes

Obrigado a @xnor por algumas melhorias engenhosas!

(n#m)e|e>n*m*1e3=0|n<m=m#n$e|d<-n-m=(d#m)e+1
n!m=n#m$n*m

Experimente online!

JavaScript (ES6), 59 58 bytes

f=(m,n=!(k=m/1e3,c=0))=>m*n<k?c:(c++,m-=n)<n?f(n,m):f(m,n)

Teste

f=(m,n=!(k=m/1e3,c=0))=>m*n<k?c:(c++,m-=n)<n?f(n,m):f(m,n)

console.log(f(1.002))
console.log(f(1.003))
console.log(f(1.004))
console.log(f(1.005))
console.log(f(1.006))
console.log(f(1.007))
console.log(f(1.008))
console.log(f(1.009))

Mathematica, não concorrente (21 bytes)

Esta resposta não é competitiva porque não responde à pergunta real! Mas ele responde a uma variante da pergunta e fornece uma desculpa para destacar algumas matemáticas interessantes.

Tr@*ContinuedFraction

Função simbólica, tendo como entrada um número racional positivo (cujo numerador e denominador representam as dimensões do artigo original) e retornando um número inteiro positivo. Por exemplo, Tr@*ContinuedFraction[1350/1000]retorna 10. ( ContinuedFractionatua de maneira diferente nos números de ponto flutuante devido a problemas de precisão, e é por isso que um número racional é necessário como entrada nesse contexto.)

Uma interpretação interessante do procedimento geométrico descrito no problema (cortar quadrados um retângulo repetidamente) é que é uma implementação do algoritmo euclidiano para encontrar os maiores divisores comuns! Considere o exemplo da pergunta em si, com relação1.35, que pode ser modelado com um pedaço de papel com dimensões (1350,1000). Toda vez que um quadrado é cortado, o número menor é subtraído do número maior; portanto, os retângulos resultantes neste exemplo têm dimensões (350.1000), depois (350.650), depois (350.300), depois (50.300), depois (50.250) e (50.200) e (50.150) e (50.100) e (50.100) 50), e também (50,0) uma vez que tiramos o último quadrado de si mesmo. É exatamente assim que o algoritmo euclidiano opera (módulo a diferença entre divisão e subtração repetida) e, de fato, vemos que 50 é realmente o MDC de 1350 e 1000.

Tipicamente, no algoritmo euclidiano, é possível acompanhar essas dimensões intermediárias e descartar o número de subtrações; no entanto, é possível registrar alternadamente quantas vezes subtraímos um número do outro antes que a diferença se torne muito pequena e precisamos mudar o que estamos subtraindo. Esse método de gravação é precisamente a fração continuada de um número racional. (Frações contínuas de números irracionais, que nunca terminam, também são super legais, mas não relevantes aqui.) Por exemplo, no exemplo 1350/1000, subtraímos 1000 1vezes, depois 350 2vezes, depois 300 1, depois 50 6vezes; portanto, a fração continuada de 1350/1000 é {1,2,1,6}. Matematicamente, reescrevemos 1350/1000 como 1+ 1 / ( 2+ 1 / ( 1+ 1 /6)), que você pode verificar.

Portanto, para esse problema, se você não parar quando os quadrados ficarem menores que um determinado limiar, mas simplesmente contar todos os quadrados finitos antes que ele pare, o número total de quadrados será igual ao número total de subtrações, ou seja a soma de todos os números inteiros na fração continuada - e é exatamente isso que a composição das funções Tr@*ContinuedFractioncalcula! (No exemplo 1.35, ele obtém a resposta que o OP deseja, porque o quadrado final é grande o suficiente para que todos os quadrados fossem contados. Mas Tr@*ContinuedFraction[1001/1000], por exemplo, cede 1001, uma vez que conta o único quadrado enorme e todos os 1000 dos pequenos quadrados 1x1000 .)

Mathematica, 64 53 bytes

({t=1,#}//.{a_,b_}/;1000a*b>#:>Sort@{++t;a,b-a};t-1)&

Uma solução imperativa (estilo C) tem exatamente o mesmo comprimento:

(For[t=a=1;b=#,1000a*b>#,If[a>b,a-=b,b-=a];++t];t-1)&

C (GCC / Clang), 61 59 bytes

c,k;f(m,n){for(k=m*n;m*n/k;m>n?(m-=n):(n-=m))++c;return c;}

A entrada é dois números inteiros (largura e altura) sem ponto, como f(1999,1000).

Espero que alguém possa salvar um byte pressionando C no clube de 58 bytes. ;)

C, 59 bytes

s,a,n=1e3;C(m){for(a=m;m*n>a;s++)m>n?m-=n:(n-=m);return s;}

Experimente online

A entrada é um número inteiro, que é a relação largura / altura em milésimos (por exemplo, 1002 para 1,002: 1).

Versão ungolfed

int C(int m)
{
    int n = 1000;
    int a = m;
    int s = 0;

    while (m * n > a)
    {
        if (m > n)
            m -= n;
        else
            n -= m;

        s++;
    }

    return s;
}