загрузка...
загрузка...
На головну

Пошук половинним діленням

  1. Sub пошук ()
  2. Алгоритм діагностичного пошуку при ЛНГ
  3. Алгоритм пошуку опорного і оптимального рішення
  4. Алгоритми роботи з двійковими впорядкованими деревами (деревами пошуку)
  5. блоковий пошук
  6. У вибірці, заданої розподілом відносних частот
  7. У пошуках кадрової стратегії XXI століття

Візьмемо для прикладу гру в вгадування цілого числа в певному діапазоні. Наприклад, від 1 до 128. Один грає загадує число, другий намагається його вгадати, задаючи питання, на які відповіддю може бути «так» або «ні». Ключем пошуку в цьому випадку є число, а критерієм пошуку - збіг числа, задуманого першим гравцем, з числом, званим другим гравцем.

Якщо питання задавати такі: «Число дорівнює одиниці?». Відповідь: «Ні». Питання: «Число дорівнює двом?» І т.д., то це буде послідовним перебір. Середнє число питань при багаторазовому повторенні гри з загадуванням різних чисел з даного діапазону дорівнюватиме 12/2 = 64.

Такий метод пошуку називається методом половинного ділення. Відповідно до цього методу, питання треба ставити так, щоб кожен відповідь зменшував число невідомих в два рази.

 Так само треба шукати і одне число з 128. Перше питання: «Число менше 65?» - «Так! - «Число більше 32?» - «Ні!» І т. Д. Будь-яке число вгадується максимум за 7 питань. Це пов'язано з тим, що 128 = 27 . Знову працює головна формула інформатики.

Метод половинного ділення для упорядкованого набору даних працює набагато швидше (у середньому), ніж метод послідовного перебору.

На малюнку наочно показаний процес пошуку (вгадування) числа «3» з діапазону цілих чисел від 1 до 8.

Якщо максимальне число діапазону N не дорівнює цілій степені двійки, то оптимальна кількість питань не буде постійною величиною, а дорівнюватиме одному з двох значень: X або Х + 1, де

2Х < N <2X+1

Наприклад, якщо тіло шукається в діапазоні від 1до 7то його можна вгадати за 2 або 3 питання, оскільки

22 <7 <23.

Число з діапазону від 1 до 200 можна вгадати за 7 або 8 питань, оскільки

27 <200 <28.

Перевірте ці твердження експериментально.

Половинним діленням можна шукати, наприклад, потрібну сторінку в товстій книзі: відкрити книгу посередині, зрозуміти, в якій з половин знаходиться шукана сторінка. Потім відкрити середину цієї половини і т. Д.

Набір даних може бути впорядкований не тільки по числовому ключу. Інший варіант упорядкування - за алфавітом. Половинним діленням можна здійснювати пошук в орфографічному словнику або в словнику перекладів слів з іноземної мови.



Попередня   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   Наступна

Система основних понять | Визначення розміру диска, файлу або папки | Надійність і довготривалість зберігання інформації | Передача інформації | Обробка інформації | II Архів інформації | Основні види програм-архіваторів | Програма архівації Microsoft Backup (резервна копія) | Постановка завдання пошуку даних | Організація набору даних |

загрузка...
© um.co.ua - учбові матеріали та реферати