Итерация по бесконечной последовательности в Ruby

Я пытаюсь решить проблему Project Euler #12:

Последовательность номеров треугольников генерируется путем сложения натуральных чисел. Таким образом, число 7-го треугольника будет 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. Первые десять слагаемых будут:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Перечислим факторы первых семи треугольных чисел:

 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

Мы можем видеть, что 28 - это первое число треугольника, имеющее более пяти делителей. Каково значение первого треугольного числа, имеющего более пятисот делителей?

Вот решение, которое я придумал, используя Ruby:

triangle_number = 1
(2..9_999_999_999_999_999).each do |i|
  triangle_number += i
  num_divisors = 2 # 1 and the number divide the number always so we don't iterate over the entire sequence
  (2..( i/2 + 1 )).each do |j|
    num_divisors += 1 if i % j == 0
  end
  if num_divisors == 500 then
    puts i
    break
  end
end

Я не должен использовать произвольное огромное число, такое как 9_999_999_999_999_999. Было бы лучше, если бы у нас была последовательность Math.INFINITY, как у некоторых функциональных языков. Как я могу генерировать ленивую бесконечную последовательность в Ruby?

Источник

8 ответов

Решение

В Ruby >= 1.9 вы можете создать объект Enumerator, который выдает любую последовательность, которая вам нравится. Вот тот, который дает бесконечную последовательность целых чисел:

#!/usr/bin/ruby1.9

sequence = Enumerator.new do |yielder|
  number = 0
  loop do
    number += 1
    yielder.yield number
  end
end

5.times do
  puts sequence.next
end

# => 1
# => 2
# => 3
# => 4
# => 5

Или же:

sequence.each do |i|
  puts i
  break if i >= 5
end

Программирование Ruby 1.9 (он же "Книга кирки"), 3-е. ред., стр. 83, есть пример перечислителя для треугольных чисел. Должно быть легко изменить перечисленный выше перечислитель для генерации треугольных чисел. Я бы сделал это здесь, но это воспроизвело бы дословный пример, вероятно, больше, чем позволяет "добросовестное использование".

Источник

Несколько ответов близки, но я не вижу никого, кто бы использовал бесконечные диапазоны. Ruby поддерживает их просто отлично.

Inf = Float::INFINITY # Ruby 1.9
Inf = 1.0/0 # Ruby before 1.9
(1..Inf).include?(2305843009213693951)
# => true
(1..Inf).step(7).take(3).inject(&:+)
# => 24.0

В твоем случае

(2..Inf).find {|i| ((2..( i/2 + 1 )).select{|j| i % j == 0}.count+2)==42 }
=> 2880

Ваш метод грубой силы является грубым и может занять очень много времени, чтобы закончить.

Источник

Бесконечность определяется на Float (Ruby 1.9)

a = Float::INFINITY
puts a #=> Infinity
b = -a
puts a*b #=> -Infinity, just toying

1.upto(a) {|x| break if x >10; puts x}
Источник

Текущие версии Ruby поддерживают генераторы:

sequence = 1.step
Источник

В Ruby 2.6 это становится намного проще:

(1..).each {|n| ... }

Источник: https://bugs.ruby-lang.org/issues/12912

Источник

Как сказал Амадан, вы можете использовать замыкания:

triangle = lambda { t = 0; n = 1; lambda{ t += n; n += 1; t } }[]
10.times { puts triangle[] }

Не думаю, что это намного медленнее, чем петля. Вы также можете сохранить состояние в объекте класса, но вам потребуется больше ввода:

class Tri
  def initialize
    @t = 0
    @n = 1
  end

  def next
    @t += n
    @n += 1
    @t
  end
end

t = Tri.new
10.times{ puts t.next }

Добавлено:

Для тех, кто любит longjmps:

require "generator"

tri =
  Generator.new do |g|
    t, n = 0, 1
    loop do
      t += n
      n += 1
      g.yield t
    end
  end

puts (0..19).map{ tri.next }.inspect
Источник

Это было бы лучше всего как простой цикл.

triangle_number = 1
i  = 1
while num_divisors < 500
  i += 1
  triangle_number += i
  # ...
end
puts i
Источник

Основываясь на отличном ответе Уэйна и духе Ruby делать вещи с наименьшим количеством символов, здесь есть немного обновленная версия:

sequence = Enumerator.new { |yielder| 1.step { |num| yielder.yield num } }

Очевидно, не решает исходную проблему Эйлера, но хорош для генерации бесконечной последовательности целых чисел. Определенно работает для Ruby > 2.0. Наслаждайтесь!

Источник

На Рождество 2018 года Руби представила бесконечный ассортимент, предоставив простой новый подход к этой проблеме.

Это реализуется путем пропуска последнего символа из диапазона, например:

(1..)
(1...)
(10..)
(Time.now..)

Или обновить, используя решение Йонаса Эльфстрёма:

(2..).find { |i| ((2..( i / 2 + 1 )).select { |j| i % j == 0 }.count + 2) == 42 }

Надеюсь, что это окажется полезным для кого-то!

Источник

Я считаю, что волокна (добавленные в Ruby 1.9, я считаю) могут быть близки к тому, что вы хотите. Смотрите здесь для получения дополнительной информации или просто поиск рубиновых волокон

Источник
Другие вопросы по тегам