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

[Hayleia]

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

[critor]

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

[davidElmaleh]

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?

[Bisam]

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

[davidElmaleh]

Voila ma réponse :

Code: Tout sélectionner

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


[Bisam]

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

Voici ce que j'avais fait :

Code: Tout sélectionner

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

[Bisam]

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

[davidElmaleh]

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? )

[Adriweb]

(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 )

[davidElmaleh]

Ok j'y penserai