A. Sigayret : Algorithmique

Exercices d'algorithmique : série 2

N.B. Rechercher sur Wikipedia (ou autre) les définitions inconnues nécessaires à la résolution des exercices.

Exercice 2.1.
algorithme 21
Donnée : un entier n.
Résultat : un entier p tel que...
p←0;
Pour i de 1 à n faire  p←p+i;
p←2*p−n.
a) Faire une trace de l'algorithme ci-dessus pour n=4, puis n=5.
b) Que fait cet algorithme ?
c) Quel est sa complexité ?

Exercice 2.2.
a) Ecrire un algorithme itératif qui calcule n! (factoriel-n).
b) A partir de quelle valeur de n le résultat ne pourra plus tenir dans un mot-mémoire de 16 bit ? 32 bit ?
c) Quelle est la complexité de cet algorithme ?
d) Ecrire un algorithme récursif qui calcule n!.

Exercice 2.3.
a) Ecrire un algorithme qui retourne la somme des diviseurs d'un entier naturels n (y compris 1 et n).
b) Utiliser cet algorithme pour vérifier si un nombre est premier.
c) Ecrire un algorithme qui vérifie si un nombre est parfait.
c) Ecrire un algorithme qui vérifie si deux nombres sont amis.
e) Utiliser ces algorithmes pour trouver l'ensemble des nombres premiers compris entre 1 et n.

Exercice 2.4.
a) Ecrire un algorithme qui recherche la valeur maximale d'un tableau de n valeurs.
b) Ecrire un algorithme qui calcule le nombre de fois où le caractère 'a' est présent dans une chaine de n caractères.
c) Ecrire un algorithme qui calcule la somme d'un tableau de n valeurs.
d) Ecrire un algorithme qui calcule la moyenne d'un tableau de n valeurs.
e) Qu'y a-t-il de commun entre les trois problèmes précédents ? Montrer que ces problèmes sont en O(n).

Exercice 2.5.
a) Ecrire un algorithme qui donne la position, dans un tableau T de taille n, de la première occurrence d'une valeur x donnée. Que fera l'algorithme si la valeur n'a pas été trouvée ?
b) Même question pour la dernière occurrence.
c) Ecrire un algorithme qui supprime la k-ième valeur d'un tableau T de taille n≥k et déplace en conséquence les valeurs suivantes d'une case vers le début du tableau.
d) Ecrire un algorithme Plateau qui recherche dans un tableau une plus longue suite croissante de valeurs et retourne les longueur et indice de début d'une telle liste.
e) Donner la preuve et la complexité de ces algorithmes.

Exercice 2.6.
a) Ecrire un algorithme qui remplace dans un tableau toutes les occurrences d'une valeur x par une valeurs y.
b) Ecrire un algorithme PURGER qui ne conserve dans un tableau qu'un unique exemplaire de chaque valeur qu'il contient. La taille n du tableau sera modifiée en conséquence et la fin du tableau "abandonnée".
c) Dans des tableaux purgés modélisant des ensembles, quelle pourrait être la complexité algorithmique du test d'appartenance, de la recherche d'intersection, de l'union ? La complexité de ces problèmes changerait-elle si les tableaux sont déjà triés ?

Exercice 2.7.
Ecrire un algorithme et donner sa complexité pour chacun des problèmes suivants. Si possible donner la complexité du problème.
a) Calculer la moyenne pondérée des notes d'un étudiant. Les notes sont dans un tableau T de n entiers compris entre 0 et 20, les coefficients sont dans un tableau C de n entiers naturels.
b) Calculer la n-ième valeur d'une suite arithmétique de premier terme U0 et de raison x.
c) Même question pour une suite géométrique.
d) Vérifier si un mot ou une phrase est un palindrome.

Exercice 2.8.
Ecrire un algorithme et donner sa complexité pour chacun des problèmes suivants. Si possible donner la complexité du problème.
N.B. Pour afficher ces figures géométriques, on disposera de la fonction Afficher qui affiche un caractère ASCII (y compris l'espace et le retour chariot).
a) Affichage d'un rectangle de 'r' de largeur n et de hauteur p données.
b) Affichage d'un triangle rectangle de 't' de largeur n et de hauteur p données.
c) Affichage d'un grand X sur l'écran avec les caractères '/', '\' et 'x', pour une taille n impaire.
d) Affichage d'un disque de rayon n.
e) Affichage d'un carré de côté n/2 centré dans un carré de côté n+1.