logo标签列表

编程竞技：考拉兹猜想

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

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

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个回答
14

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;}}

注意: 不要在没有至少原型化malloc/realloc的情况下删除#include <stdlib.h>，因为这样在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

在IT技术领域，云计算是一个热门话题。它是指通过网络将数据和应用程序存储在远程服务器上，并从任何地方通过互联网访问它们。

12

另一个汇编版本。这个版本不仅限于32位数字，它可以处理高达1065534的数字，尽管MS-DOS使用的“.com”格式仅限于80位数字。使用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
10

dc-24个字符2528

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
9

方案：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)

......运行得很好。[这只是一个数字 -- 我只是为了适应屏幕而把它分开了。]

8

Mathematica，45个字符

c=NestWhileList[If[OddQ@#,3#+1,#/2]&,#,#>1&]&
我数了58个字符。你可以用OddQ@#代替OddQ[#]来节省1个字符。 - kennytm
2
c[n_]:=NestWhileList[If[OddQ@#,3#+1,#/2]&,n,#>1&] - Michael Pilat
7

Ruby, 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
那是哪个版本的Ruby？我得到了n.odd??未定义的错误。此外，对于大数，它容易受到堆栈溢出的影响。 - Earlz
有趣的是，我使用的是 1.8.7 版本。在问号之间添加一个空格应该就可以解决这个问题。你说得对，确实会导致堆栈溢出。我会编辑我的答案并做出相应注释。 - Jordan Running
3
使用 p n=[n/2,n*3+1][n%2] 可以节省四个字符。该代码的功能是根据输入的数值，当它为偶数时除以2，否则乘以3再加1。 - Wayne Conrad
7
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);
    }
}
50
Java：这种语言需要使用BigIntegers来计算解决方案代码中的字符数。 - Jared Updike
3
@Jared 我完全同意Java很啰嗦。你必须承认所呈现的解决方案 a) 满足要求 b) 比实际需要的要长得多 c) 以一种令人愉悦的方式玩弄了Java类型系统 - wowest
7

Python 45字符

从makapuf的答案中删除了一个字符。

n=input()
while~-n:n=(n/2,n*3+1)[n%2];print n
非常聪明地使用了~运算符。我不太熟悉Python中的二进制运算符，所以我不得不查一下它的作用。 - Ponkadoodle
5

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
4

Ruby, 43个字符

支持bignum，但易受堆栈溢出攻击：

def c(n)p n;n%2>0?c(3*n+1):c(n/2)if n>1 end

...并且支持50个字符的大数，不会出现堆栈溢出的情况：

def d(n)while n>1 do p n;n=n%2>0?3*n+1:n/2 end end

向Jordan致敬。我之前不知道 'p' 可以替代puts。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接