6.Базовые управляющие структуры: следование, ветвление, цикл, вызов подпрограммы. Нисходящее и пошаговое проектирование алгоритма программы.

Типы алгоритмов:

1.Следование – последовательность блоков, каждый из которых имеет по одному входу и выходу и выполняется ровно один раз.

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

3.Цикл – многократное повторение участков алгоритма.

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

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

7.Алгоритм линейного поиска значений в одномерном массиве. Поиск с барьером.

Простейший алгоритм поиска – линейный. Исходный массив просматривается последовательно от первого до последнего элемента.

Наихудший случай – слова нет в массиве (не найдено) – вывод можно сделать после просмотра всего массива.

Достоинство: простота реализации.

Недостаток: большое время.

Если используется for, всегда выполняется ровно n операций сравнения, независимо от того, найдено слово или нет. Разумно прекращать поиск, если слово найдено (если не требуется найти все вхождения слова).

При равномерном распределении элементов в массиве среднее время поиска обычно пропорционально величине n/2.

Во всех ниже изложенных алгоритмах будем считать, что производится поиск в массиве A из N целых чисел элемента, равного X.

const int n=10;

int a[n], x, i;

cin >> x;

for (i=0; i<n; i++)

if (a[i]==x) break;

if (a[i]<n)

cout <<"первое вхождение "<< х <<" на "<< i <<" номере";

else cout << " не нашли ";

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

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

Достоинство: на одну проверку меньше в цикле.

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

const int n=10;

int a[n], x, i=0;

cin >> x;

a[n-1]=x;

while (a[i]!=x) i++;

if (i<n-1) cout <<"первое вхождение "<< х <<" на "<< i <<" номере";

else cout << "не нашли";