Ruby——使用Hash求解Collat​​z序列

Question

我对解决算法还很陌生，所以请多多包涵。

我已经解决了最大长度为 1,000,000 的 Collat​​z 序列，但我想通过使用哈希表查找已经存在的键来提高效率，从而使函数更快。但是，我知道我做错了什么，因为运行 number = 1,000,000 应该只需要大约 1-2 秒，但它仍然需要 9-10 秒才能运行。我对在算法中使用哈希表还很陌生，所以有人可以告诉我我的方法中做错了什么吗？

非常感谢!

def collatz(n)
  chain = 1
  until n == 1
    n = (n.even?) ? (n/2) : (n*3+1)
    chain += 1
  end
  chain
end

def longest_chain2(number)
  cache = { 1 => 1 }
  start_num = 1
  longest = 1
  while start_num < number
    chain = cache[start_num]
    if chain > longest
      longest = chain
      longest_start = start_num
    end
    start_num += 1
    cache[start_num] = collatz(start_num)
  end
  return longest_start
end

puts longest_chain2(1000000)

Answer 1

绞尽脑汁一晚上后，我重新做了整个事情，把每一步都写了出来，意识到我的根本问题是我不能调用之前的 collat​​z 方法(因为那个方法计算整个链条，而我需要它停在我已经计算出的数字处)。所以下面是我的解决方案:

def longest_chain2(number)
  cache = { 1 => 1 }
  start_num = 1
  longest = 1
  while start_num < number
    n = start_num
    chain = 0
    while n != 1 && n >= start_num
      if n.even?
        n = n/2
      else
        n = 3*n+1
      end
      chain += 1
    end
    chain += cache[n]
    if chain > longest
      longest = chain
      longest_start = start_num
    end
    cache[start_num] = chain
    start_num += 1
  end
  return longest_start
end

这样，我将添加尚不存在的键，同时调用 cache[n] 的值添加到该点之前的链号。