Récursivité terminale

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é.

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.

Ecrire un programme permettant de résoudre le problème du monayeur: é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 = Σ_i=0^n-1 a_i*w_i et
Σ_i=0^n-1 a_i 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 Σ_i=0^n-1 a_i.

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.