Divinație binară

Această intrare pe subiectul matematic este orfană , ceea ce înseamnă că nu există legături de intrare din alte intrări . Introduceți cel puțin unul relevant și non-generic și eliminați avertismentul. Urmați sfaturile de proiectare de referință .

Această intrare sau secțiune despre matematică nu citează sursele necesare sau cei prezenți sunt insuficienți . Puteți îmbunătăți această intrare adăugând citate din surse de încredere în conformitate cu liniile directoare privind utilizarea surselor . Urmați sfaturile de proiectare de referință .

Divinarea binară este un joc automat de matematică pentru a ghici un număr, folosind câteva întrebări prefixate care se bazează pe sistemul binar .

Operațiune

Odată ce un număr a fost ales într-un interval, fiecare întrebare vizează în secret identificarea unei cifre din scrierea sa în baza 2. Întrebările sunt puse implicit și pur și simplu întreb dacă numărul aparține unui set dat.

Succesiunea de răspunsuri „da” și „nu” pentru întrebări oferă apoi scrierea binară în „1” și „0” pentru a ghici numărul. Fără a fi nevoie să cunoașteți scrierea din baza 2, numărul poate fi obținut dând fiecărei întrebări o „valoare” dublă a celei anterioare: prima întrebare este 1, a doua 2, a treia 4, a patra 8 și așa mai departe . Adunând întrebările la care se dă un răspuns pozitiv, veți găsi numărul de ghicit.

Mai exact, prima întrebare întreabă dacă numărul este par sau impar, sau dacă scrierea sa binară se termină cu 0 sau 1. A doua întrebare întreabă dacă numărul este de tipul 4k sau 4k + 1 sau de tipul 4k + 2 sau 4k + 2 + 1 , deci dacă penultima cifră, întotdeauna în baza două, este 0 sau 1. Fiecare întrebare ulterioară descoperă o nouă cifră. Prin urmare, cu n întrebări este posibil să descoperiți orice număr ales la întâmplare în intervalul dintre 0 și ${\displaystyle {\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">2</span></span>}}^{\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">n</span></span>}}<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">-</span></span>\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">1</span></span>}}${\ displaystyle 2 ^ {n} -1} (a cărui scriere în bază binară este 11 ... 11, cu cifra 1 repetată de n ori). În schimb, pentru a ghici un număr între 0 și N, aveți nevoie cel puțin ${\displaystyle {\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">Buturuga</span></span>}}_{\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">2</span></span>}}<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;"></span></span><span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">(</span></span>\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">Nu.</span></span>}<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">+</span></span>\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">1</span></span>}<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">)</span></span>}${\ displaystyle \ log _ {2} (N + 1)} solicitări.

Exemplu de joc

Pentru a ghici un număr între 0 și 15, sunt suficiente patru întrebări care, conform acestei metode, întreabă dacă numărul este inclus sau nu în următoarele seturi:

Cu numărul 11, de exemplu, răspunsurile din ordine vor fi: da, da, nu, da. Prin urmare, adăugând valorile corespunzătoare fiecărei întrebări, obținem exact 1 + 2 + 8 = 11.

Variante

Prin aplicarea unei permutări numerelor intervalului, este posibil să se atribuie fiecărui număr un „cod” diferit de zerouri și unii, adică de răspunsuri afirmative și negative. În acest fel este posibil să se obțină toate sistemele care permit ghicirea numărului utilizând un număr minim de întrebări prestabilite: prin fiecare întrebare este de fapt posibil să se excludă (aproximativ) jumătate din numere și să se reducă cu (aproximativ) jumătate din mulțimea în care se găsește.numărul de ghicit.

O versiune mai complicată a acestui joc permite interlocutorului să mintă cu un anumit număr de întrebări, dar pentru aceasta este necesar să introducem câteva întrebări redundante. Această variantă se bazează pe algoritmi computerizați pentru reconstituirea datelor compromise într-o transmisie, subiacentă RAID . ^{[ fără sursă ]}