SMIA

Langage C - Travaux Dirigés n° 2

Exercice n° 1 (Évaluation d'expression)

Que font les fonctions biz1 et biz2 suivantes ?

int biz1(int a)

{

  return a*((a>0)-(a<0 o:p="">

}

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 C_n^p = 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 C_n^p 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 C_n^p=n!/((n-p)!p!). Ceux-ci peuvent être définis par la relation de récurrence suivante : C_n^p =

• 1 si n=p ou p=0
• 0 si p>n
• C_n-1^p+C_n-1^p-1 si 0

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 C_n^p).
• deux tableaux simples de taille N.
• un tableau simple de taille N.