Цепной алгоритм Коллатца RUBY

Я пытаюсь заполнить массив в соответствии с последовательностью Коллатца. Ограничения для последовательности следующие:

положительные целые числа:

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)

ruby recursion collatz
person Natasha Kelly    schedule 16.08.2017    source источник
comment
Какая конкретная проблема возникает в настоящее время?   -  person whodini9    schedule 16.08.2017
comment
@ whodini9 рекурсивный вызов не выполняется, вывод застревает на {5 = ›[5, 16], 4 =› [4, 2], 3 = ›[3, 10], 2 =› [2, ​​1], 1 = ›[1]} и, как уже упоминалось, я хотел бы заполнять подмассивы хешей до тех пор, пока последний элемент не станет равным 1   -  person Natasha Kelly    schedule 17.08.2017
comment
Я также попытался реализовать ту же логику с другим подходом: def collatzSum (maxNumber) sequenceHash = Hash.new (0) # взять число # проверить номер по сравнению с последовательностью # заполнить хеш числами из проверки последовательности checkNum = lambda do | п | до n == 1, если n.even? (n / 2) else (n * 3 + 1) end n - = 1 конец конец checkNum.call (maxNumber) sequence = lambda do | i | пока i == 1 не выполните sequenceHash [i] = [checkNum.call (i)] end i - = 1 end sequence.call (maxNumber) end collatzSum (5)   -  person Natasha Kelly    schedule 17.08.2017

Ответы (2)


arrow_upward
2
arrow_downward

Итак, вы упомянули, что вам нужен рекурсивный алгоритм, ваш текущий подход мне кажется итеративным. Чтобы быть рекурсивным, вам нужно вызвать метод, в котором вы находитесь, со значениями, которые все ближе и ближе к базовому условию, а затем, как только вы достигнете базового условия, вы вернетесь обратно, вверх по цепочке вызовов, создав ваши возвращаемые значения. Итак, для последовательности Коллатца рекурсивный подход будет выглядеть так:

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 в качестве значений, вы можете использовать помощник для вызова этого для каждого значения до max (этот помощник является итеративным, но его можно сделать рекурсивным. .. упражнение для зрителя, если вы хотите, чтобы оно было рекурсивным):

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 лямбде, вы устанавливаете значение (j), а затем увеличиваете его и просто выполняете цикл до тех пор, пока k не станет равным 1. Это также бесконечный цикл, потому что вы изначально задали k как:

j = 0
k = j[-1]

и так k == 0, а затем вы выполняете итерацию до k == 1, а затем никогда не обновляете значение k снова.

person Simple Lime    schedule 16.08.2017
comment
это ТОЧНО то, чего я пытался достичь! Спасибо за подробное объяснение - person Natasha Kelly; 17.08.2017

arrow_upward
1
arrow_downward

Неясно, нужна ли здесь рекурсивная операция, поскольку это кажется прямым отображением между значением x и f (x). Переключившись на простой вывод массива, вы можете добиться того, чего хотите:

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