voici l'algorithme en lisp
Code : Tout sélectionner
(defun compare-groups (group1 group2)
"Compare deux groupes de boules sur une balance.
Retourne : 'equal si les groupes sont équilibrés,
'left si le premier groupe est plus lourd,
'right si le second groupe est plus lourd."
(cond ((= (reduce #'+ group1) (reduce #'+ group2)) 'equal)
((> (reduce #'+ group1) (reduce #'+ group2)) 'left)
(t 'right)))
(defun find-fake-ball (balls)
"Trouve la boule fausse parmi 12 boules avec 3 pesées.
Les boules sont représentées par une liste de 12 éléments : 1 pour une boule vraie,
0.9 pour une boule plus légère et 1.1 pour une boule plus lourde."
(let* ((group1 (subseq balls 0 4)) ; A, B, C, D
(group2 (subseq balls 4 8)) ; E, F, G, H
(group3 (subseq balls 8 12)) ; I, J, K, L
(first-weigh (compare-groups group1 group2)))
;; Première pesée : A,B,C,D contre E,F,G,H
(cond
;; Cas 1: Équilibre (les boules A à H sont équilibrées, la boule différente est parmi I, J, K, L)
((eq first-weigh 'equal)
(let ((second-weigh (compare-groups (subseq balls 0 3) ; A, B, C
(subseq balls 8 11)))) ; I, J, K
(cond
((eq second-weigh 'equal)
(let ((third-weigh (compare-groups (list (nth 11 balls)) (list (nth 0 balls))))) ; L contre A
(cond
((eq third-weigh 'equal) "IMPOSSIBLE")
((eq third-weigh 'left) "L est plus lourde")
(t "L est plus légère"))))
((eq second-weigh 'left)
(let ((third-weigh (compare-groups (list (nth 8 balls)) (list (nth 9 balls))))) ; I contre J
(cond
((eq third-weigh 'equal) "K est plus légère")
((eq third-weigh 'left) "J est plus légère")
(t "I est plus légère"))))
(t
(let ((third-weigh (compare-groups (list (nth 8 balls)) (list (nth 9 balls))))) ; I contre J
(cond
((eq third-weigh 'equal) "K est plus lourde")
((eq third-weigh 'left) "I est plus lourde")
(t "J est plus lourde")))))))
;; Cas 2: Côté gauche (A,B,C,D) plus bas
((eq first-weigh 'left)
(let ((second-weigh (compare-groups (list (nth 0 balls) (nth 1 balls) (nth 4 balls)) ; A, B, E
(list (nth 2 balls) (nth 5 balls) (nth 8 balls))))) ; C, F, I
(cond
((eq second-weigh 'equal)
(let ((third-weigh (compare-groups (list (nth 6 balls)) (list (nth 7 balls))))) ; G contre H
(cond
((eq third-weigh 'equal) "D est plus lourde")
((eq third-weigh 'left) "H est plus légère")
(t "G est plus légère"))))
((eq second-weigh 'left)
(let ((third-weigh (compare-groups (list (nth 0 balls)) (list (nth 1 balls))))) ; A contre B
(cond
((eq third-weigh 'equal) "F est plus légère")
((eq third-weigh 'left) "A est plus lourde")
(t "B est plus lourde"))))
(t
(let ((third-weigh (compare-groups (list (nth 2 balls)) (list (nth 8 balls))))) ; C contre I
(cond
((eq third-weigh 'equal) "E est plus légère")
((eq third-weigh 'left) "C est plus lourde")
(t "IMPOSSIBLE")))))))
;; Cas 3: Côté droit (E,F,G,H) plus bas
(t
(let ((second-weigh (compare-groups (list (nth 0 balls) (nth 1 balls) (nth 4 balls)) ; A, B, E
(list (nth 2 balls) (nth 5 balls) (nth 8 balls))))) ; C, F, I
(cond
((eq second-weigh 'equal)
(let ((third-weigh (compare-groups (list (nth 6 balls)) (list (nth 7 balls))))) ; G contre H
(cond
((eq third-weigh 'equal) "D est plus légère")
((eq third-weigh 'left) "G est plus lourde")
(t "H est plus lourde"))))
((eq second-weigh 'left)
(let ((third-weigh (compare-groups (list (nth 2 balls)) (list (nth 8 balls))))) ; C contre I
(cond
((eq third-weigh 'equal) "E est plus lourde")
((eq third-weigh 'left) "C est plus légère")
(t "IMPOSSIBLE"))))
(t
(let ((third-weigh (compare-groups (list (nth 0 balls)) (list (nth 1 balls))))) ; A contre B
(cond
((eq third-weigh 'equal) "F est plus lourde")
((eq third-weigh 'left) "B est plus légère")
(t "A est plus légère"))))))))))
;; exemple
(let ((balls '(1 1 1 1 0.9 1 1 1 1 1 1 1))) (find-fake-ball balls))