[Mini-Challenge Basic #8] : Comment tu paies ?

→ **MyCalcs** profile · by **Hayleia** » 10 Jul 2014, 11:17

Non mais je rigole

Je pense que ça se passe plutôt dans l'autre sens : quand une personne a une idée, on la laisse la proposer, et quand personne n'en a, on force le gagnant à en trouver une

→ **MyCalcs** profile · by **critor** » 10 Jul 2014, 23:27

Bisam wrote:Je n'ai pas cherché à tout comprendre dans ton algorithme, critor, et je n'ai pas du tout regardé s'il était performant mais tes réponses sont exactes.

Pour faire des tests de performance supplémentaires, essayez de trouver la réponse pour 15€ à payer (19 secondes sur ma calculette... pour un résultat égal à 3844287444)

C'est sûrement catastrophique à côté de toi, j'ai juste sorti l'algorithme qui m'est venu naturellement.
Avec une boucle tant que et une récursivité.

La 1ère mini-boucle que je passe sous silence ici sert juste à obtenir la pièce de valeur maximale utilisable, puisque j'ai considéré que la liste passée en 2ème paramètre n'était pas forcément triée.

Je n'ai pas encore réfléchi à une quelconque optimisation - je vais peut-être laisser cela à tes fans

En gros:

L'algorithme détermine la pièce de valeur maximale.
Il s'impose de l'utiliser successivement 0 fois, 1 fois, 2 fois, etc... sous la seule contrainte de ne pas dépasser le montant à payer (boucle tant que).
Pour chaque tentative, il complète le paiement si besoin est selon le même principe avec les pièces de valeurs inférieures (récursivité)

Mais visiblement, tu as beaucoup mieux

→ **MyCalcs** profile · by **davidElmaleh** » 11 Jul 2014, 17:18

Mon algorithme donne 3844287444 pour coins(1500,{1,2,5,10,20,50,100,200}) en 650 ms sur ordi (mesuré avec un script Lua, merci Adriweb

) et sur Nspire CX CAS OS 3.6 sans ndless : 25460 ms soit 25 secondes

Je n'ai donc pas encore battu le grand Bisam

J'y travaillerais

EDIT: Juste pour savoir s'il y a une modification du temps d'exécution en fonction des machines, Bisam, je t'envoi, par MP, mon algorithme. Pourrais-tu mesurer son temps d'exécution?

→ **MyCalcs** profile · by **Bisam** » 11 Jul 2014, 22:47

Je regarderai demain ton algorithme, david... mais je devine où tu t'es inspiré, et j'ai quasiment la même chose.

→ **MyCalcs** profile · by **davidElmaleh** » 12 Jul 2014, 23:59

Voila ma réponse :

Code: Select all: Define coins(tot,list)= Func Local chemins,i,j chemins:=newList(tot+1) chemins[1]:=1 For i,1,dim(list) For j,list[i]+1,tot+1 chemins[j]:=chemins[j]+chemins[j-list[i]] EndFor EndFor chemins[tot+1] EndFunc

→ **MyCalcs** profile · by **Bisam** » 13 Jul 2014, 01:12

La méthode est excellente... mais on peut encore un peu améliorer !

Voici ce que j'avais fait :

Code: Select all: Define pieces(n,pcs)= Func Local paie,p,pc,i,j paie:=newList(n+1) paie[1]:=1 p:=dim(pcs) For i,1,p pc:=pcs[i] For j,pc+1,n+1 paie[j]:=paie[j]+paie[j-pc] EndFor EndFor paie[n+1] EndFunc

→ **MyCalcs** profile · by **Bisam** » 25 Jul 2014, 21:28

Bon, je te déclare officiellement vainqueur, david !

→ **MyCalcs** profile · by **davidElmaleh** » 27 Jul 2014, 03:38

Merci, mais tu mérites la victoire!

btw : je vais essayer de préparer un nouveau défi, vu que ça n'avance pas trop (peut être en Lua cette fois-ci?

)

My calculator programs · by **Adriweb** » 27 Jul 2014, 11:33

(Pour le Lua (si tu veux le faire dans cette catégorie), il faudrait si possible que ce soit relatif à l'usage de l'API Nspire, sinon on trouve trop de problèmes/solutions sur le net, et c'est moins drôle

)