반응형
코드 골프 : Collatz 추측
http://xkcd.com/710/ 에서 영감을 얻은 여기에 대한 코드 골프가 있습니다.
도전
0보다 큰 양의 정수가 주어지면 해당 숫자에 대한 우박 시퀀스를 인쇄합니다.
우박 시퀀스
자세한 내용은 Wikipedia 를 참조하십시오 .
- 숫자가 짝수이면 2로 나눕니다.
- 숫자가 홀수이면 세 배로 만들고 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/>+
LOLCODE : 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;
기원전 41 자
나는 이런 종류의 문제가 bc발명 된 것이라고 생각합니다.
for(n=read();n>1;){if(n%2)n=n*6+2;n/=2;n}
테스트:
bc1 -q collatz.bc
21
64
32
16
8
4
2
1
적절한 코드 :
for(n=read();n>1;){if(n%2)n=n*3+1else n/=2;print n,"\n"}
bc최대 자릿수 로 숫자를 처리합니다.INT_MAX
편집 : 위키 백과 문서가 이 추측까지의 모든 값에 대해 확인 된 언급 20X2 58 (. 함께 aprox 5.76e18 ). 이 프로그램:
c=0;for(n=2^20000+1;n>1;){if(n%2)n=n*6+2;n/=2;c+=1};n;c
테스트 2 20,000 +1 (함께 aprox. 3.98e6,020 )에서 68 초 144,404 사이클.
Perl : 31 자
perl -nE 'say$_=$_%2?$_*3+1:$_/2while$_>1'
# 123456789 123456789 123456789 1234567
2 개의 불필요한 공백을 제거하도록 편집되었습니다.
불필요한 공간 1 개를 제거하도록 수정되었습니다.
MS Excel, 35 자
=IF(A1/2=ROUND(A1/2,0),A1/2,A1*3+1)
Wikipedia 에서 바로 가져 왔습니다 .
In cell A1, place the starting number.
In cell A2 enter this formula =IF(A1/2=ROUND(A1/2,0),A1/2,A1*3+1)
Drag and copy the formula down until 4, 2, 1
시작 번호 1000에 대한 결과를 얻으려면 수식을 111 번 복사 / 붙여 넣기 만했습니다.;)
C : 64 자
main(x){for(scanf("%d",&x);x>=printf("%d,",x);x=x&1?3*x+1:x/2);}
큰 정수 지원 : 431 (필수) 문자
#include <stdlib.h>
#define B (w>=m?d=realloc(d,m=m+m):0)
#define S(a,b)t=a,a=b,b=t
main(m,w,i,t){char*d=malloc(m=9);for(w=0;(i=getchar()+2)/10==5;)
B,d[w++]=i%10;for(i=0;i<w/2;i++)S(d[i],d[w-i-1]);for(;;w++){
while(w&&!d[w-1])w--;for(i=w+1;i--;)putchar(i?d[i-1]+48:10);if(
w==1&&*d==1)break;if(*d&1){for(i=w;i--;)d[i]*=3;*d+=1;}else{
for(i=w;i-->1;)d[i-1]+=d[i]%2*10,d[i]/=2;*d/=2;}B,d[w]=0;for(i=0
;i<w;i++)d[i+1]+=d[i]/10,d[i]%=10;}}
참고 : #include <stdlib.h>최소한 malloc / realloc 프로토 타이핑없이 제거 하지 마십시오 . 64 비트 플랫폼에서는 안전하지 않습니다 (64 비트 void *는 32 비트 int로 변환 됨).
이것은 아직 격렬하게 테스트되지 않았습니다. 단축을 사용할 수도 있습니다.
이전 버전:
main(x){for(scanf("%d",&x);printf("%d,",x),x-1;x=x&1?3*x+1:x/2);} // 66
(아무도 출력 형식을 따르지 않기 때문에 12 자 제거 ... : |)
다른 어셈블러 버전. 이것은 32 비트 숫자로 제한되지 않으며 MS-DOS에서 사용하는 ".com"형식은 80 자리 숫자로 제한되지만 최대 10 65534의 숫자를 처리 할 수 있습니다 . A86 어셈블러 용으로 작성되었으며 실행하려면 Win-XP DOS 상자가 필요합니다. 180 바이트로 조립 :
mov ax,cs
mov si,82h
add ah,10h
mov es,ax
mov bh,0
mov bl,byte ptr [80h]
cmp bl,1
jbe ret
dec bl
mov cx,bx
dec bl
xor di,di
p1:lodsb
sub al,'0'
cmp al,10
jae ret
stosb
loop p1
xor bp,bp
push es
pop ds
p2:cmp byte ptr ds:[bp],0
jne p3
inc bp
jmp p2
ret
p3:lea si,[bp-1]
cld
p4:inc si
mov dl,[si]
add dl,'0'
mov ah,2
int 21h
cmp si,bx
jne p4
cmp bx,bp
jne p5
cmp byte ptr [bx],1
je ret
p5:mov dl,'-'
mov ah,2
int 21h
mov dl,'>'
int 21h
test byte ptr [bx],1
jz p10
;odd
mov si,bx
mov di,si
mov dx,3
dec bp
std
p6:lodsb
mul dl
add al,dh
aam
mov dh,ah
stosb
cmp si,bp
jnz p6
or dh,dh
jz p7
mov al,dh
stosb
dec bp
p7:mov si,bx
mov di,si
p8:lodsb
inc al
xor ah,ah
aaa
stosb
or ah,ah
jz p9
cmp si,bp
jne p8
mov al,1
stosb
jmp p2
p9:inc bp
jmp p2
p10:mov si,bp
mov di,bp
xor ax,ax
p11:lodsb
test ah,1
jz p12
add al,10
p12:mov ah,al
shr al,1
cmp di,bx
stosb
jne p11
jmp p2
dc-24 자
25
28
dc 이 시퀀스에 적합한 도구입니다.
?[d5*2+d2%*+2/pd1<L]dsLx
dc -f collatz.dc 21 64 32 16 8 4 2 1
또한 Golfscript 항목 의 공식을 사용하는 24 자 :
?[3*1+d2%5*1+/pd1<L]dsLx
사양을 충족하는 57 자 :
[Number: ]n?[Results: ]ndn[d5*2+d2%*+2/[ -> ]ndnd1<L]dsLx
dc -f collatz-spec.dc 번호 : 3 결과 : 3-> 10-> 5-> 16-> 8-> 4-> 2-> 1
계획 : 72
(define(c n)(if(= n 1)`(1)(cons n(if(odd? n)(c(+(* n 3)1))(c(/ n 2))))))
이것은 재귀를 사용하지만 호출은 꼬리 재귀이므로 반복에 최적화 될 것이라고 생각합니다. 일부 빠른 테스트에서 어쨌든 스택이 오버플로되는 숫자를 찾을 수 없었습니다. 예를 들면 :
(c 9876543219999999999000011234567898888777766665555444433332222 7777777777777777777777777777777798797657657651234143375987342987 5398709812374982529830983743297432985230985739287023987532098579 058095873098753098370938753987)
... 잘 작동합니다. [그게 모두 하나의 숫자입니다. 화면에 맞추기 위해 방금 부순 것입니다.]
Mathematica, 45 세 50 문자
c=NestWhileList[If[OddQ@#,3#+1,#/2]&,#,#>1&]&
루비, 50 자, 스택 오버플로 없음
기본적으로 makapuf의 Python 솔루션을 직접 추출 합니다 .
def c(n)while n>1;n=n.odd?? n*3+1: n/2;p n end end
Ruby, 45 자, 오버플로
기본적으로 질문에 제공된 코드를 직접 추출합니다.
def c(n)p n;n.odd?? c(3*n+1):c(n/2)if n>1 end
import java.math.BigInteger;
public class SortaJava {
static final BigInteger THREE = new BigInteger("3");
static final BigInteger TWO = new BigInteger("2");
interface BiFunc<R, A, B> {
R call(A a, B b);
}
interface Cons<A, B> {
<R> R apply(BiFunc<R, A, B> func);
}
static class Collatz implements Cons<BigInteger, Collatz> {
BigInteger value;
public Collatz(BigInteger value) { this.value = value; }
public <R> R apply(BiFunc<R, BigInteger, Collatz> func) {
if(BigInteger.ONE.equals(value))
return func.call(value, null);
if(value.testBit(0))
return func.call(value, new Collatz((value.multiply(THREE)).add(BigInteger.ONE)));
return func.call(value, new Collatz(value.divide(TWO)));
}
}
static class PrintAReturnB<A, B> implements BiFunc<B, A, B> {
boolean first = true;
public B call(A a, B b) {
if(first)
first = false;
else
System.out.print(" -> ");
System.out.print(a);
return b;
}
}
public static void main(String[] args) {
BiFunc<Collatz, BigInteger, Collatz> printer = new PrintAReturnB<BigInteger, Collatz>();
Collatz collatz = new Collatz(new BigInteger(args[0]));
while(collatz != null)
collatz = collatz.apply(printer);
}
}
파이썬 45 자
makapuf의 대답에서 문자를 깎았습니다.
n=input()
while~-n:n=(n/2,n*3+1)[n%2];print n
TI-BASIC
가장 짧지는 않지만 새로운 접근 방식입니다. 큰 시퀀스로 상당히 느려질 수 있지만 오버플로해서는 안됩니다.
PROGRAM:COLLATZ
:ClrHome
:Input X
:Lbl 1
:While X≠1
:If X/2=int(X/2)
:Then
:Disp X/2→X
:Else
:Disp X*3+1→X
:End
:Goto 1
:End
하스켈 : 50
c 1=[1];c n=n:(c$if odd n then 3*n+1 else n`div`2)
짧지는 않지만 우아한 클로저 솔루션
(defn collatz [n]
(print n "")
(if (> n 1)
(recur
(if (odd? n)
(inc (* 3 n))
(/ n 2)))))
C # : 216 자
using C=System.Console;class P{static void Main(){var p="start:";System.Action<object> o=C.Write;o(p);ulong i;while(ulong.TryParse(C.ReadLine(),out i)){o(i);while(i > 1){i=i%2==0?i/2:i*3+1;o(" -> "+i);}o("\n"+p);}}}
긴 형식 :
using C = System.Console;
class P
{
static void Main()
{
var p = "start:";
System.Action<object> o = C.Write;
o(p);
ulong i;
while (ulong.TryParse(C.ReadLine(), out i))
{
o(i);
while (i > 1)
{
i = i % 2 == 0 ? i / 2 : i * 3 + 1;
o(" -> " + i);
}
o("\n" + p);
}
}
}
새 버전, 입력 유효성 검사없이 명령 줄을 통해 제공된 입력으로 하나의 숫자를 허용합니다.
173154
자
using System;class P{static void Main(string[]a){Action<object>o=Console.Write;var i=ulong.Parse(a[0]);o(i);while(i>1){i=i%2==0?i/2:i*3+1;o(" -> "+i);}}}
긴 형식 :
using System;
class P
{
static void Main(string[]a)
{
Action<object>o=Console.Write;
var i=ulong.Parse(a[0]);
o(i);
while(i>1)
{
i=i%2==0?i/2:i*3+1;
o(" -> "+i);
}
}
}
잠시 대신 for 루프를 사용하기 위해이 답변 에서 아이디어를 떼어 냄으로써 몇 문자를 면도 할 수 있습니다. 150 자.
using System;class P{static void Main(string[]a){Action<object>o=Console.Write;for(var i=ulong.Parse(a[0]);i>1;i=i%2==0?i/2:i*3+1)o(i+" -> ");o(1);}}
루비, 43 자
스택 오버플로 민감도와 함께 bignum 지원 :
def c(n)p n;n%2>0?c(3*n+1):c(n/2)if n>1 end
... 50 자, bignum 지원, 스택 오버플로 없음 :
def d(n)while n>1 do p n;n=n%2>0?3*n+1:n/2 end end
요르단에 대한 명성. 풋을 대체하는 'p'에 대해 몰랐습니다.
nroff 1
함께 실행 nroff -U hail.g
.warn
.pl 1
.pso (printf "Enter a number: " 1>&2); read x; echo .nr x $x
.while \nx>1 \{\
. ie \nx%2 .nr x \nx*3+1
. el .nr x \nx/2
\nx
.\}
1. groff 버전
Scala + Scalaz
import scalaz._
import Scalaz._
val collatz =
(_:Int).iterate[Stream](a=>Seq(a/2,3*a+1)(a%2)).takeWhile(1<) // This line: 61 chars
그리고 행동 :
scala> collatz(7).toList
res15: List[Int] = List(7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2)
스칼라 2.8
val collatz =
Stream.iterate(_:Int)(a=>Seq(a/2,3*a+1)(a%2)).takeWhile(1<) :+ 1
여기에는 후행 1도 포함됩니다.
scala> collatz(7)
res12: scala.collection.immutable.Stream[Int] = Stream(7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1)
다음과 같은 암시 적
implicit def intToEven(i:Int) = new {
def ~(even: Int=>Int, odd: Int=>Int) = {
if (i%2==0) { even(i) } else { odd(i) }
}
}
이것은 단축 될 수 있습니다
val collatz = Stream.iterate(_:Int)(_~(_/2,3*_+1)).takeWhile(1<) :+ 1
편집-58 자 (입력 및 출력 포함, 초기 번호 제외)
var n=readInt;while(n>1){n=Seq(n/2,n*3+1)(n%2);println(n)}
개행이 필요하지 않으면 2로 줄일 수 있습니다 ...
F #, 90 자
let c=Seq.unfold(function|n when n<=1->None|n when n%2=0->Some(n,n/2)|n->Some(n,(3*n)+1))
> c 21;;
val it : seq<int> = seq [21; 64; 32; 16; ...]
또는 F # 대화 형을 사용하여 결과를 표시하지 않는 경우 102 자 :
let c=Seq.unfold(function|n when n<=1->None|n when n%2=0->Some(n,n/2)|n->Some(n,(3*n)+1))>>printf"%A"
Common Lisp, 141 자 :
(defun c ()
(format t"Number: ")
(loop for n = (read) then (if(oddp n)(+ 1 n n n)(/ n 2))
until (= n 1)
do (format t"~d -> "n))
(format t"1~%"))
테스트 실행 :
Number: 171
171 -> 514 -> 257 -> 772 -> 386 -> 193 -> 580 -> 290 -> 145 -> 436 ->
218 -> 109 -> 328 -> 164 -> 82 -> 41 -> 124 -> 62 -> 31 -> 94 -> 47 ->
142 -> 71 -> 214 -> 107 -> 322 -> 161 -> 484 -> 242 -> 121 -> 364 ->
182 -> 91 -> 274 -> 137 -> 412 -> 206 -> 103 -> 310 -> 155 -> 466 ->
233 -> 700 -> 350 -> 175 -> 526 -> 263 -> 790 -> 395 -> 1186 -> 593 ->
1780 -> 890 -> 445 -> 1336 -> 668 -> 334 -> 167 -> 502 -> 251 -> 754 ->
377 -> 1132 -> 566 -> 283 -> 850 -> 425 -> 1276 -> 638 -> 319 ->
958 -> 479 -> 1438 -> 719 -> 2158 -> 1079 -> 3238 -> 1619 -> 4858 ->
2429 -> 7288 -> 3644 -> 1822 -> 911 -> 2734 -> 1367 -> 4102 -> 2051 ->
6154 -> 3077 -> 9232 -> 4616 -> 2308 -> 1154 -> 577 -> 1732 -> 866 ->
433 -> 1300 -> 650 -> 325 -> 976 -> 488 -> 244 -> 122 -> 61 -> 184 ->
92 -> 46 -> 23 -> 70 -> 35 -> 106 -> 53 -> 160 -> 80 -> 40 -> 20 ->
10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
Jerry Coffin 프로그램은 정수 오버 플로우를 가지고 있습니다.
#include <iostream>
int main(unsigned long long i)
{
int j = 0;
for( std::cin>>i; i>1; i = i&1? i*3+1:i/2, ++j)
std::cout<<i<<" -> ";
std::cout<<"\n"<<j << " iterations\n";
}
테스트
총 정지 시간이 가장 긴 1 억 미만의 숫자는 63,728,127이며 949 보입니다.
총 정지 시간이 가장 긴 10 억 개 미만의 숫자는 670,617,279 개로 986 걸음이 있습니다.
ruby, 43, I / O 요구 사항 충족 가능
함께 실행 ruby -n hail
n=$_.to_i
(n=n%2>0?n*3+1: n/2
p n)while n>1
C # : BigInteger 지원이 포함 된 659 자
using System.Linq;using C=System.Console;class Program{static void Main(){var v=C.ReadLine();C.Write(v);while(v!="1"){C.Write("->");if(v[v.Length-1]%2==0){v=v.Aggregate(new{s="",o=0},(r,c)=>new{s=r.s+(char)((c-48)/2+r.o+48),o=(c%2)*5}).s.TrimStart('0');}else{var q=v.Reverse().Aggregate(new{s="",o=0},(r, c)=>new{s=(char)((c-48)*3+r.o+(c*3+r.o>153?c*3+r.o>163?28:38:48))+r.s,o=c*3+r.o>153?c*3+r.o>163?2:1:0});var t=(q.o+q.s).TrimStart('0').Reverse();var x=t.First();q=t.Skip(1).Aggregate(new{s=x>56?(x-57).ToString():(x-47).ToString(),o=x>56?1:0},(r,c)=>new{s=(char)(c-48+r.o+(c+r.o>57?38:48))+r.s,o=c+r.o>57?1:0});v=(q.o+q.s).TrimStart('0');}C.Write(v);}}}
미 골프
using System.Linq;
using C = System.Console;
class Program
{
static void Main()
{
var v = C.ReadLine();
C.Write(v);
while (v != "1")
{
C.Write("->");
if (v[v.Length - 1] % 2 == 0)
{
v = v
.Aggregate(
new { s = "", o = 0 },
(r, c) => new { s = r.s + (char)((c - 48) / 2 + r.o + 48), o = (c % 2) * 5 })
.s.TrimStart('0');
}
else
{
var q = v
.Reverse()
.Aggregate(
new { s = "", o = 0 },
(r, c) => new { s = (char)((c - 48) * 3 + r.o + (c * 3 + r.o > 153 ? c * 3 + r.o > 163 ? 28 : 38 : 48)) + r.s, o = c * 3 + r.o > 153 ? c * 3 + r.o > 163 ? 2 : 1 : 0 });
var t = (q.o + q.s)
.TrimStart('0')
.Reverse();
var x = t.First();
q = t
.Skip(1)
.Aggregate(
new { s = x > 56 ? (x - 57).ToString() : (x - 47).ToString(), o = x > 56 ? 1 : 0 },
(r, c) => new { s = (char)(c - 48 + r.o + (c + r.o > 57 ? 38 : 48)) + r.s, o = c + r.o > 57 ? 1 : 0 });
v = (q.o + q.s)
.TrimStart('0');
}
C.Write(v);
}
}
}
참고 URL : https://stackoverflow.com/questions/2388254/code-golf-collatz-conjecture
반응형
'IT story' 카테고리의 다른 글
| Android, 캔버스 : surfaceView에있는 캔버스 (= 비트 맵)를 지우는 (내용을 삭제) 어떻게합니까? (0) | 2020.09.12 |
|---|---|
| UIButton의 이미지를 AspectFit으로 조정 하시겠습니까? (0) | 2020.09.12 |
| 읽을 수있는 / 계층 적 형식으로 배열 표시 (0) | 2020.09.12 |
| 스레드 또는 타이머에서 HttpServerUtility.MapPath 메서드에 액세스하는 방법은 무엇입니까? (0) | 2020.09.11 |
| CMD 셸의 여유 공간 (0) | 2020.09.11 |