Manipulation des nombres et de leur représentation.

Rappel: A partir de maintenant, plus aucune valeur de test ne devra être codé en dur. Elles devront systématiquement être passées via la ligne de commande. Ex: ./mon_programe une_valeur une_autre_valeur etc

Exercice 1 : Calendrier

  1. Écrivez une fonction qui indique si une année passée en paramètre est bissextile ou non. Rappel de la règle : les années bissextiles sont soit multiples de 4 et non multiples de 100, soit multiples de 400. Par exemple, 2000 et 2008 sont bissextiles, mais 1900 et 2010 ne le sont pas.
  2. Écrivez un programme qui prend un numéro de mois et une année en paramètres, et affiche le nombre de jours que dure le mois.

  3. Dans un article publié en 1990 dans le Journal of Recrational Mathematics, Vol. 22, No. 4, 1990, p. 280, Mike Keith propose un algorithme pour la détermination du jour de la semaine correspondant à une date quelconque. Sa formule est inspirée de la congruence de Zeller. Wikibooks

    Si \(m >= 3\), \(z = y\) et \(D = [23m/9] + d + 4 + y + [z/4] - [z/100] + [z/400] - 2 \equiv 7\)
    Si \(m < 3\), \(z = y - 1\) et \(D = [23m/9] + d + 4 + y + [z/4] - [z/100] + [z/400] \equiv 7\)

    Avec day, month, year, [ / ] une division entière et \(\equiv\) le reste de la division (qui dans cette notation à une priorité plus faible que l’addition).

    Remarque: Mike Keith est américain (d’ou le choix des lettres … et plus).

    • Proposez une signature pour cette fonction
    • l’écrire
  4. Bonus Regarder le resultat de la commande cal, vous avez toutes les clefs en mains pour la reproduire.

Exercice 2 : Table ASCII

  1. Afficher la table des caractères sous la forme suivante :

     Car. dec.  hexa   octal
 'A'  65    0x41   0101
 'B'  66    0x42   0102
 ...
 'Z'  90    0x5a   0132
  2. Compléter la table pour tous les caractères ([0..127]). Attention les caractères de [0..32[ ne s’affichent pas correctement, que proposez vous ?
  3. Pour le fun, essayez d’aller jusqu’à la fin (i.e., 255).
  4. Bonus En afficher n sur un même ligne (commencer par 4 sur une même ligne).
  5. Bonus Lire sur la ligne de commande le nombre à en afficher par ligne, s’il n’est pas présent penser à afficher l’usage de votre programme.
  6. Bonus Sur la ligne de commande, ajouter une option (donc facultative) --min nombre et --max nombre pour limiter cette table à un intervalle.

Exercice 3 : Nombres de bits à un

Un masque est un nombre dont seuls la position des 1 et des 0 qu’il contient dans sa représentation binaires comptent (i.e., sa valeur décimale importe peu)

  1. Compter le nombre de bits positionnés à un dans un entier \(n\). L’entier sera lu depuis la ligne de commande.
    • Il ne sera fait aucune supposition sur la taille du nombre (i.e., vous utiliserez sizeof pour déterminer le nombre de bits si votre algorithme s’en sert).
    • On propose les deux algorithmes suivants :
    1. Pour tous les bits i de \(n\) on ajoute un si ce bit est présent (décalage du masque).
    2. Tant que \(n\) n’est pas zéro on ne regarde seulement le dernier bit (décalage du nombre) - Quel algorithme est le plus efficace, en moyenne ? Dans le pire des cas ?
  2. On améliorera cet algorithme en utilisant l’algorithme du Hacker’s Deligth (Henry S. Warren, Jr.) :
    • Tant qu’il y a au moins un bit à un, alors le ET d’un nombre et son complément à deux ne vaut pas zéro et contient un seul bit à un (c’est le bit de poids le plus faible).
    • Retirer ce bit (le but de poids faible) en utilisant un OU EXCLUSIF. Rappel le OU EXCLUSIF d’un bit et d’un 1 inverse l’état de ce bit.
    • Recommencer
    • Sous qu’elle condition cette version est-elle plus efficace ?

Exercice 4 : Résistance

Le code couleur d’une résistance 3 anneau est donné par :

\[Resistance = (Couleur1 * 10 + Couleur2) * 10^{Couleur3}\]

Chaque couleur est associée à une valeur,

Valeur Couleur Mnémotechnique
0 Noir Ne
1 Marron Manger
2 Rouge Rien
3 Orange Ou
4 Jaune Jeuner
5 Vert Voila
6 Bleu Bien
7 Violet Votre
8 Gris Grande
9 Blanc Bêtise
  • Écrire le type enum color qui correspond à ce tableau
  • Écrire la fonction times_pow10, qui retourne n fois la \(10^p\) .
  • Écrire la fonction qui en fonction de 3 couleurs retourne la valeur de la résistance. Quel type doit retourner cette fonction.
  • Écrire la fonction index_of qui retourne l’indice d’une chaine de caractère dans un tableau de chaines.
  • Écrire un programme qui, en fonction de trois couleurs données soit textuellement, affiche la valeur de la résistance correspondante.

Exercice 5 : Morpion

(:alert class:warning:) Cet exercice est un peu long, il ne sera jamais corrigé en TD. Bien entendu il est intéressant, et il vous est fortement conseillé de prendre un peu de temps chez vous pour le faire. (:end_alert:)

Pour saisir un nombre dans la variable entière a: scanf("%d", &a);

Écrivez un programme qui permet à deux utilisateurs de jouer au morpion à neuf cases. Le principe du jeu est le suivant : les deux joueurs inscrivent tour à tour un symbole dans l’une des cases libres de la grille (x pour le joueur 1, o pour le joueur 2) ; le premier joueur qui réussit à aligner 3 symboles identiques en ligne, colonne ou diagonale est vainqueur, et le match est nul si toutes les cases sont remplies et si aucun joueur n’a gagné. Le programme affichera la grille de la manière suivante :

  1 2 3
1 . . .
2 . . .
3 . . .

Tour à tour, chaque joueur saisira le numéro de ligne suivi du numéro de colonne où il souhaite jouer, puis la grille sera affichée à nouveau en remplaçant le . de la case choisie par le symbole du joueur (x ou o). Le programme déclarera une victoire d’un joueur ou un match nul si applicable.

Exercice 6 : RLE (Bonus)

  1. On se propose d’implémenter un codage de type RLE (Run Length Enconding). Ce codage affiche une suite de paire { nombre-consécutifs, bit }. C’est à dire pour le nombre binaire suivant 00111011, elle affiche 2 0 3 1 1 0 2 1 (à prononcer : il y’a deux zéros, puis 3 un, puis 1 zéro puis 2 un).
  2. Cette méthode nécessite d’afficher deux nombres (la paire). Peut on la limiter à un seul ? L’implémenter.

Exercice 7 : Palindrome (Bonus)

  1. On se propose de tester si la représentation binaire d’un nombre est un palindrome (11011011 est un palindrome).