[Algorytmy] Odgadywanie wylosowanej liczby ze zbioru 1-10

[kaki2308]

Mamy dany zbiór 1-10. Program losuje jedną liczbę z tego przedziału.
Zadaniem użytkownika jest odgadnąć tą liczbie przy jak najmniejszej liczbie prób.

Po wytypowaniu liczby program może udzielić następujących odpowiedzi:
-Odgadłeś!
-Nie udało się ustalić czy liczba jest mniejsza lub większa (losowo)
-Wybrałeś za dużo
-Wybrałeś za mało

Gdyby nie było opcji "Nie udało sie ustalić", skorzystałbym z metody "Dziel i zwyciężaj"
Zaczynam od 5, następnie dziele zbiór zależnie od tego czy wybrałem za dużo czy za mało, i znowu typuje liczbę i tak do komunikatu Odgadłeś.

Ale jest opcja "Nie udało sie ustalić" wybierana losowo, więc zastanawiam się jak najszybciej odgadnać taką liczbę.

Wydaje mi się że liczbę 5 musimy obstawiać aż dowiemy się czy wylosowana liczba jest mniejsza czy większa od 5. Ale dalej nie wiem jak to najszybciej zrobić.

[norwimaj]

Zaczynam od 5,

Jeżeli liczby są losowane z rozkładu jednostajnego, to można zacząć od \(\displaystyle{ 5}\) albo \(\displaystyle{ 6}\).

Co do dalszej części, napisz dokładniej, co komputer odpowiada i z jakimi prawdopodobieństwami. W szczególności istotne tu jest, czy kolejne odpowiedzi są niezależne. Jeśli są, to gdy raz nie udało się ustalić, następnym razem zadajemy to samo pytanie. Mogą to być zdarzenia całkiem zależne i jak raz się nie udało ustalić, to nigdy się nie uda. W takim wypadku nie ma sensu zadawać dwa razy tego samego pytania.

[kaki2308]

Prawdopodobieństwo wylosowania którejkolwiek z liczb jest takie same.
Prawdopodobieństwo pojawienia się informacji, że "nie udało się ustalić czy wylosowana liczba jest większa lub mniejsza" wynosi równo 30%

Kolejne odpowiedzi są niezależne, tzn kiedy wybierzemy np 5, program odpowie, że "nie udało się ustalić", to kiedy ponownie wybierzemy 5 mamy znowu 30% na pojawienie się informacji, "że nie udało się ustalić".

[norwimaj]

W takim razie trzeba pytać tak, jakby program zawsze udzielał informacji, a w razie gdy jej nie udzieli, pytać do skutku.

[kaki2308]

Na pewno jest to najwydajniejsza metoda?

Np program wylosował 6

Obstawiam:
-5 - wybrałeś za mało
-7 - nie udało się ustalić (czyli wiemy, że ta liczba jest błędna, bo gdyby była poprawna to pokazało by się, więc chyba nie ma sensu ponownie jej wybierać)

[norwimaj]

-7 - nie udało się ustalić (czyli wiemy, że ta liczba jest błędna, bo gdyby była poprawna to pokazało by się)

Dlaczego? Przecież gdy \(\displaystyle{ 7}\) jest szukaną liczbą, to też program może odpowiedzieć, że nie udało się ustalić, chyba że źle rozumiem treść.

[kaki2308]

No właśnie chyba nie do końca zrozumiałeś/aś, albo ja źle opisałem,
Kiedy jest poprawna program zatrzymuje się i wypisuje że podana liczba jest poprawna i kończy działanie.
Więc "nie udało się ustalić" ma 30% szans na wystąpienie jeśli podana liczba jest nie poprawna, jeśli jest poprawna to jest 0%, program wyświetla komunikat "Poprawna liczba" i kończy działanie.

[norwimaj]

W takim razie trzeba zapamiętywać, które liczby już są wykluczone, i strzelać w medianę tych pozostałych.-- 11 maja 2012, o 20:34 --Oczywiście w taką medianę, która należy do zbioru, czyli jeśli jest parzysta liczba pozostałych liczb, to można wylosować jedną z dwóch środkowych.

[kaki2308]

Też tak myślałem ale wolałem się upewnić. Zrobiłem sobie tablicę 10 elementową typu bool, która odpowiada za to czy liczba jest wykluczona czy nie.