Algorithmique c urgent

Bonjour,
s'il vous plait j'ai un exo que j'ai pa compris

je vous envoi l'exo celui qu'il le comprend s'il vou plai me le fai comprend

Exercice 1
On souhaite construire un algorithme pour obtenir une somme S (S est un entier) a partir de n sortes de

pieces de valeurs diferentes (et entieres) : v1; : : : ;Vn. On suppose que pour chaque valeur vi, le nombre

de pieces disponibles est illimite. On suppose de plus que Vn >Vn-1 > : : : > v1 et que v1 = 1.
Ex



On considere l'algorithme suivant ou les vi sont stockees dans un tableau Val. Le tableau Sol est utilise

pour d'ecrire une maniere de composer une somme : Sol[i] donne le nombre de pieces de valeur vi. La

somme correspondante est donc : n
i=1Sol[i] Val[i].
Dans l'algorithme suivant, le symbole = designe la division entiere et % le reste de la division entiere.
Procedure Somme(S;Val)
begin
Sol := tableau d'entiers de taille n initialise avec [0; : : : ; 0];
j := n ;
tant que S > 0 faire
Sol[j] := S=Val[j] ;
S := S%Val[j] ;
j := j-1;
retourner Sol
end
Question 1. Donnez le resultat renvoye dans le cas S = 236 et v1 = 1, v2 = 3, v3 = 50 et v4 = 70.

Question 2. Donnez le resultat renvoye dans le cas S = 8 et v1 = 1, v2 = 4, et v3 = 6.

Question 3. Decrivez l'idee sous-jacente a cet algorithme.

Question 4. Montrez que cet algorithme termine.

Question 5. Montrez qu'il fournit une solution au probleme, c'est-a-dire une