Ruby Project Euler 26, не может придумать ответ на проблему

Question

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

numberWithLargestCycle = 0
largestCycleSize = 0

for i in 1..1000
    for j in 1..i
        if ((10 ** j) % i) == 1

            puts "i is #{i}, j is #{j}, #{(10 ** j) % i}"
            if largestCycleSize < j
                numberWithLargestCycle = i
                largestCycleSize = j
            end
        end
    end
end

puts numberWithLargestCycle

Проблема, которую я пытаюсь решить

Дробная единица содержит 1 в числителе. Десятичный Представление единицы дроби со знаменателями от 2 до 10 Дано:

1/2 = 0,5 1/3 = 0. (3) 1/4 = 0,25 1/5 = 0,2 1/6 = 0,1 (6) 1/7 = 0. (142857) 1/8 = 0,125 1/9 = 0. (1) 1/10 = 0,1 где 0,1 (6) означает 0,166666 ... и имеет повторяющийся цикл из 1 цифры. Видно, что 1/7 имеет 6-значный повторяющийся цикл.

Найти значение d <1000, для которого 1 / d содержит самый длинный повторяющийся цикл в десятичной дроби. </p>

Answer 1

Вот грубый метод вычисления длины повторяющегося десятичного числа любого рационального числа 1/m, m >= 1 с повторяющимся десятичным числом.

Во-первых, 1/m - это завершающий десятичный знак или повторяющийся десятичный знак. Это первое, если и только если главные факторы m равны 2 и / или 5. (См., Например, this Wiki .) Например, 1.0/40 #=> 0.025 является десятичным знаком с конца 40 = 2^3 * 5^1. 2^0 (= 1), 2^1 и 5^1 также имеют конечные десятичные дроби.

require 'prime'

def cycle_length(m)
  return 0 if (Prime.prime_division(m).map(&:first) - [2,5]).empty?
  r = Rational(1,m)
  1.step.find do |n|
    p = (10**n)*r
    p - r == p.to_i.to_r
  end
end

[1,2,3,7,27,40,97].each do |m|
  puts "1/#{m} = #{(1.0/m).round(15).to_s.ljust(17)}: #{cycle_length(m).to_s.rjust(3)}"
end
1/1  = 1.0              :   0
1/2  = 0.5              :   0
1/3  = 0.333333333333333:   1
1/7  = 0.142857142857143:   6
1/27 = 0.037037037037037:   3
1/40 = 0.025            :   0
1/97 = 0.010309278350515:  96

Answer 2

Основная проблема заключается в том, что код не останавливается, когда он фактически находит размер цикла;внутренний цикл for продолжает выполняться.

Я бы настоятельно рекомендовал бы использовать значимые имена переменных, поскольку это делает его более понятным, что на самом деле делает код!Кроме того, переместите неочевидный код (((10 ** j) % i) == 1) в метод, чтобы предотвратить загрязнение «основного» кода сложными деталями реализации.

(На самом деле этот метод не всегда работает должным образом, например,i = 6, но это пока не главный блокатор ...)

Давайте рассмотрим случай, когда вы ищите размер цикла 1/9:

def is_cycle_size?(denominator, cycle_size)
  (10 ** cycle_size) % denominator) == 1
end

denominator = 9
for cycle_size in 1..denominator
  if is_cycle_size?(cycle_size, denominator)
    puts "cycle_size is #{cycle_size}"
  end
end

# Output:
cycle_size is 1
cycle_size is 2
cycle_size is 3
cycle_size is 4
cycle_size is 5
cycle_size is 6
cycle_size is 7
cycle_size is 8
cycle_size is 9

Сейчаспроблема стала более очевидной.Вы на самом деле не хотите перебирать все возможные размеры цикла;вы действительно просто хотите получить размер цикла!

Другими словами, ваша базовая структура кода должна выглядеть следующим образом:

denominator_with_largest_cycle_size = 0
largest_cycle_size = 0

def find_cycle_size(denominator)
  # Define me!!
end

for denominator in 1..1000
  cycle_size = find_cycle_size(denominator)
  puts "denominator is #{denominator}, cycle size is #{cycle_size}"
  if largest_cycle_size < cycle_size
    denominator_with_largest_cycle_size = denominator
    largest_cycle_size = cycle_size
  end
end

(Есть и другие улучшенияэто тоже можно сделать; это только «минимальное» изменение вашей попытки.)

Обратите внимание, что, выполнив это, вы также можете протестировать find_cycle_size в изоляции, например, вы должны иметь возможность запустить find_cycle_size(238487).

---

Бонус: После того, как вы выяснили, как определить вышеописанный метод, этот код рубина можно упростить до:

denominator_with_largest_cycle_size = (1..1000).max_by do |denominator|
  find_cycle_size(denominator)
end