Информатика. Курс лекций. Громов Ю.Ю - 88 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

Рис. 4.6. Алгоритм последовательного поиска,
записанный с помощью псевдокода
Применить процедуру Поиск к списку ингредиентов, используя в качестве искомого значе-
ния "мускатный орех"
Данная инструкция позволит установить, входит ли мускатный орех в перечень ингредиентов некоторого блюда.
Итак, можно сказать, что представленный на рис. 4.6 алгоритм последовательно рассматривает все элементы списка. По
этой причине данный алгоритм называется алгоритмом последовательного поиска (sequential search). В силу своей простоты
он часто применяется к коротким спискам либо, когда это необходимо, по каким-то иным соображениям. Однако в случае
длинных списков этот метод оказывается менее эффективным, чем другие (в чем мы скоро убедимся).
Управление циклами. Неоднократное использование инструкции
или последовательности инструкций представляет собой важную алгоритмическую концепцию. Одним из методов органи-
зации такого повторения является итеративная структура, известная как цикл (loop); здесь последовательность инструкций,
называемая телом цикла, многократно выполняется под контролем некоторого управляющего процесса. Типичный пример цикла
можно найти в алгоритме последовательного поиска, представленном на рис. 4.6. Здесь инструкция while используется в целях
управления повторным выполнением единственной инструкции "выбрать следующий элемент списка как Проверяе-
мое_значение". Общий синтаксис инструкции while имеет такой вид:
while (условие) do {тело цикла}
Эта инструкция представляет собой типичный образец циклической структуры, т.е. при ее выполнении циклически со-
вершаются следующие действия:
проверить условие
выполнить тело цикла
проверить условие
выполнить тело цикла
.
.
.
проверить условие
Эти действия будут продолжаться до тех пор, пока заданное условие будет выполняться.
Как правило, использование циклических структур придает алгоритму большую гибкость по сравнению с явным мно-
гократным написанием тела цикла. Рассмотрим такой пример:
Выполнить инструкцию "Добавить каплю серной кислоты" три раза.
Эта циклическая структура эквивалентна такой последовательности инструкций:
Добавить каплю серной кислоты.
Добавить каплю серной кислоты.
Добавить каплю серной кислоты.
Однако невозможно написать аналогичную последовательность, эквивалентную следующему циклу:
while (уровень рН больше, чем 4) do {добавить каплю серной кислоты}
Суть в том, что мы не знаем заранее, сколько капель серной кислоты понадобится в каждом конкретном случае.
А теперь давайте подробно рассмотрим, как осуществляется управление циклом. Может показаться, что эта часть
структуры цикла менее важна. Ведь именно в теле цикла непосредственно выполняются требуемые действия (например, до-
бавляются капли кислоты). Поэтому управляющие действия можно рассматривать просто как надстройку, появившуюся
только из-за того, что мы решили повторять выполнение тела цикла. Однако опыт показывает, что именно управление цик-
лом чаще всего служит источником ошибок в циклических структурах и, следовательно, требует особого внимания.
Управление циклом состоит из трех операций: инициализации, проверки и модификации (рис. 4.7), причем все они обя-
зательны для успешного управления циклом. Назначение операции проверки состоит в обеспечении своевременного оконча-
ния циклического процесса за счет отслеживания возникновения условия, указывающего, что цикл пора заканчивать. Это
условие называют условием завершения цикла. Именно для выполнения операции проверки некоторое условие обязательно
указывается при записи каждой инструкции while нашего
procedure Поиск (Список, ИскомоеЗначение)
if (Список пуст)
then {сообщить о неудаче}
else {выбрать в качестве ПроверяемоеЗначение
первый элемент Списка;
while (ИскомоеЗначение > ПроверяемоеЗначение
и есть непроверенные элементы) do
{выбрать в качестве ПроверяемоеЗначение
следующий элемент списка}
if (ИскомоеЗначение = ПроверяемоеЗначение)
then {сообщить об успехе}

Страницы