Все возможные продукты

Question

Я пытаюсь найти все возможное произведение двух трехзначных чисел. Когда я работаю с небольшими диапазонами, я могу получить результат за короткий промежуток времени, но когда диапазоны большие, это, кажется, занимает очень много времени. Есть ли способ сократить время получения результата?

Проблема Я работаю на это:

«А палиндромический число читается одинаково в обоих направлениях Крупнейшее палиндром сделан из произведения двух 2-значных чисел 9009 = 91 × 99.

.

Найти самый большой палиндром, изготовленный из продукта двух 3-значных чисел. "

a = [] 
for x in 100..999 
    for y in 100..999 
     num = (x * y) 
     unless a.include? num 
      a.push num 
     end 
    end 
end 

p a 

Answer 1

Глядя на ваш код быстрой оптимизации вам может сделать это использование набора, а не массива для хранения уже вычисленных продуктов.

С a это массив, a.include?(num) должен будет перебирать весь список элементов перед возвратом true/false.

Если a должен был быть установленным, a.include?(num) вернется в сублинейное время.

Пример:

require 'set' 
a = Set.new 
for x in 100..999 
    for y in 100..999 
     num = (x * y) 
     unless a.include? num 
      a.add(num) 
     end 
    end 
end 
puts a.to_a.join(", ") 

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

require 'set' 
a = Set.new 
for x in 100..999 
    for y in 100..999 
     num = (x * y) 
     a.add(num) 
    end 
end 
puts a.to_a.join(", ") 

Answer 2

Это будет вычислить 100 х 101 и 101 х 100 отдельно, даже если они не собираются быть прижаты к массиву, так как они уже в ней.

Я плохо разбираюсь в математике, но, возможно, каждый раз, когда x идет вверх, минимальный диапазон y может повышаться, поскольку тот был только использован? люди, которые лучше разбираются в математике, могут сказать мне, если это начнет пропускать цифры.

z= 100 
for x in 100..999 
    for y in z..999 
     num = (x * y) 
     unless a.include? num 
      a.push num 
     end 
    z = z+1 
    end 
end 

Я думаю, что это может сделать ненужную строку «if a.include? Num».

Answer 3

Что вы действительно пытается сделать, то, что является исходная задача и почему вам нужны все эти продукты?

Вы печатаете каждый из них? Кто-то просит вас составить конкретный список каждого из них?

Если нет, вероятно, лучший способ справиться с этой проблемой. Например, если все, что вы хотели, чтобы проверить, является ли число X будет элементом в «этом списке продуктов», все, что вам придется сделать, это:

range = 100..999 
range.any? { |i| range.include?(x/i) }