Алгоритмы и программы. Язык С++ : учебное пособие для СПО [Елена Александровна Конова] (pdf) читать постранично, страница - 4
Книга в формате pdf! Изображения и текст могут не отображаться!
[Настройки текста] [Cбросить фильтры]
слово «неоднократно» не означает «до бесконечности».
Организация циклов, никогда не приводящая к остановке в выполнении алгоритма («зацикливание» алгоритма),
нарушает требование его результативности — получения
результата за конечное число шагов.
Блок, для выполнения которого организуется цикл,
называется телом цикла. Остальные операторы служат
для управления процессом повторения вычислений: это
начальные установки, проверка условия продолжения
цикла и модификация параметра цикла. Один проход
цикла называется итерацией.
Цикл с предусловием
Цикл с постусловием
Начальные установки служат для того, чтобы до входа в цикл задать значения переменных, которые в нем используются.
Проверка условия продолжения цикла выполняется
на каждой итерации либо до тела цикла (цикл с предусло-
13
Ос н о в ы а л г о р и т м и з а ц и и
вием), либо после тела цикла (цикл с постусловием). Тело
цикла с постусловием всегда выполняется хотя бы один
раз. Проверка необходимости выполнения цикла с предусловием делается до начала цикла, поэтому возможно,
что он не выполнится ни разу.
При конструировании циклов следует соблюдать обязательное условие результативности алгоритма (т. е. его
окончания за конечное число шагов). Практически это
означает, что в условии должна быть переменная, значение которой изменяется в теле цикла. Причем, изменяется таким образом, чтобы условие в конечном итоге перестало выполняться. Такая переменная называется управляющей переменной цикла или параметром цикла.
Еще один вид циклов — цикл с параметром, или
арифметический цикл. Тело цикла выполняется, пока
параметр цикла i пробегает множество значений от начального (In) до конечного (Ik).
Переменная i определяет количество повторений тела
цикла S. Если шаг изменения значения параметра цикла
обозначить через ∆I, то количество повторений тела цикла n можно вычислить по формуле
−
n = I k I n + 1.
∆I
Если параметр цикла i изменяется с шагом 1, то шаг
может не указываться.
Цикл выполняется так: начальное значение параметра
цикла i равно In. Если i ≤ Ik, выполняется тело цикла S, после
чего параметр цикла увеличивается на 1 с помощью оператора присваивания i = i + 1, и снова проверяется условие i ≤ Ik.
Пример 1.3. Дано целое положительное число n. Вычислить
факториал этого числа. Известно, что факториал любого целого
положительного числа n определяется как произведение чисел от 1 до заданного числа n:
n! = 1 ⋅ 2 ⋅ 3 ⋅ ... ⋅ n.
14
Гл а в а 1
По определению 0! = 1 и 1! = 1.
Задача решается с помощью циклического алгоритма. Введем следующие обозначения: N — заданное число,
F — факториал числа, R — параметр цикла. Составим два
варианта алгоритма: с использованием цикла с предусловием и цикла с параметром.
Правильность алгоритма можно проверить, если выполнить его формально «вручную». Выполним алгоритм
при n = 4.
Цикл с предусловием
Цикл с параметром
Цикл с предусловием
Цикл с параметром
R
R 0 выполняется (выход
«Да»), то вычисляется группа операторов в блоке 4:
k = k + 1; Y[k] = X[i].
Тест
Данные
Результат
n=5
X = (–1, 2, 0, 4, –3)
k=2
Y = (2, 4)
Выполнение алгоритма.
k
0
i
xi > 0?
1
x1 > 0? «Нет»
2
x2 > 0? «Да»
3
x3 > 0? «Нет»
4
x4 > 0? «Да»
yk = xi
y 1 = x2 = 2
1
y2 = x4 = 4
2
5
x5 > 0? «Нет»
6
Конец цикла
23
Ос н о в ы а л г о р и т м и з а ц и и
Мы используем цикл с заданным числом повторений.
Напомним, что такой цикл (арифметический цикл) применяется, когда число повторений цикла известно к началу его выполнения.
1.3.2. Вычисление суммы и количества элементов
массива
Пример 1.8. Вычислить сумму элементов одномерного
массива.
Дано: n — размер массива; массив А = (a1, a2, …, an).
Найти: S — сумму элементов массива.
Начальное значение суммы равно нулю. В предыдущих подпараграфах мы говорили о том, что значение суммы накапливается с каждым шагом выполнения алгоритма. Вычисляем сумму по формуле S = S + ai.
Тест
Данные
N=4
Результат
A = (3, 5, –2, 8) S = 14
Исполнение алгоритма
i
S
0
1
2
3
4
S + a1 = 0 + 3 = 3
S + a2 = a1 + a2 = 3 + 5 = 8
S + a3 = a1 + a2 + a3 = 8 – 2 = 6
S + a4 = a1 + a2 + a3 + a4 = 6 + 8 = 14
Фрагмент алгоритма
Пример 1.9. Найти количество положительных и отрицательных чисел в данном массиве.
Дано: n — размер массива; массив А = (a1, a2, …, an).
Обозначим k1 — количество положительных чисел, k2 —
количество отрицательных чисел.
Найти: k1, k2 — количество положительных и отрицательных чисел массива.
Математическая модель. Пусть k1 = 0 и k2 = 0. Если
a[i] > 0, то k1 = k1 + 1. Если a[i] < 0, то k2 = k2 + 1. Процесс
повторяется до окончания просмотра всех чисел массива.
Приведем фрагмент блок-схемы алгоритма и ее словесное описание.
24
Гл а в а 1
Блок 1. Задание начальных значений переменным k1
и k2.
Блок 2. Заголовок арифметического цикла.
Блок 3. Проверка условия. Если очередное
Последние комментарии
5 часов 27 минут назад
14 часов 30 минут назад
1 день 13 часов назад
1 день 14 часов назад
1 день 14 часов назад
1 день 14 часов назад