Collatz 链算法 RUBY

Question

我正在尝试根据 Collatz 序列填充一个数组。序列的约束条件如下：

正整数：

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

所以你提到你想要一个递归算法，你当前的方法在我看来是迭代的。要递归，您需要使用越来越接近基本条件的值来调用您所在的方法，然后，一旦达到基本条件，您 return 退出，沿着调用链构建您的 return 值。因此，对于 Collatz 序列，递归方法如下所示：

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 以及它们的 Collatz 链作为值，你可以使用一个助手来为每个值调用它，直到最大值（这个助手是迭代的，但可以递归...如果你想让它递归，为观众练习）：

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

然后当您调用 collatz_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]}

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

j = 0
k = j[-1]

等等 k == 0，然后你迭代直到 k == 1，然后你再也不会更新 k 的值。

Answer 2

不清楚这里是否需要递归操作，因为这似乎是值 x 和 f(x)[=15 之间的直接映射=].通过切换到简单的数组输出，您可以通过以下方式实现您想要的：

def collatz_sum(max) (2..max).map do |i| [ i, if (i.even?) i / 2 else 3 * i + 1 end ] end.reverse + [ [ 1 ] ] end

Collatz 链算法 RUBY

Collatz Chain Algorithm RUBY

ruby

recursion

collatz

Collat​​z 链算法 RUBY

Collatz Chain Algorithm RUBY

ruby

recursion

collatz

Collatz 链算法 RUBY