 |
#1 - 02-09-2013 19:25:44
- lol37
- Passionné de Prise2Tete
- Enigmes résolues : 0
- Messages : 68
[Combinatoire] Au voleru !
plus de géométrie pour maintenant, et c'est tant mieux pour vous ( ou pas pour certains, n'est ce pas vasimolo ? )
vous avez un porte monnaie avec autant de pièces que vous voulez, disons [latex]n[/latex] pièces, chaque pièce a une valeur monétaire déterminée, on va appeler A le plus grand entier tel que tout achat à valeur entière entre 1 à A puisse être effectué avec le porte monnaie sans rendre la monnaie, c'est à dire payer exactement l'article dit avec nos pièces
on suppose que les pièces ont des valeurs [latex](a_1,a_2,...,a_k,...,a_n)[/latex]
dont leur valeur monétaire sont croissantes ( pas forcément strictement ) en fonction de k
par exemple pour (1,3,5) on peut bien évidemment payer 1 euros ( ou la devise que vous voulez ), 2 euros ne va pas être possible sans rendre la monnaie, on s'arrête ICI donc A vaut 1
autre exemple (1,2,7), 1 est ok, 2 aussi, 3 aussi car 1+2 = 3, par contre 4 non... A vaut 3 ici
Y'a t'il une méthode / un algorithme général(e) le plus rapide qui soit pour calculer A ? si oui laquelle ?
#2 - 02-09-2013 19:58:53
- SabanSuresh
- Elite de Prise2Tete
- Enigmes résolues : 45
- Messages : 1951
- Lieu: Paris
[Combinatoire] Auu voleur !
J'ai pas compris : est-ce qu'on a un porte-monnaie qui contient une pièce de 1 euro, une pièce de 2, un pièce de 3 (en supposant que ça existe) ... ?
#3 - 02-09-2013 20:02:00
- lol37
- Passionné de Prise2Tete
- Enigmes résolues : 0
- Messages : 68
[[Combinatoire] Au voleur !
pas forcément, du moment que les valeurs soient croissantes.
par exemple (1,3,7) ou (1,2,5,8) fonctionne
#4 - 02-09-2013 20:16:12
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,996E+3
[Combiatoire] Au voleur !
Vu qu'on prend ou pas une pièce, 1 2 4 8 16 32 .... ne serait pas valable ?
Juste comme ça en base 2.
#5 - 02-09-2013 20:19:22
- lol37
- Passionné de Prise2Tete
- Enigmes résolues : 0
- Messages : 68
[combinatoire] au vpleur !
gwen27 : tu n'as pas compris le but du problème, on ne veut pas choisir une telle disposition de pièces mais savoir comment calculer A pour N'IMPORTE quel disposition qui satisfait à l'énoncé
#6 - 02-09-2013 20:48:50
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
[combinatiire] au voleur !
Les valeurs des [latex]a_k[/latex] sont-elles entières ?
Qu'appelles-tu une méthode ?
Quelque chose comme "J'écris toutes les sommes possibles puis je les classe dans l'ordre puis je repère A" ?
#7 - 02-09-2013 20:50:18
- lol37
- Passionné de Prise2Tete
- Enigmes résolues : 0
- Messages : 68
[colbinatoire] au voleur !
elles sont entières oui
un truc du genre oui, j'imagine qu'il y a plusieurs algorithmes mais moi je veux le plus rapide
j'ai édité mon problème selon ta remarque, ca devrait éclaircir ce que je demande.
#8 - 02-09-2013 21:52:48
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,996E+3
[combinatoire] ai voleur !
En gros , tu veux la somme max payable sans monnaie avec des pièces toutes différentes ?
En rébarbatif : quels entiers consécutifs peut-on obtenir au maximum avec une somme de n entiers différents.
Si c'est ça, forfait... m
#9 - 02-09-2013 21:53:05
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,996E+3
[Combinatoire] A uvoleur !
En gros , tu veux la somme max payable sans monnaie avec des pièces toutes différentes ?
En rébarbatif : quels entiers consécutifs peut-on obtenir au maximum avec une somme de n entiers différents.
Si c'est ça, forfait...
#10 - 02-09-2013 22:00:29
- lol37
- Passionné de Prise2Tete
- Enigmes résolues : 0
- Messages : 68
[combinatoore] au voleur !
pas nécessairement différentes...
forfait ? tu laisses tomber ?
#11 - 02-09-2013 23:58:23
- Nombrilist
- Expert de Prise2Tete
- Enigmes résolues : 10
- Messages : 568
C[ombinatoire] Au voleur !
On peut déjà voir jusqu'à combien peut monter A en incrémentant un compteur par pas de 1 avec les ak pris un par un. Dès que la somme est supérieure au compteur, on passe à la suite: jusqu'à combien on peut aller en scannant les a1+ak, puis a1+ak+aj, puis a1+ak+aj+... et rebelote avec a2+ak etc. A chaque fois, on scanne les ak, aj etc du plus petit au plus grand et dès que la somme est supérieure au compteur, on passe au scan suivant.
Je ne sais pas si c'est très clair.
#12 - 03-09-2013 09:36:22
#13 - 03-09-2013 11:03:57
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
[combinatoore] au voleur !
On range les nombres dans l'ordre croissant.
On essaye de faire le 1 avec le plus petit. Si OK, on vérifie que le second est <3. S oui, on pourra faire n+1.
Plus généralement, avec les k premiers termes, on peut aller de 1 à n. Si le (k+1) ième terme est >n+1, c'est fini on ne pourra pas aller plus loin car on ne peut faire n+1. Sinon, on pourra aller jusqu'à n+m si le (k+1)ième terme vaut m.
Etc....
#14 - 04-09-2013 18:36:07
- nolina
- Habitué de Prise2Tete
- Enigmes résolues : 25
- Messages : 17
[Combinatoire] Au volleur !
Il faut suivre l'algorithme suivant :
On examine a(1).
Si a(1) est strictement inférieur à 1, alors A=0, sinon, on examine le terme suivant.
Par la suite, on examine les termes un par un. Pour tout a(k), si a(k) est strictement supérieur à la somme de tous les termes précédents, plus 1, alors A est égal à la somme de tous les termes précédents. Si a(k) est inférieur ou égal à la somme de tous les termes précédents, plus 1, alors on examine le terme suivant.
#15 - 05-09-2013 21:03:17
- lol37
- Passionné de Prise2Tete
- Enigmes résolues : 0
- Messages : 68
[combinatoire] au vpleur !
Vous avez tous bon, même si la vitesse de vos algorithmes ne sont pas pareils,
Félicitations à tous !
Mots clés des moteurs de recherche
|
 |
Accueil
