Bignum trop grand pour être converti en 'long' (RangeError)

Question

Essayer de m'enseigner ruby ​​- Je travaille sur le projet Euler problème 14 en rubis.

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") 

Ce code fonctionne bien pour n = 100000 et au-dessous, mais quand je vais jusqu'à n = 1000000, il fonctionne pendant une courte période (jusqu'à ce que j = 999167 * 3 + 1 = 2997502). Quand il essaie accéder à l'index de 2997502th du tableau, il jette l'erreur

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

sur la ligne 27 (qui est l'instruction while:

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

Comment puis-je obtenir ce pour ne pas jeter une erreur Vérification? si le tableau est à zéro, cela économise l'efficacité du code, car cela vous permet de ne pas recalculer quelque chose qui a déjà été fait, mais si je supprime l'instruction et, elle s'exécute et donne la bonne réponse. un tableau ne peut pas être un bignum, mais peut-être y a-t-il un moyen de déclarer mon tableau de telle sorte qu'il peut être? Je ne me soucie pas beaucoup de la réponse elle-même, j'ai déjà s J'ai essayé cela en C# - j'essayais juste d'apprendre le rubis, donc j'aimerais savoir pourquoi mon code le fait (si je me trompe) et comment le réparer.

Answer 1

Le code ci-dessus fonctionne avec bonheur pour toute entrée produisant une sortie dans un temps acceptable. Je crois que c'est parce que vous pourriez rencontrer des problèmes étant sur l'arche 32bits, ou comme. Quoi qu'il en soit, la solution du problème énoncé serait simple (à moins que vous ne manquiez de mémoire, ce qui est un autre problème possible.)

Les index de tableau sont limités, comme il ressort de l'erreur que vous avez eue. Cool, utilisons plutôt le hachage!

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 

S'il vous plaît noter que, puisque je le hachage avec initialiseur, array[i] ne peut pas devenir nil, c'est la raison pour laquelle le contrôle est fait pour zéro uniquement les valeurs.