1.6.3 Построение алгоритмов и практические вычисления

Составим блок-схему алгоритма вычисления суммы знакопеременного ряда:

с заданной точностью ε.

Для решения данной задачи используем обозначения:

S - частичная сумма ряда (стартовое значение равно 0);

ε - точность вычисления;

i - номер очередного слагаемого;

m - значение очередного слагаемого;

p - числитель очередного слагаемого.

Требуемая точность вычисления будет достигнута в случае, когда очередное слагаемое станет по абсолютной величине меньше ε. Составим блок-схему алгоритма:

        надо  l  S=x-x²/2+x³/3+x⁴/4+...

        нач цел i, вещ m, p

            Р := -p*x

            i := i+1
        кц

Все значения массива являются упорядоченными и имеют свой индекс.

 Именно поэтому найти некий элемент в массиве можно с помощью его имени и индекса.

Пример 1. В массиве а каждый элемент равен 0 или 1. Заменить все нули единицами и наоборот.

Решение. Достаточно одного оператора присваивания в теле цикла:

Пример 2. В массиве каждый элемент равен 0,1 или 2. Переставить элементы массива так, чтобы сначала располагались все 0, затем все 1 и, наконец, все 2. Дополнительный массив не использовать.

Решение. Можно не переставлять элементы массива, а подсчитать количество 0,1,2 и заново заполнить массив требуемым образом.

        надо  l  упорядочить массив по возрастанию

        нач цел i, k1, k2

Пример 3. Даны два n-элементных массива x и Y одного типа. Поменять местами все x_i и Y_i, (i=1...n) не используя промежуточные величины.

Решение. Обмен можно выполнить в цикле для всех i от 1 до n с помощью серии из трех операторов присваивания:

x[i] := x[i] + y[i]

y[i] := x[i] - y[i]

x[i] := x[i] - y[i]

Пример 4. Найти сумму элементов одномерного массива А(n).

Решение. Для суммирования положительных элементов массива вместо оператора S := S+А[i] необходимо записать:

        надо  l  найти сумму элементов массива

        нач

Данные в массиве можно искать или же сортировать. 

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

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

Сортировка производится перед поиском для более быстрого его завершения.

Существует большое разнообразие способов сортировки. Давайте рассмотрим некоторые из них:

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

        надо  l  упорядочить массив по возрастанию

        нач

          цел i, j

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

        надо  l  упорядочить массив по возрастанию

        нач

          цел i, j

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

        надо  l  упорядочить массив по возрастанию

        нач

          цел i, k

Подпрограммы включают в основной алгоритм более сложной программы. Они делятся на функции и процедуры.

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

 

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