http://xkcd.com/710/ 에서 영감을 얻은 여기에 대한 코드 골프가 있습니다.
도전
0보다 큰 양의 정수가 주어지면 해당 숫자에 대한 우박 시퀀스를 인쇄합니다.
우박 시퀀스
자세한 내용은 Wikipedia 를 참조하십시오 .
- 숫자가 짝수이면 2로 나눕니다.
- 숫자가 홀수이면 3 배로 만들고 1을 더합니다.
1에 도달 할 때까지 생성 된 숫자로 이것을 반복합니다. (1 이후에 계속되면 무한 루프로 이동합니다 1 -> 4 -> 2 -> 1...
)
때로는 코드가 설명하는 가장 좋은 방법이므로 여기에 Wikipedia의 일부가 있습니다.
function collatz(n)
show n
if n > 1
if n is odd
call collatz(3n + 1)
else
call collatz(n / 2)
이 코드는 작동하지만 추가 과제를 추가하고 있습니다. 프로그램은 스택 오버플로에 취약하지 않아야합니다 . 따라서 반복 또는 꼬리 재귀를 사용해야합니다.
또한 큰 숫자를 계산할 수 있고 언어가 아직 구현하지 않은 경우에 대한 보너스 포인트. (또는 고정 길이 정수를 사용하여 큰 숫자 지원을 다시 구현하는 경우)
테스트 케이스
Number: 21
Results: 21 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1
Number: 3
Results: 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
또한 코드 골프에는 전체 사용자 입력 및 출력이 포함되어야합니다.
답변
x86 어셈블리, 1337 자
;
; To assemble and link this program, just run:
;
; >> $ nasm -f elf collatz.asm && gcc -o collatz collatz.o
;
; You can then enjoy its output by passing a number to it on the command line:
;
; >> $ ./collatz 123
; >> 123 --> 370 --> 185 --> 556 --> 278 --> 139 --> 418 --> 209 --> 628 --> 314
; >> --> 157 --> 472 --> 236 --> 118 --> 59 --> 178 --> 89 --> 268 --> 134 --> 67
; >> --> 202 --> 101 --> 304 --> 152 --> 76 --> 38 --> 19 --> 58 --> 29 --> 88
; >> --> 44 --> 22 --> 11 --> 34 --> 17 --> 52 --> 26 --> 13 --> 40 --> 20 --> 10
; >> --> 5 --> 16 --> 8 --> 4 --> 2 --> 1
;
; There's even some error checking involved:
; >> $ ./collatz
; >> Usage: ./collatz NUMBER
;
section .text
global main
extern printf
extern atoi
main:
cmp dword [esp+0x04], 2
jne .usage
mov ebx, [esp+0x08]
push dword [ebx+0x04]
call atoi
add esp, 4
cmp eax, 0
je .usage
mov ebx, eax
push eax
push msg
.loop:
mov [esp+0x04], ebx
call printf
test ebx, 0x01
jz .even
.odd:
lea ebx, [1+ebx*2+ebx]
jmp .loop
.even:
shr ebx, 1
cmp ebx, 1
jne .loop
push ebx
push end
call printf
add esp, 16
xor eax, eax
ret
.usage:
mov ebx, [esp+0x08]
push dword [ebx+0x00]
push usage
call printf
add esp, 8
mov eax, 1
ret
msg db "%d --> ", 0
end db "%d", 10, 0
usage db "Usage: %s NUMBER", 10, 0
답변
Befunge
&>:.:1-|
>3*^ @
|%2: <
v>2/>+
답변
롤 코드 : 406 CHARAKTERZ
HAI
BTW COLLATZ SOUNDZ JUS LULZ
CAN HAS STDIO?
I HAS A NUMBAR
BTW, I WANTS UR NUMBAR
GIMMEH NUMBAR
VISIBLE NUMBAR
IM IN YR SEQUENZ
MOD OF NUMBAR AN 2
BOTH SAEM IT AN 0, O RLY?
YA RLY, NUMBAR R QUOSHUNT OF NUMBAR AN 2
NO WAI, NUMBAR R SUM OF PRODUKT OF NUMBAR AN 3 AN 1
OIC
VISIBLE NUMBAR
DIFFRINT 2 AN SMALLR OF 2 AN NUMBAR, O RLY?
YA RLY, GTFO
OIC
IM OUTTA YR SEQUENZ
KTHXBYE
TESTD UNDR 저스틴 J. 메자 ‘S INTERPRETR . KTHXBYE!
답변
Python- 95 64 51 46 자
분명히 스택 오버플로를 생성하지 않습니다.
n=input()
while n>1:n=(n/2,n*3+1)[n%2];print n
답변
Perl
나는 약간 반 경쟁적이기로 결정하고 Perl에서 이러한 문제를 일반적으로 코딩하는 방법을 보여줍니다.
끝에 46 자 (총) 자 코드 골프 항목도 있습니다.
이 처음 세 가지 예는 모두이 헤더로 시작합니다.
#! /usr/bin/env perl
use Modern::Perl;
# which is the same as these three lines:
# use 5.10.0;
# use strict;
# use warnings;
while( <> ){
chomp;
last unless $_;
Collatz( $_ );
}
-
단순 재귀 버전
use Sub::Call::Recur; sub Collatz{ my( $n ) = @_; $n += 0; # ensure that it is numeric die 'invalid value' unless $n > 0; die 'Integer values only' unless $n == int $n; say $n; given( $n ){ when( 1 ){} when( $_ % 2 != 0 ){ # odd recur( 3 * $n + 1 ); } default{ # even recur( $n / 2 ); } } }
-
단순 반복 버전
sub Collatz{ my( $n ) = @_; $n += 0; # ensure that it is numeric die 'invalid value' unless $n > 0; die 'Integer values only' unless $n == int $n; say $n; while( $n > 1 ){ if( $n % 2 ){ # odd $n = 3 * $n + 1; } else { #even $n = $n / 2; } say $n; } }
-
최적화 된 반복 버전
sub Collatz{ my( $n ) = @_; $n += 0; # ensure that it is numeric die 'invalid value' unless $n > 0; die 'Integer values only' unless $n == int $n; # state @next; $next[1] //= 0; # sets $next[1] to 0 if it is undefined # # fill out @next until we get to a value we've already worked on until( defined $next[$n] ){ say $n; # if( $n % 2 ){ # odd $next[$n] = 3 * $n + 1; } else { # even $next[$n] = $n / 2; } # $n = $next[$n]; } say $n; # finish running until we get to 1 say $n while $n = $next[$n]; }
이제 v5.10.0 이전 버전의 Perl로 마지막 예제를 수행하는 방법을 보여 드리겠습니다.
#! /usr/bin/env perl
use strict;
use warnings;
while( <> ){
chomp;
last unless $_;
Collatz( $_ );
}
{
my @next = (0,0); # essentially the same as a state variable
sub Collatz{
my( $n ) = @_;
$n += 0; # ensure that it is numeric
die 'invalid value' unless $n > 0;
# fill out @next until we get to a value we've already worked on
until( $n == 1 or defined $next[$n] ){
print $n, "\n";
if( $n % 2 ){ # odd
$next[$n] = 3 * $n + 1;
} else { # even
$next[$n] = $n / 2;
}
$n = $next[$n];
}
print $n, "\n";
# finish running until we get to 1
print $n, "\n" while $n = $next[$n];
}
}
기준
먼저 IO는 항상 느린 부분이 될 것입니다. 따라서 실제로 그대로 벤치마킹했다면 각각의 속도가 거의 같아야합니다.
그런 다음이를 테스트하기 위해 /dev/null
( $null
)에 대한 파일 핸들을 열고 say $n
대신 읽기 위해 every 를 편집했습니다 say {$null} $n
. 이것은 IO에 대한 의존성을 줄이기위한 것입니다.
#! /usr/bin/env perl
use Modern::Perl;
use autodie;
open our $null, '>', '/dev/null';
use Benchmark qw':all';
cmpthese( -10,
{
Recursive => sub{ Collatz_r( 31 ) },
Iterative => sub{ Collatz_i( 31 ) },
Optimized => sub{ Collatz_o( 31 ) },
});
sub Collatz_r{
...
say {$null} $n;
...
}
sub Collatz_i{
...
say {$null} $n;
...
}
sub Collatz_o{
...
say {$null} $n;
...
}
10 번 실행 한 후 다음은 대표적인 샘플 출력입니다.
재귀 반복 최적화 평가 재귀 1715 / s--27 % -46 % 반복 2336 / s 36 %--27 % 최적화 됨 3187 / s 86 % 36 %-
마지막으로 실제 코드 골프 항목 :
perl -nlE'say;say$_=$_%2?3*$_+1:$_/2while$_>1'
총 46 자
시작 값을 인쇄 할 필요가없는 경우 5자를 더 제거 할 수 있습니다.
perl -nE'say$_=$_%2?3*$_+1:$_/2while$_>1'
실제 코드 부분은 41 자 총
31 자이지만 -n
스위치 없이는 코드가 작동하지 않습니다 . 그래서 나는 전체 예를 내 계산에 포함시킵니다.
답변
Haskell, 62 자 63 76 83 , 86 , 97 , 137
c 1=[1]
c n=n:c(div(n`mod`2*(5*n+2)+n)2)
main=readLn>>=print.c
사용자 입력, 인쇄 출력은 상수 메모리와 스택을 사용하며 임의의 큰 정수로 작동합니다.
모든 ‘1’(!)의 80 자리 숫자가 입력 된이 코드 의 샘플 실행 은보기에 매우 재미 있습니다.
원본, 기능 전용 버전 :
Haskell 51 자
f n=n:[[],f([n`div`2,3*n+1]!!(n`mod`2))]!!(1`mod`n)
어쨌든 @ & ^ #에 조건부가 필요한 사람은 누구입니까?
(편집 : 나는 “영리”하고 수정을 사용했습니다. 그것 없이는 코드가 54 자로 떨어졌습니다. edit2 : 인수 분해하여 51로 떨어졌습니다 f()
)
답변
Golfscript : 20 자
~{(}{3*).1&5*)/}/1+`
#
# Usage: echo 21 | ruby golfscript.rb collatz.gs
이것은
stack<int> s;
s.push(21);
while (s.top() - 1) {
int x = s.top();
int numerator = x*3+1;
int denominator = (numerator&1) * 5 + 1;
s.push(numerator/denominator);
}
s.push(1);
return s;