#ruby
#ruby
Вопрос:
Если мы перечислим все натуральные числа ниже 10, кратные 3 или 5, мы получим 3, 5, 6 и 9. Сумма этих кратных равна 23. Найдите сумму всех чисел, кратных 3 или 5, меньше 1000.
def multiples_of(number)
number = number.to_f - 1.0
result = 0
if (number / 5.0) == 1 || (number / 3.0) == 1
return result = result 5.0 3.0
elsif (number % 3).zero? || (number % 5).zero?
result = number
multiples_of(number-1)
else
multiples_of(number-1)
end
return result
end
p multiples_of(10.0)
Мой код возвращает 9.0, а не 23.0.
Комментарии:
1. Слово «рекурсивно» появляется только в названии. Это обязательное условие?
Ответ №1:
Использование основных методов для выбора и суммирования из диапазона
Не совсем ясно, что вы действительно хотите здесь сделать. Это явно домашнее задание, поэтому, вероятно, оно предназначено для того, чтобы заставить вас определенным образом подумать о том, каким будет урок. Если это так, обратитесь к своему плану урока или спросите своего преподавателя.
Тем не менее, если вы ограничиваете набор возможных входных значений целыми числами и используете итерацию, а не рекурсию, вы можете тривиально решить эту проблему, используя Array#select в исключительном диапазоне, а затем вызывая Array#sum для промежуточного результата. Например:
(1...10).select { |i| i.modulo(3).zero? || i.modulo(5).zero? }.sum
#=> 23
(1...1_000).select { |i| i.modulo(3).zero? || i.modulo(5).zero? }.sum
#=> 233168
Оставьте #sum, если хотите увидеть все выбранные значения. Кроме того, вы можете создать свой собственный механизм проверки подлинности, сравнив свою логику с ожидаемым результатом. Например:
def valid_result? range_end, checksum
(1 ... range_end).select do |i|
i.modulo(3).zero? || i.modulo(5).zero?
end.sum.eql? checksum
end
valid_result? 10, 9
#=> false
valid_result? 10, 23
#=> true
valid_result? 1_000, 233_168
#=> true
Комментарии:
1. спасибо Тодду. Это классный ответ для сравнения, которого я никогда не видел
select
раньше. Я пытался решить это рекурсивно, чтобы попрактиковаться в рекурсивном решении моей проблемы
Ответ №2:
В вашем коде есть ряд проблем. Самое главное, вы выполняете рекурсивные вызовы, но вы никоим образом не объединяете их результаты.
Давайте пошагово рассмотрим, что происходит при вводе 10.
Вы присваиваете number = number.to_f - 1.0
, которое будет равно 9.
Затем вы достигаете elsif (number % 3).zero? || (number % 5).zero?
условия, которое является истинным, поэтому вы вызываете result = number
и multiples_of(number-1)
.
Однако вы отбрасываете возвращаемое значение рекурсивного вызова и вызываете return result
независимо ни от чего. Итак, ваша рекурсия не оказывает никакого влияния на возвращаемое значение. И для любого ввода, кроме 3 или 5, вы всегда будете возвращать input-1
возвращаемое значение. Вот почему вы получаете 9.
Вот реализация, которая работает, для сравнения:
def multiples_of(number)
number -= 1
return 0 if number.zero?
if number % 5 == 0 || number % 3 == 0
number multiples_of(number)
else
multiples_of(number)
end
end
puts multiples_of(10)
# => 23
Обратите внимание, что я вызываю multiples_of(number)
вместо multiples_of(number - 1)
, потому что вы уже уменьшаете ввод в первой строке функции. Вам не нужно уменьшать дважды — это заставило бы вас обрабатывать только каждое другое число, например, 9,7,5,3
объяснение
чтобы немного ускорить рекурсию, чтобы помочь вам понять это. Допустим, у нас есть входные данные, равные 4.
Сначала мы уменьшаем входные данные, чтобы число = 3. Затем мы выполняем if number % 5 == 0 || number % 3 == 0
условие, поэтому возвращаем number multiples_of(number)
.
Что multiples_of(number)
возвращает? Теперь мы должны оценить следующий рекурсивный вызов. Мы уменьшаем число, так что теперь у нас есть число = 2. Мы попали в else
блок, так что теперь мы вернемся multiples_of(number)
.
Мы делаем то же самое со следующим рекурсивным вызовом, с числом = 1. Это multiples_of(1)
. Мы уменьшаем входные данные, так что теперь у нас есть число = 0. Это соответствует нашему базовому варианту, так что, наконец, мы закончили с рекурсивными вызовами и можем обработать стек, чтобы выяснить, каково наше фактическое возвращаемое значение.
Для ввода 6
это выглядело бы так:
multiples_of(6)
5 multiples_of(5)
multiples_of(4)
3 multiples_of(3)
multiples_of(2)
multiples_of(1)
multiples_of(0)
0
Комментарии:
1. Спасибо, что нашли время разобраться, где я ошибся. Глядя на ваше решение, я слежу за ним до тех пор, пока не появится переменная для сохранения результата. Я просто не могу понять, как это суммируется. Сохраняется ли возвращаемое значение каждого вызова метода в памяти, а затем суммируется?
2. Блестяще! Спасибо, что разъяснили мне, что имеет смысл.
Ответ №3:
Желаемый результат может быть получен из выражения в замкнутой форме. То есть никаких итераций не требуется.
Предположим, нам дано положительное целое число n
и мы хотим вычислить сумму всех положительных чисел, кратных 3
, которые не превышают n
.
1*3 2*3 ... m*3 = 3*(1 2 ... m)
где
m = n/3
1 2 ... m
является суммой алгоритмического выражения, заданного:
m*(1 m)/2
Поэтому мы можем написать:
def tot(x,n)
m = n/x
x*m*(1 m)/2
end
Например,
tot(3,9) #=> 18 (1*3 2*3 3*3)
tot(3,11) #=> 18
tot(3,12) #=> 30 (18 4*3)
tot(3,17) #=> 45 (30 5*3)
tot(5,9) #=> 5 (1*5)
tot(5,10) #=> 15 (5 2*5)
tot(5,14) #=> 15
tot(5,15) #=> 30 (15 3*5)
Следовательно, сумма чисел, не превышающих n
, кратных 3
s и 5
‘s, определяется следующим образом:
def sum_of_multiples(n)
tot(3,n) tot(5,n) - tot(15,n)
end
- tot(15,n)
необходимо, потому что первые два члена удваивают числа, кратные 15
.
sum_of_multiples(9) #=> 23 (3 6 9 5)
sum_of_multiples(10) #=> 33 (23 2*5)
sum_of_multiples(11) #=> 33
sum_of_multiples(12) #=> 45 (33 4*3)
sum_of_multiples(14) #=> 45
sum_of_multiples(15) #=> 60 (45 3*5)
sum_of_multiples(29) #=> 195
sum_of_multiples(30) #=> 225
sum_of_multiples(1_000) #=> 234168
sum_of_multiples(10_000) #=> 23341668
sum_of_multiples(100_000) #=> 2333416668
sum_of_multiples(1_000_000) #=> 233334166668
Комментарии:
1. Кристиан, я неправильно понял вопрос, поэтому пересмотрел свой ответ.