Материал: Основы алгоритмизации и программирования вычислительных процессов. Кононов А.Д., Кононов А.А

Решение достигается использованием одного полного условного предложения.

2. Усложняем. Найти наибольшее из трех чисел – max{A,B,C}. По методу парных сравнений получим следующий алгоритм

1)Ввод (A,B,C)

2)Если A≥B, то {если A≥C, то MAX :=A, иначе MAX:= C},

Иначе {если B≥C, то MAX:=B, иначе MAX:=C}

3)Вывод (M)

Здесь решение получается с использованием трех полных условных предложений, два из которых внутренние и одно внешнее. Графическая иллюстрация решения приведена на рис. 4.

Рис.4. Блок-схема нахождения наибольшего из трех чисел

Решение примера 2 для 4, 5,…чисел приводит уже к более громоздким алгоритмам, то есть с увеличением размерности задачи алгоритм, построенный на базе парных сравнений, может стать необозримым.

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

1)Ввод (A,B,C)

2)MAX:=A

3)Если MAX<B, то MAX:=B

4)Если MAX<C, то MAX:=C

5)Вывод (MAX)

16

В пунктах 3,4 применяются укороченные условные предложения. Теперь после второго этапа ячейка MAX «помнит» наибольшее из одного числа, то есть само это число, после третьего шага – наибольшее из двух чисел, после четвертого – наибольшее из трех чисел и т.д.

4. Обобщаем. Пользуясь последней методикой, найдем наибольшее из n чисел – max {ai, i=1,2,…, n}, приведя решение задачи к циклической процедуре с известным числом повторений

Здесь A – имя массива – структурного набора однородных данных. Заметим, что ш аг, равный единице настолько популярен, что его можно опустить («по умолчанию»). Записанная конструкция носит название «разветвление в цикле» (Рис. 5)

Рис. 5. Блок-схема отыскания наибольшего из N чисел

17

5. Найти номер первого наибольшего элемента одномерного массива А длины N. Для решения этой задачи наряду с запоминанием наибольшего элемента требуется фиксация и его положения в массиве. Соответствующая блоксхема алгоритма приведена на рис. 6.

Рис.6. Определение первого наибольшего элемента в массиве

Задание. Ответить на вопросы (устно):

–что надо изменить в алгоритме для отыскания минимального элемента в массиве?

–что надо изменить в алгоритме примера 5 для нахождения номера последнего наибольшего элемента в массиве?

6. Классическая задача определения суммы и произведения элементов одномерного массива

методом накопления имеет следующее решение:

1)Ввод (N,A))

2)S:=0 P:=1

3)Для I от 1 до N шаг 1 повторяй

S:=S+A(I); P:=P*A(I)

4) Вывод (S,P).

Задание. Объяснить необходимость этапа 2). Нарисовать соответствующую блок-схему решения.

Занятие 4. Практическая алгоритмизация

1. Дан одномерный массив А длины N. Определить количество его элементов, равных единице.

1)Ввод (N,A)

2)K:=0

3)Для I от 1 до N шаг 1 повторяй если A(I)=1, то K:=K+1

4)Вывод (К). Блок схема представлена на рис. 7.

Рис.7. Подсчет числа элементов, равных единице

19

2. Вычислить скалярное произведение двух n – мерных векторов

i=1

Решим эту задачу, используя цикл с предусловием

1)Ввод (N,X,Y)

2) S:=0 I:=0

3)I:=I+1

4)S:=S+X(I)*Y(I)

5)Если I ≤ N, то перейти к 3), иначе перейти к 6)

6)Вывод (S)

Задание. Нарисовать соответствующую блок-схему.

4.Вычислить сумму

Факториал непосредственно компьютер считать не умеет. Поэтому в общем виде на неформальном уровне алгоритм решения задачи можно представить

1)Ввод (N,X)

2)S:=0

3)Для I от 1 до N шаг 1 повторяй

{вычисли I-oe слагаемое, пополни сумму I-ым слагаемым}

4)Вывод (S).

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

иалгоритм принимает следующий вид:

1)Ввод (N,X)

2) S:=0 A:=1

3)Для I от 1 до N шаг 1 повторяй

4)Вывод (S)

4. Вычислить сумму бесконечного ряда с точностью до ε:

20