ruby - Bignum 太大而无法转换为 'long' (RangeError)

Question

尝试自学 ruby​​ - 我正在用 ruby​​ 解决 Project Euler 问题 14。

n = 1000000
array = Array.new(n,0)
#array[x] will store the number of steps to get to one if a solution has been found and 0 otherwise. x will equal the starting number. array[0] will be nonsensical for these purposes
i = n-1#We will start at array[n-1] and work down to 1
while i > 1
    if array[i] == 0
        numstep = 0 #numstep will hold the number of loops that j makes until it gets to 1 or a number that has already been solved
        j = i
        while j > 1 && (array[j] == 0 || array[j] == nil)
            case j%2
            when 1 # j is odd
                j = 3*j + 1
            when 0 # j is even
                j = j/2
            end
            numstep += 1
        end
        stop = array[j] #if j has been solved, array[j] is the number of steps to j = 1. If j = 1, array[j] = 0
        j = i
        counter = 0
        while j > 1 && (array[j] == 0 || array[j] == nil)
            if j < n
                array[j] = numstep + stop - counter #numstep + stop should equal the solution to the ith number, to get the jth number we subtract counter
            end

            case j%2
            when 1 #j is odd
                j = 3*j+1
            when 0 #j is even
                j = j/2
            end
            counter += 1
        end
    end
    i = i-1
end

puts("The longest Collatz sequence starting below #{n} starts at #{array.each_with_index.max[1]} and is #{array.max} numbers long")

此代码适用于 n = 100000 及以下，但当我达到 n = 1000000 时，它会运行一小段时间(直到 j = 999167 *3 + 1 = 2997502)。当它尝试访问数组的第 2997502 个索引时，它抛出错误

in '[]': bignum too big to convert into 'long' (RangeError) 

第 27 行(while 语句:

while j > 1 && (array[j] == 0 || array[j] == nil)

我怎样才能让它不抛出错误？检查数组是否为零可以节省代码效率，因为它允许您不重新计算已经完成的事情，但是如果我删除了 and 语句，它会运行并给出正确的答案。我很确定问题是数组的索引不能是大数，但也许有一种方法可以声明我的数组，这样它就可以了？我不太关心答案本身；我实际上已经在 C# 中解决了这个问题 - 只是想学习 ruby​​，所以我想知道为什么我的代码这样做(如果我错了为什么)以及如何解决它。

Answer 1

对于在可接受的时间内产生输出的任何输入，上面的代码对我来说运行得很愉快。我相信这是因为您可能会在 32 位架构等方面遇到问题。无论如何，所述问题的解决方案很简单(除非你可能会用完内存，这是另一个可能的故障。)

数组索引是有限的，从你得到的错误中可以看出。太棒了，让我们改用哈希吧!

n = 1000000
array = Hash.new(0)
#array[x] will store the number of steps to get to one if a solution has been found and 0 otherwise. x will equal the starting number. arr
i = n-1#We will start at array[n-1] and work down to 1
while i > 1 
  if array[i].zero?
        numstep = 0 #numstep will hold the number of loops that j makes until it gets to 1 or a number that has already been solved
        j = i 
        while j > 1 && array[j].zero?
            case j%2 
            when 1 # j is odd
                j = 3*j + 1 
            when 0 # j is even
                j = j/2 
            end
            numstep += 1
        end
        stop = array[j] #if j has been solved, array[j] is the number of steps to j = 1. If j = 1, array[j] = 0
        j = i 
        counter = 0 
        while j > 1 && array[j].zero?
            if j < n 
                array[j] = numstep + stop - counter #numstep + stop should equal the solution to the ith number, to get the jth number we 
            end

            case j%2 
            when 1 #j is odd
                j = 3*j+1
            when 0 #j is even
                j = j/2 
            end
            counter += 1
        end
    end 
    i = i-1 
end


puts("Longest Collatz below #{n} @#{array.sort_by(&:first).map(&:last).each_with_index.max[1]} is #{arr

请注意，由于我使用带有初始化程序的散列，array[i] 不能变为 nil，这就是为什么只对零值进行检查的原因。