Cet examen dure 2 heures.
A la fin de l’examen, vous devrez créer une archive contenant tous les fichiers sources que vous avez écrits (.c, .h). Le nom de cette archive devra avoir la structure nom_prenom.zip
(ou .tgz selon l’outil d’archivage que vous utilisez). Par exemple, Laura Croft nommera son archive laura_croft.zip
. Avec l’outil zip, la commande serait
zip -r laura_croft.zip nom_du_dossier_a_zipper
Cette archive est à soumettre deux fois, comme suivant :
(sur papier)
L’objectif est de réussir à chiffrer et déchiffrer un message avec une méthode relativement simple appelée le code de César. L’idée est de décaler les lettres de l’alphabet. Imaginons que nous utilisions un décalage de 4 lettres, alors le a
devient un e
, le b
un f
, le c
un g
etc. et le z
un d
.
Ecrivez une fonction encode qui encode une chaîne de caractères avec la méthode expliquée en introduction. Cette fonction prendra en argument :
Exemple :
encode("bonjour", 4) renvoie "fsrnsyv"
encode("voiture", 6) renvoie "buozaxk"
Ecrivez une fonction main qui permettra de récupérer 2 arguments qui seront passés en ligne de commande :
Votre programme devra afficher :
Ecrivez un fonction decode et qui permettra de déchiffrer un message codé. Cette fonction prendra en argument :
Complétez votre fonction main pour qu’elle affiche également la chaîne décodée.
Profitez-en pour vérifier que votre algorithme fonctionne bien.
On définit un polynôme comme une fonction de la forme : .
Nous souhaitons implémenter une bibliothèque de gestion de polynômes. Les polynômes sont à stocker dans la structure suivante :
struct polynom {
int degree;
float *coefficients;
};
Cette structure contient un pointeur vers un tableau de flottants pour stocker les coefficients du polynômes (i.e., les ) et un entier pour stocker le degré de (i.e., la valeur de ).
Implémentez une fonction struct polynom* create_polynom(int degree, float *coefficients*)
qui alloue de la mémoire pour stocker un polynôme de degré degree
dont les coefficients sont ceux du tableau coefficients
. Le premier élément de coefficients
est le coefficient de degré 0 (), le deuxième élément est celui de degré 1 (), etc.
Cette fonction retourne un pointeur vers la zone mémoire allouée.
Implémentez une fonction float random_float(float max)
qui retourne un flottant aléatoire dans l’intervalle .
Astuce : générez un nombre aléatoire que vous divisez par RAND_MAX
une valeur inclue dans stdlib.h
qui est la valeur maximal d’un entier tiré aléatoirement : vous obtenez un nombre entre 0 et 1. Multipliez ensuite le résultat par max
.
Implémentez une fonction struct polynom create_random_polynom(int degree, float max)
qui crée et retourne un polynome de degré degree
et dont les coefficients sont choisi aléatoirement et inférieur à max
.
Astuce : utilisez la fonction random_float
de la question précédente. Si vous n’avez pas réussi à répondre à cette question, vous la simplifiez par une fonction qui donne toujours la valeur .
Implémentez une fonction struct polynom create_custom_polynom(int degree)
qui crée un polynome de degré degree
et dont les coefficients sont saisis par l’utilisateur via l’utilisation de la fonction scanf
.
Implémentez une fonction void print_polynom(struct polynom *)
qui affiche le polynôme dans l’ordre de degrés croissants, sans les coefficients qui valent zéro. Par exemple, au lieu d’afficher 0*X^0 + 1*X^1 + 0*X^2 + 3*X^3
, on affichera X + 3*X^3
. On évitera de faire suivre un +
par un -
, donc au lieu d’afficher X^2 + -3*X^3
, on affichera X^2 - 3*X^3
.
Implémentez une fonction struct polynom sum_polynom(struct polynom p1, struct polynom p2)
pour construire un nouveau polynome qui est la somme des deux polynômes donnés en paramètre, i.e., et tel que .
Implémentez une fonction struct polynom prod_polynom(struct polynom p1, struct polynom p2)
pour construire un nouveau polynôme qui est la multiplication des deux polynômes donnés en paramètre, i.e., et tel que .
Implémentez une fonction float eval_naive_polynom(float x, struct polynom *p)
qui retourne l’évaluation naïve du polynôme p
en x
, c’est-à-dire sans aucune optimisations de calcul.
Astuce : utiliser la fonction powf
de la librairie math.h
. Par exemple, l’instruction powf(x,i)
donne la valeur de .
Les polynômes dorés (Golden polynomials) sont définis avec la suite , et
Ecrivez une fonction struct polynom* golden_polynom(int k)
qui retourne un tableau contenant les polynômes . Utilisez obligatoirement les fonctions sum_polynom
et prod_polynom
(on ne cherche pas à trouver l’implémentation la plus rapide).
Dans votre main
, appelez golden_polynom
avec k=6 et affichez le tableau résultant en utilisant print_polynom
.
Astuce: N’oubliez pas de libérer toute la mémoire réservée à la fin du programme.