Pickles AcademyZacznij za darmo

Wyszukiwanie binarne – ćwiczenia dla klasy 8

Przykładowe zadania z tematu Wyszukiwanie binarne z poprawną odpowiedzią i rozwiązaniem krok po kroku, od łatwego do trudnego. W aplikacji Pickles Academy dziecko za każdym razem dostaje nowe zadania tego samego typu, więc nie nauczy się ich na pamięć.

Przedmiot
Informatyka
Klasa
klasa 8
Dział
Systemy informacyjne

Rodzaje zadań: Zgadywanie liczby przez połowienie

Zasada: Wyszukiwanie binarne

Zawsze zgaduj środek pozostałych liczb. Każda odpowiedź odrzuca mniej więcej połowę.

n prób wystarczy, gdy 2ⁿ − 1 to co najmniej tyle, ile jest liczb: 7 liczb 3 próby, 15 liczb 4, 1000 liczb 10.

Przykład: Od 1 do 100: 2⁷ − 1 = 127 wystarczy, 2⁶ − 1 = 63 nie → najwyżej 7 prób

Uwaga: Nie zgaduj po kolei od początku: przy 100 liczbach mogłoby to zająć prawie 100 prób.

Przykładowe zadania

  1. Zadanie 1 Łatwe

    Myślę o liczbie całkowitej od 1 do 31. Na każdą próbę odpowiadam „większa”, „mniejsza” albo „zgadłeś”. Ile prób potrzebujesz co najwyżej, jeśli zawsze podajesz środkową z pozostałych liczb?

    Pokaż rozwiązanie
    Poprawna odpowiedź: 5

    Sposób: Każda próba co najmniej połowi resztę: 2^4 = 16 ≤ 31 < 2^5 = 32, więc 5 prób.

  2. Zadanie 2 Normalne

    Myślę o liczbie całkowitej od 1 do 530. Na każdą próbę odpowiadam „większa”, „mniejsza” albo „zgadłeś”. Ile prób potrzebujesz co najwyżej, jeśli zawsze podajesz środkową z pozostałych liczb?

    Pokaż rozwiązanie
    Poprawna odpowiedź: 10

    Sposób: Każda próba co najmniej połowi resztę: 2^9 = 512 ≤ 530 < 2^10 = 1024, więc 10 prób.

  3. Zadanie 3 Trudne

    Myślę o liczbie całkowitej od 1 do 80. Na każdą próbę odpowiadam „większa”, „mniejsza” albo „zgadłeś”. Zawsze podajesz środkową z pozostałych liczb (przy parzystej liczbie mniejszą z dwóch środkowych). Za którym razem zgadniesz liczbę 54?

    Pokaż rozwiązanie
    Poprawna odpowiedź: 7

    Sposób: Próby: 40, 60, 50, 55, 52, 53, 54.

Powiązane tematy

Wszystkie tematy: Informatyka

Ćwicz dalej w aplikacji

W minutę dziecko ma własnego awatara i pierwsze zadanie. Za darmo, bez reklam, dane w UE.

Zacznij za darmo