Un match Etoile

Algorithmique
td Algo 2 – Nov. 2014
Info-sup S1
Epita
TD répétitif
1
Itérations
Exercice 1.1 (Zorglub)
Que calcule l’algorithme suivant lorsqu’il est appelé avec un entier n strictement positif ?
algorithme fonction zorglub : entier
parametres locaux
entier
n
variables
entier
i, j, k
debut
j ← 1
k ← 0
i ← 1
tant que i <= n faire
j ← i*j
k ← j+k
i ← i+1
fin tant que
retourne k
fin algorithme fonction zorglub
Exercice 1.2 (Multiplication)
1. Écrire une fonction qui calcule x × y, avec (x, y) ∈ N2 en n’utilisant que les opérateurs + et -.
2. Écrire une fonction qui calcule x × y, avec cette fois-ci (x, y) ∈ Z2 .
Exercice 1.3 (Puissance N)
Écrire une fonction calculant le résultat de nn , avec n ∈ N. La fonction doit afficher également toutes
les puissances de n intermédiaire.
Exercice 1.4 (Fibonacci)
Écrire une fonction itérative calculant le ne`me terme de la suite de Fibonacci.
f ibo(0) = f ibo(1) = 1
f ibo(n) = f ibo(n − 1) + f ibo(n − 2)
1
Algorithmique
td Algo 2 – Nov. 2014
Info-sup S1
Epita
Exercice 1.5 (Maximum)
1. Écrire une fonction qui à partir d’un entier n strictement positif :
lit n valeurs entières (données par l’utilisateur),
retourne la plus grande des n valeurs lues.
2. Modifier la fonction pour qu’elle n’accepte que des valeurs strictement positives (elle doit en lire
n).
Exercice 1.6 (Suite)
Soit une suite numérique u dont le ne`me terme peut être calculé par l’appel à la fonction u(n).
1. Écrire une fonction qui retourne la somme Sn des n premiers termes de la suite u.
2. Sans utiliser la fonction précédente, écrire une fonction qui retourne
n
X
Si
i=1
où Si est la somme des i premiers termes de la suite u.
3. Si ce n’est pas déjà le cas, écrire de nouveau la fonction précédente avec une seule boucle !
2
Répétitions
Exercice 2.1 (Où il faut arriver à 1)
La conjecture de Syracuse est définie par :
Soit n un entier naturel non nul,
◦ si n est pair, le nombre suivant sera n/2 ;
◦ si n est impair, le nombre suivant sera 3n + 1.
Cette suite s’arrête toujours avec la valeur n = 1.
Écrire un algorithme qui, à partir de l’entier n, affiche les valeurs calculées en utilisant la conjecture
de Syracuse jusqu’à obtenir la valeur 1, si n est strictement positif. Dans le cas contraire, l’algorithme
doit déclencher une erreur.
Exercice 2.2 (Euclide)
Écrire un algorithme calculant le pgcd de 2 entiers a et b strictement positifs en utilisant la méthode
d’Euclide dont le principe est rappelé ci-dessous.
Algorithme d’Euclide :
Si a et b sont deux entiers avec a ≥ b, si r est le reste de la division euclidienne de a par b :
a = bq + r avec r < b, alors le pgcd de a et b vaut le pgcd de b et r.
Si a est divisible par b, alors le pgcd de a et b est b.
2
Algorithmique
td Algo 2 – Nov. 2014
Info-sup S1
Epita
Exercice 2.3 (Miroir)
Écrire une fonction qui donne le "miroir" d’un entier passé en paramètre s’il est positif.
Exemple : 1278 → 8721.
Remarque : si l’entier donné est 1250, le résultat sera 521.
Exercice 2.4 (Quotient)
Soient deux entiers naturels non nuls a et b. Écrire une fonction calculant le quotient entier de a sur
b en n’utilisant que des opérateurs additifs (les seules opérateurs autorisés sont + et -).
Exercice 2.5 (Où on cherche la puissance)
Écrire une fonction qui à partir de deux entiers naturels non nuls a et b, détermine si a est une puissance de b, c’est-à-dire ∃p ∈ N / a = bp . Une erreur devra être déclenchée en cas d’entrées non valides.
Exemples :
◦ si a = 16 et b = 2, alors la fonction retourne vrai.
◦ si a = 15 et b = 5, alors la fonction retourne f aux.
◦ si a = 81 et b = 3, alors la fonction retourne vrai.
Exercice 2.6 (Factorielle calculable ?)
Écrire une fonction itérative qui, à partir d’une valeur entière donnée limite, calcule le plus grand
nombre entier pair n tel que n! < limite. Si la valeur ne peut pas être calculée (limite ≤ 0), la fonction
retournera 0.
Par exemple : si limite = 150 et 5! < 150 < 6!
alors le plus grand entier pair dont la factorielle ne dépasse pas 150 est 4.
3
Algorithmique
td Algo 2 – Nov. 2014
3
Info-sup S1
Epita
Divisibilité
Exercice 3.1 (Divisibilité par 11)
Ce test particulier de la divisibilité par 11 a été donné en 1897 par Charles L. Dodgson (Lewis Carroll).
Soit un entier naturel à tester, former un nouveau nombre en :
— enlevant le chiffre des unités
— soustrayant le chiffre enlevé du nombre raccourci.
Le nombre résultant est divisible par 11 si et seulement si le nombre initial est divisible par 11.
Exemple :
24684 → 2464 → 242 → 22. Le nombre 24684 est divisible par 11.
Écrire une fonction qui vérifie si un entier naturel non nul est divisible par 11 en utilisant le principe
donné ci-dessus. Les seules divisions entières (quotients et restes) qui pourront être utilisées seront des
divisions par 10 (pas de division par 11 !).
Exercice 3.2 (Nombre parfait)
Un nombre est dit parfait s’il est plus grand que 1 et égal à la somme de tous ses diviseurs qui lui
sont strictement inférieurs.
Exemple : 28 = 1 + 2 + 4 + 7 + 14.
Écrire une fonction qui détermine si un entier supérieur à 1 est parfait.
Question bonus :
Dans une version optimisée, peut-on encore afficher les diviseurs en ordre croissants ?
4
Algorithmique
td Algo 2 – Nov. 2014
Info-sup S1
Epita
Exercice 3.3 (Preuve par 9)
La preuve par neuf permet de "vérifier" l’exactitude d’une multiplication sur les entiers naturels.
Pour cela il faut savoir calculer la racine numérique d’un nombre : on ajoute les chiffres du nombre,
puis ceux de la somme obtenue, et ainsi de suite jusqu’à n’obtenir un seul chiffre.
Pour effectuer la preuve par neuf d’une multiplication A × B = C, il suffit de comparer la racine
numérique du produit des racines numériques de A et de B avec la racine numérique de C. L’égalité des
deux chiffres obtenus constitue la vérification de l’opération.
Écrire une fonction qui à partir de 3 entiers naturels non nuls a, b et c, teste l’égalité a/b = c en
utilisant la preuve par neuf.
Cette technique est-elle vraiment une preuve mathématique ?
Exercice 3.4 (Nombre premier)
Écrire une fonction qui détermine si un entier strictement supérieur à 1 est premier ou non.
Exercice 3.5 (Vilain nombre)
Un ”nombre vilain“ est un nombre qui a au moins deux paires de facteurs telles que la somme des
facteurs d’une paire équivaut à la différence des facteurs de l’autre.
Ainsi, par exemple :
— le nombre 6 est un nombre vilain puisque 6 × 1 = 6, 2 × 3 = 6, et 6 - 1 = 2 + 3 ;
— aussi, 24 est un autre nombre vilain puisque 12 - 2 = 6 + 4.
Écrire une fonction qui détermine si un entier naturel est un nombre vilain ou non.
5
Algorithmique
td Algo 2 – Nov. 2014
4
Info-sup S1
Epita
Des chaînes
Exercice 4.1 (Recherche)
1. Écrire une fonction booléenne qui recherche si un caractère donné appartient à une chaîne. La
fonction devra retourner la position du premier caractère trouvée, la valeur −1 si celui-ci n’est pas
présent.
2. Écrire une fonction qui retourne le nombre d’occurrences d’un caractère donné dans une chaîne.
3. Écrire une fonction qui retourne le caractère le plus fréquent dans une chaîne.
Exercice 4.2 (Où on change de base)
Écrire une fonction itérative qui, à partir d’une chaîne de caractères représentant un entier naturel en
base 2 retourne l’entier en décimal. La chaîne vide est l’entier 0.
Exemples :
— Si la chaîne contient "101010", la fonction retourne 42 (car 42 = 32 + 8 + 2).
— Si elle contient "11010000000", la fonction retourne 1664 (car 1664 = 1024 + 512 + 128).
On supposera la chaîne valide : elle ne contient que des ’0’ et des ’1’.
Exercice 4.3 (Sous-chaîne)
1. Écrire une fonction booléenne qui teste si une chaîne est contenue dans une autre chaîne.
2. Écrire une fonction qui retourne le nombre d’occurrences d’une chaîne dans une autre chaîne.
Exemple : Si la chaîne contient "tototot" et que la chaîne recherchée est "tot", la fonction retournera 3.
6

Download Report