도전
종이 접기 (접는 종이)는 창조적 인 예술 형태입니다. 내가 아는 한, 종이 접기의 주인은 사각형 종이를 선호합니다. 처음부터 시작하겠습니다-직사각형 용지를 정사각형 용지로 변환하십시오.
따라서 종이는 사각형으로 나뉩니다. 현재 모양과 짧은 가장자리를 하나씩 공유하는 가장 큰 사각형을 단계별로 제거합니다 (아래 그림 참조). 한 단계 후 남은 부분이보다 작거나 같으면 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.
답변
MATL , 19 바이트
`SZ}y-htG/p1e-3>}x@
입력은와 같이 원래 비율을 정의하는 두 숫자가있는 배열입니다 [1, 1.009]. (숫자를 정렬하거나 그 중 하나가 1 일 필요는 없습니다.)
설명
` % 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)
답변
하스켈 , 71 70 65 63 62 61 58 56 바이트
독창적 인 개선을 위해 @xnor에게 감사드립니다!
(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답변
자바 스크립트 (ES6), 59 58 바이트
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))답변
수학, 비경쟁 (21 바이트)
이 답변은 실제 질문에 답변하지 않기 때문에 경쟁이 아닙니다! 그러나 그것은 질문의 변형에 대한 답변을 제공하며 흥미로운 수학을 강조하는 변명을 제공합니다.
Tr@*ContinuedFraction
양수의 유리수를 입력으로 취하고 (분자 및 분모가 원래 용지의 크기를 나타냄) 양의 정수를 반환하는 기호 함수. 예를 Tr@*ContinuedFraction[1350/1000]들어을 반환합니다 10. ( ContinuedFraction정밀 문제로 인해 부동 소수점 숫자에 대해 다르게 작동하므로이 컨텍스트에서 입력으로 합리적인 숫자가 필요합니다.)
문제에 설명 된 기하학적 프로 시저에 대한 흥미로운 해석 (직사각형에서 사각형을 반복해서 잘라 냄)은 가장 큰 제수를 찾는 유클리드 알고리즘의 구현이라는 것입니다! 질문 자체의 예를 비율과 함께 고려하십시오.1.35치수 (1350,1000)의 종이를 사용하여 모델링 할 수 있습니다. 사각형이 잘릴 때마다 큰 숫자에서 작은 숫자를 뺍니다. 이 예에서 결과 사각형의 크기는 (350,1000), (350,650), (350,300), (50,300), (50,250), (50,200), (50,150), (50,100) 및 (50, 50) 그리고 (50,0) 일단 우리가 마지막 정사각형을 가져 가면. 이것이 정확히 유클리드 알고리즘이 작동하는 방식 (나눗셈과 반복 뺄셈의 차이를 모듈로 한 것)이며, 실제로 50은 실제로 1350과 1000의 GCD라는 것을 알 수 있습니다.
일반적으로 유클리드 알고리즘에서 이러한 중간 차원을 추적하고 빼기 횟수를 버립니다. 그러나 차이가 너무 작아지기 전에 한 숫자를 다른 숫자에서 빼는 횟수를 번갈아 기록 할 수 있으며 빼는 값을 바꿔야합니다. 그 기록 방법은 정확하게 합리적인 수의 연속 된 부분입니다. (종료되지 않는 비이성적 인 숫자의 계속 된 부분도 역시 매우 시원하지만 여기서는 관련이 없습니다.) 예를 들어, 1350/1000 예에서 우리는 1000 1시간, 350 2시간, 300 1시간, 50 6시간 을 뺍니다 . 따라서 1350/1000의 연속 비율은입니다 {1,2,1,6}. 수학적으로 1350/1000을 1+ 1 / ( 2+ 1 / ( 1+ 1 /6))로 확인할 수 있습니다.
따라서이 문제의 경우, 사각형이 특정 임계 값보다 작을 때 멈추지 않고 멈추기 전에 유한하게 많은 사각형을 모두 세면 총 제곱 수는 총 빼기 수와 같습니다. 연속 분수의 모든 정수의 합 – 정확히 함수의 구성이 Tr@*ContinuedFraction계산하는 것입니다! (예제 1.35의 경우, 최종 제곱이 모든 제곱을 세기에 충분하기 때문에 OP가 원하는 답을 얻지 만 Tr@*ContinuedFraction[1001/1000], 예를 들어, 1001하나의 거대한 제곱과 작은 1×1000 제곱의 1000 개를 모두 계산하기 때문에 yields 가됩니다. .)
답변
수학, 64 53 바이트
({t=1,#}//.{a_,b_}/;1000a*b>#:>Sort@{++t;a,b-a};t-1)&
명령형 (C 스타일) 솔루션은 정확히 같은 길이입니다.
(For[t=a=1;b=#,1000a*b>#,If[a>b,a-=b,b-=a];++t];t-1)&
답변
C (GCC / 클랑) 61 59 바이트
c,k;f(m,n){for(k=m*n;m*n/k;m>n?(m-=n):(n-=m))++c;return c;}
입력은 점이없는 두 개의 정수 (너비 및 높이)입니다 (예 🙂 f(1999,1000).
누군가가 C를 58 바이트 클럽에 밀어 넣는 1 바이트를 절약 할 수 있기를 바랍니다. 😉
답변
C, 59 바이트
s,a,n=1e3;C(m){for(a=m;m*n>a;s++)m>n?m-=n:(n-=m);return s;}입력은 1000 분의 1의 폭 / 높이 비율 인 정수입니다 (예 : 1.002 : 1의 경우 1002).
언 골프 버전
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;
}
