exercices : Écrire et prouver des algorithmes itératifs et récursifs

Cours/Algorithmie/exercices : Écrire et prouver des algorithmes itératifs et récursifs

À chaque fois, on vous demande d'écrire un algorithme puis de le prouver.

Arithmétique

Entier vers décimal

Écrivez (et prouvez) un algorithme de signature base10(entier) -> [entier] rendant la forme décimale (un tableau de chiffres allant de 0 à 9) d'un entier. On doit avoir :

base10(123) = [3, 2, 1]

Étendre

Écrivez (et prouvez) un algorithme de signature étendre([entier], n) -> [entier] qui ajoute n 0 en à la fin du tableau. Par exemple :

étendre([3, 2, 1], 4) = [3, 2, 1, 0, 0, 0, 0]

Décimal vers entier

Écrivez (et prouvez) un algorithme de signature entier([entier]) -> entier rendant la valeur d'un entier écrit en forme décimale. On doit avoir :

entier([3, 2, 1]) = 123

Somme

Écrivez (et prouvez) un algorithme permettant de calculer la somme de 2 nombres donnés sous leur forme décimale (un tableau de chiffres allant de 0 à 9). Cet algorithme devra être de signature : somme([entier], [entier]) -> [entier]

Soustraction

Écrivez un algorithme permettant de calculer la soustraction de 2 nombres donnés sous leur forme décimale (un tableau de chiffres allant de 0 à 9). Cet algorithme devra être de signature : soustraction(n: [entier], m: [entier]) -> [entier] et tel que soustraction(n, m) = base10(|entier(n)-entier(m)|)

Bon parenthésage

Uniquement des parenthèses

Écrivez un algorithme permettant de savoir si une chaîne de caractères uniquement formée des caractères "(" et ")" est un bon parenthésage ou pas. Ainsi :

parenthèses("(())()") = Vrai
parenthèses("(())()(") = Faux

Couple de parenthèses

Si s est une chaîne de caractères uniquement formée de parenthèses ouvrante et fermante, écrivez un algorithme de signature couple(s: chaîne, i: entier) -> entier qui rend l'index de la parenthèse associée à celle d'indice i ou -1 si elle n'existe pas (et s n'est pas un bon parenthésage). Par exemple :

parenthèses("(())()", 0) = 3
parenthèses("(())()(", 5) = 4
parenthèses("()))", 2) = -1

Parenthèses et lettres

Écrivez un algorithme permettant de savoir si une chaîne de caractères uniquement formée des caractères "(" et ")" et des lettres de l'alphabet est un bon parenthésage.

Parenthèses, crochets et lettres

Même question que précédemment mais la chaîne de caractère contient des crochets ouvrants ("[") et fermants ("]") en plus des lettres de l'alphabet et des parenthèses ouvrantes et fermantes.

Vous pourrez créer un algorithme récursif qui utilise le fait que si les chaînes s1 et s2 sont des parenthésages corrects alors :

la chaîne s1 + s2 est un parenthésage correct.
la chaîne s = "(" + s1 + ")" + s3 est un parenthésage correct.
la chaîne s = "[" + s1 + "]" + s3 est un parenthésage correct.

Polynômes

Valeur

écrivez une fonction valeur telle que

paramètres d'entrée :
1. une liste de $n+1$ réels $[a_0, \dots, a_n]$ $n \geq 0$
2. un réel $x$
sortie :
- $\sum_{i=0}^na_i x^i$

On pourra supposer que la fonction puissance $x^n$ existe pour tout réel $x$ et tout entier positif $n$.

Somme

Écrivez une fonction somme telle que

paramètres d'entrée :
1. une liste de réels $[a_0, \dots, a_n]$
2. une liste de réels $[b_0, \dots, b_m]$
sortie :
- $[a_0 + b_0, \dots, a_n+b_n]$ si $n = m$
- $[a_0 + b_0, \dots, a_n+b_n, b_{n+1}, \dots, b_m]$ si $n < m$
- $[a_0 + b_0, \dots, a_m+b_m, a_{m+1}, \dots, a_n]$ si $m < n$

Produit

Écrivez une fonction produit telle que

paramètres d'entrée :
1. une liste de réels $[a_0, \dots, a_n]$
2. une liste de réels $[b_0, \dots, b_m]$
sortie (on suppose):
- une liste $[c_0, \dots, c_{m+n}]$ telle que $c_k = \sum_{i+j=k}a_ib_j$ pour tout $0\leq k \leq m+n$