Discussion :

[Sve@r]

Je n'avais pas vu cette configuration. Je l'ai essay�e et... tu as raison! J'ai compris pourquoi, et j'ai corrig� mon algorithme.

Faudra penser � celui qui passe les pi�ces dans l'ordre croissant (ex print(tuple(rendumonnaie(((1, 2), (3, 2), (4, 1)), 6)))) car l� il ne sort pas la solution 4, 1, 1 (oui, le test du couillon dans sa plus pure expression). Un petit tri au d�but de la fonction peut-�tre...

Il y a encore un petit d�faut de syntaxe ici: if arendre > sum([p*n for p, n in C]). C'est if arendre > sum(p*n for p, n in C) qu'il faut �crire.
On pourrait penser que c'est �quivalent (et dans le cas actuel, si on n�glige la ram inutilement consomm�e, �a l'est) mais c'est une mauvaise habitude d'int�grer un tuple/list dans un truc qui est d�j� fait pour traiter un it�rable, car bien souvent ledit truc fonctionne � l'�conomie mais si on lui passe un tuple/list, tuple/list alors enti�rement cr�� avant l'appel, l'�conomie ne se fait plus.
Exemple

Code python :

S�lectionner tout - Visualiser dans une fen�tre � part

1
2
3
def fct(n):
    print(n)
    return n == 5

Si on �crit print(any([fct(x) for x in range(10)])) on aura � l'�cran tous les chiffres de 0 � 9 avant d'avoir le r�sultat True, r�sultat pourtant in�vitable sit�t le 5 atteint. Mais si on �crit print(any(fct(x) for x in range(10))) l� on voit la recherche s'arr�ter au 5

[tyrtamos]

Bonjour Sve@r,

Faudra penser � celui qui passe les pi�ces dans l'ordre croissant (ex print(tuple(rendumonnaie(((1, 2), (3, 2), (4, 1)), 6)))) car l� il ne sort pas la solution 4, 1, 1 (oui, le test du couillon dans sa plus pure expression). Un petit tri au d�but de la fonction peut-�tre...

J'ai ajout� un tri de C au d�but de la fonction:

Code :

S�lectionner tout - Visualiser dans une fen�tre � part

1
2
    # Etre sûr que les valeurs de la caisse sont dans le bon ordre
    C.sort(key=itemgetter(0), reverse=True)

Code :

S�lectionner tout - Visualiser dans une fen�tre � part

Il y a encore un petit défaut de syntaxe ici: if arendre > sum([p*n for p, n in C]). C'est if arendre > sum(p*n for p, n in C) qu'il faut écrire.

Ce n'est pas un probl�me de syntaxe, mais un travail inutile. J'ai modifi�!
Je connais le probl�me, mais j'ai toujours des r�ticences, parce qu'il faut vraiment se pencher sur les sp�cificit�s de Python: container, generator, iterator, iterable, etc...
Par exemple:
[p*n for p, n in C] ===> est une liste compr�hension, et donc un container, qui est aussi un iterable: c'est ce que j'ai utilis� avec sum.
(p*n for p, n in C) ===> est un g�n�rateur
p*n for p, n in C ===> est aussi un g�n�rateur mais provoque une erreur de syntaxe en dehors d'une fonction comme sum qui demande un iterable.
etc...

Avec, en plus:
- un g�n�rateur est un it�rateur
- un it�rateur est un iterable
- un container (list, set, dic compr�hension) est aussi un iterable

Il y a vraiment de quoi se perdre, et je ne suis m�me pas s�r d'en avoir compris toutes les subtilit�s... En dehors de la doc Python, quelques explications compl�mentaires ici:
https://nvie.com/posts/iterators-vs-generators/
https://stackoverflow.com/questions/...-and-iterators

J'ajoute ces am�liorations dans le code pr�c�dent.

Merci! Je reste � l'�coute s'il y a d'autres probl�mes ou d'autres am�liorations!

[Pyramidev]

J'arrive certainement un peu tard, mais �a fait pas mal de temps que ce probl�me de rendre la monnaie m'intrigue, et j'ai creus� un peu.

Si tu veux creuser ce sujet, il s'agit du probl�me du sac � dos (en anglais : knapsack problem) dont voici le lien Wikip�dia fran�ais : https://fr.wikipedia.org/wiki/Probl%...sac_%C3%A0_dos

[tyrtamos]

Bonjour Pyramidev,

Merci pour le lien! Il est vrai que j'ai d�barqu� sur le sujet du "rendu monnaie" sans rien regarder sur ce qui avait �t� �crit d�j� sur le sujet, et je m'aper�ois que c'est un probl�me assez g�n�ral.

En plus, j'ai d�j� eu personnellement un probl�me � r�soudre proche du "sac � dos": celui du chargement de ma 1�re caravane de vacances, dont le poids �tait � la limite de ce que pouvait supporter ma petite voiture d'alors (une Peugeot 104). J'avais fait la liste des objets que je pouvais emporter, �valu� leur poids, tout rentr� dans une base de donn�es (sur Apple II), et j'ai d� s�lectionner les objets � emporter pour ne pas d�passer la charge utile. Je n'avais pas d'algorithme informatique pour �a, mais �a a march�: j'ai fait cette ann�e-l� 3000km avec cette caravane, c'�tait en... 1982.

Mais ce probl�me, comme celui du sac � dos, est plus complexe que le rendu de monnaie, parce qu'il est multidimensionnel: en plus du poids, les objets peuvent avoir un int�r�t plus ou moins grand d'�tre emport�s (ex: la s�curit� est plus importante que le confort), leur volume peut compter aussi, ainsi que la plus ou moins grande facilit� � les remplacer quand on ne les a pas (on peut se passer de vaisselle si on a acc�s � un restaurant l� o� on va). Etc... Ainsi, l'optimum n'est pas ici dans le nombre minimum d'objets � emporter.

Je me rends bien compte qu'l ne peut pas y avoir d'algorithme simple et parfait pour r�soudre des probl�mes aussi complexes. Des recherches "� t�tons" sont in�vitables mais elles ne sont pas d�plaisantes � construire!

[wiztricks]

Salut,

Il est vrai que j'ai d�barqu� sur le sujet du "rendu monnaie" sans rien regarder sur ce qui avait �t� �crit d�j� sur le sujet, et je m'aper�ois que c'est un probl�me assez g�n�ral.

Ce qui fait que le probl�me est NP-complet, c'est sa complexit� exponentielle.

Dans le cas o� on travaille sur un nombre fini de N �l�ments, "calculer toutes les solutions et choisir parmi les meilleures" fonctionnera tant qu'on a le temps et les ressources physiques.

Par contre, la question initiale �tait de trouver un algorithme optimal de rendu de monnaie. �a existe lorsqu'on a un syst�me mon�taire canonique (et c'est la d�finition du "canonique") mais, dans le cas g�n�ral, on bricole en esp�rant que le fond de caisse soit "petit" (car �� va prendre du temps).

- W