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

62. Алгоритмы накопления сумм и произведений.

Исходной величиной задачи является переменная N целого типа - количество слагаемых, величина i - номер текущего слагаемого - является промежуточной также целого типа, а величина S - искомая сумма вещественного типа.

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

Итак, тело цикла образуют следующие действия: вычисление очередного слагаемого, добавление его к текущему значению S и переход к следующему слагаемому.

Условие, при котором выполняются эти действия - наличие еще не вычисленных и не добавленных слагаемых.

До начала вычислений уже накопленное значение суммы равно нулю, а накапливать сумму можно начать с первого слагаемого.

Суммирование с рекуррентным соотношением между слагаемыми

Для накопления суммы переменной S присвоим значение нулевого слагаемого, а циклическое накопление начнем с первого. Кроме того, учтем, что в данном случае потребуется явное использование переменной a, служащей для хранения значения очередного слагаемого

62. Алгоритмы определения экстремального элемента массива.

Пусть задан массив x ={x1,x2,…,xn}. В простейшем случае необходимо найти его наибольший (наименьший) элемент.

Пусть max - переменная, которая играет роль «кандидата на должность» наибольшего элемента, i - номер очередного элемента массива. Если элементы массива, относятся к целому типу, то и max тоже величина целого типа.

Короче сравниваем каждый с max если больше max то присваиваем max значение .

63. Задача поиска. Алгоритмы линейного поиска.

Общая постановка. В заданной совокупности элементов требуется найти элемент, обладающий заданным набором свойств.

Важнейший частный случай. Задан массив x, нужно определить имеет ли в нем элемент, совпадающий с заданным числом a. Если такой элемент обнаружен, то в качестве дополнительной информации следует получить номер совпадающего с заданным элемента массива

a) Классический алгоритм

Предлагается очевидный подход к решению задачи: последовательное сравнение каждого очередного элемента массива с заданным. Такой способ называется линейным поиском.

б) Быстрый алгоритм

Идея быстрого алгоритма состоит в том, что выражения flag и x[i]=a эквивалентны. Следовательно, в условии в заголовке цикла вместо not flag можно использовать x[i]<>a, и отказаться от использования индикатора flag.

в) Алгоритм с барьером

Следующее улучшение состоит в упрощении условия в заголовке цикла. Целевым является условие x[i]<>a, которое убрать или упростить невозможно. Следовательно, можно рассматривать только условие i<=N, обеспечивающие прекращение просмотра после исчерпания всех элементов цикла. Идея состоит в выставлении в конце массива «барьера». Для этого в массив добавляется N+1 элемент, значение которого приравнивается к искомому.

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

64. Бинарный поиск.

Если данные упорядочены, то поиск можно сделать значительно более эффективным. Если x[i]<=x[i+1], i=1,2,…,N-1, то массив называется упорядоченным (отсортированным) по возрастанию.

Искомый элемент сравнивается со средним элементом массива.

Если они совпадают, то задача уже решена. Так как массив упорядочен, то при не совпадении элементов, в дальнейшем поиске можно не рассматривать одну из половин массива.

А именно, если средний элемент массива больше искомого, то все элементы, расположенные правее его, также будут больше искомого и дальнейший поиск следует осуществлять в левой половине массива.

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

Итак, во время поиска приходится повторять следующие действия: 1) выбирать средний элемент массива; 2) сравнивать его с искомым; 3) при необходимости уменьшать рассматриваемую часть массива в два раза выбором его правой или левой половины.

Так как начальный и конечный элементы рассматриваемой части массива при отбрасывании одной из половин массива будут изменяться, то для записи алгоритма следует использовать переменные, имеющие смысл номеров начального (левого) L и конечного (правого) R элементов массива. Поскольку в начале рассматривается весь массив, то L=1, а R=N. Номер среднего элемента M можно найти стандартным способом: M=(R+L) div 2.

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

На первом шаге количество K рассматриваемых элементов массива равно N

После первого шага количество K рассматриваемых элементов массива уменьшается в два раза K=N/2.

После второго шага - в четыре раза

Вообще, после шага с номером m:

В худшем случае процесс поиска закончится после того, как останется один элемент: . Отсюда:

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