Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#51 25-01-2012 09:03:19

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 7 457

Re : A faire perdre la boule à totomn !!!

Salut,

c'est beaucoup trop !


De la considération des obstacles vient l’échec, des moyens, la réussite.

Hors ligne

#52 25-01-2012 15:10:04

amatheur
Membre
Inscription : 02-10-2011
Messages : 299

Re : A faire perdre la boule à totomn !!!

salut
@youssef, freddy avait juste préciser qu'elles sont indiscernable au toucher et à la "souspesée", mais rien n’empêche de les marquer à l'ancre par exemple!
et même en considérant ta condition, tu n'optimise pas ta méthode, la dernière pesée qui permet de casser la i ème boule, permet aussi de classer les deux autres boules, alors en prenant la boule moyenne pour débuter la série de tests pour casser la i+1 boule, tu peux d'emblée éliminer  la moins lourde des tests, ainsi pour caser la deuxième boule, tu n auras besoin que de 6 tests et ainsi de suite..


J'aimais les fées et les princesses,
Qu'on me disait n'exister pas..

Hors ligne

#53 25-01-2012 15:25:44

youssef
Invité

Re : A faire perdre la boule à totomn !!!

il a precise boule indicernable donc j ai pris le cas le plus difficile (sinon trop facile si on peut numeroter car dans ce cas les boules sont dicernables)
sinon la derniere pesee ne permet que de dire qui est la plus lourde elle ne donne aucune indication sur les 2 autre par rapport au tas restant le plus legere pouvant etre de la 1 a la treizieme place et la milieu de la seconde a la quatorzieme place

#54 25-01-2012 15:53:21

amatheur
Membre
Inscription : 02-10-2011
Messages : 299

Re : A faire perdre la boule à totomn !!!

re
eh bein justement! la moins lourde ne peut pas être à la quatorzième place, alors ce n'est pas la peine de la tester pour caser la 14 ème, donc tu  n'auras qu'a challenger la moyenne avec les douze autres, ce qui te fait 6 tests  seulement.
si tu considère que le cas où les boules sont discernables est trop fastoche, montre nous comment tu fais!!!!!


J'aimais les fées et les princesses,
Qu'on me disait n'exister pas..

Hors ligne

#55 05-02-2012 17:29:23

totomm
Membre
Inscription : 25-08-2011
Messages : 1 093

Re : A faire perdre la boule à totomn !!!

Bonjour,

freddy Post #30 (11-01-2012) a écrit :

Salut,
28 est encore un peu trop ...

jpp Post #37 (12-01-2012) a écrit :

salut .
  j'ai une méthode que je vais expliquer, et vous l'essaierez avec des papiers.
……
  au final , je revérifierai demain :  a , 1 , 2 , 3 , 4 , v , 5 , w , x , b ,   c , y , z , d , e en   20   pesées.(....)

en attendant que freddy précise le résultat qu'il faut obtenir, voici une méthode que j'ai entièrement testée et qui donne, pour n=15 : "au mieux 25 pesées avec le dispositif " (c'est-à-dire jamais plus de 25 pesées),

Rappel concernant le "tri rapide" (voir Algorithmes de tri par yoshi –forum programmation) :
il consiste à choir un pivot qui est positionné à sa  place définitive en ayant à sa gauche tous les éléments plus légers et à sa droite tous les éléments plus lourds que lui.
S'il y a n éléments sur des positions de 1 à n, le premier pivot est choisi en position n et viendra en position k
On applique récursivement le positionnement d'un élément pivot sur les éléments précédemment placés de 1 à (k-1) et de (k+1) à n.
 
Une amélioration de la méthode consiste à commencer en "moyenne par 3", c'est –à dire comparer 3 éléments entre eux , positionner le plus léger en 1, le plus lourd en n, et le moyen en (n-1).
Ensuite on prend 2 par 2 les éléments situés de la position 2 à la position (n-2), on les complète avec le pivot et on les positionne comme convenu à gauche ou à droite du pivot en déplaçant celui-ci ainsi jusqu'à sa position définitive.

Pour n=2p+1, p>1 on doit ainsi, dans le pire cas effectuer [tex]\frac{p(p+1)}{2}+1[/tex] tests soit 29 tests si n=15

Mais les 2 "pires cas" se rencontrent dès le positionnement du premier pivot, et ce sont les configurations :
a1 a2->a3 a4->a5 a6->a7…a12->a13 Pivot a15 (13 éléments à gauche et 1 à droite du pivot)
a1 a2->a3 a4->a5 a6->a7…a12 Pivot a13 a15 (12 éléments à gauche et 2 à droite du pivot)
Desquelles parties gauches on peut d'emblée trouver, dès la première pesée, un pivot avec 4 éléments à sa droite.

Ce qui conduit à n'avoir que 25 pesées dans tous les "pires cas".

Cordialement

Hors ligne

#56 06-02-2012 15:18:16

amatheur
Membre
Inscription : 02-10-2011
Messages : 299

Re : A faire perdre la boule à totomn !!!

salut

totomm a écrit :

On applique récursivement le positionnement d'un élément pivot sur les éléments précédemment placés de 1 à (k-1) et de (k+1) à n

@totomm: pourrais-tu être un peu plus explicite sur ce point?
merci.


J'aimais les fées et les princesses,
Qu'on me disait n'exister pas..

Hors ligne

#57 07-02-2012 02:03:29

totomm
Membre
Inscription : 25-08-2011
Messages : 1 093

Re : A faire perdre la boule à totomn !!!

Bonjour,

@ amatheur : Je veux bien expliciter, mais c'est tellement bien décrit à l'adresse tri rapide Wikipedia

Cordialement

Hors ligne

#58 07-02-2012 07:18:21

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 7 457

Re : A faire perdre la boule à totomn !!!

Bonjour,

j'avoue ne pas bien comprendre non plus la méthode. Le tri rapide est une comparaison 2 à 2, mais ici, j'ai un contrainte forte : je ne peux faire que des comparaisons 3 à 3.

Comment fais tu, au juste ?


De la considération des obstacles vient l’échec, des moyens, la réussite.

Hors ligne

#59 07-02-2012 12:12:44

totomm
Membre
Inscription : 25-08-2011
Messages : 1 093

Re : A faire perdre la boule à totomn !!!

Bonjour,

totomm a écrit :

Une amélioration de la méthode consiste à commencer en "moyenne par 3", c'est –à dire comparer 3 éléments entre eux , positionner le plus léger en 1, le plus lourd en n, et le moyen en (n-1).
Ensuite on prend 2 par 2 les éléments situés de la position 2 à la position (n-2), on les complète avec le pivot et on les positionne comme convenu à gauche ou à droite du pivot en déplaçant celui-ci ainsi jusqu'à sa position définitive.

Après avoir choisi le pivot (première comparaison de 3 éléments) et l'avoir positionné en (n-1), en 1 il y a un élément  < pivot et en n un élément > pivot. je prend les éléments en 2 et 3 et je les compare au pivot :
a) S'ils sont tous deux < pivot, je continue avec les éléments 4 et 5 etc...
b) Si le pivot est entre les deux, je mets le plus petit en 2, le pivot en n-2 et le plus lourd en n-1. et je continue avec les éléments qui étaient en 4 et 5 et qui ont glissé d'une position vers la gauche etc...
c) S'ils sont tous deux > pivot je les place en n-2 et n-1 et mets le pivot en n-3, et je continue avec les éléments qui étaient en 4 et 5 et qui ont glissé de deux positions vers la gauche etc...

Ainsi le principe bien établi du tri rapide est respecté. La comparaison 3 par 3 avec le dispositif proposé laisse en général des informations de couples (ordonnés) non utilisées, mais en réutilisant ces infos dans les 2 pires cas, on passe de 29 à 25.

Mais peut-être freddy sait proposer mieux ...

Cordialement

Hors ligne

#60 07-02-2012 13:40:08

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 7 457

Re : A faire perdre la boule à totomn !!!

Re,

je connais un peu le pivot. Donc je prends A, B et C que je confie au quidam qui me les rend ordonnés.

J'ai donc 1, 2 , 3 et je décide que 2 est le pivot.

Je prends ensuite C, D et 2 que je confie au même quidam qui me les rend ordonnés.

Mais je ne sais pas où est passé  2 ?!?

Je me trompe ?


De la considération des obstacles vient l’échec, des moyens, la réussite.

Hors ligne

#61 07-02-2012 15:13:39

totomm
Membre
Inscription : 25-08-2011
Messages : 1 093

Re : A faire perdre la boule à totomn !!!

Re,

freddy a écrit :

Je me trompe ?

Pour reprendre vos notations : Le tri opère sur un tableau dont les cases sont repérées de 1 à n=15
et dans lesquelles au départ se trouvent des boules que l'on repère A, B, C,...M, N, O

On commence par exemple avec A, B et C. Si elles ressortent dans l'ordre (par exemple) C, A, B :
La plus légère prend la case 1, et comme A va être le pivot et comme B est la plus lourde,
on a le tableau de 15 cases comme suit : C D E F G H I J K L M N O A B
Ensuite on trie D, E et A, puis F, G et A etc...
Voila une bonne adaptation du tri rapide (binaire) au tri avec le quidam ternaire proposé, dans la mesure où seuls les appels au quidam sont comptabilisés.
Si on comptabilisait aussi les repositionnements, ce serait une autre affaire !

Si opérer avec ce quidam était vraiment performant, cela se saurait dans la communauté des informaticiens !

Cordialement

Hors ligne

#62 07-02-2012 15:45:03

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 7 457

Re : A faire perdre la boule à totomn !!!

Re,

donc on a après le premier tri  C D E F G H I J K L M N O A B

Ensuite, on prend D E et A et supposons que le quidam rende dans l'ordre A D et E

Si je comprends bien, on aura alors dans les cases :

C A D F G H I J K L M N O E B

Ensuite, on compare  F G et E ?


De la considération des obstacles vient l’échec, des moyens, la réussite.

Hors ligne

#63 07-02-2012 15:47:03

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 7 457

Re : A faire perdre la boule à totomn !!!

Re,

car quand on me rend A D et E, je ne sais plus où se trouve le pivot A ?

Je me trompe ?


De la considération des obstacles vient l’échec, des moyens, la réussite.

Hors ligne

#64 07-02-2012 16:32:23

totomm
Membre
Inscription : 25-08-2011
Messages : 1 093

Re : A faire perdre la boule à totomn !!!

Re,

freddy a écrit :

car quand on me rend A D et E, je ne sais plus où se trouve le pivot A ?

On respecte le principe même du tri rapide : Pendant le partitionnement, on a le même pivot et, dans la partie considérée,
on place à gauche du pivot toutes les boules plus légères, et à droite du pivot toutes les plus lourdes.

Dans le cas que vous considérez où le quidam rend A,D,E dans cet ordre, puisque l'on avait :
C D E F G H I J K L M N O A B
on positionne :
C F G H I J K L M N O A D E B et on continue le partitionnement en présentant au quidam, F,G et A, puis H,I et A, puis
J,K et A, puis LM et A puis NO et A.
Fin du partitionnement et appels récursifs pour les parties à gauche puis à droite de A.

Surtout ne pas perdre la boule pivot pendant un partitionnement pour que le pivot se mette à sa place définitive et que l'on puisse récursivement traiter deux parties plus réduites devenues indépendantes.
C'est l'essence même du tri rapide !!

Cordialement

Hors ligne

#65 07-02-2012 17:23:47

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 7 457

Re : A faire perdre la boule à totomn !!!

Re,

je suis d'accord, l'ordinateur sait, grâce au programmateur, conserver l'information de la position du pivot quand il classe à droite et/ou à gauche d'icelui.

Mais quand je donne au quidam trois boules à trier, il me les rend dans l'ordre, mais je ne sais plus dire où était mon pivot puisque le quidam ne me donne aucune autre indication que les trois boules ordonnées ...

Donc je persiste à dire que je ne comprends pas comment tu fais, l'ami !

Vois tu mieux la nature de mon problème ?


De la considération des obstacles vient l’échec, des moyens, la réussite.

Hors ligne

#66 08-02-2012 11:41:52

totomm
Membre
Inscription : 25-08-2011
Messages : 1 093

Re : A faire perdre la boule à totomn !!!

Bonjour,

freddy post #1 a écrit :

j'ai 15 boules parfaitement identiques, indiscernables ni au toucher, ni à la "soupesée".

justement, nous avons 5 sens (au moins), et il n'est pas dit que les boules sont indiscernables à la vue : Si elles ne sont pas de couleurs différentes, j'ai supposé que je les avais marquées pour reconnaitre d'où elles étaient parties une fois retournées "classées dans l'ordre de leur poids croissant" par le dispositif.....

freddy a écrit :

Donc je persiste à dire que je ne comprends pas comment tu fais, l'ami !

Si, l'ami, vous comprenez très bien comment je fais, mais je reconnais que je n'ai pas traité votre problème tel que vous l'entendez.

Cordialement.

Hors ligne

#67 08-02-2012 12:29:20

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 7 457

Re : A faire perdre la boule à totomn !!!

totomm a écrit :

Bonjour,

freddy post #1 a écrit :

j'ai 15 boules parfaitement identiques, indiscernables ni au toucher, ni à la "soupesée".

justement, nous avons 5 sens (au moins), et il n'est pas dit que les boules sont indiscernables à la vue : Si elles ne sont pas de couleurs différentes, j'ai supposé que je les avais marquées pour reconnaitre d'où elles étaient parties une fois retournées "classées dans l'ordre de leur poids croissant" par le dispositif.....

freddy a écrit :

Donc je persiste à dire que je ne comprends pas comment tu fais, l'ami !

Si, l'ami, vous comprenez très bien comment je fais, mais je reconnais que je n'ai pas traité votre problème tel que vous l'entendez.

Cordialement.

Re,

que nenni, je ne comprenais pas! Je viens de comprendre que tu les marques. Je crois qu'un mathématicien ne ferait pas ça. En tout cas, c'est exclu. Sinon, tu prends un pot de peinture, tu les notes de 1 à 15 et roulez bolides ! Dans l'énoncé, il n'y a pas de pot de peinture et les boules sont pures et parfaites. Un problème idiot, quoi, qui reste ouvert.

La seule chose qu'on sache est qu'elles sont toutes d'un poids différent (on va dire 1 gramme), et donc qu'il y a une plus grande et une plus petite.

A partir de là, on peut faire des classements, par exemple je donne A B et C et on me rend trois boule en 1 2 3
et je peux comparer D, E et F puis ... ensuite classer les 5 plus grandes par exemple, puis les  5 plus petites, ou bien commencer par les classer par groupe de 5 ...

C'est un sujet un peu velu, je pense.

Dernière modification par freddy (08-02-2012 12:30:30)


De la considération des obstacles vient l’échec, des moyens, la réussite.

Hors ligne

#68 08-02-2012 17:06:08

amatheur
Membre
Inscription : 02-10-2011
Messages : 299

Re : A faire perdre la boule à totomn !!!

salut
@freddy, toutes les méthodes présentées jusqu’à maintenant , sauf celle de youssef (poste50), supposent que les les boules sont discernables "à la vue". maintenant que tu viens de préciser les conditions du problème, je propose de traiter dans ce topic les deux cas; discernable et non discernable! ça aura le mérite de mettre en valeur les différentes méthodes de tri utilisées dans chaque cas de figure. qu'est ce que tu en penses?


J'aimais les fées et les princesses,
Qu'on me disait n'exister pas..

Hors ligne

#69 08-02-2012 17:52:17

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 7 457

Re : A faire perdre la boule à totomn !!!

Re,

oui, tu les vois une fois qu'ils te reviennent ordonnés, et tu continues à les suivre. Mais tu ne les marques pas !

Dernière modification par freddy (08-02-2012 17:55:05)


De la considération des obstacles vient l’échec, des moyens, la réussite.

Hors ligne

#70 08-02-2012 19:08:06

karlun
Membre
Inscription : 05-05-2010
Messages : 216

Re : A faire perdre la boule à totomn !!!

Bonsoir,

A la grosse louche:
Avec des boules non identifiées seulement écartées

Je trie toutes les boules j'obtiens cinq lignes de boules classées de la plus légère à la plus lourdes et donc trois colonnes: à gauche la colonne des boules légères à droite la colonne des boules lourdes.
Il est logique que la boule la plus légère de toutes se trouve dans la colonne de gauche et la plus lourde dans la colonne de droite.

On passe à la machine trois des cinq boules de la colonne de gauche et on en retire la plus légère. On joint cette boule aux deux autres non testées, on les passe à la machine et la plus légère de toute est trouvée.
On fait la même chose avec la colonne des plus lourdes.

Donc     
1)                 5 + 2 + 2 = 9       opérations.
Restent 13 boules indifférenciées.
On recommence la même méthode.

2)               9 + 4 + 2 + 2 = 17       

3)               17+ 3 + 2 + 2 = 24   

4)        24 + 3 + 2        = 29
         
5)        29 + 2 + 2        = 33

6)        33 + 1 + 2        = 36

7)        36 + 1        = 37

Après 37 passages à la machine les 15 boules sont classées.

Mais j'entends déjà Freddy: « try again! ».

A+-*/


Qui trouve, cherche.

Hors ligne

#71 08-02-2012 21:31:54

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 7 457

Re : A faire perdre la boule à totomn !!!

Yes, try again, too much !


De la considération des obstacles vient l’échec, des moyens, la réussite.

Hors ligne

#72 10-02-2012 17:43:00

jpp
Membre
Inscription : 31-12-2010
Messages : 1 105

Re : A faire perdre la boule à totomn !!!

salut.
totomm  je n'étais pas chez moi et j'ai bien vu cet après midi que quelque chose n'allait pas donc j'ai suppprimé le post
alors que tu étais sans doute entrain d'écrire.

Hors ligne

#73 10-02-2012 17:55:09

totomm
Membre
Inscription : 25-08-2011
Messages : 1 093

Re : A faire perdre la boule à totomn !!!

Bonjour,

@jpp : Oui, mais je ne commente plus une modification que vous avez supprimée...

Je suis quand même curieux de voir qui va améliorer les 37 de Karlun (ou mes 25-29) après toutes ces péripéties...

Cordialement

Hors ligne

#74 11-02-2012 09:03:53

jpp
Membre
Inscription : 31-12-2010
Messages : 1 105

Re : A faire perdre la boule à totomn !!!

salut.

  de toute façon , puisqu'il n'est pas autorisé de marquer les boules , il faut les placer sur une table horizontale.

en travaillant linéairement , en 49 coups de gauche à droite , puis de droite à gauche puis à nouveau ... on place 15 boules.

maintenant il faut trouver la forme   géomètrique  du placement. En remarquant que 3 & 15 sont deux nombres triangulaires c.a.d  de la forme
                                             [tex]\frac{n.(n+1)}{2}[/tex]

alors , et c'est peut-etre un tuyau percé que je donne , en disposant les 15 boules dans un panier à oeuf comme ceci :

                                            O
                                        O      O
                                    O      O      O
                                 O     O      O      O
                             O     O      O      O      O

Il y a peut-etre moyen d'avancer plus vite . Hier , j'ai essayé façon matrice 5 lignes , 3 colonnes . ça avance assez vite mais il y a des boules qui restent coincées dans une colonne , alors cette nuit m'est venue l'idée de la disposition en triangle. je vais chercher en travaillant sur les triplets triangulaires et les lignes alternativement.

(...)                                                                              à plus

Hors ligne

#75 11-02-2012 13:42:15

karlun
Membre
Inscription : 05-05-2010
Messages : 216

Re : A faire perdre la boule à totomn !!!

Bonjour,

Deuxième proposition:

Même idée de départ.

Cinq lignes de trois boules classées en ordre croissant
et donc trois colonnes dont une légère à gauche et une lourde à droite.
S'il est logique que la plus légère des boules se trouve dans la colonne de gauche (et la plus lourde à droite) il est aussi logique que la boule « 2° plus légère » ne peut pas être dans la colonne des plus lourdes (et symétriquement concernant la boule avant dernière des plus lourdes).

Partant de ce fait, je ne repasse pas à la machine toutes les boules restantes après déduction des deux extrêmes; mais j'analyse les colonnes des boules misent  en couple croissant (reste de chaque passage à la machine)

Résultat payant:

31 passages nécessaires pour classer les quinze boules.

Ok Freddy ! Je sais... « too much ! ».

A+-*/


Qui trouve, cherche.

Hors ligne

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
trente huit plus dix-sept
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums