Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 02-09-2013 19:25:44

lol37
Passionné de Prise2Tete
Enigmes résolues : 0
Messages : 68

[Cobminatoire] Au voleur !

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 ?

  • |
  • Répondre

#0 Pub

 #2 - 02-09-2013 19:58:53

SabanSuresh
Elite de Prise2Tete
Enigmes résolues : 45
Messages : 1951
Lieu: Paris

[oCmbinatoire] Au 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

[Combinatoirre] 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,993E+3

[Combinaotire] 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

[Combintaoire] Au voleur !

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

[Combinatoire] Au volur !

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

[Combiantoire] 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,993E+3

[combinatoore] au 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,993E+3

[CCombinatoire] Au 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...

 #10 - 02-09-2013 22:00:29

lol37
Passionné de Prise2Tete
Enigmes résolues : 0
Messages : 68

[ombinatoire] 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

[Combinatoire] Au vloeur !

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

BilouDH
Habitué de Prise2Tete
Enigmes résolues : 46
Messages : 29

[combinatiire] au voleur !

Salut,

Est ce que ton prochain sujet sera sur les racines m-ième de l'unité? Franchement il te suffirait de copier le lien http://concoursgeneral.free.fr/cg/sujet … es2011.pdf Il y en a d'autres qui se sont faits bannir pour moins que ça. Je pense que le premier problème devrait rappeler quelques souvenirs à ceux qui ont planché sur ton énigme "Mais ça va rentrer oui???" (http://www.prise2tete.fr/forum/viewtopic.php?id=11407)

A bon entendeur...

 #13 - 03-09-2013 11:03:57

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

C[ombinatoire] 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

[Combinnatoire] Au voleur !

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 oleur !

Vous avez tous bon, même si la vitesse de vos algorithmes ne sont pas pareils,
Félicitations à tous !

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Tim, Tam et ?

Sujets similaires

Mots clés des moteurs de recherche

Mot clé (occurences)

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete