Вычисление суммы числового ряда

Числовой ряд – это последовательность чисел, подчиняющаяся определенному закону.

Например:

Ряд натуральных чисел: 1, 2, 3, 4, 5, 6, …

Закон: каждый следующий элемент ряда на 1 больше предыдущего.

Задача: вычислить сумму чисел от 1 до 100.

Решение: обозначим сумму чисел - S.

Идея решения: каждое число от 1 до 100 нужно прибавлять к сумме.

Программа:

Program z1;

Var s, a: integer;

Begin

S:=0;

For a:=1 to 100 do

Begin

S:=S + a;

End;

Writeln(‘s=‘,s);

End.                

                   Вычисление очередного слагаемого по рекуррентной формуле

Пусть необходимо вычислить сумму следующего вида:

.

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

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

Другой подход связан с использованием функциональной связи между двумя последовательными значениями слагаемых искомой суммы y. Обозначим эти значения слагаемых через Ai и Ai+1. Составим отношение этих слагаемых

При таком подходе отпадает необходимость в вычислении факториала i!. Кроме того, вычисления могут быть выполнены с помощью одного цикла (нет необходимости в организации вложенных циклов).

Следующий фрагмент программы реализует необходимые вычисления:

Y := 0;

A := sqr(sqr(x)) / 24;

For I := 4 To n Do

Begin

Y := Y + A;

A := A * X /(i + 1);

End;

21 Алгоритм поиска максимального (минимального) элемента одномерного массива. Пример.

Дан массив X, состоящий из n элементов. Найти максимальный элемент массива и номер, под которым он хранится в массиве.

Алгоритм решения задачи следующий. Пусть в переменной с именем Max хранится значение максимального элемента массива, а в переменной с именем Nmax - его номер. Предположим, что первый элемент массива является максимальным, и запишем его в переменную Max, а в Nmax занесем его номер, то есть - 1. Затем все элементы, начиная со второго, сравниваем в цикле с максимальным. Если текущий элемент массива оказывается больше максимального, то записываем его в переменную Max, а в переменную Nmax - текущее значение индекса i. Процесс определения максимального элемента в массиве приведен в таблице 3.1 и изображен при помощи блок-схемы на рис. 3.7.

Рис. 3.7. Поиск максимального элемента и его номера в массиве

Совет. Алгоритм поиска минимального элемента в массиве будет отличаться от приведенного выше лишь тем, что в условном блоке знак поменяется с > на <.

22 Сортировка элементов в массиве

Сортировка представляет собой процесс упорядочения элементов в массиве в порядке возрастания или убывания их значений. Например, массив X из n элементов будет отсортирован в порядке возрастания значений его элементов, если X1 ≤ X2 ≤...≤ Xn, и в порядке убывания, если X1 ≥ X2 ≥ ... ≥ Xn.

Существует большое количество алгоритмов сортировки, но все они базируются на трех основных:

• сортировка обменом;

• сортировка выбором;

• сортировка вставкой.

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

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

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

Итак, решим следующую задачу. Задан массив Y из n целых чисел. Расположить элементы массива в порядке возрастания их значений.

3.6.1. Сортировка методом "пузырька"

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

Сортировка методом "пузырька" использует метод обменной сортировки и основана на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов. Рассмотрим алгоритм пузырьковой сортировки более подробно.

Сравним первый элемент массива со вторым, если первый окажется больше второго, то поменяем их местами. Те же действия выполним для второго и третьего, третьего и четвертого, i-го и (i+1)-го, (n-1)-го и n-го элементов. В результате этих действий самый большой элемент станет на последнее n-е место. Теперь повторим данный алгоритм сначала, но последний n-й элемент, рассматривать не будем, так как он уже занял свое место. После проведения данной операции самый большой элемент оставшегося массива станет на (n-1)-е место. Так повторяем до тех пор, пока не упорядочим весь массив.

В табл.3.2 подробно расписан процесс упорядочивания элементов в массиве. Нетрудно заметить, что для преобразования массива, состоящего из n элементов, необходимо просмотреть его n-1 раз, каждый раз уменьшая диапазон просмотра на один элемент. Блок-схема описанного алгоритма приведена на рис. 3.8. Обратите внимание на то, что для перестановки элементов (блок 4) используется буферная переменная b, в которой временно хранится значение элемента, подлежащего замене.

Таблица 3.2. Процесс упорядочивания элементов в массиве по возрастанию

Совет. Для перестановки элементов в массиве по убыванию их значений необходимо при сравнении элементов массива заменить знак > на <.

Рис. 3.8.	Сортировка массива пузырьковым	Рис. 3.9. Сортировка массива выбором наибольшего элемента

методом

3.6.2. Сортировка выбором

Алгоритм сортировки выбором приведен в виде блок-схемы на рис. 3.9. Найдем в массиве самый большой элемент (блоки 3-7) и поменяем его местами с последним элементом (блок 8). Повторим алгоритм поиска максимального элемента, уменьшив количество просматриваемых элементов на единицу (блок 9), и поменяем его местами с предпоследним элементом (блоки 3-7). Описанную выше операцию поиска проводим до полного упорядочивания элементов в массиве. Так как в блоке 9 происходит изменение переменной n, то в начале алгоритма ее значение необходимо сохранить (блок 1).

Совет. Для упорядочивания массива по убыванию необходимо перемещать минимальный элемент.

3.6.3. Сортировка вставкой

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

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

Составим блок-схему алгоритма (рис. 3.11), учитывая, что возможно описанные выше действия придется выполнить неоднократно.

Организуем цикл для просмотра всех элементов массива, начиная со второго (блок 4). Сохраним значение текущего i-го элемента во вспомогательной переменной X, так как оно может быть потеряно при сдвиге элементов (блок 5) и присвоим переменной j значение индекса предыдущего (i-1)-го элемента массива (блок 6). Далее движемся по массиву влево в поисках элемента меньшего, чем текущий и пока он не найден сдвигаем элементы вправо на одну позицию. Для этого организуем цикл (блок 7), который прекратиться, как только будет найден элемент меньше текущего. Если такого элемента в массиве не найдется и переменная j станет равной нулю, то это будет означать, что достигнута левая граница массива, и текущий элемент необходимо установить в первую позицию. Смещение элементов массива вправо на одну позицию выполняется в блоке 8, а изменение счетчика j в блоке 9. Блок 10 выполняет вставку текущего элемента в соответствующую позицию.

ю.   Рис. 3.11. Сортировка массива вставкой