ruby - 我用于求解 Collat​​z 序列的代码中是否存在无限循环？

Question

我的代码试图找到这个问题的答案:为正整数集定义了以下迭代序列:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

使用上述规则并从 13 开始，我们生成以下序列:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

可以看出这个序列(从 13 开始到 1 结束)包含 10 个项。尽管尚未证明(Collat​​z Problem)，但认为所有起始数字都以 1 结尾。

哪个起始数(小于一百万)产生最长的链？

注意:一旦链开始，条款就可以超过一百万。

这是我的代码:

step_count = 1
score = {}
largest_score = 1
(1..1000000).map do |n|
  while n >= 1 do
    if n%2 == 0 then
      n/2
      step_count += 1
    else
      (3*n)+1
      step_count += 1
    end
  end
  score = {n => step_count}
end
score.each {|n, step_count| largest_score = step_count if largest_score < step_count}
puts score.key(largest_score)

我运行了一个多小时，仍然没有答案。我的代码中是否存在无限循环，或者可能存在其他问题，如果有，那是什么？

我正在使用 Ruby 1.8.7

Answer 1

是的，你有一个无限循环。它在这里:

while n >= 1 do
  if n%2 == 0 then
    n/2
    step_count += 1
  else
    (3*n)+1
    step_count += 1
  end
end

while 循环中的条件正在测试 n，但是循环中的任何内容都没有改变它的值。你可能想做的是:

while n >= 1 do
  if n % 2 == 0
    n = n / 2
    step_count += 1
  else
    n = (3 * n) + 1
    step_count += 1
  end
end

一些旁注:

• 看起来你的意思是用新的键值对更新 score 散列，但正如所写的那样，score = { n => step_count } 将替换它完全在每次迭代中。要将新对添加到现有哈希，请使用 score[n] = step_count。
• 通过键在散列中查找值比相反的方式更有效，因此您可能想要反转散列存储:score[step_count] = n，用score.each { |step_count, n| 找到最大的分数#... 并用 score[largest_score] 读出。这还有一个额外的好处，就是您不必存储所有的百万个结果；它只会存储您达到的最后一个数字，该数字会导致给定长度的链。当然，这也意味着您只会看到一个导致最大链的数字，即使有多个数字具有相同的最长链也是如此!问题的措辞好像答案是唯一的，但如果不是，你将找不到答案。
• 为了在将来调试此类问题，将循环迭代次数减少到很小(比如说十次)并在循环中散布一些 puts 语句以观察正在发生的事情并感受一下会很方便用于执行流程。