Collat​​z猜想 - 迭代而不是递归 [英] Collatz Conjecture - Iteration rather than Recursion

问题描述

我正在为了学习的目的而工作，我已经处理了 Collat​​z 使用递归。如果你看到下面我使用 @_ 和 $ _ 来保持 / code> alive。

 ＃！/ usr / bin / env perl 
 
 sub collat​​z {
 my（$ num，$ count）= @_; 
 $ count ++; 
 if（$ num == 1）{
 return $ count; 
} elsif（$ num％2 == 0）{
 return collat​​z（$ num / 2，$ count）; 
} else {
 return collat​​z（$ num * 3 + 1，$ count）; 
} 
} 
 
 
 my $ max = 0; 
 my $ saved = 0; （1..1000）{
 my $ length = collat​​z（$ _，0）; 
 
 
打印Num：。 $ _。  长度：  。 $长度。 \\\
; 
 if（$ length> $ max）{
 $ max = $ length; 
 $ saved = $ _; 
} 
} 
 
 print最长的序列开头。 $保存。 \\\
; 
  

我正在尝试使用迭代而不是递归，但我无法想到如何解决这个问题。我不是在问题的代码之后，我只是想要一些提示/提示如何解决这个问题，以获得相同的结果。

我怀疑我需要使用，或直到字段

将不胜感激，再次我不想确切的答案。

---

更新 p>

这是我的第二次尝试，它给了我一个错误：

$ b $无法在answer2.pl第38行的子程序之外返回。 b

  my $ number = 0; 
 my $ counter = 0; 
 
 while（$ number！= 1000）{
 $ counter ++; 
 if（$ number == 1）{
 return $ counter; 
 
 elsif（$ number％2 == 0）{
 return（$ number / 2，$ counter）; 
} 
 else {
 return（$ number * 3 + 1，$ counter）; 
} 
 $ number ++; 
} 
 
打印号码。 $号。 柜台。 $柜台。 \\\
; 
  

解决方案

基本上你有 tail recursion ，这很好，很容易消除。

代替 collat​​z 调用自己来生成序列中的下一个步骤，只需简单地更改就地变量并循环回到顶部即可。

最简单的形式是

  sub collat​​z2 {
 my （$ num，$ count）= @_; 
 
下一个：
 $ count ++; 
 
 if（$ num == 1）{
 return $ count; 
 
 elsif（$ num％2 == 0）{
 $ num = $ num / 2; 
} 
 else {
 $ num = $ num * 3 + 1; 
} 
 
 goto NEXT; 
} 
  

但是应该写得比这更好。

我结束了这个

  sub collat​​z {
 my（$ num ）= @_; 
 my $ count = 1; 
 while（$ num> 1）{
 $ num = $ num％2？ $ num * 3 + 1：$ num / 2; 
 ++ $ count; 
} 
 $ count; 
} 
  

I am working on something for learning purposes where I have tackled Collatz using recursion. If you see below I make use of @_ and $_ to keep the for alive.

#!/usr/bin/env perl

sub collatz {
    my ($num, $count) = @_;
    $count++;
    if ($num == 1) {
        return $count;
    } elsif ($num % 2 == 0) {
        return collatz($num/2, $count);
    } else {
        return collatz($num*3 + 1, $count);
    }
}


my $max = 0;
my $saved = 0;

for (1..1000) {
    my $length = collatz($_, 0);
    print "Num: " . $_ . " Length: " . $length . "\n";
    if ($length > $max) {
        $max = $length;
        $saved = $_;
    }
}

print "The longest sequence starts with " . $saved . "\n";

I am trying to use iteration instead of recursion but I just can't think of how to tackle this. I am not after the code in the question, I just want some tips / hints on how to tackle this to get the same result.

I suspect I will need to use a while or an until field.

Any help would be appreciated, again I don't want the exact answer.

---

Update

Here is my second attempt, which is giving me an error of

Can't return outside a subroutine at answer2.pl line 38.

my $number  = 0;
my $counter = 0;

while ($number != 1000) {
  $counter++;
  if ($number == 1) {
    return $counter;
  }
  elsif ($number % 2 == 0) {
    return ($number / 2,     $counter);
  }
  else {
    return ($number * 3 + 1, $counter);
  }
  $number++;
}

print "number" . $number . "counter" . $counter . "\n";

解决方案

Basically you have tail recursion, which is nice and simple to eliminate.

Instead of collatz calling itself to generate the next step in the sequence, you simply change the variables in-place and loop back to the top.

In its crudest form this would be

sub collatz2 {
  my ($num, $count) = @_;

NEXT:
  $count++;

  if ($num == 1) {
    return $count;
  }
  elsif ($num % 2 == 0) {
    $num = $num / 2;
  }
  else {
    $num = $num * 3 + 1;
  }

  goto NEXT;
}

but it should be written much more nicely than that.

I ended up with this

sub collatz {
  my ($num) = @_;
  my $count = 1;
  while ($num > 1) {
    $num = $num % 2 ? $num * 3 + 1 : $num / 2;
    ++$count;
  }
  $count;
}

这篇关于Collat​​z猜想 - 迭代而不是递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！