Project Euler 1 слишком медленный с треугольными номерами

Я пытался решить проблему Эйлера Project 1. Я заметил последовательность, которая ведет к более быстрому решению каждого 15-го номера.Project Euler 1 слишком медленный с треугольными номерами

Это код Clojure

(defn fifteenator [n] 
    (* 15 (+ (* (+ 1 n) 3) (* (/ (+ (* n n) n) 2) 7))))

на 15 п равно 0 для 30 п равно 1, и так далее.

Таким образом, я могу рассчитать ближайшее число, делящееся на 15, и выполнить только несколько рекурсивных вычислений. Но все же один из тестов HackerRank истекает. Прежде чем приступить к профилированию кода, я хотел бы убедиться, что мои рассуждения верны. Есть ли более быстрый способ рассчитать его, или я должен научиться профилю Clojure?

источник

2017-02-18 ruby_object

Рассматривали ли вы с помощью [применить] (https://clojuredocs.org/clojure. core/apply) и [filter] (https://clojuredocs.org/clojure.core/filter) вместо этого? – shash678

Вы можете оценить время, завернув оператор в ['time'] (https://clojuredocs.org/clojure.core/time), который печатает время, затраченное на стандартное изложение. –

Несколько советов: 1. Последовательность кратных 'i' до, но не включая' n' is '(range i n i)'. 2. Вы можете использовать '(reduce + ...)' или '(apply + ...)' для суммирования последовательности. 3. Если вы суммируете кратные 3 и 5, вы будете считать кратные 15 дважды. Существуют более быстрые решения с использованием алгебры [арифметических прогрессий] (https://en.wikipedia.org/wiki/Arithmetic_progression#Sum) – Thumbnail

Я не уверен в вашем подходе. Clojure отлично поддерживает диапазоны и фильтры. С этим решением Эйлера 1 не так уж сложно:

(defn euler1 
    [n] 
    (reduce + 
    (filter #(or (= (rem % 5) 0) (= (rem % 3) 0)) (range n))))

Тестирование, если мы получаем правильный результат:

user=> (euler1 10) 
23

источник

2017-03-14 08:01:39 Istvan

Project Euler 1 слишком медленный с треугольными номерами

ответ

Смежные вопросы