Конспект для учителя по теме «Построение алгоритмов и практические вычисления»

827

На странице размещен конспект для учителя по теме «Построение алгоритмов и практические вычисления». Материал актуален для ЕГЭ.

Циклы

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

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

Необходимо представить алгоритм в виде псевдокода.

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

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

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

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

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

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

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

На псевдокоде запись алгоритма будет выглядеть следующим образом:

алг Сумма (арг вещ х, ε рез вещ S)
дано l 0<х<1

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

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

ввод х, ε

S := 0; i :=1
m :=1; p := -1
нц пока abc(m)>ε

Р := -p x

m := p/i
S := S+m

i := i+1
кц

вывод S

кон

Массивы

Массивы – это множество элементов, значение которых относится к одному типу.

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

Индекс позволяет присвоить элементу массива свое место.

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

Максимальное количество элементов данного массива – это его размерность.

Если массив состоит из некоторого ряда элементов, то он называется векторным или одномерным, если же он состоит из нескольких рядов, то он называется матричным или многомерным массивом.

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

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

a[i] := 1 - a[i]

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

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

алг Сумма (арг цел n, рез арг вещ таб А[1:n] )
дано l массив А содержит нули, единицы и двойки

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

нач цел i, k1, k2

k1 := 0; k2 :=0

нц дляi от 1 до n

если А[i] =0
то k1 := k1+1; всё

если А[i] =1
то k2 := k2+1; всё

кц
нц дляi от 1 до k1

А[i] =0
кц

нц для i от k1+1 до k2+2
А[i] =1
кц

нц для i от k1+k2 до n
А[i] =2
кц

кон

Пример 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] необходимо записать:

если А[i]>0

то S := S+А[i]

всё

На псевдокоде алгоритм расчета суммы выглядит следующим образом:

алг Сумма (арг цел n, арг вещ таб А[1:n], рез вещ S )
дано l массив А

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

нач

цел i

S := 0

нц для i от 1 до n

S := S+А[i]

кц

кон

Действия над массивом

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

Основным действием, которое производится над массивом, называется поиск.

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

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

Сортировка – это действие, которое приводит к изменению положения элементов в заданном массиве, согласно поставленным условиям.

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

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

Сортировка с помощью обмена

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

Пример сортировки массива с помощью псевдокода:

алг Обменная_сортировка (арг цел n, арг рез вещ таб А[1:n] )
дано l А - массив размерности n

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

нач

цел i, j

вещ Tmp

нц дляiот2доn

нц дляjотnдо1

еслиА[j]<А[j-1]

тоTmp :=А[j]; А[j] :=А[j-1];

А[j-1] :=Tmp

всё

кц

кон

Метод сортировки прямым включением

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

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

алг Сортировка_вставкой (арг цел n, арг рез вещ таб А[1:n] )
дано l А - массив размерности n

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

нач

цел i, j

вещ Tmp

нц дляiот2доn

Tmp :=А[j]; j :=i-1;

нц покаj>= 1 и А[j]>Tmp

А[j+1] :=А[j]

j :=i-1

кц

А[j+1] :=Tmp

кц

кон

Метод сортировки прямым выбором

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

Пример алгоритма сортировки методом прямого выбора:

алг Сортировка_выбором (арг цел n, арг рез вещ таб А[1:n] )
дано l А - массив размерности n

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

нач

цел i, k

вещ Min

нц дляiот1доn-1

Min :=А[j]; k :=i

нц дляj от i+1 до n

еслиMin > А[j]

тоMin :=А[j]; k :=j

всё

кц

А[k] :=А[i]; А[i] :=Min

кц

кон

Процедуры и функции

Подпрограмма – это готовый алгоритм, который можно использовать многократно в различных программах.

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

Функция - выражение, используемое для вычислений, которому присваивается идентификатор функции.

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

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

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

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

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