ruby - Collat​​z 链算法 RUBY

Question

我正在尝试根据 Collat​​z 序列填充一个数组。序列的约束条件如下:

正整数:

n → n/2(n 为偶数)

n → 3n + 1(n 为奇数)

示例输出

3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

理想情况下，我想构建一个递归调用，根据序列的约束填充数组。但是，我相信我的递归调用逻辑是非常有缺陷的。预期的行为是遍历嵌套数组，仅操作每个子数组的最后一个元素，直到元素达到 1。我正在努力加深对递归的理解，如果有任何关于如何解决此问题的建议，我将不胜感激。

def collatzSum(maxNumber)

 sequenceHash = Hash.new(0)
  i = maxNumber
  until i == 0 do 
    if i.even?
      sequenceHash[i] = [(i), (i / 2)]
    elsif i.odd? && i != 1
      sequenceHash[i] = [(i), (3 * i + 1)]
   elsif i == 1 
      sequenceHash[i] = [i]
  end 
    i -= 1
 end
 p sequenceHash

helper_method 递归。方法应接受哈希值并根据 if 语句进行迭代。

=begin 
    desired output
    hash = {5=>[5,16, 8, 4, 2,1],
            4=>[4,2,1],
            3=>[3,10,5,16,8,4,2,1],
            2=>[2,1],
            1=>[1]}
=end 

代码:

 collatzChain = lambda do |k|
  j = 0
  k = j[-1]
   until k == 1 do
      if k.even?
        sequenceHash[k] << (k / 2)
     elsif k.odd?
       sequenceHash[k] << (3 * k + 1)
      end 
    end
  j += 1
end 
collatzChain.call(sequenceHash.values)
sequenceHash
end 

collatzSum(5)

Answer 1

所以你提到你想要一个递归算法，你目前的方法对我来说看起来是迭代的。要递归，您需要使用越来越接近基本条件的值来调用您所在的方法，然后，一旦达到基本条件，您就返回，沿着调用链建立返回值。因此，对于 Collat​​z 序列，递归方法如下所示:

def build_collatz_chain(max_number)
  return_value = [max_number]
  # our base condition is when the number passed in is equal to 1, so
  # when we get 1 as the max_number, we'll return an array looking like
  # [1]
  return return_value if max_number == 1

  if max_number.even?
    # here, with an even max_number, we'll recurse and call our method
    # again, passing in the new max_number, which is the current
    # max_number / 2.
    return_value + build_collatz_chain(max_number / 2)
  else
    # same as above, but we're odd, so we'll recurse with 3 * max_number + 1
    return_value + build_collatz_chain(3 * max_number + 1)
  end
end

现在当我们用 5 的值调用它时，最终会发生的事情是这样的:

call build_collatz_chain(5)
  call build_collatz_chain(16)
    call build_collatz_chain(8)
      call build_collatz_chain(4)
        call build_collatz_chain(2)
          call build_collatz_chain(1)
          We have hit the base condition! return with [1]
        return from 2 with [2, 1]
      return from 4 with [4, 2, 1]
    return from 8 with [8, 4, 2, 1]
  return from 16 with [16, 8, 4, 2, 1]
return from 5 with [5, 16, 8, 4, 2, 1]

因此，现在如果您想要所有数字的哈希值，直到传入的 max_number 以及它们的 Collat​​z 链作为值，您可以使用帮助程序为每个值调用它，直到最大值(这helper 是迭代的，但可以递归...如果您希望它递归，请为查看者练习):

def collatz_sum(max_number)
  { }.tap do |sequence_hash|
    max_number.downto(1) do |i|
      sequence_hash[i] = build_collatz_chain(i)
    end
  end
end

然后当您调用 collat​​z_sum(5) 时，您会返回:

{5=>[5, 16, 8, 4, 2, 1], 4=>[4, 2, 1], 3=>[3, 10, 5, 16, 8, 4, 2, 1], 2=>[2, 1], 1=>[1]}

你的方法是迭代的原因是在 collat​​zChain lambda 中，你正在设置一个值 (j) 然后递增它并循环直到 k 等于 1。这也是一个无限循环，因为您最初将 k 设置为:

j = 0
k = j[-1]

所以 k == 0，然后你迭代直到 k == 1 然后你永远不会更新 k 的值又是。