Subscribe RSS

Posts Tagged ‘projet Euler’

Projet Euler avec Clojure (1)

août 26th, 2009 by fmn | No Comments | Filed in Enseignement

L’énoncé du premier problème du Projet Euler est :

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

Il s’agit donc de calculer la somme des multiples de 3 ou 5 inférieurs (strictement) à 1000.

Une première solution naïve, consiste à parcourir tous les entiers de 0 à 999, ne retenir que les multiples de 3 ou 5, puis de sommer les nombres restants :

(def sum #(reduce + %))

(defn euler1-a []
  (sum (filter #(or (zero? (rem % 3))
                    (zero? (rem % 5)))
               (range 1000))))

La valeur calculée est :

user> (euler1a)
233168

qui est la bonne réponse.

Cette solution a l’avantage de la lisibilité : elle est la traduction directe du problème en programme. Cependant elle n’est pas efficace en terme de temps de calcul. Tous les nombres inférieurs à 1000 sont parcouru, y compris ceux qui ne sont multiples ni de 3, ni de 5. Il serait donc plus efficace de ne considérer que les multiples intéressants.

Une seconde solution vient lorsque l’on voit qu’une séquence des multiples de 3 est obtenue avec :

(range 0 1000 5)

Il suffit donc de d’additionner les multiples de 3 et de 5 :

user> (+ (sum (range 0 1000 3))
         (sum (range 0 1000 5)))
266333

Le résultat obtenu est faux. En effet certains nombre apparaissent dans les deux séquences de multiples : tous les nombres ayant 3 et 5 comme multiples communs. Voici les multiples communs inférieurs à 100 :

user> (intersection (set (range 0 100 3)) (set (range 0 100 5)))
#{0 75 45 15 90 60 30}

Il ne s’agit en fait que des multiples de 15 (i.e. 3 * 5). Pour obtenir le bon résultat, il s’agit donc de retrancher la somme des multiples de 15 de la somme initiale :

(defn euler1-b []
  (+ (sum (range 0 1000 3))
     (sum (range 0 1000 5))
     (- (sum (range 0 1000 15)))))

Cette fois ci le résultat est le bon :

user> (euler1b)
233168

Pour s’amuser un peu, voici une solution itérative qui ne considère que les multiples différents de 3 et 5. L’idée est d’avoir deux compteurs, un pour les multiples de 3 et un second pour les multiples de 5. A chaque itération, un seul des deux compteurs est incrémenté (de 3 pour celui des multiples de 3 et de 5 pour celui des multiples de 5) et la valeur de ce compteur est ajoutée à la somme finale :

(defn euler1-c []
  (loop [x3 0
         x5 0
         s 0]
    (let [x3+ (+ 3 x3)
          x5+ (+ 5 x5)]
      (if (or (< x3+ 1000)
              (< x5+ 1000))
        (cond
          (= x3+ x5+) (recur x3+ x5+ (+ x3+ s))
          (< x3+ x5+) (recur x3+ x5 (+ x3+ s))
          :else (recur x3 x5+ (+ x5+ s)))
        s))))

A chaque itération, le choix du compteur est réalisée en retenant le plus petit des deux. Par exemple si x3 vaut 9 et x5 vaut 10, alors x3+ vaut 12 et x5+ vaut 15. Dans ce cas, c’est x3 qui est incrémenté. Si les deux compteurs sont égaux, les deux sont incrémenté pour ne pas prendre en compte deux fois le même nombre. La valeur calculée est juste :

user> (euler1c)
233168

Voici une petite comparaison des temps de calculs basée sur la répétition de 1000 appels de chaque fonction :

user> (defmacro timex [n stuff]
        `(time (dotimes [x# ~n]
                 ~stuff)))
#'user/timex
user> (timex 1000 (euler1-a))
"Elapsed time: 2270.722148 msecs"
nil
user> (timex 1000 (euler1-b))
"Elapsed time: 1337.681488 msecs"
nil
user> (timex 1000 (euler1-c))
"Elapsed time: 534.767148 msecs"
nil

La fonction euler1-c qui ne considère que les multiples différents de 3 et de 5 est clairement la plus rapide. Par contre elle est loin d’être la plus claire. Comme souvent, c’est une affaire de compromis.

FMN.

Wikio
Wikio

Tags: , ,