Лихрелые числа

Question

Прежде всего, для тех из вас, кто не знает (или забыл) о числах Лихреля, есть запись из Википедии: http://en.wikipedia.org/wiki/Lychrel_number.

Я хочу реализовать детектор числа Лихреля вдиапазон от 0 до 10_000.Вот мое решение:

class Integer

  # Return a reversed integer number, e.g.:
  # 
  #   1632.reverse #=> 2361
  #
  def reverse
    self.to_s.reverse.to_i
  end

  # Check, whether given number
  # is the Lychrel number or not.
  #
  def lychrel?(depth=30)
    if depth == 0
      return true
    elsif self == self.reverse and depth != 30 # [1]
      return false
    end
    # In case both statements are false, try
    # recursive "reverse and add" again.
    (self + self.reverse).lychrel?(depth-1)
  end
end

puts (0..10000).find_all(&:lychrel?)

Проблема с этим кодом - значение глубины [1].Таким образом, в основном, глубина - это значение, которое определяет, сколько раз нам нужно пройти через итерационный процесс, чтобы быть уверенным, что текущее число действительно является числом Лихрелла.Значение по умолчанию составляет 30 итераций, но я хочу добавить больше широты, чтобы программист мог указать свою собственную глубину через параметр метода.30 итераций идеально подходят для такого небольшого диапазона, который мне нужен, но если я хочу охватить все натуральные числа, я должен быть более гибким.

Из-за рекурсии, которая занимает место в Integer # lychrel?Я не могу быть проворным.Если бы я предоставил аргумент для lychrel?, не было бы никаких изменений из-за оператора [1].

Итак, мой вопрос звучит так: «Как мне реорганизовать мой метод,так он будет правильно принимать параметры? ".

Answer 1

То, что у вас есть, известно как хвостовая рекурсия .Обычно это можно переписать в виде цикла, чтобы избавиться от рекурсивного вызова и устранить риск нехватки места в стеке.Попробуйте что-то вроде этого:

def lychrel?(depth=30)
    val = self
    first_iteration = true

    while depth > 0 do
        # Return false if the number has become a palindrome,
        #   but allow a palindrome as input
        if first_iteration
            first_iteration = false
        else
            if val == val.reverse
                return false
        end

        # Perform next iteration
        val = (val + val.reverse)
        depth = depth - 1
    end
    return true
  end

У меня не установлен Ruby на этом компьютере, поэтому я не могу проверить, правильно ли это на 100%, но вы поняли идею.Кроме того, я предполагаю, что цель бита and depth != 30 - предоставить палиндром в качестве входных данных без немедленного возврата false.

Зацикливая, вы можете использовать переменную состояния, такую ​​как first_iteration чтобы отслеживать, нужно ли вам проверять val == val.reverse.В рекурсивном решении ограничения области видимости не позволяют легко отслеживать это (вам нужно добавить еще один параметр функции и передать переменную состояния каждому рекурсивному вызову по очереди).

Answer 2

Более чистое и похожее на рубин решение:

class Integer

  def reverse
    self.to_s.reverse.to_i
  end

  def lychrel?(depth=50)
    n = self
    depth.times do |i|
      r = n.reverse
      return false if i > 0 and n == r
      n += r
    end
    true
  end

end

puts (0...10000).find_all(&:lychrel?) #=> 249 numbers

Answer 3

Решение

bta с некоторыми исправлениями:

class Integer

  def reverse
    self.to_s.reverse.to_i
  end

  def lychrel?(depth=30)
    this = self
    first_iteration = true

    begin
      if first_iteration
        first_iteration = false
      elsif this == this.reverse
        return false
      end

      this += this.reverse
      depth -= 1
    end while depth > 0

    return true
  end
end

puts (1..10000).find_all { |num| num.lychrel?(255) }

Не так быстро, но работает:

code/practice/ruby% time ruby lychrel.rb > /dev/null 
ruby lychrel.rb > /dev/null  1.14s user 0.00s system 99% cpu 1.150 total