1. Znajdujesz się w n-piętrowym budynku. Chcesz sprawdzić z którego piętra możesz zrzucić swój telefon tak aby nie został uszkodzony. W tym celu zrzucasz telefon i sprawdzasz czy nie został zniszczony(zniszczonego nie można użyć do dalszych prób). Napisz najkrótszą strategię w której możesz wykorzystać:
a) jeden telefon
b) dwa telefony
2. Grasz w grę :zgadnij liczbę:. Aby wygrać musisz zgadnąć przypadkowo wylosowaną liczbę \(\displaystyle{ x \in \left\{0,...,999 \right\}}\) w maksymalnie 10-ciu próbach. Po każdej próbie dostajemy informacje, czy nasza liczba \(\displaystyle{ a}\) jest większa lub mniejsza od liczby którą musimy odgadnąć \(\displaystyle{ x}\). Napisz algorytm który umożliwi zgadnięcie liczby
Proszę o podpowiedzi
[Algorytmy]Zrzucanie komórki
[Algorytmy]Zrzucanie komórki
W 2) można zacząć od \(\displaystyle{ 500}\) i potem \(\displaystyle{ 250}\) lub \(\displaystyle{ 750}\) itd. żeby co próbę zmniejszać przedział o połowę.
-
Afish
- Moderator
- Posty: 2828
- Rejestracja: 15 cze 2008, o 15:45
- Płeć: Mężczyzna
- Lokalizacja: Seattle, WA
- Podziękował: 3 razy
- Pomógł: 356 razy
[Algorytmy]Zrzucanie komórki
1. Co znaczy „najkrótszą”? Najkrótszą w zapisie czy generującą najmniej prób? Jeżeli to drugie, to:
a) tutaj cudów nie ma, trzeba sprawdzać po kolei od dołu po jednym piętrze
b) rozwiązanie dynamiczne, definiujemy funkcję \(\displaystyle{ f(h, k)}\) która poda nam najmniejszą liczbę zrzuceń (w zależności od \(\displaystyle{ n}\) reprezentującego wysokość budynku i \(\displaystyle{ k}\) reprezentującego liczbę dostępnych telefonów) potrzebnych do ustalenia wysokości, na której telefon się rozbija; mamy prostą rekurencję:
\(\displaystyle{ f(h, k) = \min _{ 1 \le i \le h } \{f(i-1, k-1), f(h-i, k) \} + 1}\)
Rozwiązaniem jest \(\displaystyle{ f(n, 2)}\). Jest to dokładnie zadanie Jajka z OI.
2. Wyszukiwanie binarne.
a) tutaj cudów nie ma, trzeba sprawdzać po kolei od dołu po jednym piętrze
b) rozwiązanie dynamiczne, definiujemy funkcję \(\displaystyle{ f(h, k)}\) która poda nam najmniejszą liczbę zrzuceń (w zależności od \(\displaystyle{ n}\) reprezentującego wysokość budynku i \(\displaystyle{ k}\) reprezentującego liczbę dostępnych telefonów) potrzebnych do ustalenia wysokości, na której telefon się rozbija; mamy prostą rekurencję:
\(\displaystyle{ f(h, k) = \min _{ 1 \le i \le h } \{f(i-1, k-1), f(h-i, k) \} + 1}\)
Rozwiązaniem jest \(\displaystyle{ f(n, 2)}\). Jest to dokładnie zadanie Jajka z OI.
2. Wyszukiwanie binarne.
-
kasia00
- Użytkownik
- Posty: 106
- Rejestracja: 31 paź 2015, o 22:06
- Płeć: Kobieta
- Lokalizacja: Frankfurt
- Podziękował: 34 razy
[Algorytmy]Zrzucanie komórki
Jajko z OI?Afish pisze:1. Co znaczy „najkrótszą”? Najkrótszą w zapisie czy generującą najmniej prób? Jeżeli to drugie, to:
a) tutaj cudów nie ma, trzeba sprawdzać po kolei od dołu po jednym piętrze
b) rozwiązanie dynamiczne, definiujemy funkcję \(\displaystyle{ f(h, k)}\) która poda nam najmniejszą liczbę zrzuceń (w zależności od \(\displaystyle{ n}\) reprezentującego wysokość budynku i \(\displaystyle{ k}\) reprezentującego liczbę dostępnych telefonów) potrzebnych do ustalenia wysokości, na której telefon się rozbija; mamy prostą rekurencję:
\(\displaystyle{ f(h, k) = \min _{ 1 \le i \le h } \{f(i-1, k-1), f(h-i, k) \} + 1}\)
Rozwiązaniem jest \(\displaystyle{ f(n, 2)}\). Jest to dokładnie zadanie Jajka z OI.
2. Wyszukiwanie binarne.