도전

종이 접기 (접는 종이)는 창조적 인 예술 형태입니다. 내가 아는 한, 종이 접기의 주인은 사각형 종이를 선호합니다. 처음부터 시작하겠습니다-직사각형 용지를 정사각형 용지로 변환하십시오.

따라서 종이는 사각형으로 나뉩니다. 현재 모양과 짧은 가장자리를 하나씩 공유하는 가장 큰 사각형을 단계별로 제거합니다 (아래 그림 참조). 한 단계 후 남은 부분이보다 작거나 같으면 0.001 * (area of the original paper)용지를 더 이상 나눌 수 없습니다. 마지막에 아무것도 남아 있지 않을 수 있습니다.

당신의 작업은 프로세스 동안 얼마나 많은 제곱이 만들어 지는지를 계산하는 것입니다. 마지막 단계에서 용지를 나눌 수없는 사각형은 출력으로 계산됩니다.

예 ( 1.350폭 / 높이 의 용지 ), 출력은 10입니다.

입력과 출력

입력 : 직사각형 용지 폭 / 높이 비율에서 소수 (또는 도트없는 정수) 1.002에 1.999최소한의 단계와 0.001. 비율을 설명하는 다른 적절한 형식을 사용할 수도 있습니다. 답에 언급하십시오.

출력 : 제곱 수, 하나의 정수.

예제 I / O

매핑 형식은 페이지를 깔끔하게 유지하는 데 사용되는 반면, 코드는 목록 입력을 지원하거나 매핑 기능 일 필요가 없습니다.

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

모든 답변 목록

@LuisMendo 덕분에 답변 그래프가 있습니다.

비고

• 이것은 코드 골프이므로 가장 짧은 코드가 승리합니다.
• 표준 허점에주의
• 입력 및 출력 처리 방법을 결정하는 것은 자유이지만 표준 제한을 따라야합니다.

그건 그렇고 …

• 당신이 도전에 대해 분명하지 않은 것이 있으면 의견
• 골프 언어를 사용하는 경우 귀하의 답변에 설명이 포함되어 있다고 제안합니다.
• @GregMartin 덕분에 도전에 대한 좋은 수학적 설명을 위해 그의 대답을 읽으십시오.

예제 코드

다음은 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;
}

예제 코드와 관련된 모든 계산에는 6 자리의 정확도가 필요합니다 float.

답변

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

`        % 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)

(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

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

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

Tr@*ContinuedFraction

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

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

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

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

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