Algorithmique - NSI
Algorithme glouton
Exercice 1 : Algorithme glouton et rendu de monnaie
Une caisse dispose des pièces et des billets suivants : 100;50;30;10;1.
On a autant de pièces et de billets que nécessaire.
Lors d'un achat, un caissier doit rendre 74 € à un client.
En utilisant l'algorithme glouton, compléter le tableau ci-dessous, qui répertorie les pièces et billets rendus par le caissier pour que le nombre d'éléments soit minimum :
Exercice 2 : Algorithme glouton et problème du sac à dos
- - La somme des poids des objets sélectionnés soit inférieure à 39 kg.
- - La somme des valeurs des objets sélectionnés soit la plus grande possible.
Exercice 3 : Algorithme glouton et rendu de monnaie
Une caisse dispose des pièces et des billets suivants : 40;30;25;2;1.
On a autant de pièces et de billets que nécessaire.
Lors d'un achat, un caissier doit rendre 124 € à un client.
En utilisant l'algorithme glouton, compléter le tableau ci-dessous, qui répertorie les pièces et billets rendus par le caissier pour que le nombre d'éléments soit minimum :
Exercice 4 : Algorithme glouton et problème du sac à dos
- - La somme des poids des objets sélectionnés soit inférieure à 67 kg.
- - La somme des valeurs des objets sélectionnés soit la plus grande possible.
Exercice 5 : Algorithme glouton et rendu de monnaie
Une caisse dispose des pièces et des billets suivants : 100;50;30;10;1.
On a autant de pièces et de billets que nécessaire.
Lors d'un achat, un caissier doit rendre 74 € à un client.
En utilisant l'algorithme glouton, compléter le tableau ci-dessous, qui répertorie les pièces et billets rendus par le caissier pour que le nombre d'éléments soit minimum :