Exemples de programmation PHP et MySql Dénombrement

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

/*///////////////////////////////////////////////
		Copyright © Jean-Paul Molina
///////////////////////////////////////////////*/

define('FACT_LIMITE', 170);

/*-------------------------------------------------
	fonction factorielle

Entrée :  nombre entier
Sortie  :     n! 
	ou rien si limite système dépassé
-------------------------------------------------*/
function factorielle( $n )
{
	#double $f;
	if ( $n > FACT_LIMITE) return;
	$f = 1;
	while ($n > 1) 
	{
	   $f = $n * $f;
	   $n--;
	}
	return $f;
}
/*--------------------------------------------------
	fonction C

Entrées :   2 nombres entiers
Sortie :   le coefficient du triangle de Pascal
----------------------------------------------------*/
function C( $n , $p )
{
	#double $x;
	if ( $p > ($n >>1)) $p = $n - $p;
	if ($p < 1) return 1;
	elseif  ($n < FACT_LIMITE) $x = ( factorielle( $n ) / (factorielle( $p )*factorielle( $n - $p ) )  );
	else $x = C( $n-1 , $p-1 ) + C( $n-1 , $p );

return $x;
}
?>
<html><body>
<table><tr><td>
<h1>Quelques factorielles</h1>
<?
for ($i=1; $i < 16; $i++) 
{
	$f = factorielle($i);
	echo $i."! = ".$f."<br>";
}
?>
</td>
<td>         </td>
<td valign='top'>
<center><h1>Triangle de Pascal</h1></center>
<?
for ($i=1; $i < 16; $i++) 
{
   for ($j=0; $j < $i+1; $j++) 
	   printf("%d  " , C($i , $j)  );
   echo "<br>";
}
?>
</td></tr></table>
</body></html>

Page de Jean-Paul Molina

Matières

Ressources

Conception assistée

Langages

Flash

Systèmes

Réseaux sociaux

Dénombrement