[Algorytmy] Odgadywanie wylosowanej liczby ze zbioru 1-10
-
- Użytkownik
- Posty: 34
- Rejestracja: 11 maja 2012, o 12:20
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
[Algorytmy] Odgadywanie wylosowanej liczby ze zbioru 1-10
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ć.
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ć.
Ostatnio zmieniony 12 maja 2012, o 14:20 przez Afish, łącznie zmieniany 1 raz.
Powód: Otagowanie tematu.
Powód: Otagowanie tematu.
-
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
[Algorytmy] Odgadywanie wylosowanej liczby ze zbioru 1-10
Jeżeli liczby są losowane z rozkładu jednostajnego, to można zacząć od \(\displaystyle{ 5}\) albo \(\displaystyle{ 6}\).kaki2308 pisze: Zaczynam od 5,
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.
-
- Użytkownik
- Posty: 34
- Rejestracja: 11 maja 2012, o 12:20
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
[Algorytmy] Odgadywanie wylosowanej liczby ze zbioru 1-10
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ć".
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ć".
-
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
[Algorytmy] Odgadywanie wylosowanej liczby ze zbioru 1-10
W takim razie trzeba pytać tak, jakby program zawsze udzielał informacji, a w razie gdy jej nie udzieli, pytać do skutku.
-
- Użytkownik
- Posty: 34
- Rejestracja: 11 maja 2012, o 12:20
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
[Algorytmy] Odgadywanie wylosowanej liczby ze zbioru 1-10
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ć)
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ć)
-
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
[Algorytmy] Odgadywanie wylosowanej liczby ze zbioru 1-10
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 pisze: -7 - nie udało się ustalić (czyli wiemy, że ta liczba jest błędna, bo gdyby była poprawna to pokazało by się)
-
- Użytkownik
- Posty: 34
- Rejestracja: 11 maja 2012, o 12:20
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
[Algorytmy] Odgadywanie wylosowanej liczby ze zbioru 1-10
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.
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.
-
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
[Algorytmy] Odgadywanie wylosowanej liczby ze zbioru 1-10
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.
-
- Użytkownik
- Posty: 34
- Rejestracja: 11 maja 2012, o 12:20
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
[Algorytmy] Odgadywanie wylosowanej liczby ze zbioru 1-10
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.