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

Суть алгоритма накопления в том, что сумма или произведение вычисляются не сразу, а постепенно накапливаются за счет добавления очередного элемента массива на каждом шаге цикла. Для правильной работы алгоритма переменной, в которой будет накапливаться сумма (произведение), должно быть присвоено определенное начальное значение, не влияющее на действие накопления. Например, при накоплении суммы в качестве начального значения берется 0 (т.к. прибавление нуля не влияет на сумму), а при накоплении произведения начальное значение равно 1 (при умножении на 1 произведение не меняется).

                Рис. 8. Накопление суммы            Рис. 9. Накопление произведения

Пусть Х – одномерный массив из n элементов (чисел). Требуется вычислить сумму элементов массива S. Переменную-индекс для перебора элементов в цикле обозначим как i.

Блок-схема накопления суммы элементов массива Х в переменную S изображена на рисунке 8. Накопление произведения элементов массива Х в переменную P выполняется аналогично накоплению суммы (рис. 9).

 

Алгоритм поиска максимального (минимального) элемента

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

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

Пусть Х – одномерный массив из n элементов (чисел), М – переменная для поиска максимального (минимального) элемента, k – номер максимального (минимального) элемента, i – номер очередного элемента.

Блок-схема поиска максимального элемента массива и его номера изображена на рисунке 10. Поиск минимального элемента выполняется аналогично, только необходимо поменять знак сравнения “>” на “<” при проверке условия в цикле.

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

Алгоритмы сортировки

Сортировкой называют упорядочивание элементов по какому-либо признаку. Например, числовые данные можно упорядочить (отсортировать) либо по возрастанию, либо по убыванию их значений. А строковые данные – в алфавитном порядке, либо в порядке обратном алфавитному.

Наиболее известны два метода сортировки: 1) сортировка методом выбора, 2) пузырьковая сортировка.

 

Сортировка методом выбора

 

Данный метод сортировки базируется на поиске минимального (максимального) элемента. Вначале находится минимальный элемент, который затем меняется местами с первым элементом. Далее находится следующий минимум, т.е. начиная со второго элемента. Затем найденный минимум меняется со вторым элементом и т.д. Таким образом, упорядочивание осуществляется за счет постепенной расстановки элементов по своим местам через последовательный выбор очередного минимума. Сортировка по убыванию выполняется аналогично, только поиск минимальных элементов заменяется на поиск максимальных элементов.

Рис. 11. Сортировка по возрастанию методом выбора

Пусть Х – одномерный массив из n элементов (чисел). Требуется отсортировать его по возрастанию значений элементов. Для реализации метода выбора потребуется организовать два цикла: один вложенный в другой. Поэтому потребуется два индекса: переменная i – для управления внешним циклом, переменная j – для управления внутренним циклом. Переменная М используется для поиска минимального (максимального) элемента. Необходима также дополнительная переменная А для обмена местами очередного минимума (максимума) с нужным элементом. В переменную k заносится номер очередного минимума (максимума).

На рисунке 11 изображена блок-схема сортировки по возрастанию элементов массива Х методом выбора. Сортировка по убыванию выполняется аналогично, только необходимо заменить знак «<» на знак «>» (чтобы заменить поиск минимумов на поиск максимумов).

 

Пузырьковая сортировка

 

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

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

Пусть Х – одномерный массив из n элементов (чисел). Требуется отсортировать его по возрастанию значений элементов. Для реализации пузырьковой сортировки потребуется организовать два цикла: один вложенный в другой.

Во внутреннем цикле (с управляющей переменной i) будет осуществляться сравнение пар соседних элементов X(i) и X(i+1) от начала и до конца массива. Для перестановки соседних элементов потребуется дополнительная переменная А.

Во внешнем цикле будет проверяться условие окончания сортировки (по значению переменной-признака).

В качестве переменной-признака окончания сортировки можно использовать либо переменную, логического типа (со значениями True и False), либо целочисленную переменную (со значениями 0 и 1). Будем использовать переменную В целого типа. Если при проверке условия В=0, то сортировка еще не завершена. Если В=1, то сортировка закончена.

На рисунке 12 изображена блок-схема сортировки по возрастанию элементов массива Х методом пузырьковой сортировки.

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

Рис.12. Пузырьковая сортировка по возрастанию