Материал: Информатика. Неформальное программирование и основы алгоритмизации вычислительных процессов. Кононов А.Д., Кононов А.А
3)для I от 2 до N шаг 1 повторяй если MAX<A(I), то MAX:=A(I)
4)Вывод (MAX)
Здесь A – имя массива – структурного набора однородных данных. Заметим, что шаг, равный единице, настолько популярен, что его можно опустить («по умолчанию»). Записанная конструкция носит название «разветвление в цикле» (рис. 5).
начало
N, A
MAX:=A(1)
I= 2,N,1
Нет
MAX<A(I)
Да
MAX:=A(I)
MAX
конец
Рис. 5. Блок-схема отыскания наибольшего из N чисел
5. Найти номер первого наибольшего элемента одномерного массива А длины N. Для решения этой задачи наряду с запоминанием наибольшего элемента требуется фиксация и его положения в массиве. Соответствующая блок-схема алгоритма приведена на рис. 6.
Задание. Ответить на вопросы (устно):
– что надо изменить в алгоритме для отыскания минимального элемента в массиве?
20
– что надо изменить в алгоритме примера 5 для нахождения номера последнего наибольшего элемента в массиве?
начало
N,A
MAX:=A(1) K:=1
I= 2,N,1
Нет
MAX<A(I)
Да
MAX:=A(I) K:=I
MAX, K
конец
Рис. 6. Определение первого наибольшего элемента в массиве
6. Классическая задача определения суммы и произведения эле-
|
n |
n |
|
ментов одномерного массива s = ∑ai и |
|||
p = ∏ai методом накоп- |
|||
|
i=1 |
i=1 |
|
ления имеет следующее решение |
|
||
1) |
Ввод (N,A)) |
|
|
2) |
S:=0 P:=1 |
|
|
3) |
Для I от 1 до N шаг 1 повторяй |
|
|
21
S:=S+A(I); P:=P*A(I) 4) Вывод (S,P).
Задание. Объяснить необходимость этапа 2). Нарисовать соответствующую блок-схему решения.
7. Дан одномерный массив А длины N. Определить количество его элементов, равных единице.
1)Ввод (N,A)
2)K:=0
3)Для I от 1 до N шаг 1 повторяй если A(I)=1, то K:=K+1
4)Вывод (К)
Блок-схема представлена на рис. 7.
начало
N,A
К = 0
I= 1,N,1
Нет
A(I) = 1
Да
K:= K+1
K
конец
Рис. 7. Подсчет числа элементов, равных единице
22
8. Вычислить скалярное произведение двух n-мерных векторов
n
(XY) = ∑xi yi . Решим эту задачу, используя цикл с предусловием
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)
Задание. Нарисовать соответствующую блок-схему.
|
n |
x |
i |
|
x |
2 |
|
x |
3 |
|
x |
n |
|
|
s = ∑ |
|
= x + |
|
+ |
|
+ ... + |
|
. |
||||
9. Вычислить сумму |
|
|
|
|
|
|
|
|
|||||
i=1 |
i! |
2! |
3! |
|
n! |
||||||||
|
|
||||||||||||
Факториал непосредственно компьютер считать не умеет. Поэтому в общем виде на неформальном уровне алгоритм решения задачи можно представить
1)Ввод (N,X)
2)S:=0
3)Для I от 1 до N шаг 1 повторяй
{вычисли I-oe слагаемое, пополни сумму I-ым слагаемым}
4)Вывод (S).
Это простой пример так называемого нисходящего проектирования программ – последовательная детализация. Сначала для сложной программы разрабатывается обобщенная структура, чтобы не потерялся общий сюжет задания, создается укрупненный эскиз программы, затем отдельные части последовательно детализируются.
Конкретизируем алгоритм. Любое I-е слагаемое можно записать
как
|
|
xi |
|
xi−1 x |
|
x |
||
ai = |
|
|
= |
|
= ai−1 |
|
|
, и алгоритм принимает вид |
|
i! |
(i −1)!i |
i |
|||||
1) |
Ввод (N,X) |
|
|
|
||||
2) |
S:=0 |
A:=1 |
|
|
|
|||
3) |
Для I от 1 до N шаг 1 повторяй |
|||||||
|
{A := A*X / I |
|
|
S := S+A } |
||||
4) |
Вывод (S) |
|
|
|
||||
10. |
|
Вычислить сумму бесконечного ряда с точностью до ε |
||||||
23
∞ |
i |
2 |
|
|
3 |
|
|
n |
||||
s = ∑ |
x |
|
= x + |
x |
|
+ |
x |
|
+ ...+ |
x |
|
+... |
|
|
|
|
|
|
|
|
|||||
=i! 2! 3! n!
i 1
Вэтой задаче число повторений в цикле заранее неизвестно, оно зависит от требуемой точности и скорости сходимости ряда. Поэтому здесь могут использоваться только циклы типа «пока», а суммировать надо до тех пор, пока последнее прибавленное слагаемое не станет меньше ε.
1) Ввод (X, ε)
2) S:=0 A:=1 I:=1
3)Повторяй A:=A*X / I S:=S+A I:=I+1
пока А≥ε
4)Вывод (S)
Задание. Нарисовать блок-схему решения задачи 10, используя цикл с предусловием.
11. Дан набор чисел, его нужно упорядочить, например, в порядке возрастания.
Можно, как это делалось в предыдущих задачах, найти самый маленький элемент, записать его первым, потом среди оставшихся элементов (в укороченном массиве) опять искать минимальный элемент, записать его следующим и далее повторять подобную процедуру, но это неэффективно.
Лучше использовать идею «борьбы с беспорядком» – попарное сравнение двух соседних элементов и, если предыдущий элемент больше соседнего последующего, их меняют местами.
После первого прохождения массива справа окажется самое большое из имеющихся чисел (оно «всплывает» – «метод пузырька»). Снова проход, но уже на один шаг короче и так n раз, но порядок может быть достигнут раньше (в частном случае вообще можно предположить, что исходный массив был уже упорядочен). Если на каком-то проходе перестановок не было, то порядок достигнут и просматривать элементы дальше уже не нужно. Алгоритм (с учетом комментариев в фигурных скобках) может быть записан следующим образом:
24