Scribd
Importer
2 vues1 page

## L'énoncé Du Problème

Le document présente un défi d'algorithme basé sur le Problème du Sac à Dos, axé sur le rendu de monnaie avec un nombre minimal de pièces. Il décrit les étapes à suivre pour créer un script qui calcule et affiche les pièces nécessaires pour rendre un montant donné, en utilisant un tableau de pièces triées. Un exemple d'interaction est fourni pour illustrer le fonctionnement du script.

Transféré par

oulairayane6
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
2 vues1 page

## L'énoncé Du Problème

Le document présente un défi d'algorithme basé sur le Problème du Sac à Dos, axé sur le rendu de monnaie avec un nombre minimal de pièces. Il décrit les étapes à suivre pour créer un script qui calcule et affiche les pièces nécessaires pour rendre un montant donné, en utilisant un tableau de pièces triées. Un exemple d'interaction est fourni pour illustrer le fonctionnement du script.

Transféré par

oulairayane6
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Voici un défi d'algorithme axé sur le tri et l'optimisation, sans fichiers ni structures

complexes : le Problème du Sac à Dos version gloutonne (Knapsack Problem).


Le but est d'écrire un script de caisse automatique qui doit rendre la monnaie à un client en
utilisant le moins de pièces possible.

## L'énoncé du problème
Vous disposez d'un système de monnaie avec les pièces suivantes : [50, 20, 10, 5, 2, 1]. Le
script doit :
1.​ Demander à l'utilisateur de saisir un montant entier (ex: 88).
2.​ Calculer de manière optimale quelles pièces donner pour atteindre exactement ce
montant.
3.​ Afficher le résultat détaillé dans le terminal.

## Exemple d'interaction
Montant à rendre : 88​
​
Résultat du rendu :​
- 1 x 50​
- 1 x 20​
- 1 x 10​
- 1 x 5​
- 1 x 2​
- 1 x 1​
Total de pièces : 6​

## L'indice pour l'algorithme


●​ Stockez vos pièces dans un tableau trié de la plus grande à la plus petite.
●​ Parcourez ce tableau avec une boucle. À chaque étape, utilisez la division entière
(intdiv()) pour savoir combien de pièces de cette valeur vous pouvez donner, puis utilisez
l'opérateur modulo (%) pour obtenir le reste à payer avant de passer à la pièce suivante.
Est-ce que cet exercice de pure logique te convient ?

Vous aimerez peut-être aussi