émilie voila
;
; Question 1 : distribue
;
;;;;;;; Premiere version
(define distribue-v1 ; -> liste (entier, liste)
(lambda (nbgraines lcases) ; entier, liste
(cond ((null? lcases) (list nbgraines lcases))
; liste vide : renvoie le resultat : graine et liste vide
((= 0 nbgraines) (list nbgraines lcases))
; plus de graine : renvoie le resultat : graine a 0 et liste
(else (let ((r (distribue-v1 (- nbgraines 1) (cdr lcases))))
; r : on a distribue nbgraines-1 graines dans le reste de lcases
; r = (nbgraines, liste cases)
; (cadr r) : liste des cases
; (car r) : nb de graines
(list (car r) (cons (+ (car lcases) 1) (cadr r))))))))
; on renvoie le nb de graines obtenue avec r
; pour la liste des cases :
; on ajoute 1 a la premiere case de lcases
; et on met le resultat en tete de la liste de cases de r
;(distribue-v1 5 '(2 3 1 5 5 2))
;(distribue-v1 1 '(2 3 1 5 5 2))
;(distribue-v1 5 '(2 3 1))
;(distribue-v1 5 '())
;;;;;;;;;;; Autre solution avec utilisation d une fonction intermediaire :
; Fonction intermediaire pour distribuer les graines
; qui construit la liste de resultats (liste vide pour le premier appel)
; sous-liste construite avec des cons
; (element mis en tete de la liste a chaque fois)
; il faut donc renverser la sous-liste des cases pour l'avoir dans l ordre
; (utilisation de la fonction reverse)
; On distribue les graines case par case jusqu a
; - ne plus avoir de graine
; - ne plus avoir de cases a traiter
(define distribue-aux ; -> liste (entier, liste)
(lambda (x l res) ; x nb graines (entier), l liste de nbs, res liste de nbs
(cond ((null? l) (list x (reverse res)))
; liste vide : renvoie le resultat : graine et liste resultat
; (qui doit etre renversee)
((= x 0) (list 0 (append (reverse res) l)))
; plus de graine : renvoie le resultat : graine a 0 et liste finale
(else (distribue-aux (- x 1) (cdr l) (cons (+ (car l) 1) res)))
; une graine en moins a distribeur dans le reste de la liste
; ajoute (car l) incremente de un dans la liste resultat
)))
; Distribue les graines dans les cases
; les cases sont donnees sous la forme d'une liste
(define distribue ; -> liste (entier, liste)
(lambda (x l) ; x nb de graines (entier), l liste de nbs
(distribue-aux x l '())))
;(distribue 5 '(2 3 1 5 5 2))
;(distribue 5 '(2 3 1))
;(distribue 5 '())
; ---------------------------------------------------------------------------
;
; Question 2 : vide
;
;;;;;;;;; Premiere version
(define vide-v1 ;-> liste (entier, liste)
(lambda (indicecases listecases)
; n position (entier positif) <= nb d'element de l, l liste de nbs
(if (= 0 indicecases)
; on s interesse a la premiere case de listecases
; on distribue les graines de cette premiere case dans les autres cases
; on obtient r = (nb graines, liste)
; resultat final :
; on doit mettre 0 en tete de la nouvelle liste obtenue avec r
; pour la case videe
(let ((r (distribue (car listecases) (cdr listecases))))
(list (car r) (cons 0 (cadr r))))
; sinon ...
(let ((d (vide-v1 (- indicecases 1) (cdr listecases))))
; vider la n e case de la liste l revient a vider la n-1 e case de cdr l
; d = (entier, liste)
; (car d ) : nb de graine
; (cadr d) : liste des cases
; resultat final : il faut remettre la premiere case
; de listecases en tete de la nouvelle liste de cases de d
(list (car d) (cons (car listecases) (cadr d)))))))
;(vide-v1 1 '(2 3 1 5 5 2))
;(vide-v1 4 '(2 3 1 5 5 2))
;(vide-v1 6 '(2 3 1 5 5 2))
;;;;;;;;;;; Autre solution avec utilisation d une fonction intermediaire :
; Fonction intermediaire pour vider la case de position n
(define vide-aux ;-> liste (entier, liste)
(lambda (n l debut-ligne)
; n position (entier positif) <= nb d'element de l, l liste de nbs
(cond ((= n 1)
; cas ou le premier element de l est la case a traiter
(let* ((restmp (distribue (car l) (cdr l)))
; distribue les graines de (car l) dans le reste de la liste
; restmp : (x, fin-ligne)
(x (car restmp))
; premier element de la liste resultante: nb graines restantes
(fin-ligne (cadr restmp)))
; recupere la liste resultante
(list x (append (reverse debut-ligne) (list 0) fin-ligne))))
; resultat :
; - nb de graines restantes : x
; - il faut renverser le debut de la ligne faite avec des cons
; - 0 pour la position videe
; - liste resultante de la distribution
(else (vide-aux (- n 1) (cdr l) (cons (car l) debut-ligne))))))
; le premier element de l est mis dans la liste resultat
; decremente la position
; ote un element a la liste
; Vide la position n de la liste l en distribuant
; les graines dans les cases suivantes
(define vide ;-> liste (entier, liste)
(lambda (n l) ; n position (entier) <= nb d'element de l, l liste de nbs
(vide-aux n l '())))
;(vide 1 '(2 3 1 5 5 2))
;(vide 4 '(2 3 1 5 5 2))
;(vide 6 '(2 3 1 5 5 2))
;----------------------------------------------------------------------------
;
; Question 3 : prise
;
;;;;;;;; Premiere version
(define prise-v1 ; -> liste (entier , liste d'entiers)
(lambda (l) ; liste de cases
(cond ((null? l) '(0 ())) ; cas de la liste vide
((or (= (car l) 2) (= (car l) 3))
; cas ou la premiere case contient 2 ou 3 graines
(let ((r (prise-v1 (cdr l))))
; r = resultat de la prise sur le reste de la liste des cases
; r = (entier, liste)
(list (+ (car l) (car r)) (cons 0 (cadr r)))))
; resultat final : ajoute le premier element de l a la prise de r
; on doit mettre 0 en tete de la liste obtenue de r
(else (list 0 l))))) ; pas de prise a faire
;;;;;;;;;;; Autre solution avec utilisation d une fonction intermediaire :
; Fonction intermediaire pour la prise des graines
(define prise-aux ; -> liste (entier , liste d'entiers)
(lambda (l gain res)
; l liste des cases (liste d'entiers), entier, liste d'entiers
(cond ((or (null? l) (and (not (eq? (car l) 2)) (not (eq? (car l) 3)) ))
; la liste des cases est vide OU
; le premier element de la liste des cases n'est pas egal a 2 ou 3
; -> on arrete la prise
(list gain (append (reverse res) l)))
; renvoie le resultat
; (doit renverser la liste construite avec des cons)
(else (prise-aux (cdr l) (+ (car l) gain) (cons 0 res))))))
; sinon on continue la prise sur le reste de l
; gain : ajoute le (car l)
; liste des nouvelles cases : met 0 pour la case videe
; Prise des graines des cases comportant 2 ou 3 graines
; Appel initiale de prise-aux avec gain a 0 et liste vide pour les resultats
(define prise ; -> liste (prise (entier) , liste des cases (entiers))
(lambda (l) ; l liste des cases (liste d'entiers)
(prise-aux l 0 '())))
;(prise '(2 3 1 5))
;----------------------------------------------------------------------------
;
; Question 4 : distribue-avec-prise
;
; Fonction intermediaire pour distribue-avec-prise
(define distribue-avec-prise-aux ; ->liste (entier, entier, liste d'entier)
(lambda (x l res) ; x entier, l liste d'entiers, res liste d'entiers
(cond ((null? l) (list x 0 (reverse res)))
; la liste est vide : renvoie les graines restantes, pas de prise, et
; renverse la liste des cases resultats
((= x 0)
; plus de graines a distribuer, on regarde si il y a des prises a faire
(let* ((restmp (prise res))
; Effectue la prise sur la liste des nouvelles cases
; -> restmp = (gain, liste cases)
(gain (car restmp))
; recupere le gain de la prise
(newres (cadr restmp)))
; recupere la listes des nouvelles cases suite a la prise
(list 0 gain (append (reverse newres) l))))
; resultat : graine restante = 0, gain, renverse liste obtenues
(else
(distribue-avec-prise-aux (- x 1) (cdr l) (cons (+ (car l) 1) res))))))
; sinon on continue la distribution avec une graine en moins,
; le reste des cases,
; et la premiere case de la liste a une graine de plus que l'on met
; dans la liste des nouvelles cases
; Distribution des graines avec prise
; Appel fonction intermediaire avec liste vide pour la liste de resultats
(define distribue-avec-prise
; -> liste (nb graines restantes (entier), prise (entier), liste d'entiers)
(lambda (x l) ; x entier (nb de graines), l liste d'entiers
(distribue-avec-prise-aux x l '())))
; (distribue-avec-prise 3 '(2 3 1 5 5 2)) ;-> (0 2 (3 4 0 5 5 2))
;(distribue-avec-prise 3 '(1 1 1 5 5 2)) ;-> (0 6 (0 0 0 5 5 2))
;(distribue-avec-prise 8 '(2 3 1 5 5 2)) ;-> (2 0 (3 4 2 6 6 3))
;(distribue-avec-prise 8 '(1 2 2 1 1 1)) ;-> (2 0 (2 3 3 2 2 2))
;----------------------------------------------------------------------------
;
; Question 5 : joue et tourne
;
; Deroulement pour jouer un coup:
; 1- distribution des graines dans son camp vers la droite
; 2- prolongement en sens contraire dans le camp adverse s'il reste des graines,
; (avec eventuellement prise si arret sur case de 2 ou 3 graines)
; 3- prolongement dans son propre camp s'il reste des graines,
; avec boucle sur 2 et 3
; Fonction pour continuer le coup dans le camp adverse
(define tourne ; -> triplet (l1 liste d'entiers, l2 listes d'entiers, g1 entier)
(lambda (x l1 l2 g1) ;
; x entier (nb de graines a jouer),
; l1 et l2 listes d'entiers, g1 entier (gain du joueur 1)
(let* ((res (distribue-avec-prise x l2))
; distribution avec prise des graines dans la liste l2
; res = (nb graines restantes (entier), prise (entier), liste entiers)
(x2 (car res))
; x2 : nb de graines restantes
(gain (cadr res))
; gain = prise effectuée
(newl2 (caddr res)))
; newl2 = nouvelle ligne de l2
(if (= x2 0)
; Si toutes les graines ont ete distribuees
(list l1 newl2 (+ g1 gain))
; renvoie le resultat : l1, nouvelle liste l2,
; ajoute gain a g1 pour le nouveau gain
(let* ((res (distribue x2 l1))
; sinon, il reste des graines a distribuer
; on les distribue sur la ligne l1 donc sans prise
; res = (nb de graines restantes, liste)
(x1 (car res))
; x1 : nb de graines restantes
(newl1 (cadr res)))
; newl1 : nouvelle ligne de l1
(if (= x1 0)
; Si toutes les graines ont ete disribuees
(list newl1 newl2 g1)
; renvoie le resultat : nouvelles lignes l1 et l2, gain g1
(tourne x1 newl1 newl2 g1)))))))
; sinon il reste des graines a distribuer, on continue sur l2
; Fonction pour jouer un coup
(define joue
; -> triplet (l1 liste d'entiers, l2 listes d'entiers, g1 entier)
(lambda (n1 l1 l2 g1)
; n1 entier (indice de la case a jouer : 1 Ã 6),
; l1 et l2 listes d'entiers,
; g1 entier (gain du joueur 1)
(let* ((res (vide n1 l1))
; 1- distribution des graines dans la liste de l1
; -> res = (graine restante, liste de l1)
; (il faut vider la case sur laquelle on joue,
; puis distribuer les graines)
(x (car res))
; x = graine restant à distribuer
(newl1 (cadr res)))
; newl1 : nouvelle liste des cases de l1
(if (= x 0)
; Si toutes les graines ont ete distribuees
(list newl1 l2 g1)
; pas de prise car on s'est arrete dans son camp
; renvoie la nouvelle liste l1, l2 et g1
(tourne x newl1 l2 g1)))))
; Sinon 2 - on continue avec le restant de graines,
; et la nouvelle liste de l1
; et on va les distribuer sur l2
;(joue 2 '(4 4 4 4 4 4) '(4 4 4 4 4 4) 0)
;(joue 6 '(1 3 4 3 2 4) '(4 1 2 2 4 4) 0)
;(joue 6 '(1 1 4 3 2
'(4 1 2 2 4 4) 0)