码高尔夫: Collatz猜想

Question

受http://xkcd.com/710/的启发，这里有一个代码高尔夫。

挑战

给定大于0的正整数，打印出该数字的冰雹序列。

Hailstone序列

有关更多细节，请参见维基百科。

• 如果这个数字是偶数，除以二。
• 如果这个数字是奇数，那就把它增加三倍，再加一个。

用所产生的数字重复这个过程，直到它达到1。(如果它在1之后继续，它将进入一个无限的1 -> 4 -> 2 -> 1...循环)

有时候，代码是最好的解释方法，下面是维基百科的一些

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

此外，代码高尔夫必须包括完整的用户输入和输出。

Answer 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

Answer 2

贝芬奇

&>:.:1-|
  >3*^ @
  |%2: <
 v>2/>+

Answer 3

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

UNDR 贾斯汀·J·梅扎的插曲.克希比耶！