Поиск элемента в таблице – Типичные задачи при работе с таблицами


§ 64. Поиск элемента в таблице

Изучив этот пункт, мы:

Познакомимся с типичными задачами обработки таблиц;

Узнаем, как осуществляется поиск элемента в неблагоустроенном линейной таблицы; узнаем об алгоритме бинарного поиска и его особенности;

Выясним, как порядок хранения данных в таблицах влияет на возможность быстрого доступа к нужной информации.

==== 64.1.Типичные задачи при работе с таблицами ==================================

В таблицах размещают и хранят различные данные, которые нужны человеку. Например, данные справочного характера (расписание движения транспорта, адреса и номера телефонов жителей города, наличие лекарственных препаратов в аптеках и т. Д.) данные, характеризующие экономические показатели работы предприятия (выпуск продукции, движение материальных ценностей, кадровый состав и т. п.); данные наблюдений (астрономических, экологических, медицинских) и др. Таблицы могут объединять различное количество элементов — и небольшую, если речь идет, скажем, о списке телефонов наших друзей, и огромную, если это телефонная книга миллионного города.

Задачи обработки таблиц чрезвычайно разнообразны. По данным таблицы можно исследовать тенденции, например, экономических или политических сдвигов и прогнозировать дальнейшие события; устанавливать связи между различными процессами, выявлять их взаимное тому подобное. При работе с таблицами информационно-справочного характера выделяются две основные задачи: упорядочение элементов таблицы по определенному признаку и поиск элемента с заданным свойством.

Методы поиска различаются по тому, упорядочены или нет данные в таблице. Большие таблицы конечно упорядочивают, то есть элементы в них размещают по возрастанию или по убыванию определенного признака (строго говоря, по неубывания или невозрастания определенного признака).Так, в городском телефонном справочнике номера телефонов расположены по алфавитному списку абонентов, иначе мы не смогли бы пользоваться таким справочником. Таблицы с небольшим количеством данных могут содержать неупорядоченные данные.

Мы рассмотрим два метода поиска элемента в линейной таблицы. Первый метод предназначается для поиска в неупорядоченных линейных таблицах, второй — в благоустроенных.

Сначала выясним, что является целью поиска. При наличии элемента в таблице недостаточно только зафиксировать этот факт. Важно найти номер, по которому нужный элемент размещен в таблице.

Например, если в таблице, содержащей перечень товаров на складе, мы нашли нужный нам товар по телефону 378, то по этому номеру мы можем установить характеристики этого товара, которые хранятся в других разделах таблицы — его стоимость, количество имеющихся экземпляров, дату поступления и т. д. Итак, Задачу Поиска элемента в таблице будем рассматривать в такой постановке: даны таблицу A, которая состоит из различных между собой целочисленных элементов, занумерованных числами натурального ряда от 1 до N. Определить, содержит ли эта таблица элемент X. Если да, указать номер элемента X в таблице; если нет — вывести соответствующее сообщение.

Читать  Лекция Паскаль 6 – Условные операторы, логика в Паскаль

==== 64.2.Поиск в неблагоустроенном таблицы. Программа «Последовательный перебор» =========

Если таблица неупорядоченное, то для поиска нужного элемента ничего другого не остается, как последовательно просматривать элементы таблицы, пока не найдется нужный элемент или таблицу будет исчерпан (в таком случае отмечаем, что таблица не содержит искомого элемента). Такой метод поиска называется Методом последовательного перебора.

Алгоритм последовательного перебора предусматривает просмотр элементов одного за другим в цикле.

Начинаем просмотр с первого элемента, его индекс i = 1.Раз за разом увеличиваем значение i на 1.Просмотр таблицы прекращается, если для очередного значения i элемент a [i] = x или если таблицу исчерпан, то есть пересмотрен элемент является последним: i = n. Для организации такого цикла уместно воспользоваться циклом с постусловием. Условие выхода из цикла имеет вид:

(a [i] = x) Или (i = n)

После выхода из цикла необходимо проверить, какая из простых условий — первая или вторая — сбылась. Если первая, то элемент найден и значение переменной i является номером элемента x в таблице.

Таблицу a сформируем из целых чисел от 10 до 50 с помощью датчика случайных чисел. Количество элементов таб-ке n зададим как константу. Выберем значение n = 10, чтобы и таблица, и диалог с пользователем размещались на одном экране. Сформированы элементы таблицы выведем на экран до начала поиска, чтобы удобно было задавать значение x, которое нужно найти в таблице.

Все переменные, используемые в программе, по их смысловому значению относим к целому типу.

Приведем текст программы поиска элемента методом последовательного перебора.

Program linear_search;

Uses Crt;

Const n = 10;

Ar i, x: Integer;

A: Array [1..n] Of integer; Begin

Randomize; Clrscr; For i: = 1 To n Do

Begin

A [i] = 10+ Random (41); {Определяем элементы Таблицы}

Writeln (i, ‘. «, a [i]); {Выводим их с номерами на Экран}

End;

Write ( ‘Какое значение нужно найти?’);

Читать  Понятие о языке программирования Turbo Pascal, главное окно Turbo

Readln (x); {Вводим искомое Значение}

I = 0;

Repeat

I = i + 1; {Перебираем поочередно Индексы Элементов} Until (a [i] = x) Or (i = 100); {Проверяем условие Завершения Просмотра} If a [i] = x {Проверяем, первая Условие Сбылась} Then writeln ( ‘Номер элемента — «, i) {Выводим результат Поиска}

Else writeln ( ‘Такого в таблице нет.’);

Readln end.

Для проверки правильности программы следует запустить ее на выполнение меньшей мере 4 раза с такими значениями x: значением, которое совпадает с первым элементом таблицы; с ее последним элементом; с одним из внутренних элементов; не совпадает ни с одним элементом таблицы.

Заметим, что мы рассмотрели метод последовательного перебора для таблицы с целочисленными элементами, но алгоритм решения задачи сохраняет свою значимость для любой таблицы.

==== 64.3.Поиск в упорядоченной таблице. Программа «Бинарный поиск» ==============

Метод последовательного перебора не является эффективным, поэтому его применяют только в тех случаях, когда другие методы предложить нельзя. Если таблица содержит элементы, упорядоченные определенным образом, то этим свойством таблицы можно воспользоваться для существенного ускорения процесса поиска элемента.

Будем считать, что целочисленные элементы нашей таблице упорядочены по возрастанию.

Идея Метода бинарного поиска заключается в том, что на каждом шагу диапазон неопределенности (т. е. диапазон таблицы, где осуществляется поиск) сокращается вдвое. Именно это и подчеркивается названием метода: слово «бинарный» происходит от английского binary двоичный.

Рассмотрим алгоритм бинарного поиска.

Сначала диапазон поиска охватывает элементы с индексами от 1 до n. Обозначим нижнюю границу поиска через ng, верхнюю — через vg: ng = 1, vg = n. Найдем середину этого диапазона s как пивсуму границ. Сравним срединный элемент a [s] с X.Есть один из трех случаев:

A [s] = x, тогда поиск завершен;

A [s]> x, тогда x следует искать в нижней половине диапазона, то есть между ng и s-1.Итак, меняем верхнюю границу поиска: vg = s-1;

A [s] <x, тогда x следует искать в верхней половине диапазона, то есть между s + 1 и vg. Итак, меняем нижнюю границу поиска: ng = s + 1.

Продолжаем, если нужно, поиск в сокращенном вдвое диапазоне. В конце концов мы или найдем элемент x, или в результате передвижений границ (нижней вверх, а верхней вниз) окажется, что верхняя граница стала ниже нижней, то есть vg <ng. Это свидетельствует об отсутствии элемента x в таблице.

Читать  Файлы Паскаль, файловый тип, Процедуры и Функции в Pascal

Просмотр таблицы целесообразно реализовать как цикл с постусловием. Условие выхода из цикла имеет вид: (a [s] = x) Или (vg <ng).

По разработанному алгоритму составим программу нахождения заданного элемента в благоустроенной таблицы методом бинарного поиска. Сформируем элементы таблицы по формуле a [i] = i 2 (можно взять и другую, но такую, чтобы значения элементов росли с увеличением их номера и).По смыслу задачи переменные i, x, s, vg, ng являются переменными целого типа.

Запишем программу.

Program binary_search;

Uses Crt;

Const n = 20;

Var i, s, vg, ng, x: Integer; a: Array [1..n] Of integer;

Begin Clrscr;

For i: = 1 To n Do begin

A [i] = Sqr (i) {Формируем упорядоченную Таблицу}

Writeln (i, ‘. «, a [i]); {Выводим ее элементы на Экран}

End;

Write ( ‘Какое значение нужно найти?’);

Readln (x); {Вводим искомое Значение}

Ng = 1, {Устанавливаем нижнюю границу Поиска}

Vg = n; {Устанавливаем верхнюю границу Поиска}

Repeat

S = (ng + vg) Div 2; {Находим индекс Среднего Элемента} If a [s]> x {Если средний элемент больше, чем Искомый, } Then vg = s-1; {то смещаем верхнюю Границу} If a [s] <x {Если средний элемент меньше, чем Искомый, } Then ng = s + 1; {то смещаем Нижнюю Границу} Until (a [s] = x) Or (vg <ng) {Проверяем условие Завершения Цикла} If a [s] = x {Проверяем, первая Условие Сбылась} Then writeln ( ‘Номер элемента — «, s) {Выводим результат Поиска}

Else writeln ( ‘Такого в таблице нет.’);

Readln end.

Для проверки правильности программы следует запустить ее на выполнение не менее 6 раз с такими значениями x: значением, которое совпадает с первым элементом таблицы; с ее последним элементом; с одним из внутренних элементов; меньше наименьшего элемента; больше самого элемента; находится между элементами таблицы.

Поскольку с каждым прохождением цикла диапазон неопределенности сокращается вдвое, можно доказать, что для поиска элемента или установления его отсутствии в благоустроенной таблицы с N элементов понадобится не более log 2 N шагов. Итак, поиск среди тысячи элементов завершится максимум за 10 шагов (2 10 = 1024), среди миллиона элементов — всего за 20 шагов (2 20 = 1048576), среди миллиарда — за 30 шагов. Для сравнения напомним, что по методу последовательного перебора соответствующая количество шагов оценивается как количество элементов

(Т. е. для тысячи элементов — тысяча шагов и т. Д.).

Читать  Лекция Паскаль 2 – настройка компонентов и форм, изменение их свойств

Как видим, упорядоченное хранение данных позволяет обеспечить быстрый доступ к ним. Это чрезвычайно важно, учитывая то, какую множество информации получило и продолжает получать человечество и как крайне необходимо иметь возможность оперативно использовать эти богатства, чтобы как можно быстрее идти вперед.

Если захотите убедиться в эффективности метода бинарного поиска и попробовать найти нужный элемент среди миллиона заданных (n = 1000000), то не забудьте все переменные программы объявить не как Integer, а как Longint; выбрать другую формулу для формирования элементов таблицы с тем, чтобы их значения не выходили за пределы диапазона данных типа Longint (например, a [i] = 10 + 5 * i;) влечет оператор вывода элементов таблицы на экран.

ВЫВОДЫ

Поиск элемента в таблице является типичной задачей при работе с таблицей. Целью поиска является определение номера, по которому искомый элемент содержится в таблице, или установления отсутствия такого элемента в таблице. Если таблица не упорядочена, то поиск элемента осуществляется методом последовательного просмотра элементов таблицы. Если элементы таблицы упорядочены, то для поиска элемента можно применить метод бинарного поиска. Это позволяет значительно сократить количество шагов, необходимых для осуществления поиска.

Контрольные вопросы и упражнения

1. Какие задачи являются основными при работе с информационно-справочными таблицами? а) переименования таблицы;

Б) поиск элемента с заданным свойством; в) упорядочение элементов таблицы;

Г) копирования данных из одной таблицы в другую.

2. Целью поиска элемента в таблице являются:

А) вычисление значения этого элемента;

Б) получения сообщения о том, есть ли искомый элемент в таблице;

В) нахождение номера, по которым элемент содержится в таблице, или установление его отсутствия в таблице.

3. Среди приведенных таблиц выберите упорядочены: а) таблица цифр: -56, -17, 0, 2, 2, 43, 100;

Б) таблица цифр: -7566, -7056, 2145, 0, 2145, 4321, 99001;

В) таблица цифр: -512, -517, -6240, -7584, -23100;

Г) таблица слов: весна, зима, лето, осень;

Д) таблица фамилий: Барабашев, Веприк, Мельник, Потемкин; е) таблица слов: bit, byte, kilobyte, gigabyte, megabyte.

4. Для поиска элемента в неблагоустроенном таблицы можно применить: а) метод последовательного перебора;

Б) метод бинарного поиска.

5. Метод бинарного поиска можно применить для поиска элемента: а) в таблице чисел, упорядоченных по убыванию;

Читать  Тип дата-время в Паскаль

Б) в таблице чисел, упорядоченных по возрастанию;

В) в любой числовой таблицы;

Г) в таблице слов, упорядоченных по алфавиту.

6. Составьте программу, которая в неблагоустроенном таблицы с 20 целых чисел с диапазона [10; 10], определенных датчиком случайных чисел, осуществляет поиск числа 0.Если таких несколько, найти первое.

7. Создайте две таблицы. Первая содержит названия конечных пунктов следования поездов, вторая — время их отправления. Составьте программу, которая по запросу пользователя выводит на экран сообщение, когда отправляется его поезд.

8. Создайте две таблицы. Первая содержит выигрышные номера лотереи, упорядоченные по возрастанию, вторая — выигрыши, которые выпали на эти номера. Составьте программу, которая проверяет номер лотерейного билета пользователя и сообщает, выиграл он в лотерею, и именно, если выиграл.

9. Создайте две таблицы. Первая содержит список фамилий учеников, упорядоченный по алфавиту, вторая — даты их рождения. Составьте программу, которая будет находить дату рождения ученика с заданным фамилией.

10. Сложите две таблицы. Первая содержит перечень товаров в магазине подарков, вторая — их цены. Товары упорядочены по возрастанию цены. Составьте программу, которая по запросу покупателя сообщает, есть подарки на заданный диапазон цен, и какие они, если есть.

11. Составьте программу «Угадай число». Программа предлагает пользователю загадать целое число от 1 до 250.Программа может задавать пользователю только вопросы типа: «Ваше число больше (указывает число)?». Пользователь может отвечать только одно из двух: «Да» или «Нет».После нескольких вопросов программа выводит на экран сообщение: «Вы загадали число…» (указывает число) или «Вы неправильно отвечали на мои вопрос! ».

12. Составьте игровую программу «Угадай мое число!». Пользователь задает диапазон чисел для игры. Программа с помощью датчика случайных чисел «загадывает» число из заданного диапазона и предлагает пользователю угадать его. Программа выводит на экран вопрос «Вы знаете мое число?».Если пользователь отвечает «Да», то программа предлагает ему ввести число и проверяет правильность отгадывание. Если пользователь отвечает «Нет», то программа предлагает ему подсказку: «Введите какое-нибудь число, а я скажу, больше оно от задуманного».Программа ведет учет количества подсказок, которые понадобились пользователю для отгадывание числа.

[Всего голосов: 3    Средний: 5/5]