编程竞技：考拉兹猜想

Question

编程竞技：考拉兹猜想

language-agnosticcode-golfrosetta-stonecollatz

86

受http://xkcd.com/710/启发，这里提供一个代码高尔夫挑战。

挑战

给定一个大于0的正整数，输出它的Hailstone序列。

Hailstone序列

详见Wikipedia。

如果数是偶数，则将其除以2。
如果数是奇数，则将其乘以3再加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

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

- Earlz

4

请查看 http://projecteuler.net/index.php?section=problems&id=14。 - Skilldrick

20

“must not be vulnerable to stack overflows”的意思是“不能容易受到堆栈溢出攻击”。而你说的“那你就不应该在这里发布了！”是一种玩笑话语，暗示讨论的内容可能存在安全漏洞。 - Felix Kling

51

我的朋友不再打电话给我了，这是否意味着我已经解决了问题？ - Martin

18

你在SO上，但曾经有朋友吗？那是什么感觉？ - Pops

5

汇编语言的回答很棒，但选择最长的答案有点反对代码高尔夫。 - John La Rooy

显示剩余7条评论

70个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Danko Durbić · Answer 1

PowerShell ：80个字符

一行代码：

"Results: $(for($x=read-host Number;1%$x;$x=@($x/2;3*$x+1)[$x%2]){""$x ->""}) 1"

美化输出：

"Results: $( for( $x = read-host Number; 1%$x; $x = @( $x/2; 3*$x+1 )[ $x%2 ] )
             { 
                 ""$x ->"" 
             }
           ) 1"

没有输入提示和输出格式 - 44 个字符：

for($x=read-host;1%$x;$x=@($x/2;3*$x+1)[$x%2]){$x}1

- egaga · Answer 2

因子:

不进行高尔夫比赛

USE: math
: body ( n -- n ) >integer dup . "->" . dup odd? = [ 3 * 1 + ] [ 2 / ] if ;
: hailstone ( n --  ) dup 1 > [ body hailstone ] [ . ] if  ;
21 hailstone

高尔夫:

21 [ dup 1 > ] [ >integer dup . "->" . dup 2 mod 1 = [ 3 * 1 + ] [ 2 / ] if ] while .

输出：

21
"->"
64
"->"
32
"->"
16
"->"
8
"->"
4
"->"
2
"->"
1

- Neil Aitken · Answer 3

PHP. 69个字符

感谢Danko Durbić提供的fgets(STDIN)，希望你不介意:)

<?$i=fgets(STDIN);while($i!=1){echo ($i=$i%2?$i*3+1:$i/=2),"\r\n";}?>

- Dan Andreatta · Answer 4

bash 57/61/60

另一个bash条目。不执行无限精度数学运算，可能会溢出。

#!/bin/bash
x=$1;echo $x;((x>1))&&$0 $((x%2?x*3+1:x/2))

一个不会溢出的版本可能是：

#!/bin/bash
x=$1;echo $x;((x>1))&&exec $0 $((x%2?x*3+1:x/2))

（编辑）还有一个迭代版本：

#!/bin/bash
for((x=$1;x>1;x=x%2?x*3+1:x/2));do echo $x;done

- Kuroki Kaze · Answer 5

0

JavaScript，61个70字符的输入

迭代，精度取决于JS限制

var i=prompt('');while(i>1){console.log(i);i=(i%2)?3*i+1:i/2}

- Kuroki Kaze

可以使用 alert 替换 console.log，将字符数减少到 55，但可用性会受到影响。 - Kuroki Kaze

使用 for(i=prompt();i>1;i=i%2?3*i+1:i/2) 可以将变量var移除并减少更多字符, 同时也可以去掉大括号。然而，你的代码没有输出最后的 1 或包含 ->。 - gnarf

- user257858 · Answer 6

Go，130个字符

package main
import(."os"
."strconv")
func main(){n,_:=Atoi(Args[1])
println(n)
for n>1{if n%2!=0{n=n*3+1}else{n/=2}
println(n)}}

例子

./collatz 3
3
10
5
16
8
4
2
1

- cheng81 · Answer 7

Erlang，120个字符

-module (f).
-export ([f/1]).
f(1)->1;
f(N)->
    io:format("~p ",[N]),
    if N rem 2 =:= 0
        ->f(trunc(N/2));
        true->f(3*N+1)
end.

测试：

f:f(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

- Frank Shearar · Answer 8

Common Lisp，76 74个字符

(defun c(n)(if (eql n 1)'(1)(cons n(if(oddp n)(c(1+(* 3 n)))(c(/ n 2))))))

或者，正确书写为：

(defun collatz (n)
  (if (eql n 1)
      '(1)
    (cons n (if (oddp n)
                (collatz (1+ (* 3 n)))
                (collatz (/ n 2))))))

- Frank Shearar · Answer 9

Smalltalk，103个字符

[:n||l|l:=OrderedCollection with:1.[n>1]whileTrue:[l addLast:n.n:=n odd ifTrue:[3*n+1]ifFalse:[n/2]].l]

通过发送带有所需参数的消息＃value：来调用：

[:n||l|l:=OrderedCollection with:1.[n>1]whileTrue:[l addLast:n.n:=n odd ifTrue:[3*n+1]ifFalse:[n/2]].l] value: 123

或者，更明智的做法：

[:n | | result |
        result := OrderedCollection with: 1.
        [n > 1] whileTrue: [
                result addLast: n.
                n := n odd ifTrue: [3*n + 1] ifFalse: [n / 2]].
        result] value: 123

（正确的方法是将上述内容定义为整数的一种方法，因此您可以说“123 collatz”，而不是作为匿名闭包。）

- Gerhard · Answer 10

Ruby 55个字符

n=gets.to_i
while(n>1) do n=((n%2)==1)?3*n+1:n/2;p n end