Forum de mathématiques - Bibm@th.net

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

Re,

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

Bonjour,

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

Bonjour,

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

Bonjour,

Pour le 3a), il faut simplement remarquer que l'angle de la demi-droite (d) reste fixe...
attention : Pour le 3b) il faut raisonner sur les angles comme pour le 2b)....
Pour l'apparition de e il faut regarder le développement en séries entières de sinx, cosx et [tex]e^{ix}[/tex] déduit du développement de  [tex]e^{x}[/tex]

Cordialement

Bonsoir,

Chacun sait que le meilleur, vraiment, c'est Fred ! les autres ont trop de points faibles....

Cordialement

Bonjour,

Ce serait plutôt :
[tex]P1:\,\sqrt{x-1}+2\sqrt{y-4}=\frac{x+y}{2}[/tex]

Ce calcul est déjà passé sur ce forum....

cordialement

Bonjour,

Quand [tex]C=f(x,y) = \frac{3}{4}[/tex] est déterminé, alors, tout comme

[tex]f_X(x)=\int_{0}^{1-{x^2}}\frac{3}{4}\times dy=\frac{3}{4}(1-x^2)[/tex]

alors, puisque [tex]x= (1-y)^\frac{1}{2}[/tex]

[tex]f_Y(y)=\int_{-(1-y)^\frac{1}{2}}^{ (1-y)^\frac{1}{2}}\frac{3}{4}\times dx[/tex]

qui est le résultat de votre livre

Cordialement

Bonjour,

@ karlun :  Je ne vais pas polémiquer bien que, après 28 tris mon exemple test soit :
             G          E
             H          I          F
                         K          J
Et non pas
             E          F
             G          H
                         K           I
                                      J
Suivre votre procédure en traçant les arcs d'un graphe orienté montre facilement s'il y a des contre-exemples, car on voit en évidence les sommets qui sont (ou ne sont pas) comparés entre eux. Mais votre idée de tester sur des diagonales fait partie des bons cheminements
Et votre compte autour de 28-30, un peu plus, un peu moins, doit être dans les bonnes eaux.
Reste à finaliser…

Cordialement

Bonjour,

Merci  pour cet intéressant article, bien caractéristique de ce que l'ordinateur peut aider à faire...et qui n'est pas aussi inutile que certains pourraient le croire en comparant "force brute" et "raisonnement de l'esprit humain".

Je n'ai pu résister au plaisir de résoudre la grille présentée et vérifier qu'elle n'a bien qu'une solution, car j'ai un petit programme écrit depuis que mon épouse, pour me faire plaisir, m'avait acheté une revue avec une centaine de SUDOKU...

Solution en 2 secondes, unicité en 6 secondes.

Cordialement

Bonjour,

Voila qui va compléter les algorithmes de tri présentés dans le forum programmation...
Suspense : Les comparaisons ternaires vont-elles l'emporter sur les comparaisons binaires ?

Cordialement

Bonjour,

Voulez-vous dire que pour 11 chameaux vous avez trouvé 2 partages en empruntant 1 chameau pour en partager 12,
Et qu'il vous manque une troisième solution ?
en effet 6+4+1=6+3+2=11 et on rend 1 chameau.

Que pensez-vous d'en emprunter 7, de partager 6+3+2 et d'en rendre 7 ?

Cordialement