Dénombrement

 

ou comment exploser le CPU ... en temps normal

L'objectif est de créer une fonction factorielle et les coefficients du binôme de Newton. Ceux-ci sont utilisés dans les séries entières, les développements de Taylor, ...

Compte-tenu des grandes valeurs susceptibles d'être atteintes par les factorielles, on pourra ainsi voir les limites des types de variables.

Rappels théoriques

Coefficient du binôme :

binome de Newton

Si n dépasse la limite (imposée par le système informatique), on utilise la récursivité grâce à

binome de Newton

La seconde permet de limiter les appels récursifs.
On définira une constante FACT_LIMITE en fonction du système.

Algorithmes

fonction factorielle( n )
          si ( n > FACT_LIMITE) sort de la fonction
          f ← 1
          tant que ( n > 1) faire
          #1
                    f ← n * f
                    n ← n-1
          1#
          retourne f

fonction C( n , p )
          si (p>n/2) alors p ← n-p
          si (p<1) x ← 1
          sinon
          si (n < FACT_LIMITE) x ← factorielle( n ) / ( factorielle( p ) * factorielle( n-p )
          sinon
          x ← C( n-1 , p-1 ) + C( n-1 , p )
          retourne x

Traduction en php

 


Si vous aimez le site

 

Select a language if you need :


Page chargée en 0.003 sec.

Dernière Modification : Mer 25 Janvier 2017 8:56
Copyright © 1999-2017 Jean-Paul Molina Tous droits réservés.

vers Google