Exercices (pc3)

Exercice 1 On considère le ‘jeu des chiffres’ dans lequel on donne une suite w[0], w[1], …, w[n − 1] de n nombres entiers et un nombre s. On demande de trouver un sous-ensemble I des indices tel que

∑_{i∈I} w[i] = s

Donner un algorithme résolvant ce problème. Quelle est sa complexité?

Exercice 2 A chaque execution de la procédure Hanoï on associe une chaîne de caractères de la façon suivante: Un déplacement d’une rondelle du piquet 1 vers le piquet 3 est noté par le symbole a, du piquet 1 vers le piquet 2 par le symbole b et du piquet 2 vers le piquet 3 par c. Les déplacements inverses sont notés par les mêmes lettres avec une barre dessus (\overline{a}, \overline{b}, \overline{c}). Ainsi la chaîne de caractères correspondant au déplacement de deux rondelles du piquet 1 vers le piquet 3 selon l’algorithme décrit en cours est : h_{2} = bac Celle correspondant au déplacement de trois rondelles du piquet 1 vers le piquet 3 est :

h_{3} = ab\overline{c}a\overline{b}ca

1. Donner la chaîne correspondant au déplacement de 4 rondelles.

2. Quelle est la longueur de la chaine h_{n} correspondant au déplacement de n rondelles ?

3. En s’ aidant des transformations suivantes sur les caractères donnez un procédé de calcul de la chaîne h_{n+1} en connaissant h_{n}.

a b c \overline{a} \overline{b} \overline{c}
ϕ b a \overline{c} \overline{b} \overline{a} c
ψ c \overline{b} a \overline{c} b \overline{a}

4. Montrez que lorsque l’on supprime les barres au dessus des caractères intervenant dans la chaîne h_{n} on obtient une chaîne très régulière.

5. En déduire une procédure itérative permettant de résoudre le problème des tours de Hanoï.