ПОШУК

Пошуком заданого значення в масиві доводиться займатися дуже часто При цьому задається аргумент пошуку і потрібно визначити положення в масиві такого елемента, у якого значення ключа збігається з аргументом Якщо порядок розташування даних у масиві невідомий, то немає більш ефективного методу, чим описаний раніше простий послідовний пошук, при якому ключ кожного елемента даних порівнюється з аргументом пошуку деяким регулярним чином При цьому для пошуку в масиві з N значень в середньому припадає виконати N / 2 порівнянь Запропонувати методи більш швидкого пошуку можна тільки в тому випадку, якщо дані певним чином впорядковані Наприклад, той факт, що в телефонному довіднику записи впорядковані за алфавітом, дозволяє нам дуже швидко знаходити потрібне прізвище і номер телефону

Універсальним методом швидкого пошуку в упорядкованому безлічі даних є бінарний пошук, при якому число порівнянь, виконуваних для пошуку в масиві з N значень, в середньому

пропорційно log2N Порівняємо це число із середнім числом порівнянь в простому методі послідовно-

вательного пошуку, яке пропорційно N:

N

10

100

1000

log2N

33

66

99

Очевидно, додаткові витрати на впорядкування безлічі даних більш ніж окупаються при застосуванні бінарного пошуку

Метод бінарного пошуку полягає в послідовному розподілі множини даних на дві рівні частини – звідси і назва бінарний (Двійковий) Спочатку областю пошуку вважається все безліч з нього витягується середній елемент, ключ якого порівнюється з аргументом пошуку Якщо вони співпали, то пошук на цьому успішно завершується, але якщо вони не збігаються, то аргумент пошуку може бути більше або менше ключа середнього елемента Тоді залежно від способу впорядкування даних в якості області пошуку вибирається перша або друга половина безлічі, з неї витягується середній елемент і його ключ порівнюється з аргументом пошуку Цей процес продовжується до тих пір, поки не призведе або до / спіху, або до невдачі Таке послідовне розподіл безлічі працює на диво добре На рис 43 показаний перший крок пошуку в масиві 134

Рис 43 Масив сортується в алфавітному порядку Зображений перший цикл довічного пошуку з ключем S $

рядків символів, впорядкованих за алфавітом по декількох перших символах кожного рядка

(Що є ключем)

Наведена нижче форма алгоритму бінарного пошуку слід формі, запропонованої П Наурум, згідно з якою вводяться фіктивні нижня і верхня межі значень індексів масиву, рівні -1 та N +1, в той час як фактично індекси пробігають значення від 0 до N У цьому алгоритмі перші М символів кожного рядка розглядаються як ключ і рядки упорядковуються в алфавітному порядку за цим ключам Рядки можуть містити прізвища, за якими слідують адреси або яка-небудь інша інформація таким чином, процедура пошуку може бути частиною довідкової системи Структограмма алгоритму така:

Вхідними для наведеного нижче фрагмента програми служать масив А $ (0), .. , A $ (N),

значення N, значення М, визначальне число символів в ключі, а також аргумент пошуку у змінній S $ На виході з фрагмента в Q знаходиться індекс знайденого елементу масиву або N +1, якщо елемента із заданим значенням ключа немає

1000 REM БІНАРНИЙ

1010 REM передбачалося, що МАСИВ A $ (0), .., A $ (N)

1020 REM МІСТИТЬ ЗНАЧЕННЯ Відсортовані за ПЕРШИМ М

1030 REM символи в алфавітному порядку

1040 REM В Q ПОВЕРТАЄТЬСЯ АБО ІНДЕКС знайдені значення

1050 REM ЯКОЇ N +1

1060 В2 = -1

1070 T2=N+1

1080 E=0

1090 IF T2-B2=l THEN 1220

1100 С = INT (B2 + T2) / 2)

1110   K$=LEFT$(A$(C),M)

1120   IF S$=K$ THEN 1160

1130     IF S

Пошуком заданого значення в масиві доводиться займатися дуже часто. При цьому задається аргумент пошуку і потрібно визначити положення в масиві такого елемента, у якого значення ключа збігається з аргументом. Якщо порядок розташування даних у масиві невідомий, то немає більш ефективного методу, чим описаний раніше простий послідовний пошук, при якому ключ кожного елемента даних порівнюється з аргументом пошуку деяким регулярним чином. При цьому для пошуку в масиві з N значень в середньому припадає виконати N / 2 порівнянь. Запропонувати методи більш швидкого пошуку можна тільки в тому випадку, якщо дані певним чином впорядковані. Наприклад, той факт, що в телефонному довіднику записи впорядковані за алфавітом, дозволяє нам дуже швидко знаходити потрібне прізвище і номер телефону.

Універсальним методом швидкого пошуку в упорядкованому безлічі даних є бінарний пошук, при якому число порівнянь, виконуваних для пошуку в масиві з N значень, в середньому

пропорційно log2N. Порівняємо це число із середнім числом порівнянь в простому методі послідовно-

вательного пошуку, яке пропорційно N:

N

10

100

1000

log2N

3.3

6.6

9.9

Очевидно, додаткові витрати на впорядкування безлічі даних більш ніж окупаються при застосуванні бінарного пошуку.

Метод бінарного пошуку полягає в послідовному розподілі множини даних на дві рівні частини – звідси і назва “бінарний” (Двійковий). Спочатку областю пошуку вважається все безліч; з нього витягується середній елемент, ключ якого порівнюється з аргументом пошуку. Якщо вони співпали, то пошук на цьому успішно завершується, але якщо вони не збігаються, то аргумент пошуку може бути більше або менше ключа середнього елемента. Тоді залежно від способу впорядкування даних в якості області пошуку вибирається перша або друга половина безлічі, з неї витягується середній елемент і його ключ порівнюється з аргументом пошуку. Цей процес продовжується до тих пір, поки не призведе або до / спіху, або до невдачі. Таке послідовне розподіл безлічі працює на диво добре. На рис. 4.3 показаний перший крок пошуку в масиві 134

Рис. 4.3. Масив сортується в алфавітному порядку. Зображений перший цикл довічного пошуку з ключем S $

рядків символів, впорядкованих за алфавітом по декількох перших символах кожного рядка

(Що є ключем).

Наведена нижче форма алгоритму бінарного пошуку слід формі, запропонованої П. Наурум, згідно з якою вводяться фіктивні нижня і верхня межі значень індексів масиву, рівні -1 та N +1, в той час як фактично індекси пробігають значення від 0 до N. У цьому алгоритмі перші М символів кожного рядка розглядаються як ключ і рядки упорядковуються в алфавітному порядку за цим ключам. Рядки можуть містити прізвища, за якими слідують адреси або яка-небудь інша інформація; таким чином, процедура пошуку може бути частиною довідкової системи. Структограмма алгоритму така:

Вхідними для наведеного нижче фрагмента програми служать масив А $ (0), … , A $ (N),

значення N, значення М, визначальне число символів в ключі, а також аргумент пошуку у змінній S $. На виході з фрагмента в Q знаходиться індекс знайденого елементу масиву або N +1, якщо елемента із заданим значенням ключа немає.

1000 REM БІНАРНИЙ

1010 REM передбачалося, що МАСИВ A $ (0), …, A $ (N)

1020 REM МІСТИТЬ ЗНАЧЕННЯ. Відсортовані за ПЕРШИМ М

1030 REM символи в алфавітному порядку

1040 REM В Q ПОВЕРТАЄТЬСЯ АБО ІНДЕКС знайдені значення

1050 REM ЯКОЇ N +1

1060 В2 = -1

1070 T2=N+1

1080 E=0

1090 IF T2-B2=l THEN 1220

1100 С = INT (B2 + T2) / 2)

1110   K$=LEFT$(A$(C),M)

1120   IF S$=K$ THEN 1160

1130     IF S$<K$ THEN 1160

1140       B2=C

1150             GOTO 1250

1160                  T2=C

1170             GOTO 1250

1180 PRINT “ЗНАЧЕННЯ ЗНАЙДЕНО”

1190        Q=C

1200        E=1

1210        GOTO 1250

1220 PRINT “ЗНАЧЕННЯ НЕ ЗНАЙДЕНО”

1230   Q=T2

1240   E=1

1250   IF E=0 THEN 1090

1260 REM ВИХІД

Мінлива Е вводиться для обліку різних умов виходу з циклу. Довільні передачі управління за межі такого циклу не можуть бути представлені символами структограмми, тому застосування структограмм сприяє розвитку хорошого стилю програмування. Цей фрагмент можна перевірити, додавши до нього оператори

10 REM ТЕСТ ПРОГРАМИ двійкову У

20 DIM A$(2B)

30 N=15

40 М = ​​1

50 INPUT “Введіть шукане значення”;S$

60 FOR I = 0 ТО N

70   READ A$(I)

80 NEXT I

90 DATA ABBA, BRIAN, COLIN, FRED

100 DATA GERRY, HUGH, JIM, LEN

110 DATA MIKE, NICK, OLIVER, PETER

120 DATA RUPERT, STAN, TIM, WILLIAM

1300      PRINT Q, A$(Q)

1310   END

Запуски цієї програми для пошуку по черзі всіх імен з міститься в ній списку до реєстрація чисел порівнянь показують, що в середньому на кожен успішний пошук припадає 3,4 порівняння (log2 16 дорівнює 4); самі числа розподілені між 5 (найгірший випадок) і 1 (найкращий випадок).

ВПРАВИ

4.1. Напишіть програму для читання десяти чисел зі списку даних оператора DATA і друку найбільшого і найменшого з цих чисел.

4.2. Напишіть програму для реєстрації та зображення екзаменаційних оцінок одного класу. Прізвища учнів зберігаються в кількох операторах DATA в програмі. Під час виконання програма по черзі виводить кожну прізвище і запитує введення оцінки з терміналу. На закінчення зображуються середня оцінка і список прізвищ із зазначенням оцінок.

4.3. Напишіть програму для ведення журналу відвідуваності класу. Дані представляються у вигляді списку одиниць і нулів: одиниця означає, що учень був присутній в класі, а нуль – був відсутній. Для класу з восьми учнів запис одного дня в журналі відвідуваності може мати вигляд

1, 1,0, 1, 1, 1,0,0 Ці дані можна помістити в оператор DATA або ввести з термінала.

Розробіть програму для читання зроблених протягом тижня (5 днів) записів у журналі відвідуваності і друку числа учнів у класі по днях тижня, а також кількості днів, які кожен учень був присутній у класі (при цьому будуть потрібні масиви).

4.4. Розробіть програму для виконання наступних дій з рядками символів:

(А) Присвоїти двом строковим змінним відповідно Ваші ім’я та прізвище, об’єднати ці рядки в одну і роздрукувати результат.

(Б) Виділити з строкових змінних ініціали та надрукувати їх.

(В) Присвоїти однієї строкової змінної форму звернення до Вас (Г-Н, ПАНІ і пр.), а інший –

Вашу адресу і роздрукувати Ваші прізвище та адресу в звичайній формі.

4.5. Група з шести робочих зайнята на будівельному майданчику. Протягом кожного тижня двоє з них відповідають за організацію чаювання. Розробіть і напишіть програму для друку такого списку пар імен, що становить повний графік чергувань, в якому кожен з працівників відповідає за чаювання протягом п’яти тижнів. Спробуйте використовувати оператор DATA і масив рядків символів для роботи з прізвищами.

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

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

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

4.8. Напишіть програму для видачі довідок. Відповідні відомості можна зберігати в операторах DATA, випереджаючи кожну довідку “ключовим словом”. При виконанні програма повинна запросити введення ключового слова, знайти його положення і роздрукувати відповідну йому довідку.

Як приклад використовуйте частину предметного покажчика, розглядаючи назву предмета в якості ключа, а номер сторінки в якості довідки. У відповідь на введення назви предмета програма повинна видавати номер сторінки, на якій воно зустрічається.

Можна використовувати і будь-яку іншу інформацію, наприклад з приводу виборів до парламенту, розглядаючи прізвище депутата в якості ключа, а число поданих за нього голосів у якості довідки. (Довідкову інформацію краще всього поміщати у файлі, см. гл. 8.)

Джерело: Уолш Б. Програмування на Бейсике: Пер. з англ. М.: Радіо і зв’язок, 1988. 336 с: ил.

ltK$ THEN 1160

1140       B2=C

1150             GOTO 1250

1160                  T2=C

1170             GOTO 1250

1180 PRINT ЗНАЧЕННЯ ЗНАЙДЕНО

1190        Q=C

1200        E=1

1210        GOTO 1250

1220 PRINT ЗНАЧЕННЯ НЕ ЗНАЙДЕНО

1230   Q=T2

1240   E=1

1250   IF E=0 THEN 1090

1260 REM ВИХІД

Мінлива Е вводиться для обліку різних умов виходу з циклу Довільні передачі управління за межі такого циклу не можуть бути представлені символами структограмми, тому застосування структограмм сприяє розвитку хорошого стилю програмування Цей фрагмент можна перевірити, додавши до нього оператори

10 REM ТЕСТ ПРОГРАМИ двійкову У

20 DIM A$(2B)

30 N=15

40 М = ​​1

50 INPUT Введіть шукане значення;S$

60 FOR I = 0 ТО N

70   READ A$(I)

80 NEXT I

90 DATA ABBA, BRIAN, COLIN, FRED

100 DATA GERRY, HUGH, JIM, LEN

110 DATA MIKE, NICK, OLIVER, PETER

120 DATA RUPERT, STAN, TIM, WILLIAM

1300      PRINT Q, A$(Q)

1310   END

Запуски цієї програми для пошуку по черзі всіх імен з міститься в ній списку до реєстрація чисел порівнянь показують, що в середньому на кожен успішний пошук припадає 3,4 порівняння (log2 16 дорівнює 4) самі числа розподілені між 5 (найгірший випадок) і 1 (найкращий випадок)

ВПРАВИ

41 Напишіть програму для читання десяти чисел зі списку даних оператора DATA і друку найбільшого і найменшого з цих чисел

42 Напишіть програму для реєстрації та зображення екзаменаційних оцінок одного класу Прізвища учнів зберігаються в кількох операторах DATA в програмі Під час виконання програма по черзі виводить кожну прізвище і запитує введення оцінки з терміналу На закінчення зображуються середня оцінка і список прізвищ із зазначенням оцінок

43 Напишіть програму для ведення журналу відвідуваності класу Дані представляються у вигляді списку одиниць і нулів: одиниця означає, що учень був присутній в класі, а нуль – був відсутній Для класу з восьми учнів запис одного дня в журналі відвідуваності може мати вигляд

1, 1,0, 1, 1, 1,0,0 Ці дані можна помістити в оператор DATA або ввести з термінала

Розробіть програму для читання зроблених протягом тижня (5 днів) записів у журналі відвідуваності і друку числа учнів у класі по днях тижня, а також кількості днів, які кожен учень був присутній у класі (при цьому будуть потрібні масиви)

44 Розробіть програму для виконання наступних дій з рядками символів:

(А) Присвоїти двом строковим змінним відповідно Ваші імя та прізвище, обєднати ці рядки в одну і роздрукувати результат

(Б) Виділити з строкових змінних ініціали та надрукувати їх

(В) Присвоїти однієї строкової змінної форму звернення до Вас (Г-Н, ПАНІ і пр), а інший –

Вашу адресу і роздрукувати Ваші прізвище та адресу в звичайній формі

45 Група з шести робочих зайнята на будівельному майданчику Протягом кожного тижня двоє з них відповідають за організацію чаювання Розробіть і напишіть програму для друку такого списку пар імен, що становить повний графік чергувань, в якому кожен з працівників відповідає за чаювання протягом пяти тижнів Спробуйте використовувати оператор DATA і масив рядків символів для роботи з прізвищами

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

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

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

48 Напишіть програму для видачі довідок Відповідні відомості можна зберігати в операторах DATA, випереджаючи кожну довідку ключовим словом. При виконанні програма повинна запросити введення ключового слова, знайти його положення і роздрукувати відповідну йому довідку

Як приклад використовуйте частину предметного покажчика, розглядаючи назву предмета в якості ключа, а номер сторінки в якості довідки У відповідь на введення назви предмета програма повинна видавати номер сторінки, на якій воно зустрічається

Можна використовувати і будь-яку іншу інформацію, наприклад з приводу виборів до парламенту, розглядаючи прізвище депутата в якості ключа, а число поданих за нього голосів у якості довідки (Довідкову інформацію краще всього поміщати у файлі, см гл 8)

Джерело: Уолш Б Програмування на Бейсике: Пер з англ М: Радіо і звязок, 1988 336 с: ил

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*