当前位置： 文江博客话题详情

代码高尔夫：Collat​​z 猜想

发布于 2024-08-23 18:39:01 字数 1033 浏览 9 评论 0原文

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

挑战

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

冰雹序列

有关更多详细信息，请参阅维基百科。

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

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

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

原文

Inspired by http://xkcd.com/710/ here is a code golf for it.

The Challenge

Given a positive integer greater than 0, print out the hailstone sequence for that number.

The Hailstone Sequence

See Wikipedia for more detail..

  • If the number is even, divide it by two.
  • If the number is odd, triple it and add one.

Repeat this with the number produced until it reaches 1. (if it continues after 1, it will go in an infinite loop of 1 -> 4 -> 2 -> 1...)

Sometimes code is the best way to explain, so here is some from Wikipedia

function collatz(n)
  show n
  if n > 1
    if n is odd
      call collatz(3n + 1)
    else
      call collatz(n / 2)

This code works, but I am adding on an extra challenge. The program must not be vulnerable to stack overflows. So it must either use iteration or tail recursion.

Also, bonus points for if it can calculate big numbers and the language does not already have it implemented. (or if you reimplement big number support using fixed-length integers)

Test case

Number: 21
Results: 21 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1

Number: 3
Results: 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

Also, the code golf must include full user input and output.

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（30）

柠北森屋 2024-08-30 18:39:02

贝丰格

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

Befunge

&>:.:1-|
  >3*^ @
  |%2: <
 v>2/>+
回复 原文
倥絔 2024-08-30 18:39:02

Python - 95 64 51 46 char

显然不会产生堆栈溢出。

n=input()
while n>1:n=(n/2,n*3+1)[n%2];print n

Python - 95 64 51 46 char

Obviously does not produce a stack overflow.

n=input()
while n>1:n=(n/2,n*3+1)[n%2];print n
回复 原文
绾颜 2024-08-30 18:39:02

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

测试JUSTIN J. MEZA 的翻译。再见！

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

TESTD UNDR JUSTIN J. MEZA'S INTERPRETR. KTHXBYE!

回复 原文
如痴如狂 2024-08-30 18:39:02

Haskell，62 个字符 63 76 83、86、97、 137

c 1=[1]
c n=n:c(div(n`mod`2*(5*n+2)+n)2)
main=readLn>>=print.c

用户输入，打印输出，使用常量内存和堆栈，可处理任意大的整数。

此代码的示例运行，给定 80 位数字全“1”（！）的数量作为输入，看起来很有趣。

原始、仅函数版本：

Haskell 51 个字符

f n=n:[[],f([n`div`2,3*n+1]!!(n`mod`2))]!!(1`mod`n)

@&^# 到底谁需要条件？

（编辑：我很“聪明”并使用了修复。没有它，代码就会减少到 54 个字符。
edit2：通过分解 f() 降至 51)

Haskell, 62 chars 63 76 83, 86, 97, 137

c 1=[1]
c n=n:c(div(n`mod`2*(5*n+2)+n)2)
main=readLn>>=print.c

User input, printed output, uses constant memory and stack, works with arbitrarily big integers.

A sample run of this code, given an 80 digit number of all '1's (!) as input, is pretty fun to look at.

Original, function only version:

Haskell 51 chars

f n=n:[[],f([n`div`2,3*n+1]!!(n`mod`2))]!!(1`mod`n)

Who the @&^# needs conditionals, anyway?

(edit: I was being "clever" and used fix. Without it, the code dropped to 54 chars.
edit2: dropped to 51 by factoring out f())

回复 原文
梦里南柯 2024-08-30 18:39:02

Perl

我决定采取一点反竞争的态度，并展示您通常如何在 Perl 中编写此类问题。
最后还有一个 46（总共）字符的代码高尔夫条目。

前三个示例都从此标头开始。

#! /usr/bin/env perl
use Modern::Perl;
# which is the same as these three lines:
# use 5.10.0;
# use strict;
# use warnings;

while( <> ){
  chomp;
  last unless $_;
  Collatz( $_ );
}

  • 简单的递归版本

    使用 Sub::Call::Recur;
子科拉兹{
  我的( $n ) = @_;
  $n += 0; # 确保它是数字
  die“无效值”，除非 $n > 0;
  die '仅限整数值'除非 $n == int $n;
  说$n；
  给定（ $n ）{
    当( 1 ){}
    当( $_ % 2 != 0 ){ # 奇数
      递归( 3 * $n + 1 );
    }
    默认{#偶数
      重复( $n / 2 );
    }
  }
}

  • 简单迭代版本

    子 Collat​​z{
  我的( $n ) = @_;
  $n += 0; # 确保它是数字
  die“无效值”，除非 $n > 0;
  die '仅整数值'除非 $n == int $n;
  说$n；
  while( $n > 1 ){
    if( $n % 2 ){ # 奇数
      $n = 3 * $n + 1;
    }其他{#even
      $n = $n / 2;
    }
    说$n；
  }
}

  • 优化迭代版本

    子 Collat​​z{
  我的( $n ) = @_;
  $n += 0; # 确保它是数字
  die“无效值”，除非 $n > 0;
  die '仅限整数值'除非 $n == int $n;
  #
  声明@下一个；
  $下一个[1] //= 0; # 如果 $next[1] 未定义，则将其设置为 0
  #
  # 填写@next，直到得到我们已经计算过的值
  直到（定义$next[$n]）{
    说$n；
    #
    if( $n % 2 ){ # 奇数
      $下一个[$n] = 3 * $n + 1;
    } else { # 偶数
      $下一个[$n] = $n / 2;
    }
    #
    $n = $下一个[$n];
  }
  说$n；
  # 结束运行直到达到 1
  说 $n 而 $n = $next[$n];
}

现在我将向您展示如何使用 v5.10.0

#! /usr/bin/env perl
use strict;
use warnings;

while( <> ){
  chomp;
  last unless $_;
  Collatz( $_ );
}
{
  my @next = (0,0); # essentially the same as a state variable
  sub Collatz{
    my( $n ) = @_;
    $n += 0; # ensure that it is numeric
    die 'invalid value' unless $n > 0;

    # fill out @next until we get to a value we've already worked on
    until( $n == 1 or defined $next[$n] ){
      print $n, "\n";

      if( $n % 2 ){ # odd
        $next[$n] = 3 * $n + 1;
      } else { # even
        $next[$n] = $n / 2;
      }
      $n = $next[$n];
    }
    print $n, "\n";

    # finish running until we get to 1
    print $n, "\n" while $n = $next[$n];
  }
}

基准测试

之前的 Perl 版本执行最后一个示例。首先，IO 始终是缓慢的部分。因此，如果您实际上按原样对它们进行基准测试，那么您应该从每一个中获得大约相同的速度。

为了测试这些，我打开了 /dev/null ($null) 的文件句柄，并编辑了每个 say $n 以改为读取说 {$null} $n。这是为了减少对IO的依赖。

#! /usr/bin/env perl
use Modern::Perl;
use autodie;

open our $null, '>', '/dev/null';

use Benchmark qw':all';

cmpthese( -10,
{
  Recursive => sub{ Collatz_r( 31 ) },
  Iterative => sub{ Collatz_i( 31 ) },
  Optimized => sub{ Collatz_o( 31 ) },
});

sub Collatz_r{
  ...
  say {$null} $n;
  ...
}
sub Collatz_i{
  ...
  say {$null} $n;
  ...
}
sub Collatz_o{
  ...
  say {$null} $n;
  ...
}

运行 10 次后，这是一个具有代表性的示例输出：

            Rate Recursive Iterative Optimized
Recursive 1715/s        --      -27%      -46%
Iterative 2336/s       36%        --      -27%
Optimized 3187/s       86%       36%        --

最后，一个真正的代码高尔夫条目：

perl -nlE'say;say$_=$_%2?3*$_+1:$_/2while$_>1'

总共 46 个字符

如果您不需要打印起始值，您可以再删除 5 个字符。

perl -nE'say$_=$_%2?3*$_+1:$_/2while$_>1'

总共 41 个字符
31 个字符用于实际代码部分，但如果没有 -n 开关，代码将无法工作。因此，我将整个示例包含在我的计数中。

Perl

I decided to be a little anticompetitive, and show how you would normally code such problem in Perl.
There is also a 46 (total) char code-golf entry at the end.

These first three examples all start out with this header.

#! /usr/bin/env perl
use Modern::Perl;
# which is the same as these three lines:
# use 5.10.0;
# use strict;
# use warnings;

while( <> ){
  chomp;
  last unless $_;
  Collatz( $_ );
}

  • Simple recursive version

    use Sub::Call::Recur;
sub Collatz{
  my( $n ) = @_;
  $n += 0; # ensure that it is numeric
  die 'invalid value' unless $n > 0;
  die 'Integer values only' unless $n == int $n;
  say $n;
  given( $n ){
    when( 1 ){}
    when( $_ % 2 != 0 ){ # odd
      recur( 3 * $n + 1 );
    }
    default{ # even
      recur( $n / 2 );
    }
  }
}

  • Simple iterative version

    sub Collatz{
  my( $n ) = @_;
  $n += 0; # ensure that it is numeric
  die 'invalid value' unless $n > 0;
  die 'Integer values only' unless $n == int $n;
  say $n;
  while( $n > 1 ){
    if( $n % 2 ){ # odd
      $n = 3 * $n + 1;
    } else { #even
      $n = $n / 2;
    }
    say $n;
  }
}

  • Optimized iterative version

    sub Collatz{
  my( $n ) = @_;
  $n += 0; # ensure that it is numeric
  die 'invalid value' unless $n > 0;
  die 'Integer values only' unless $n == int $n;
  #
  state @next;
  $next[1] //= 0; # sets $next[1] to 0 if it is undefined
  #
  # fill out @next until we get to a value we've already worked on
  until( defined $next[$n] ){
    say $n;
    #
    if( $n % 2 ){ # odd
      $next[$n] = 3 * $n + 1;
    } else { # even
      $next[$n] = $n / 2;
    }
    #
    $n = $next[$n];
  }
  say $n;
  # finish running until we get to 1
  say $n while $n = $next[$n];
}

Now I'm going to show how you would do that last example with a version of Perl prior to v5.10.0

#! /usr/bin/env perl
use strict;
use warnings;

while( <> ){
  chomp;
  last unless $_;
  Collatz( $_ );
}
{
  my @next = (0,0); # essentially the same as a state variable
  sub Collatz{
    my( $n ) = @_;
    $n += 0; # ensure that it is numeric
    die 'invalid value' unless $n > 0;

    # fill out @next until we get to a value we've already worked on
    until( $n == 1 or defined $next[$n] ){
      print $n, "\n";

      if( $n % 2 ){ # odd
        $next[$n] = 3 * $n + 1;
      } else { # even
        $next[$n] = $n / 2;
      }
      $n = $next[$n];
    }
    print $n, "\n";

    # finish running until we get to 1
    print $n, "\n" while $n = $next[$n];
  }
}

Benchmark

First off the IO is always going to be the slow part. So if you actually benchmarked them as-is you should get about the same speed out of each one.

To test these then, I opened a file handle to /dev/null ($null), and edited every say $n to instead read say {$null} $n. This is to reduce the dependence on IO.

#! /usr/bin/env perl
use Modern::Perl;
use autodie;

open our $null, '>', '/dev/null';

use Benchmark qw':all';

cmpthese( -10,
{
  Recursive => sub{ Collatz_r( 31 ) },
  Iterative => sub{ Collatz_i( 31 ) },
  Optimized => sub{ Collatz_o( 31 ) },
});

sub Collatz_r{
  ...
  say {$null} $n;
  ...
}
sub Collatz_i{
  ...
  say {$null} $n;
  ...
}
sub Collatz_o{
  ...
  say {$null} $n;
  ...
}

After having run it 10 times, here is a representative sample output:

            Rate Recursive Iterative Optimized
Recursive 1715/s        --      -27%      -46%
Iterative 2336/s       36%        --      -27%
Optimized 3187/s       86%       36%        --

Finally, a real code-golf entry:

perl -nlE'say;say$_=$_%2?3*$_+1:$_/2while$_>1'

46 chars total

If you don't need to print the starting value, you could remove 5 more characters.

perl -nE'say$_=$_%2?3*$_+1:$_/2while$_>1'

41 chars total
31 chars for the actual code portion, but the code won't work without the -n switch. So I include the entire example in my count.

回复 原文
窝囊感情。 2024-08-30 18:39:02

Golfscript：20 个字符

  ~{(}{3*).1&5*)/}/1+`
# 
# Usage: echo 21 | ruby golfscript.rb collatz.gs

这相当于

stack<int> s;
s.push(21);
while (s.top() - 1) {
  int x = s.top();
  int numerator = x*3+1;
  int denominator = (numerator&1) * 5 + 1;
  s.push(numerator/denominator);
}
s.push(1);
return s;

Golfscript : 20 chars

  ~{(}{3*).1&5*)/}/1+`
# 
# Usage: echo 21 | ruby golfscript.rb collatz.gs

This is equivalent to

stack<int> s;
s.push(21);
while (s.top() - 1) {
  int x = s.top();
  int numerator = x*3+1;
  int denominator = (numerator&1) * 5 + 1;
  s.push(numerator/denominator);
}
s.push(1);
return s;
回复 原文
伴我老 2024-08-30 18:39:02

bc 41 chars

我想这种问题是什么 bc发明的目的是：

for(n=read();n>1;){if(n%2)n=n*6+2;n/=2;n}

测试：

bc1 -q collatz.bc
21
64
32
16
8
4
2
1

正确的代码：

for(n=read();n>1;){if(n%2)n=n*3+1else n/=2;print n,"\n"}

bc 处理最多 INT_MAX 位数字

编辑： 维基百科文章提到此猜想已针对最高20x258的所有值进行了检查（大约5.76e18）。此程序：

c=0;for(n=2^20000+1;n>1;){if(n%2)n=n*6+2;n/=2;c+=1};n;c

在 68 秒内测试 220,000+1（大约 3.98e6,020）， >144,404 周期。

bc 41 chars

I guess this kind of problems is what bc was invented for:

for(n=read();n>1;){if(n%2)n=n*6+2;n/=2;n}

Test:

bc1 -q collatz.bc
21
64
32
16
8
4
2
1

Proper code:

for(n=read();n>1;){if(n%2)n=n*3+1else n/=2;print n,"\n"}

bc handles numbers with up to INT_MAX digits

Edit: The Wikipedia article mentions this conjecture has been checked for all values up to 20x258 (aprox. 5.76e18). This program:

c=0;for(n=2^20000+1;n>1;){if(n%2)n=n*6+2;n/=2;c+=1};n;c

tests 220,000+1 (aprox. 3.98e6,020) in 68 seconds, 144,404 cycles.

回复 原文
暖阳 2024-08-30 18:39:02

Perl：31 个字符

perl -nE 'say$_=$_%2?$_*3+1:$_/2while$_>1'
#         123456789 123456789 123456789 1234567

编辑删除 2 个不必要的空格。

编辑删除 1 个不必要的空格。

Perl : 31 chars

perl -nE 'say$_=$_%2?$_*3+1:$_/2while$_>1'
#         123456789 123456789 123456789 1234567

Edited to remove 2 unnecessary spaces.

Edited to remove 1 unnecessary space.

回复 原文
纸伞微斜 2024-08-30 18:39:02

MS Excel，35 个字符

=IF(A1/2=ROUND(A1/2,0),A1/2,A1*3+1)

取自维基百科：

In cell A1, place the starting number.
In cell A2 enter this formula =IF(A1/2=ROUND(A1/2,0),A1/2,A1*3+1) 
Drag and copy the formula down until 4, 2, 1

直接 复制/粘贴公式 111 次以获得起始数字 1000 的结果。;)

MS Excel, 35 chars

=IF(A1/2=ROUND(A1/2,0),A1/2,A1*3+1)

Taken straight from Wikipedia:

In cell A1, place the starting number.
In cell A2 enter this formula =IF(A1/2=ROUND(A1/2,0),A1/2,A1*3+1) 
Drag and copy the formula down until 4, 2, 1

It only took copy/pasting the formula 111 times to get the result for a starting number of 1000. ;)

回复 原文
那请放手 2024-08-30 18:39:02

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，如下这样做在 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

删除了 12 个字符，因为没有人遵循输出格式...:| ）

C : 64 chars

main(x){for(scanf("%d",&x);x>=printf("%d,",x);x=x&1?3*x+1:x/2);}

With big integer support: 431 (necessary) chars

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

Note: Do not remove #include <stdlib.h> without at least prototyping malloc/realloc, as doing so will not be safe on 64-bit platforms (64-bit void* will be converted to 32-bit int).

This one hasn't been tested vigorously yet. It could use some shortening as well.

Previous versions:

main(x){for(scanf("%d",&x);printf("%d,",x),x-1;x=x&1?3*x+1:x/2);} // 66

(removed 12 chars because no one follows the output format... :| )

回复 原文
乞讨 2024-08-30 18:39:02

另一个汇编版本。它不限于 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

Another assembler version. This one is not limited to 32 bit numbers, it can handle numbers up to 1065534 although the ".com" format MS-DOS uses is limited to 80 digit numbers. Written for A86 assembler and requires a Win-XP DOS box to run. Assembles to 180 bytes:

    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
回复 原文
别念他 2024-08-30 18:39:02

dc - 24 个字符 25 28

dc 是此序列的一个很好的工具：

?[d5*2+d2%*+2/pd1<L]dsLx

dc -f collatz.dc
21
64
32
16
8
4
2
1

还有 24 个字符，使用 Golfscript 条目：

?[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
Number: 3
Results: 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

dc - 24 chars 25 28

dc is a good tool for this sequence:

?[d5*2+d2%*+2/pd1<L]dsLx

dc -f collatz.dc
21
64
32
16
8
4
2
1

Also 24 chars using the formula from the Golfscript entry:

?[3*1+d2%5*1+/pd1<L]dsLx

57 chars to meet the specs:

[Number: ]n?[Results: ]ndn[d5*2+d2%*+2/[ -> ]ndnd1<L]dsLx

dc -f collatz-spec.dc
Number: 3
Results: 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
回复 原文
_畞蕅 2024-08-30 18:39:02

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

...运行得很好。 [这只是一个数字——我刚刚将其分解以适合屏幕。]

Scheme: 72

(define(c n)(if(= n 1)`(1)(cons n(if(odd? n)(c(+(* n 3)1))(c(/ n 2))))))

This uses recursion, but the calls are tail-recursive so I think they'll be optimized to iteration. In some quick testing, I haven't been able to find a number for which the stack overflows anyway. Just for example:

(c 9876543219999999999000011234567898888777766665555444433332222
7777777777777777777777777777777798797657657651234143375987342987
5398709812374982529830983743297432985230985739287023987532098579
058095873098753098370938753987)

...runs just fine. [that's all one number -- I've just broken it to fit on screen.]

回复 原文
情释 2024-08-30 18:39:02

Mathematica，45 50 个字符

c=NestWhileList[If[OddQ@#,3#+1,#/2]&,#,#>1&]&

Mathematica, 45 50 chars

c=NestWhileList[If[OddQ@#,3#+1,#/2]&,#,#>1&]&
回复 原文
伴我老 2024-08-30 18:39:02

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, 50 chars, no stack overflow

Basically a direct rip of makapuf's Python solution:

def c(n)while n>1;n=n.odd?? n*3+1: n/2;p n end end

Ruby, 45 chars, will overflow

Basically a direct rip of the code provided in the question:

def c(n)p n;n.odd?? c(3*n+1):c(n/2)if n>1 end
回复 原文
无法回应 2024-08-30 18:39:02
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);
    }
}

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);
    }
}
回复 原文
骄兵必败 2024-08-30 18:39:02

Python 45 Char

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

n=input()
while~-n:n=(n/2,n*3+1)[n%2];print n

Python 45 Char

Shaved a char off of makapuf's answer.

n=input()
while~-n:n=(n/2,n*3+1)[n%2];print n
回复 原文
凉墨 2024-08-30 18:39:02

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

TI-BASIC

Not the shortest, but a novel approach. Certain to slow down considerably with large sequences, but it shouldn't overflow.

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
回复 原文
习惯那些不曾习惯的习惯 2024-08-30 18:39:02

哈斯克尔：50

c 1=[1];c n=n:(c$if odd n then 3*n+1 else n`div`2)

Haskell : 50

c 1=[1];c n=n:(c$if odd n then 3*n+1 else n`div`2)
回复 原文
赠我空喜 2024-08-30 18:39:02

不是最短的，而是一个优雅的 clojure 解决方案

(defn collatz [n]
 (print n "")
 (if (> n 1)
  (recur
   (if (odd? n)
    (inc (* 3 n))
    (/ n 2)))))

not the shortest, but an elegant clojure solution

(defn collatz [n]
 (print n "")
 (if (> n 1)
  (recur
   (if (odd? n)
    (inc (* 3 n))
    (/ n 2)))))
回复 原文
淡水深流 2024-08-30 18:39:02

C#：216 个字符

using C=System.Console;class P{static void Main(){var p="start:";System.Action<object> o=C.Write;o(p);ulong i;while(ulong.TryParse(C.ReadLine(),out i)){o(i);while(i > 1){i=i%2==0?i/2:i*3+1;o(" -> "+i);}o("\n"+p);}}}

长格式：

using C = System.Console;
class P
{
    static void Main()
    {
        var p = "start:"; 
        System.Action<object> o = C.Write; 
        o(p); 
        ulong i; 
        while (ulong.TryParse(C.ReadLine(), out i))
        {
            o(i); 
            while (i > 1)
            {
                i = i % 2 == 0 ? i / 2 : i * 3 + 1; 
                o(" -> " + i);
            } 
            o("\n" + p);
        }
    }
}

新版本，接受一个数字作为通过命令行提供的输入，无需输入验证。 173 154 个字符。

using System;class P{static void Main(string[]a){Action<object>o=Console.Write;var i=ulong.Parse(a[0]);o(i);while(i>1){i=i%2==0?i/2:i*3+1;o(" -> "+i);}}}

长格式：

using System;
class P
{
    static void Main(string[]a)
    {
        Action<object>o=Console.Write;
        var i=ulong.Parse(a[0]);
        o(i);
        while(i>1)
        {
            i=i%2==0?i/2:i*3+1;
            o(" -> "+i);
        }
    }
}

我可以通过抄袭此 答案使用for循环而不是while。 150 个字符。

using System;class P{static void Main(string[]a){Action<object>o=Console.Write;for(var i=ulong.Parse(a[0]);i>1;i=i%2==0?i/2:i*3+1)o(i+" -> ");o(1);}}

C#: 216 Characters

using C=System.Console;class P{static void Main(){var p="start:";System.Action<object> o=C.Write;o(p);ulong i;while(ulong.TryParse(C.ReadLine(),out i)){o(i);while(i > 1){i=i%2==0?i/2:i*3+1;o(" -> "+i);}o("\n"+p);}}}

in long form:

using C = System.Console;
class P
{
    static void Main()
    {
        var p = "start:"; 
        System.Action<object> o = C.Write; 
        o(p); 
        ulong i; 
        while (ulong.TryParse(C.ReadLine(), out i))
        {
            o(i); 
            while (i > 1)
            {
                i = i % 2 == 0 ? i / 2 : i * 3 + 1; 
                o(" -> " + i);
            } 
            o("\n" + p);
        }
    }
}

New Version, accepts one number as input provided through the command line, no input validation. 173 154 characters.

using System;class P{static void Main(string[]a){Action<object>o=Console.Write;var i=ulong.Parse(a[0]);o(i);while(i>1){i=i%2==0?i/2:i*3+1;o(" -> "+i);}}}

in long form:

using System;
class P
{
    static void Main(string[]a)
    {
        Action<object>o=Console.Write;
        var i=ulong.Parse(a[0]);
        o(i);
        while(i>1)
        {
            i=i%2==0?i/2:i*3+1;
            o(" -> "+i);
        }
    }
}

I am able to shave a few characters by ripping off the idea in this answer to use a for loop rather than a while. 150 characters.

using System;class P{static void Main(string[]a){Action<object>o=Console.Write;for(var i=ulong.Parse(a[0]);i>1;i=i%2==0?i/2:i*3+1)o(i+" -> ");o(1);}}
回复 原文
过期以后 2024-08-30 18:39:02

Ruby，

支持 43 个字符 bignum，具有堆栈溢出敏感性：

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

...以及 50 个字符，支持 bignum，无堆栈溢出：

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

感谢 Jordan。我不知道“p”可以替代 put。

Ruby, 43 characters

bignum supported, with stack overflow susceptibility:

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

...and 50 characters, bignum supported, without stack overflow:

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

Kudos to Jordan. I didn't know about 'p' as a replacement for puts.

回复 原文
街角卖回忆 2024-08-30 18:39:02

nroff1

使用nroff -U hail.g

.warn
.pl 1
.pso (printf "Enter a number: " 1>&2); read x; echo .nr x $x
.while \nx>1 \{\
.  ie \nx%2 .nr x \nx*3+1
.  el .nr x \nx/2
\nx
.\}

1 运行。 groff版本

nroff1

Run with nroff -U hail.g

.warn
.pl 1
.pso (printf "Enter a number: " 1>&2); read x; echo .nr x $x
.while \nx>1 \{\
.  ie \nx%2 .nr x \nx*3+1
.  el .nr x \nx/2
\nx
.\}

1. groff version

回复 原文
私野 2024-08-30 18:39:02

Scala + Scalaz

import scalaz._
import Scalaz._
val collatz = 
   (_:Int).iterate[Stream](a=>Seq(a/2,3*a+1)(a%2)).takeWhile(1<) // This line: 61 chars

实际操作：

scala> collatz(7).toList
res15: List[Int] = List(7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2)

Scala 2.8

val collatz = 
   Stream.iterate(_:Int)(a=>Seq(a/2,3*a+1)(a%2)).takeWhile(1<) :+ 1

这还包括尾随的 1。

scala> collatz(7)
res12: scala.collection.immutable.Stream[Int] = Stream(7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1)

通过以下隐式

implicit def intToEven(i:Int) = new {
  def ~(even: Int=>Int, odd: Int=>Int) = { 
    if (i%2==0) { even(i) } else { odd(i) }
  }
}

，可以将其缩短为

val collatz = Stream.iterate(_:Int)(_~(_/2,3*_+1)).takeWhile(1<) :+ 1

编辑 - 58 个字符 （包括输入和输出，但不包括初始数字）

var n=readInt;while(n>1){n=Seq(n/2,n*3+1)(n%2);println(n)}

如果不需要换行符可以减少2...

Scala + Scalaz

import scalaz._
import Scalaz._
val collatz = 
   (_:Int).iterate[Stream](a=>Seq(a/2,3*a+1)(a%2)).takeWhile(1<) // This line: 61 chars

And in action:

scala> collatz(7).toList
res15: List[Int] = List(7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2)

Scala 2.8

val collatz = 
   Stream.iterate(_:Int)(a=>Seq(a/2,3*a+1)(a%2)).takeWhile(1<) :+ 1

This also includes the trailing 1.

scala> collatz(7)
res12: scala.collection.immutable.Stream[Int] = Stream(7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1)

With the following implicit

implicit def intToEven(i:Int) = new {
  def ~(even: Int=>Int, odd: Int=>Int) = { 
    if (i%2==0) { even(i) } else { odd(i) }
  }
}

this can be shortened to

val collatz = Stream.iterate(_:Int)(_~(_/2,3*_+1)).takeWhile(1<) :+ 1

Edit - 58 characters (including input and output, but not including initial number)

var n=readInt;while(n>1){n=Seq(n/2,n*3+1)(n%2);println(n)}

Could be reduced by 2 if you don't need newlines...

回复 原文
旧时浪漫 2024-08-30 18:39:02

F#，90 个字符

let c=Seq.unfold(function|n when n<=1->None|n when n%2=0->Some(n,n/2)|n->Some(n,(3*n)+1))

> c 21;;
val it : seq<int> = seq [21; 64; 32; 16; ...]

或者如果您不使用 F# 交互方式显示结果，则为 102 个字符：

let c=Seq.unfold(function|n when n<=1->None|n when n%2=0->Some(n,n/2)|n->Some(n,(3*n)+1))>>printf"%A"

F#, 90 characters

let c=Seq.unfold(function|n when n<=1->None|n when n%2=0->Some(n,n/2)|n->Some(n,(3*n)+1))

> c 21;;
val it : seq<int> = seq [21; 64; 32; 16; ...]

Or if you're not using F# interactive to display the result, 102 characters:

let c=Seq.unfold(function|n when n<=1->None|n when n%2=0->Some(n,n/2)|n->Some(n,(3*n)+1))>>printf"%A"
回复 原文
怪我太投入 2024-08-30 18:39:02

Common Lisp，141 个字符：

(defun c ()
  (format t"Number: ")
  (loop for n = (read) then (if(oddp n)(+ 1 n n n)(/ n 2))
     until (= n 1)
     do (format t"~d -> "n))
  (format t"1~%"))

测试运行：

Number: 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

Common Lisp, 141 characters:

(defun c ()
  (format t"Number: ")
  (loop for n = (read) then (if(oddp n)(+ 1 n n n)(/ n 2))
     until (= n 1)
     do (format t"~d -> "n))
  (format t"1~%"))

Test run:

Number: 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
回复 原文
画尸师 2024-08-30 18:39:02

Jerry Coffin 的程序有整数溢出，试试这个：用

#include <iostream>

int main(unsigned long long i)
{
    int j = 0;
    for(  std::cin>>i; i>1; i = i&1? i*3+1:i/2, ++j)
        std::cout<<i<<" -> ";

    std::cout<<"\n"<<j << " iterations\n";
}

进行测试。

小于 1 亿的数字，最长的总停止时间是 63,728,127，有 949 个步骤。

总停止时间最长的不到10亿的数字是670,617,279，有986步。

The program frm Jerry Coffin has integer over flow, try this one:

#include <iostream>

int main(unsigned long long i)
{
    int j = 0;
    for(  std::cin>>i; i>1; i = i&1? i*3+1:i/2, ++j)
        std::cout<<i<<" -> ";

    std::cout<<"\n"<<j << " iterations\n";
}

tested with

The number less than 100 million with the longest total stopping time is 63,728,127, with 949 steps.

The number less than 1 billion with the longest total stopping time is 670,617,279, with 986 steps.

回复 原文
变身佩奇 2024-08-30 18:39:02

ruby，43，可能满足 I/O 要求

使用 ruby -n hail 运行

n=$_.to_i
(n=n%2>0?n*3+1: n/2
p n)while n>1

ruby, 43, possibly meeting the I/O requirement

Run with ruby -n hail

n=$_.to_i
(n=n%2>0?n*3+1: n/2
p n)while n>1
回复 原文
橘味果▽酱 2024-08-30 18:39:02

C#：659 个字符，支持 BigInteger

using System.Linq;using C=System.Console;class Program{static void Main(){var v=C.ReadLine();C.Write(v);while(v!="1"){C.Write("->");if(v[v.Length-1]%2==0){v=v.Aggregate(new{s="",o=0},(r,c)=>new{s=r.s+(char)((c-48)/2+r.o+48),o=(c%2)*5}).s.TrimStart('0');}else{var q=v.Reverse().Aggregate(new{s="",o=0},(r, c)=>new{s=(char)((c-48)*3+r.o+(c*3+r.o>153?c*3+r.o>163?28:38:48))+r.s,o=c*3+r.o>153?c*3+r.o>163?2:1:0});var t=(q.o+q.s).TrimStart('0').Reverse();var x=t.First();q=t.Skip(1).Aggregate(new{s=x>56?(x-57).ToString():(x-47).ToString(),o=x>56?1:0},(r,c)=>new{s=(char)(c-48+r.o+(c+r.o>57?38:48))+r.s,o=c+r.o>57?1:0});v=(q.o+q.s).TrimStart('0');}C.Write(v);}}}

Ungolfed

using System.Linq;
using C = System.Console;
class Program
{
    static void Main()
    {
        var v = C.ReadLine();
        C.Write(v);
        while (v != "1")
        {
            C.Write("->");
            if (v[v.Length - 1] % 2 == 0)
            {
                v = v
                    .Aggregate(
                        new { s = "", o = 0 }, 
                        (r, c) => new { s = r.s + (char)((c - 48) / 2 + r.o + 48), o = (c % 2) * 5 })
                    .s.TrimStart('0');
            }
            else
            {
                var q = v
                    .Reverse()
                    .Aggregate(
                        new { s = "", o = 0 }, 
                        (r, c) => new { s = (char)((c - 48) * 3 + r.o + (c * 3 + r.o > 153 ? c * 3 + r.o > 163 ? 28 : 38 : 48)) + r.s, o = c * 3 + r.o > 153 ? c * 3 + r.o > 163 ? 2 : 1 : 0 });
                var t = (q.o + q.s)
                    .TrimStart('0')
                    .Reverse();
                var x = t.First();
                q = t
                    .Skip(1)
                    .Aggregate(
                        new { s = x > 56 ? (x - 57).ToString() : (x - 47).ToString(), o = x > 56 ? 1 : 0 }, 
                        (r, c) => new { s = (char)(c - 48 + r.o + (c + r.o > 57 ? 38 : 48)) + r.s, o = c + r.o > 57 ? 1 : 0 });
                v = (q.o + q.s)
                    .TrimStart('0');
            }
            C.Write(v);
        }
    }
}

C# : 659 chars with BigInteger support

using System.Linq;using C=System.Console;class Program{static void Main(){var v=C.ReadLine();C.Write(v);while(v!="1"){C.Write("->");if(v[v.Length-1]%2==0){v=v.Aggregate(new{s="",o=0},(r,c)=>new{s=r.s+(char)((c-48)/2+r.o+48),o=(c%2)*5}).s.TrimStart('0');}else{var q=v.Reverse().Aggregate(new{s="",o=0},(r, c)=>new{s=(char)((c-48)*3+r.o+(c*3+r.o>153?c*3+r.o>163?28:38:48))+r.s,o=c*3+r.o>153?c*3+r.o>163?2:1:0});var t=(q.o+q.s).TrimStart('0').Reverse();var x=t.First();q=t.Skip(1).Aggregate(new{s=x>56?(x-57).ToString():(x-47).ToString(),o=x>56?1:0},(r,c)=>new{s=(char)(c-48+r.o+(c+r.o>57?38:48))+r.s,o=c+r.o>57?1:0});v=(q.o+q.s).TrimStart('0');}C.Write(v);}}}

Ungolfed

using System.Linq;
using C = System.Console;
class Program
{
    static void Main()
    {
        var v = C.ReadLine();
        C.Write(v);
        while (v != "1")
        {
            C.Write("->");
            if (v[v.Length - 1] % 2 == 0)
            {
                v = v
                    .Aggregate(
                        new { s = "", o = 0 }, 
                        (r, c) => new { s = r.s + (char)((c - 48) / 2 + r.o + 48), o = (c % 2) * 5 })
                    .s.TrimStart('0');
            }
            else
            {
                var q = v
                    .Reverse()
                    .Aggregate(
                        new { s = "", o = 0 }, 
                        (r, c) => new { s = (char)((c - 48) * 3 + r.o + (c * 3 + r.o > 153 ? c * 3 + r.o > 163 ? 28 : 38 : 48)) + r.s, o = c * 3 + r.o > 153 ? c * 3 + r.o > 163 ? 2 : 1 : 0 });
                var t = (q.o + q.s)
                    .TrimStart('0')
                    .Reverse();
                var x = t.First();
                q = t
                    .Skip(1)
                    .Aggregate(
                        new { s = x > 56 ? (x - 57).ToString() : (x - 47).ToString(), o = x > 56 ? 1 : 0 }, 
                        (r, c) => new { s = (char)(c - 48 + r.o + (c + r.o > 57 ? 38 : 48)) + r.s, o = c + r.o > 57 ? 1 : 0 });
                v = (q.o + q.s)
                    .TrimStart('0');
            }
            C.Write(v);
        }
    }
}
回复 原文
青衫负雪 2024-08-30 18:39:01

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

x86 assembly, 1337 characters

;
; 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
回复 原文
~没有更多了~

关于作者

木格

暂无简介

0 文章
0 评论
23 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

游缘惊梦

文章 0 评论 0

小兔几

文章 0 评论 0

Glik

文章 0 评论 0

生生漫

文章 0 评论 0

Luxian

文章 0 评论 0

Champion-Ming

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文