Leçon pratique sur la programmation

Que font les fonctions biz1 et biz2 suivantes ?

int biz1(int a)

{

return a*((a>0)-(a<0));

}

int biz2(int a, int b)

{

if (a+=b)

return a;

return b;

}

Exercice n° 2 (Fonction factorielle)

Écrire une fonction fact calculant n!. Cette fonction prendra en paramètre l'entier et retourna la valeur entière n!. On rappelle que n! = n(n-1)(n-2) ··· 2. Pour quelles valeurs de n la fonction fact donne-t-elle un résultat correcte ?

Exercice n° 3

Écrire une fonction maxfact qui pour un entier k donné en paramètre calcule le plus grand entier n tel que n! ≤ k. Peut on améliorer la complexité de cette fonction ?

Exercice n° 4 (Coefficients binômiaux)

Utiliser la fonction fact de l'exercice précédent pour écrire une fonction binome qui calcule les coefficients du binômes Cnp = n!/((n-p)!p!). Quelle est la complexité de cette fonction ? Quelle est la valeur maximale calculable ? Proposer d'autres méthodes (non récursives) plus économiques et permettant de calculer des valeurs de Cnp beaucoup plus grandes.

Exercice n° 5 (Écriture binaire)

Écrire une fonction binaire qui prend en paramètre un entier et qui affiche son écriture binaire (en base 2).

Exercice n° 6 (Triangle de Pascal)

On s'intéresse encore aux coefficients du binôme Cnp=n!/((n-p)!p!). Ceux-ci peuvent être définis par la relation de récurrence suivante : Cnp =

1 si n=p ou p=0

0 si p>n

Cn-1p+Cn-1p-1 si 0<p<n

On veut afficher le triangle de Pascal complet jusqu'à l'ordre N. Résoudre ce problème en utilisant chacune des trois structures suivantes :

un tableau à deux dimensions de taille N x N (T[n][p] contient Cnp).

deux tableaux simples de taille N.

un tableau simple de taille N.

...