Répondre à la discussion
Affichage des résultats 1 à 8 sur 8

Principe de Dichotomie



  1. #1
    jeremy1907

    Principe de Dichotomie


    ------

    Bonjour,

    -Posons une echelle de 0 à 100
    -Une personne choisit un nombre x dans sa tete
    -"Le but" est de trouver se nombre en moins de coups possible ....(pour le moment rien de plus bateau)

    -"Le principe" le plus avantagueux sereais donc celui de la dichotomie, c'est a dire de donner toujours le nombre intermediaire entre l'echelle restante ...
    EX: Admettons que x=73 (mais n'en tenons pas compte)
    L'echelle est donc de 0 à 100, prenons 50, puis 75, puis 63,puis 69,puis 72 et enfin 73


    Enfin comment expliquer que l'on obitnet en maximum 6 coups ?

    -----

  2. Publicité
  3. #2
    SunnySky

    Re : Principe de Dichotomie

    J'imagine qu'à chaque essai, on nous informe si le nombre à trouver est inférieur ou supérieur à notre essai?

    Même dans ce cas, il est possible d'avoir besoin de 7 essais. Par exemple: le nombre à trouver est 1. On aura les essais suivants: 50-25-13-7-4-2-1.

    Pour être sûr de trouver au dernier essai, il ne doit rester que 1 possibilité. Cela signifie qu'à l'avant-dernier essai, il n'y a pas plus de 2 possibilités. Au tour précédent, il n'y avait donc qu'un maximum de 4 possibilités. Le tour d'avant: maximum 8 possibilités. Les tours précédents: 16, 32, 64, 128.

    Donc si on choisit un nombre inférieur à 128, il sera trouvé en un maximum de 7 essais par cette technique.
    Dernière modification par JPL ; 09/09/2007 à 13h51. Motif: Correction du titre
    Le monde se divise en 10 : ceux qui connaissent le code binaire et ceux qui ne le connaissent pas.

  4. #3
    danyvio

    Re : Principe de Dichotomie

    Citation Envoyé par jeremy1907 Voir le message

    Enfin comment expliquer que l'on obtient en maximum 6 coups ?
    J'ai eu le plaisir de programmer moult algo de recherche. Le principe est simple :
    Il suffit d'éliminer à chaque tour la moitié du reste. Comment ?
    D'abord, il faut que les éléments parmi lesquels on recherche soit TRIéS (important). On propose l'élément de milieu. En fonction de la réponse, on élimine ce qui est plus grand, ou plus petit, c'est à dire la moitié du reste.
    SUpposons qu'on recherche 720 parmi 1023 on proposera successivement :

    (1+1023/ / 2 soit 512 réponse : trop petit on élimine 1 à 512 il reste 513 à 1023
    On propose (513+1023) / 2 soit 768 réponse : trop grand, on élinmine 768 à 1023, il reste 513 à 767.
    On propose (513+767) / 2 soit 640 réponse : trop petit on élimine 513 à 640 il reste 641 à 767.

    On propose (641+767) / 2 soit 704 réponse : trop petit, on élimine 641 à 704 il reste 705 à 767.
    On propose (705+767) / 2 soit 736 réponse : trop grand on élimine 736 à 767 il reste 705 à 735.
    On propose (705+735) /2 soit 720 TROUVé !

    En conclusion, le nombre de recherches est, au maximum, = à log (de base 2) du nombre d'éléments, puisuqe à chaque itération on élimine la moitié du reste.
    On trouve des chercheurs qui cherchent ; on cherche des chercheurs qui trouvent !

  5. #4
    yat

    Re : Principe de Dichotomie

    Citation Envoyé par SunnySky Voir le message
    J'imagine qu'à chaque essai, on nous informe si le nombre à trouver est inférieur ou supérieur à notre essai?

    Même dans ce cas, il est possible d'avoir besoin de 7 essais. Par exemple: le nombre à trouver est 1. On aura les essais suivants: 50-25-13-7-4-2-1.

    Pour être sûr de trouver au dernier essai, il ne doit rester que 1 possibilité. Cela signifie qu'à l'avant-dernier essai, il n'y a pas plus de 2 possibilités. Au tour précédent, il n'y avait donc qu'un maximum de 4 possibilités. Le tour d'avant: maximum 8 possibilités. Les tours précédents: 16, 32, 64, 128.

    Donc si on choisit un nombre inférieur à 128, il sera trouvé en un maximum de 7 essais par cette technique.
    En fait je ne sais pas comment tu fais tes comptes. Si je suis ton raisonnement, au premier essai on peut avoir 128 possibilités, 64 au 2ieme, 32 au 3ieme, 16 au 4ieme, 8 au 5ieme, 4 au 6ieme, 2 au 7ieme, et ce n'est qu'au 8ieme essai qu'on est sur de trouver la solution (Je reprends tes valeurs). D'ailleurs tu peux essayer ta méthode avec la réponse 0 : comme on te répondra toujours "c'est moins", tu vas faire les mêmes propositions qu'avec le 1 sauf qu'à la fin tu n'auras pas trouvé. Il te faudra donc effectivement un 8ieme essai pour proposer le zéro.

    Une deuxième erreur dans ton raisonnement te fait retomber sur le bon résultat quand même : tu oublies qu'à chaque étape ou la réponse n'est pas trouvée, on élimine l'élément choisi. L'ensemble n'est donc pas exactement coupé en deux.

    Concrètement, pour trouver au dernier essai, en effet il faut qu'il ne reste qu'une possibilité, mais pour cela on peut avoir encore trois possibilité à l'étape précédente. Puis 7, 15, 31, 63 et 127. A un élément près, tu as donc toujours une étape de retard. Mais il faut bien 7 étapes maximum pour un ensemble de 127 éléments.

    Pour des entiers de 0 à 100, si on me répond toujours "c'est moins", la série de propositions sera, au pire : 50, 25, 12, 6, 3, 1 et 0.

  6. #5
    SunnySky

    Re : Principe de Dichotomie

    Bien vu! En effet, je me suis un peu trompé. Mais peut-être pas autant que tu le dis.

    Je disais qu'avec 7 essais, on pouvait trouver n'importe quel nombre jusqu'à 128 car 27=128, il y a donc 128 possibilités. Mais bien sûr, cela suppose implicitement que 0 est exclus: si on accepte le 0, on a 129 nombres différents entre 0 et 128. Si on accepte le zéro, alors j'aurais dû dire qu'il fallait arrêter à 127. Vouloir à tous prix me défendre, je pourrais bien dire que je précisais: Donc si on choisit un nombre inférieur à 128, il sera trouvé en un maximum de 7 essais par cette technique. Mais ce serait un peu malhonnête de ma part car je je n'y avais pas pensé du tout.

    Par contre, pour le reste, je crois avoir raison. Si tu choisis un nombre compris entre 1 et 128 (inclus...), je crois que je pourrai toujours le trouver en 7 coups. Par contre, de 1 à 129, je ne suis pas sûr d'y arriver.

    Si j'essaie d'expliquer mon raisonnement avec ta formulation, je dirais ceci: Avant mon premier essai, il y a 128 possibilités, mais après, il y en a 64. Après mon deuxième essai, il reste 32 possibilités. Il en reste 16 après le troisième, 8 après le quatrième, 8 après le quatrième, 4 après le cinquième, 2 après le sixième et par conséquent, les septième et huitième essais doivent nécessairement permettre de trouver la bonne réponse.

    Je reste toutefois sensible à ton argument selon lequel l'ensemble n'est pas exactement coupé en deux. Mais je n'arrive pas à l'exploiter de façon à résoudre un problème à 129 possibilités. Par exemple, si on choisit un chiffre entre 1 et 129, (disons le 64), on aura: 65, 32, 48, 56, 60, 62, 63, 64 et donc huit essais. J'ai besoin d'y réfléchir encore un peu.
    Le monde se divise en 10 : ceux qui connaissent le code binaire et ceux qui ne le connaissent pas.

  7. A voir en vidéo sur Futura
  8. #6
    yat

    Re : Principe de Dichotomie

    Citation Envoyé par SunnySky Voir le message
    Bien vu! En effet, je me suis un peu trompé. Mais peut-être pas autant que tu le dis.
    Sauf ton respect, la suite de ce message confirme que si
    Citation Envoyé par SunnySky Voir le message
    Je disais qu'avec 7 essais, on pouvait trouver n'importe quel nombre jusqu'à 128 car 27=128, il y a donc 128 possibilités. Mais bien sûr, cela suppose implicitement que 0 est exclus: si on accepte le 0, on a 129 nombres différents entre 0 et 128. Si on accepte le zéro, alors j'aurais dû dire qu'il fallait arrêter à 127. Vouloir à tous prix me défendre, je pourrais bien dire que je précisais: Donc si on choisit un nombre inférieur à 128, il sera trouvé en un maximum de 7 essais par cette technique. Mais ce serait un peu malhonnête de ma part car je je n'y avais pas pensé du tout.
    Quand bien même... le problème n'est pas là. Pour être sur de trouver en 7 essais, il faut que l'ensemble contienne 127 éléments. Pas 128. Donc de 1 à 128 ou de 0 à 127, ça ne marche pas. C'est 0 à 126 ou 1 à 127. La banane est quand tu dis qu'on peut trouver n'importe quel nombre jusqu'à 128 car 27=128. En effet, tu calcules ainsi le nombre d'étapes nécessaires pour connaitre le nombre, avec une division par 2 à chaque étape. Mais tu oublies qu'après l'avoir déterminé il faut encore utiliser un essai pour l'annoncer. Par exemple s'il te reste deux nombres possibles, tu peux très bien avoir besoin de deux essais pour donner le bon : il suffit de te tromper au premier essai. Donc en partant comme tu le fais sur une division par 2 de l'ensemble à chaque étape, on retombe bien sur les explications que tu donnais précédemment :
    Pour être sûr de trouver au dernier essai, il ne doit rester que 1 possibilité. Cela signifie qu'à l'avant-dernier essai, il n'y a pas plus de 2 possibilités. Au tour précédent, il n'y avait donc qu'un maximum de 4 possibilités. Le tour d'avant: maximum 8 possibilités. Les tours précédents: 16, 32, 64, 128.
    Et dans ces explications, y a pas à tortiller, si tu en déduis qu'il faut 7 étapes c'est tout simplement que tu as mal compté, il en faut 8. Donc au lieu de 1, 2, 4, 8, 16, 32, 64, 128, il faut dire 1, 3, 7, 15, 31, 63, 127. Et tu gagnes une étape, on retombe bien sur les 7 étapes nécessaires pour un ensemble d'au plus 127 éléments.
    Citation Envoyé par SunnySky Voir le message
    Par contre, pour le reste, je crois avoir raison. Si tu choisis un nombre compris entre 1 et 128 (inclus...), je crois que je pourrai toujours le trouver en 7 coups. Par contre, de 1 à 129, je ne suis pas sûr d'y arriver.
    Alors allons-y, je pense à un nombre entre 1 et 128 inclus, je te mets au défi de le trouver en 7 coups
    Pour accélérer un peu le processus et éviter d'avoir 8 allers-retours à faire, je te donne mon algorithme : je compte combien d'éléments de l'ensemble sont strictement supérieurs à ta proposition, combien sont strictement inférieurs. Si c'est égal, je reponds au hasard. Si l'un est plus grand que l'autre, alors je te branche sur le plus grand ensemble des deux. Par exemple, à la première étape, on a 128 éléments de 1 à 128. Si tu proposes 64 alors on a 63 éléments inférieurs et 64 supérieurs. Je réponds donc "c'est plus". Par contre, si tu proposes 65, alors je répondrai "c'est moins". Dans le premier cas, il te reste 64 éléments de 65 à 128... là encore, tu as un nombre pair d'éléments, donc tu ne peux pas te retrouver avec deux ensembles égaux à l'étape suivante. Si tu dis 96, tu as 31 éléments inférieurs, 32 supérieurs. Je dis donc "c'est plus". Et même si tu joues parfaitement, tu auras toujours un des deux ensembles qui aura exactement la moitié de la taille du précédent, ce qui t'amène donc à 16 possibilités après la 3ieme étape, 8 après la 4ieme, 4 après la 5ieme, 2 après la 6ieme, donc pour ta 7ieme proposition, tu auras toujours le choix entre ces deux possibilités. Comme naturellement tu vas te tromper, il te faudra un 8ieme essai pour gagner.
    Citation Envoyé par SunnySky Voir le message
    Si j'essaie d'expliquer mon raisonnement avec ta formulation, je dirais ceci: Avant mon premier essai, il y a 128 possibilités, mais après, il y en a 64. Après mon deuxième essai, il reste 32 possibilités. Il en reste 16 après le troisième, 8 après le quatrième, 8 après le quatrième, 4 après le cinquième, 2 après le sixième et par conséquent, les septième et huitième essais doivent nécessairement permettre de trouver la bonne réponse.
    Oui, oui, c'est exactement comme ça que j'ai formulé ton raisonnement hier. 128 possibilités => 8 essais pour trouver. Quel est ton propos exactement ?
    Citation Envoyé par SunnySky Voir le message
    Je reste toutefois sensible à ton argument selon lequel l'ensemble n'est pas exactement coupé en deux. Mais je n'arrive pas à l'exploiter de façon à résoudre un problème à 129 possibilités. Par exemple, si on choisit un chiffre entre 1 et 129, (disons le 64), on aura: 65, 32, 48, 56, 60, 62, 63, 64 et donc huit essais. J'ai besoin d'y réfléchir encore un peu.
    Tu n'as pas du bien lire mon post précédent. Pour un problème à 129 possibilités, il faut 8 essais au maximum. Pareil pour un problème à 128 possibilités. C'est uniquement à partir de 127 possibilités qu'on sera sur de s'en sortir en 7 essais.

    De manière un peu plus formelle, la démo : admettons qu'il faut au plus n essais pour trouver un élément dans un ensemble de 2n-1 éléments.

    Si on a un ensemble qui contient 2n+1-1 éléments, en choisissant l'élément médian on sépare l'ensemble en trois parties : l'élément médian et deux parties de 2n-1 éléments (2n-1 + 2n-1 + 1 = 2n+1-1).
    Si la réponse est "c'est ça", alors on aura trouvé en 1 essai. Si c'est "c'est plus" ou "c'est moins", alors on aura dépensé un premier essai, il reste à trouver la solution dans un sensemble de 2n-1 éléments. Or pour cela il faut au plus 2 essais, donc si l'ensemble contient 2n+1-1 éléments, il faudra au plus n+1 essais.

    Pour un ensemble d'un élément, il faut au plus un essai pour trouver la solution, donc la propriété est vraie pour n=0...

    Pour tout n entier positif, il faut donc au plus n essais pour trouver la solution dans un ensemble de 2n-1 éléments.


    Et maintenant, je démontre qu'il n'est pas possible d'être sur de trouver en n essais un élément parmi 2n : pour n=1, il n'est pas possible de trouver en un essai un élément parmi deux. C'est fini.

  9. Publicité
  10. #7
    SunnySky

    Re : Principe de Dichotomie

    Citation Envoyé par SunnySky Voir le message
    J'ai besoin d'y réfléchir encore un peu.
    Je ne regrette pas d'avoir écrit cette ligne...

    En effet, ton algorithme m'a convaincu. Ce qui m'avais distrait, dans ton message précédent, c'était que tu avais pris zéro, nombre que je n'acceptais pas. Du coup, ayant trouvé un os, je croyais que c'était le seul. Erreur...

    Et je comprends mieux la division en sous-ensembles égaux produite par un nombre impair de possibilités initiales.

    Bref, c'est un peu pénible pour mon orgueil, mais je te donne raison sur toute la ligne...
    Le monde se divise en 10 : ceux qui connaissent le code binaire et ceux qui ne le connaissent pas.

  11. #8
    magique

    Re : Principe de Dichotomie

    c'est l'alternance de valeurs paires et impaires qui fait que selon les limites données au départ, on commence par une valeur paire ou impaire c'est à dire que l'on peut diviser en deux parties égales ou non.
    Ce que je veux dire c'est que si on dit entre 0 et 100 inclus, il y a 101 valeurs et le but est donc d'enlever celle du milieu pour qu'il nous reste deux "lots" identiques je vais donc prendre 50 et il restera donc de 0 à 49 soit 50 valeurs et de 51 à 100 soit aussi 50 valeurs. Par contre au coup suivant quel que soit la réponse il y aura un nombre pair que je vais devoir donc diviser en deux parties forcément inégales!... et il y en aura une paire et l'autre impaire quel que soit mon choix
    Ce choix aurait pu intervenir dès le départ si l'on donne comme limite de 1 à 100 car nous avons 100 possibilités soit un nombre pair de valeur. Et je peux choisir soit 50 dans ce cas il restera de 1 à 49 = 49 valeurs et de 51 à 100 soit 50 valeurs. Mais je peux aussi choisir 51 et dans ce cas c'est l'inverse : nous avons 50 valeur de 1 à 50 et 49 de 52 à 100.
    C'est ce deuxième choix qui est préférable dans le cas où c'est un matheux qui vous propose ce jeu en effet pensant que vous allez choisir 50 qui vient naturellement à l'esprit
    Esope reste ici et se repose

Sur le même thème :

Discussions similaires

  1. Second principe
    Par mamono666 dans le forum Physique
    Réponses: 5
    Dernier message: 10/12/2007, 08h59
  2. principe d'equivalence
    Par felipe dans le forum Orientation avant le BAC
    Réponses: 2
    Dernier message: 02/11/2006, 17h53
  3. Principe de Construction
    Par Jack-Jack dans le forum Physique
    Réponses: 3
    Dernier message: 19/03/2006, 13h18
  4. Principe de dégradation .....
    Par wylli13 dans le forum Biologie
    Réponses: 0
    Dernier message: 25/09/2005, 12h36
  5. Second principe
    Par Josquin dans le forum Physique
    Réponses: 4
    Dernier message: 30/04/2005, 02h25