Algorithmique

Soient a et b deux entiers positifs. Le PGCD de a et de b est le plus grand entier positif qui divise a et b.

• écrire un algorithme de calcul du PGCD
• Idem, en utilisant l'algorithme d'Euclide. Cet algorithme se base sur la propriété que pgcd(a,b) = pgcd(b, a%b), avec la convention pgcd(a, 0)=a.

Écrire un test de parité estPair(n) sans utiliser l'opérateur % ni l'opérateur /. Les boucles, tests, comparaisons, affectations et décrémentations sont autorisées.

Le but de cet exercice est d'afficher la représentation en binaire d'un entier positif.

• 19 = 16 + 2 + 1 ⇒ 10011
• 42 = 32 + 8 + 2 ⇒ 101010
• 63 = 32 + 16 + 8 + 4 + 2 + 1 ⇒ 111111

• Comment déterminer le chiffre le plus à droite de la représentation binaire d'un entier ? Utiliser ce résultat; pour afficher la représentation binaire d'un entier, à l'envers.
• Déterminer le plus grand entier p tel que 2p < n. Utiliser ce résultat pour afficher la représentation binaire d'un entier, à l'endroit.

En utilisant les opérations de division entiére et de modulo, affichez à l'envers un nombre entré au clavier.

À partir d'un montant entré par l'utilisateur, affichez les différentes façons d'obtenir ce montant avec des billets de 100 €, 50 € et 20 €. Affichez également le nombre de façons possibles. Utilisez pour cela trois boucles imbriquées.

Écrivez un programme devinant un nombre choisi par l'utilisateur dans un intervalle donné. Le programme propose un nombre, l'utilisateur répond par «plus grand» ou «plus petit» en fonction du nombre qu'il avait choisi.

Écrivez un programme simulant une calculatrice simple : l'utilisateur rentre une opération puis ses opérandes, et le programme renvoie le résultat du calcul. Ce programme devra comprendre les quatre opérations arithmétiques de base, ainsi que les opérations trigonométriques de base.

L'intégrale d'une fonction f sur un petit intervalle [a,b] peut être approximée par : ∫_a^bf(x) dx ≈ (b-a) (f(a)+f(b))/2. L'intégrale d'une fonction sur un intervalle [a,b] peut donc être approchée par : ∫_a^bf(x) dx ≈ h ∑_k=0^n-1 (f(a+kh)+f(a+(k+1)h))/2. Dans cette formule, l'intervalle [a,b] est divisé en n sous-intervalles de largeur h.

• Écrire l'algorithme réalisant cette intégration.
• En utilisant les propriétés des intégrales des fonctions sin et cos, étudier la précision de cette méthode d'intégration en fonction du pas h.

Une fraction égyptienne est une somme de fractions unitaires, c'est à dire dont les numérateurs valent 1, et dont les dénominateurs sont des entiers positifs distincts. Par exemple, une écriture possible de 2/5 comme fraction égyptienne est 2/5 = 1/5+1/6+1/30.

Toute fraction peut être écrite comme une fraction égyptienne. Un des algorithmes pour arriver à ce résultat est basé sur la propriété suivante : x/y = 1/⌈y/x⌉ + (-y % x)/ (y⌈y/x⌉). Dans cette formule, ⌈x⌉ est les plus petit entier supérieur à x.

Écrire un algorithme permettant de calculer la fraction égyptienne d'une fraction donnée par l'utilisateur sous la forme de deux entiers. Attention : même si cet algorithme donne toujours un résultat, certains dénominateurs peuvent être trop grands pour la représentation des entiers de Java. C'est par exemple le cas pour la fraction 5/121.

Écrire un programme qui affiche la conjugaison d'un verbe du premier groupe au présent, à l'imparfait, au futur et au passé simple. Ne pas oublier de prendre en compte les verbes du type manger ou bouger.

Écrire un programme permettant de comparer deux chaînes de caractère en utilisant l'ordre lexicographique (ordre du dictionnaire). Ce programme renverra -1 si la première chaîne est inférieure à la seconde, 0 si les deux chaînes sont égales et +1 si la seconde chaîne est supérieure à la première.

Écrire un programme qui chiffre une chaîne en utilisant le chiffre de César : chaque caractère est décalé d'un nombre fixe de positions dans l'alphabet. Par exemple la chaîne “bonjour” donne, en décalant de 13 positions, “obawbhe”.

Écrire un programme réalisant la fonction de décodage du chiffre de César. On supposera que la phrase à chiffrer est composée de minuscules.

Note : en stockant le décalage dans un int et en additionant ce décalage à un char, le résultat est un int, affiché comme un nombre. Pour afficher le résultat comme un caractère, il faut utiliser la syntaxe (char) (c+decalage).

Écrire un programme qui chiffre une chaîne en utilisant le chiffre de Vigenère : chaque caractère est décalé d'un nombre de positions dans l'alphabet en utilisant une phrase clé. La phrase clé est répétée pour atteindre la longueur du texte à chiffrer. Chaque caractère de la phrase à chiffrer est décalé du nombre de position donné par le caractère de la phrase clé situé à cet endroit.

Exemple : avec une clé valant “musique”, le chiffre de “j'adore ecouter la radio toute la journee” est “V'UVWHY IOIMBUL PM LSLYI XAOLM BU NAOJVUY”.

Écrire un programme réalisant la fonction de décodage du chiffre de Vigenère. On supposera que la phrase à chiffrer et la clé sont composées de minuscules.

Note : dans cet exercice, la clé de chiffrage est donnée comme une chaîne de caractère. Il faut donc reconvertir chaque caractère en sa position dans l'alphabet, soit (int) (c-'a').

On considère le jeu des mots croisés. Lorsque un joueur cherche un mot connaissant sa longueur et éventuellement certaines lettres déjà placées, il utilise l'ordinateur pour afficher l'ensemble des solutions possibles. Dans la suite de l'énoncé, on désignera par patron le modèle du mot cherché.

Exemple : le joueur cherche un mot en sept lettres se terminant par “eau”, avec un 'a' en troisième position suivant le modèle ”??a?eau”. L'ordinateur affiche “chapeau”, “chameau” et “drapeau”.

Dans cet exercice, on ne traitera qu'une partie du problème.

Question 1 : écrire la fonction construit ( ) : chaîne, qui à partir d'une liste de couples (rang, lettre) saisie au clavier dans la fonction construit le mot de référence patron contenant dans toutes les cases le caractère '?' sauf dans les cases indiquées par les valeurs de rang qui contiennent les caractères lettre saisis. On introduira en premier la longueur du mot à construire suivie de la liste des couples terminée par une valeur de rang égale à -1.

On suppose que la chaîne patron contient au moins une lettre, que les valeurs de rang sont correctes, saisies dans l'ordre croissant, et que l'utilisateur n'introduit que des lettres minuscules (ne pas faire de test de vérification).

Attention, le rang des lettres connues est donné à partir de 1 !

Vous disposez des opérations définies sur le type chaîne de caractères, c'est à dire: lc(), sch(…), conc(…), ième(…), opérateurs de comparaison, etc.

Exemple : la saisie des données suivantes: longueur = 11 et liste saisie = (3,'e'), (5,'b'), et (8,'m') donne le mot de référence: « ??e?b??m??? »

Question 2 : écrire la fonction booléenne Compare (e : mot, patron) : bool, avec mot, patron: chaîne qui retourne vrai si la chaîne de caractères mot est une solution possible au mot cherché patron, qui retourne faux sinon; la chaîne mot est une solution possible si elle contient exactement les mêmes lettres connues que patron placées aux mêmes endroits et n'importe quelle autre lettre aux endroits correspondant à '?'.

Par exemple, le mot « tremblement » est une solution au patron « ??e?b??m??? » de la question précédente.

Un algorithme de recherche de sous-chaine est un type d'algorithme de recherche qui a pour objectif de trouver une chaîne de caractères à l'intérieur d'une autre. Un tel algorithme fournit la position du premier caractère de la sous-chaîne recherchée dans la chaîne fournie en entrée.

L'algorithme le plus simple compare la chaîne initiale à la chaîne recherchée caractère par caractère : dès qu'on trouve un caractère identique au premier caractère de la chaîne recherchée, on parcourt les caractères suivants tant qu'ils correspondent.

Le premier terme de la suite de Conway est posé comme égal à 1. Chaque terme de la suite se construit en épelant le terme précédent, c'est-à-dire en indiquant combien de fois chacun de ses chiffres se répète.

Concrètement :

• X0 = 1

Ce terme comporte juste un « 1 ». Par conséquent, le terme suivant est :

• X1 = 11

Celui-ci est composé de deux « 1 » :

• X2 = 21

En poursuivant le procédé :

• X3 = 1211
• X4 = 111221
• X5 = 312211
• X6 = 13112221

Et ainsi de suite.

Écrire un programme donnant les n premiers termes de cette suite.