rendu de monnaie [1, 2, 5]

 Rédiger l'algorithme glouton pour le problème du rendu de monnaie. On testera notre programme avec le système de monnaie suivant : euros = [1, 2, 5].

===

un algorithme glouton classique pour le problème du rendu de monnaie et l’adapter au système d’euros [1, 2, 5]. Je vais aussi expliquer la logique étape par étape.

---

1️⃣ Problème

Entrée :

• Un montant N à rendre.

• Un ensemble de pièces disponibles euros = [1, 2, 5].

Sortie :

• Le nombre minimal de pièces utilisées pour rendre N.

• La liste des pièces choisies.

Idée du glouton :

• À chaque étape, choisir la plus grande pièce possible ≤ montant restant.

• Répéter jusqu’à ce que le montant restant soit 0.

Le glouton fonctionne correctement ici car les pièces sont “canonique” : [1, 2, 5]

---

2️⃣ Algorithme en pseudo-code

Entrée : montant N, tableau euros trié décroissant
Sortie : liste de pièces utilisées, nombre total de pièces

Algorithme RenduGlouton(N, euros):
    Trier euros en ordre décroissant
    liste_pieces ← []
    reste ← N

    pour chaque piece dans euros:
        tant que reste >= piece:
            liste_pieces.ajouter(piece)
            reste ← reste - piece

    retourner liste_pieces, longueur(liste_pieces)

---

3️⃣ Exemple avec N = 11

euros = [5, 2, 1]
N = 11

- prendre 5 → reste = 6, liste = [5]
- prendre 5 → reste = 1, liste = [5,5]
- prendre 2 → reste = 1 < 2 → ignorer
- prendre 1 → reste = 0, liste = [5,5,1]

Résultat : pièces = [5,5,1], nombre = 3

---

4️⃣ Implémentation C#

using System;
using System.Collections.Generic;

class RenduMonnaie
{
    static void Main()
    {
        int[] euros = { 1, 2, 5 };
        int montant = 11;

        List<int> pieces = RenduGlouton(montant, euros);

        Console.WriteLine("Pièces utilisées : " + string.Join(", ", pieces));
        Console.WriteLine("Nombre total de pièces : " + pieces.Count);
    }

    static List<int> RenduGlouton(int N, int[] euros)
    {
        // Trier décroissant
        Array.Sort(euros);
        Array.Reverse(euros);

        List<int> listePieces = new List<int>();
        int reste = N;

        foreach (int piece in euros)
        {
            while (reste >= piece)
            {
                listePieces.Add(piece);
                reste -= piece;
            }
        }

        return listePieces;
    }
}

---

5️⃣ Exemple de sortie

Montant = 11
Pièces utilisées : 5, 5, 1
Nombre total de pièces : 3

✅ Correct et optimal pour ce système [1, 2, 5].

==============================

Back Tracking:

using System;

using System.Collections.Generic;

class Program

{

    static int best = int.MaxValue;

    static List<int> bestResult = new List<int>();

    static void Change(int[] coins, int amount, List<int> current)

    {

        if (amount == 0)

        {

            if (current.Count < best)

            {

                best = current.Count;

                bestResult = new List<int>(current);

            }

            return;

        }

        if (amount < 0 || current.Count >= best)

            return;

        foreach (int coin in coins)

        {

            current.Add(coin);

            Change(coins, amount - coin, current);

            current.RemoveAt(current.Count - 1);

        }

    }

    static void Main()

    {

        int[] coins = { 1, 3, 4 };

        int amount = 6;

        Change(coins, amount, new List<int>());

        Console.WriteLine("Số đồng tối thiểu: " + best);

        Console.WriteLine(string.Join(", ", bestResult));

    }

}