10

我正在尝试解决 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 是第一个有五个以上除数的三角形数。第一个有超过 500 个除数的三角形数的值是多少？

这是我使用 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 中生成惰性无限序列？

4

10 回答 10

11

几个答案很接近，但我实际上没有看到任何人使用无限范围。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

您的蛮力方法很粗糙，可能需要很长时间才能完成。

于 2011-06-16T15:08:21.873 回答
10

在 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

或者：

sequence.take(5).each { |i| puts i }

Programming Ruby 1.9（又名“The Pickaxe Book”），第 3 期。编，页。83，有一个用于三角数的枚举器的例子。修改上面的 Enumerator 以生成三角数应该很容易。我会在这里做，但这会逐字复制示例，可能超过“合理使用”允许的范围。

于 2011-06-16T14:31:43.663 回答
7

无穷大是在 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}
于 2011-06-16T14:47:12.080 回答
6

当前版本的 Ruby 大量支持生成器：

sequence = 1.step
于 2016-08-16T09:55:23.433 回答
4

在 Ruby 2.6 中，这变得容易多了：

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

来源：https ://bugs.ruby-lang.org/issues/12912

于 2018-12-20T14:50:14.200 回答
3

这最好是一个简单的循环。

triangle_number = 1
i  = 1
while num_divisors < 500
  i += 1
  triangle_number += i
  # ...
end
puts i
于 2011-06-16T14:19:48.667 回答
3

正如 Amadan 提到的，您可以使用闭包：

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
于 2011-06-16T14:38:00.467 回答
2

基于 Wayne 的出色回答和 Ruby 用最少字符做事的精神，这里有一个稍微更新的版本：

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

显然，它不能解决原始的欧拉问题，但有利于生成无限的整数序列。绝对适用于 Ruby > 2.0。享受！

于 2015-10-12T05:36:40.467 回答
2

在 2018 年圣诞节，Ruby 引入了无限范围，为这个问题提供了一种简单的新方法。

这是通过省略范围中的最后一个字符来实现的，例如：

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

或者使用 Jonas Elfström 的解决方案进行更新：

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

希望这对某人有用！

于 2019-01-03T18:04:42.360 回答
1

我相信纤维（我相信是在 Ruby 1.9 中添加的）可能接近你想要的。请参阅此处获取一些信息或仅搜索 Ruby Fibers

于 2011-06-16T14:50:05.237 回答