Nécéssaire pour les exercices

#include <stdio.h>

/*
This program print ``Hello world’’
*/
int main(int argc, char *argv[])
{
    printf("Hello world\n");
    return 0;
}
  • Compiler example-01.c en un exécutable example-01 : cc -std=c99 -Wall -o example-01 example-01.c (vous pouvez aussi remplacer -Wall par -Werror)
  • Lancer l’exécutable example-01 : ./example-01
  • Afficher un nombre contenu dans la variable entière a puis aller à la ligne : printf("%d\n", a);

Exercice 0

  1. Copiez/coller un des exemples ci-dessus, dans un fichier (par exemple: ex-0.c)
  2. Compilez le avec cc
  3. Testez le !

Le second exemple contient des if pour les tests et des while pour les boucles (tant que). Seules ces deux formes doivent êtres utilisées dans cette feuille de td.

Exercice 1

On souhaite écrire une fonction qui calcule le PGCD (plus grand commun diviseur) de deux nombres entiers. Pour cela on rappelle l’algorithme d’Euclide: \(pgcd(a,0) = a\) et pour \(b \not= 0 \Rightarrow pgcd(a,b) = pgcd(b, a~mod~b)\)

  1. Écrivez la fonction pgcd_rec qui implémente l’algorithme d’Euclide de façon récursive.
  2. Testez votre fonction en écrivant un main. Pensez à tester plusieurs cas.
  3. Écrivez la fonction pgcd_iter qui implémente l’algorithme d’Euclide sans récursion.
  4. Testez votre fonction.

Manipulation de tableaux d’entiers

Le but de ces exercices est de se familiariser avec le C et les tableaux.

Exercice 2

  1. Écrivez une fonction qui affiche le tableau d’entiers qui lui est passé en paramètre.
  2. Testez votre fonction en écrivant une fonction main() qui affiche un tableau de littéraux (i.e., constantes écrites en dur dans le code).
  3. Écrivez une fonction qui rempli un tableau par les n premiers nombres pairs. Comment est-il possible de communiquer le résultat à la fonction appelante ?
  4. Teste la en modifiant votre main.

Exercice 3

Écrivez une fonction main() permettant de tester les fonctions au fur et à mesure que vous les écrivez. Vous vous servirez des fonctions écrites précédemment pour saisir et afficher les tableaux d’entiers. Cette remarque est valable pour tous les exercices à venir !

  1. Écrivez une fonction qui calcule la somme des éléments d’un tableau.
  2. Écrivez une fonction qui calcule le produit scalaire de deux tableaux d’entiers.
  3. Écrivez une fonction qui calcule la somme de deux tableaux d’entiers membre à membre.

Exercice 4

  1. Écrire une fonction qui, étant donné un tableau, retourne 1 s’il est trié par ordre croissant, 0 sinon.
  2. Écrire une fonction qui, étant donnés un tableau et un entier, retourne 1 si l’entier se trouve dans le tableau et 0 sinon.
  3. Écrire une nouvelle fonction qui utilise les mêmes paramètres et rend le même service, mais suppose en plus que le tableau est trié afin d’effectuer la recherche plus rapidement (recherche par dichotomie). (On considèrera que le tableau est trié, ne pas le trier vous même.)
    • Et s’il n’était pas trié, quel serait le résultat ? Essayez pour voir.
  4. Bonus Écrire la recherche dichotomique par récursion.

Exercice 5

Le triangle de Pascal est constitué des coefficients binomiaux :

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
...

Une façon aisée de calculer ce triangle est de constater qu’une ligne se déduit de la précédente avec la formule suivante :

\[C^{k}_{n+1} = C^{k-1}_{n} + C^{k}_{n}\]
  1. Écrire une fonction qui calcule la ligne \(n\) en fonction de la ligne \(n - 1\) en n’utilisant qu’un seul tableau, i.e., void pascal_ligne(int n, int valeurs[]);, où valeurs contient déjà les valeurs de la ligne précédente.
  2. Écrire la fonction affiche_pascal qui affiche les \(n\) premières lignes du triangle de pascal.
  3. Bonus Modifiez votre main pour que \(n\) soit passé en paramètre sur la ligne de commande. Attention aux erreurs d’utilisations.

Exercice 6

\[fibo(x) = \left\{ \begin{array}{rcr} 0 & si~x < 1 \\ 1 & si~x = 1 \\ fibo(n - 1) + fibo(n - 2) & si~x > 1\\ \end{array} \right.\]
  1. Écrire la fonction fibo_rec qui calcule récursivement le \(i\)ème terme de la suite de fibonnaci en fonction des termes \(i - 1\) et \(i - 2\)
  2. Testez votre fonction en écrivant un main. Pensez à tester plusieurs cas.
  3. Écrire la fonction fibo_iter qui calcule itérativement le \(i\)ème terme de la suite et le stocke dans un tableau (mémoïsation).
  4. Comparer la différence de vitesse entre les deux fonctions.
  5. Finalement a-t-on besoin d’un tableau ? S’en passer. (Bonus)

Exercice 7 (Bonus)

  1. Implémentez le crible d’Eratosthène en C. Cette fonction remplira un tableau de booléens passé en paramètre.
  2. Modifiez cette fonction pour qu’elle retourne le nombre d’accès au tableau.
  3. Écrivez un programme qui utilise cette fonction pour afficher le nombre d’opérations nécessaire pour un tableau de taille 10000, 20000, 30000, … Puis passer cette sortie à gnuplot.
    • Pour cela afficher dans votre programme sur chaque ligne un couple valeur resultat (mettez une tabulation \t à la place d’un espace, c’est plus joli).
    • “Rediriger” l’affichage de votre programme dans un fichier : ./monprogramme > resultat.dat
    • Lancer gnuplot et taper plot 'resultat.dat' with lines

Exercice 8 (Bonus)

  1. Trier le tableau d’entier passé en paramètre avec l’algorithme tri à bulle
  2. Modifier les deux fonctions de recherches de l’exercice 3 pour compter qu’elles comptent le nombre de comparaisons qu’elles effectuent
  3. Construire des grands tableaux aléatoirement (rand()) et dessiner avec gnuplot la courbe pour sort et les deux recherches