:: Enseignements :: ESIPE :: E3INFO :: 2014-2015 :: Algorithmique ::

Récursivité

On poursuit l'écriture de fonctions récursives, un peu plus complexes, qui permettent de résoudre des problèmes classiques, mais "coûteux"...

Exercice 1 - Sac à dos...

Reprendre la fonction de résolution du problème du sac à dos vu en cours et la transformer afin qu'elle affiche une trace de son déroulement, les sommes partielles cherchées ainsi que l'entier testé.

Exemple avec n = 4, tableau = 2 9 10 7 et S = 19 :

appel(19,0) 
avec 2 appel(17,1) 
      avec 9 appel(8,2) 
            avec 10 appel(-2,3) FAUX
            sans 10 appel(8,3) 
                  avec 7 appel(1,4) FAUX
                  sans 7 appel(8,4) FAUX
                  fin (8,3) retour FAUX
            fin (8,2) retour FAUX
      sans 9 appel(17,2) 
            avec 10 appel(7,3) 
                  avec 7 appel(0,4) VRAI
                  dans (7,3) affiche 7 retuour VRAI
            dans (17,2) affiche 10 retuour VRAI
      fin (17,1) retour VRAI
dans (19,0) affiche 2 retuour VRAI

Exercice 2 - Tours de Hanoï

Ecrire un programme affichant (sous forme ASCII) les différents états du problème des tours de Hanoï pour un entier positif n (petit). Les plateaux seront symbolisés par des entiers de 1 à n.
On pourra utiliser scanf("%*c") pour attendre que l'utilisateur tape une touche entre chaque mouvement.

Par exemple, pour n=3, le programme affichera successivement :

|321
|
|

|32
|
|1

|3
|2
|1

|3
|21
|

|
|21
|3

|1
|2
|3

|1
|
|32

|
|
|321

Exercice 3 - Monnayeur

Ecrire un programme permettant de résoudre le problème du monnayeur: étant donné une suite croissante de n entiers positifs w₀=1, w₁, ... w_n-1 et un entier strictement positif S, trouver la suite des coefficients a₀, a₁, ... a_n-1 telle que S = a₀*w₀ + a₁*w₁ + ... + a_n-1*w_n-1 et a₀ + a₁ + ... + a_n-1 soit minimal.

La suite des w_i (les valeurs des pièces) sera lue sur la ligne de commande, et pourra être représentée par un tableau valeurs tel que valeurs[0] soit égal à 1. On traitera le problème pour différentes valeurs de S entrées par l'utilisateur (arrêt lorsqu'une valeur négative ou nulle est fournie).

Dans un premier temps, on affichera uniquement le nombre minimal de valeurs intervenant dans la somme a₀ + a₁ + ... + a_n-1.
La version suivante affichera la suite des coefficients a_i, stockés sous la forme d'un tableau coeffs.
Attention: il faudra penser à utiliser des copies de ce tableau lors des appels récursifs pour pouvoir récupérer les "meilleurs" coefficients au final.