language-agnostic - 代码高尔夫 : Collatz Conjecture

锁定。这个问题及其答案是 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

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

最佳答案

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

关于language-agnostic - 代码高尔夫 : Collatz Conjecture，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2388254/