language-agnostic - Code Golf : Collatz Conjecture

Question

已锁定。这个问题及其答案是 locked因为这个问题是题外话，但却具有历史意义。目前不接受新的答案或互动。

灵感来自http://xkcd.com/710/这是一个高尔夫代码。

挑战

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

冰雹序列

参见Wikipedia了解更多详情..

• 如果数字是偶数，则将其除以二。
• 如果数字是奇数，则将其增加三倍并加一。

对产生的数字重复此操作，直到达到 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