;; The first three lines of this file were inserted by DrRacket. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-advanced-reader.ss" "lang")((modname binomial) (read-case-sensitive #t) (teachpacks ((lib "valrose.rkt" "installed-teachpacks"))) (htdp-settings #(#t write mixed-fraction #t #t none #f ((lib "valrose.rkt" "installed-teachpacks")))))
;;;
;;; binomial.rkt
;;; Teachpack : valrose.rkt - Langage : Etudiant avance

;;; version recursive du calcul de C(n,p)
;;; http://fr.wikipedia.org/wiki/Coefficient_binomial    --> formule (2)

(define (binomial n p)         ; on suppose 0 <= p <= n
  (if (or (= p n) (= p 0))     ; le bord du triangle de Pascal
      1
      (+ (binomial (- n 1) p) 
         (binomial (- n 1) (- p 1)))))

(printf "\nVersion lente :\n")
(printf "C(6,2) vaut ~a\n" (binomial 6 2))
(printf "Dans un jeu de 32 cartes, il y a ~a mains de 5 cartes.\n" (binomial 32 5))
;(printf "Dans un jeu de 32 cartes, il y a ~a mains de 13 cartes.\n" (binomial 32 13))        ; TROP LENT !!!
(printf "#### Avec des mains de 13 cartes, l'algorithme est trop lent !!!\n")

;;; Bien entendu un calcul par factorielles est plus rapide :

(define (binomial-fast n p)
  (local [(define (interfac a b)   ; a*(a+1)*...*b
            (if (> a b) 1 (* a (interfac (+ a 1) b))))]
    (quotient (interfac (+ (- n p) 1) n)
              (interfac 1 p))))

(printf "\nVersion rapide :\n")
(printf "C(6,2) vaut ~a\n" (binomial-fast 6 2))
(printf "Dans un jeu de 32 cartes, il y a ~a mains de 5 cartes.\n" (binomial-fast 32 5))
(time (printf "Dans un jeu de 32 cartes, il y a ~a mains de 13 cartes.\n" (binomial-fast 32 13)))   ; IMMEDIAT !!!