10
y1 = y
да
D > d нет нет
Вывод x, y
Конец
Рис. 2.6. Окончание
Вычислительные процессы, содержащие два или более включенных друг в друга циклов, называют сложными циклическими процессами (алгоритмами). Цикл, который содержит внутри себя другой цикл, называют внешним в противоположность внутреннему (вложенному). Необходимо учитывать, что за одно исполнение внешнего цикла внутренний цикл повторяется многократно.
Пример 5. Составить алгоритм вычисления и вывод на печать функции y = x*z / (A + B) при изменении аргументов 1≤ x ≤ 10 c шагом ∆x = 2 и 1≤ z ≤4 с шагом ∆z = 0.5.
Решение данного примера показано на рис. 2.7. Внутренний цикл организован по переменной z , а внешний – по переменной x . На каждом шаге изменения переменной x (переменной внешнего цикла) переменная z (переменная внутреннего цикла) проходит весь заданный диапазон изменения от 1 до 4 с шагом 0.5. Блок вывода на печать помещен во внутреннем цикле, что позволяет регистрировать переменные во всем диапазоне их изменения. На рис. 2.8 эта же задача решена с помощью модифицированной блок-схемы алгоритма. В ней циклы представлены с помощью более компактных условных обозначений, принципы организации которых становятся ясными из рис. 2.9. Первая цифра внутри фигуры (рис. 2.9) определяет начальное значение переменной, вторая –
11
ее конечное значение, а третья – шаг изменения переменной. По умолчанию (при отсутствии последней цифры) шаг изменения переменной принимается равным 1.
|
Ввод A,B |
|
x = 1 |
|
z = 1 |
|
y = x*z /(A+B) |
|
Вывод x,y,z |
|
z=z+0.5 |
|
z ≤ 4 |
|
x = x + 2 |
|
x ≤10 |
|
Конец |
|
Рис. 2.7 |
Ввод A,B
|
x = 1,10,2 |
|
z = 1,4,0.5 |
|
y = x*z /(A+B) |
|
y1 = y |
|
Вывод x,z,y |
|
Конец |
|
Рис. 2.8 |
12
|
Вход в цикл |
|||||
|
Вход i+1 |
|||||
|
X = 1,10,2 |
|||||
|
шага цикла |
Выход из |
||||
|
цикла |
Выход i-го шага цикла
Рис. 2.9
2.4. Алгоритмы с массивами
Наряду с одиночными переменными в задачах часто используются организованные переменные – массивы. Под массивом понимают совокупность данных, имеющих общее имя. По способу организации чаще всего различают одномерные и двумерные массивы. Одномерный массив – вектор, элементы которого снабжаются одним индексом, определяющим их порядковый номер в массиве. Двумерный массив – это матрица. Элементы одного массива снабжаются двумя индексами, первый из которых определяет номер строки, а второй – номер столбца. На пересечении номера строки и номера столбца расположен искомый элемент. Например, в массиве
|
A(2,2) = |
а11 |
а12 |
|
|
а21 |
а22 |
элемент а11 расположен на пересечении первой строки и первого столбца, элемент а12 – на пересечении первой строки и второго столбца, элемент а21 – на пересечении второй строки и первого столбца и т. д. Элементы массива называются переменными с индексами или индексными переменными.
Пример 6. Составить алгоритм вычисления элементов массива Y(10) по элементам массива X(10), если
|
xi + а |
||||
|
уi ,j = |
. |
|||
|
√ |
||||
|
xi2 + 1 |
Алгоритм решения данной задачи приведен на рис. 2.10. В нем показано, что после блоков ввода переменной а и массива X(10) организуется цикл по индексной переменной i для вычисления элементов массива уi по элементам массива xi
.
13
Начало
Ввод а
Ввод массива
X(10 )
i = 1,10,1
xi + а
yi =
√ xi2 + 1
Вывод yi
Конец
Рис. 2.10
14
Пример 7. Составить алгоритм получения элементов массива Y(5,4) по элементам массива X(5,4), если
|
xi, j + a |
||
|
yi, j = |
. |
|
|
√ xi2, j + 1 |
||
|
. |
Начало |
|
|
Ввод а |
||
|
Ввод массива |
||
|
X(5,4} |
||
|
i = 1,5,1 |
||
|
j =1,4,1 |
||
|
xi + a |
||
|
yi, j = |
||
|
√ xi2, j + 1 |
||
|
Вывод yi,j |
||
|
Конец |
||
|
Рис. 2.11 |
. |
15
Алгоритм решения задачи из примера 7 приведен на рис. 2.11. Он отличается от предыдущего алгоритма наличием второго цикла по переменной j, так как адрес каждого элемента двумерного массива определяется двумя индексами.
Пример 8. Дан массив ненулевых элементов А(10). Необходимо определить количество положительных и отрицательных элементов.
Пусть Р – количество положительных элементов, а Q – количество отрицательных элементов, тогда алгоритм решения задачи будет иметь вид, показанный на рис. 2.12.
|
Начало |
|
|
Ввод массива |
|
|
А(10 ) |
|
|
P = 0 |
|
|
Q = 0 |
|
|
i = 1,10,1 |
|
|
да |
нет |
|
аi>0 |
|
|
P=P+1 |
Q=Q+1 |
|
Вывод |
|
|
P, Q |
Конец
Рис. 2.12
16
Принцип работы данного алгоритма ясен из блок-схемы, однако надо иметь в виду, что перед входом в цикл необходимо выполнить обнуление переменных P и Q. В этих переменных формируются суммы по количеству положительных и отрицательных элементов, которые должны быть равны нулю перед входом в цикл.
Пример 9. Задан массив ненулевых элементов В(2,3). Определить количество положительных и отрицательных элементов.
|
Начало |
|
|
Ввод мас- |
|
|
сива В(2,3) |
|
|
P = 0 |
|
|
Q = 0 |
|
|
i = 1,2,1 |
|
|
j = 1,3,1 |
|
|
да |
нет |
|
bi,j >0 |
|
|
P = P+1 |
Q = Q+1 |
Вывод P,Q
Конец
Рис. 2.13
Соседние файлы в папке Книги
- #
- #
26.03.20159.12 Mб71C C++ Visual C++ 2008 express Pahomov.djvu
- #
26.03.20158.97 Mб62kak_programmirovat_na_cplusplus.djvu
- #
26.03.20152.99 Mб52LIPPMAN.DOC
- #
- #
26.03.201523.9 Mб56visual c++ 2005. базовый курс.djvu
- #
- #
- #
26.03.201551.32 Mб365Лаптев В. В. C++. Экспресс-курс .pdf
Нередко при алгоритмическом решении задачи возникает необходимость создания цикла, содержащего в своем теле другой цикл. Такие вложенные друг в друга циклы относятся к структурам вложенных циклов. Порядок вложенности циклов, когда в теле внутреннего цикла содержатся другие циклы, может быть достаточно большим. Этот порядок определяется методом, с помощью которого достигается решение поставленной задачи. Так, при обработке одномерных массивов, как правило, удается построить алгоритмическую схему без вложения циклов. Однако в ряде случаев при решении таких задач без вложенных циклов не обойтись.
Отметим, что все вложенные друг в друга циклы, включая наружный, должны иметь счетчики с различными именами. Вне этих циклов счетчики могут быть использованы как обычные переменные или как счетчики других циклов.
Пример 1. Рассмотрим задачу сортировки одномерного массива Z длины N. Отсортировать массив – значит расположить его элементы в порядке роста или убывания.
Опишем метод сортировки массива в порядке роста. Сначала выполняется проход по массиву с целью определения в нем наименьшего элемента. Затем производится перестановка этого элемента с первым. Далее совершается второй проход по массиву, начиная со второго элемента. Найденный наименьший элемент переставляется со вторым и т. д. После (N-1)-го прохода с выполнением названных операций массив окажется отсортированным.
Блок-схема этого алгоритма сортировки показана на рисунок 1. Она включает 12 блоков. После начала работы в блоке 2 переменная N и массив Z заполняются константами. Затем в блоке 3 проверяется условие о том, нужно ли сортировать массив.
Это сводится к установлению факта наличия в массиве нескольких элементов, т. к. массив из одного элемента всегда отсортирован. Если этот факт установлен, то алгоритм приступает к сортировке. Процедура сортировки выполняется в цикле, объединяющем блоки 4-10. В теле этого цикла содержится другой цикл, который образован блоками 6-8. Его назначение станет ясно из дальнейшего разбора алгоритма.
После входа в наружный цикл его счетчик i примет значение 1, что в рамках нашего метода подразумевает первый проход по массиву.
Далее будут выполнены блоки 5-10, составляющие тело наружного цикла. В блоке 5 размещены две вспомогательные переменные V и L. Первая из них предназначена для фиксирования наименьшего элемента, а вторая – для запоминания его индекса. Так как i = 1, то при первом проходе в блоке 5 V примет значение первого элемента, а L значение 1. Затем во внутреннем цикле, образованном блоками 6-8, где его счетчик j будет изменяться от 2 до N, последовательно проводится сравнение соответствующих элементов массива Z со значением переменной V. При этом всякий раз, как будет найден меньший чем v элемент, значение V будет заменено на значение этого элемента, а в переменной L будет зафиксирован его индекс. Понятно, что после выполнения внутреннего цикла в переменной V будет содержаться значение, равное наименьшему элементу, а в L – индекс этого элемента. В блоке 9 далее проверяется, не является ли наименьший элемент первым элементом массива. Если это не так, то в блоке 10 на место наименьшего элемента (его номер L) запишется первый (т. к. при первом проходе L =1 ), а на место первого элемента – наименьший (он равен V). После этого произойдет возврат управления к заголовку наружного цикла блоку 4. В нем значение счетчика станет равным i = 2.
Затем вновь выполняется его тело, но уже для нового значения счетчика i. Теперь с помощью блоков 5-10 отыскивается наименьший элемент массива начиная с номера 2. Затем в блоках 9-10 он займет второе место в массиве и т. д. Когда тело наружного цикла выполнится (N-1), раз массив будет отсортирован.
В блоке 12 отсортированный массив будет выведен и в блоке 13 алгоритм окончит работу.
Алгоритмы со структурами вложенных циклов часто используют при решении задач обработки двумерных массивов. В таких алгоритмах счетчики циклов используются для манипуляции с индексами массивов.
Пример 2. Дан двумерный квадратный массив Z, состоящий из N строк и N столбцов. Необходимо найти среднее арифметическое S его отрицательных элементов и заменить положительные элементы побочной диагонали массива средним арифметическим S.
Блок-схема алгоритма показана на рисунок 2. Она состоит из 13 блоков. В блоке 2 переменная N и весь массив Z заполняются константами. В блоке 3 рабочие переменные S и К получает значение нуль. Переменная S сначала будет играть роль сумматора отрицательных элементов массива, затем после накопления суммы она примет значение среднего арифметического. Переменная К нужна для подсчета количества отрицательных элементов массива.
В блоках 4-7 выполняется накопление суммы отрицательных элементов массива.
Эти блоки образует два вложенных цикла, причем внутренний цикл со счетчиком j является телом наружного цикла со счетчиком i. Проанализируем работу этой структуры.
После входа в наружный цикл в блоке 4 переменная i примет значение i = 1. Далее будет выполнено его тело ( блоки 5-7 ), которое, в свою очередь, также является циклом. После входа во внутренний цикл в блоке 5 переменная j примет значение j = 1. Затем в блоке 6 проверяется на отрицательность элемент массива Z, расположенный в первой строке и первом столбце, т. к. i = 1 и j = 1.
Если он окажется отрицательным, то в блоке 7 переменная К увеличится на 1, а к S добавляется значение этого элемента. После этого выполняется возврат к блоку 5, т. е. к заголовку внутреннего цикла. Здесь j увеличится на 1, станет равной j = 2 и управление перейдет к блоку 6. В нем проверяется элемент, стоящий все в той же первой строке, но во втором столбце (i = 1, j = 2). Если он окажется отрицательным, то К снова увеличится на 1, а к накопленному к этому времени S добавляется значение этого элемента и т.д. Когда полностью выполнится внутренний цикл, т. е. переменная j «пробежит» от 1 до N, в переменную S накопится сумма всех отрицательных элементов первой строки массива, а в К – их количество. Теперь управление передается к блоку 4 заголовка наружного цикла, где i станет равной i = 2. Снова будет отработано его тело, т. е. цикл 5-7. При этом будет найдена уже сумма отрицательных элементов первых двух строк массива, а в К сохранится количество этих элементов. Когда выполнится весь наружный цикл, в S будет константа, равная сумме отрицательных элементов всего массива, а в К – их количество. Теперь управление перейдет к блоку 8. Если окажется, что в массиве есть отрицательные элементы (К>0), то в блоке 9 вычисляется среднее арифметическое как отношение суммы элементов к их количеству. Результат помещается а ту же переменную S. Отметим, что если бы блок 8 проверки отсутствовал, то при К = 0 (в массиве нет ни одного отрицательного элемента) в блоке 9 из-за деления на нуль возникла бы ошибка. Эта ошибка повлекла бы аварийное завершение вычислений до окончания работы алгоритма.
Далее выполняется блоки 10-11, которые также образует цикл. В нем производится замена элементов побочной диагонали на среднее арифметическое S (побочной диагональю является прямолинейная цепочка ячеек в диапазоне от нижнего левого угла до верхнего правого угла массива). Обратите внимание, на то что переменная i, которая использовалась ранее, в целях экономии памяти применяется вновь.
Проследим работу этого цикла. После входа в блок 10 счетчик примет значение i = 1. Затем в блоке 11 при этом значении будет вычислен индекс столбца элемента N – 1 + i = N. Таким образом, элемент с индексами (1, N) станет равным S. На втором круге цикла i увеличится на 1 и станет i = 2. Нетрудно видеть, что теперь элемент (2, N-1) станет равным S и т. д. На последнем круге цикла элемент (N, 1) получит значение S, что завершит изменение значений всех элементов побочной диагонали на среднее арифметическое S.
Наконец, в блоке 12 измененный массив будет выведен и в блоке 13 алгоритм закончит работу.
Вопросы:
· Сложные
циклические алгоритмы.
· Вложенные
циклы.
Рассмотрим
задачу. Написать программу, которая определяет количество значимых нулей в
целом положительном числе, введённом пользователем, кроме нулей в младших
разрядах.
Для
решения задачи мы сначала уберём из числа все нули в младших разрядах. Для
этого, пока остаток от деления числа на десять равен нулю, мы будем без остатка
делить число на десять. После этого мы будем проверять правую цифру числа,
выделяя её как остаток от деления числа на десять, и в том случае, если она
будет равна нулю, будем увеличивать счётчик на единицу. После проверки мы уберём
правую цифру из числа и будем продолжать так делать, пока число больше нуля. В
конце нам лишь останется вывести на экран значение счётчика.
Напишем
программу для решения задачи. Сначала с помощью инструкции print
выведем на экран сообщение о том, что это программа, определяющая количество
нулей в целом положительном числе, кроме тех, которые находятся в младших
разрядах, и запрос на ввод числа. Теперь считаем или число в переменную n.
По условию задачи число целое, поэтому при считывании его значение мы будем
преобразовывать в целочисленный тип int.
Теперь напишем цикл для того, чтобы убрать из числа нули в младших разрядах. Он
будет работать, пока остаток от деления n
на 10 равен нулю. Тело цикла будет содержать единственную инструкцию
присваивания переменной n
результата её безостаточного деления на десять. Таким образом, мы будем убирать
из числа все правые цифры, равные нулю. Теперь объявим переменную-счётчик
количества нулей. Назовём её s
и присвоим ей значение 0, так как ни одного нуля мы ещё не учли. Дальше напишем
цикл для определения количества оставшихся нулей в числе. Он будет работать до
тех пор, пока n
> 0. В теле цикла напишем ветвление, которое будет
проверять, равна ли правая цифра числа нулю, то есть её n
% 10 = 0. Если это условие выполняется, то мы присвоим
счётчику s его значение, увеличенное
на 1. После того, как мы проверили значение правой цифры, уберём её из числа.
Для этого переменной n
присвоим результат её безостаточного деления на 10. После цикла переменная s
будет содержать ответ на вопрос задачи. С помощью инструкции print
выведем на экран сообщение о том, что количество нулей во введённом числе, за
исключением младших разрядов равно значению переменной s.
print
(‘Программа, определяющая количество нулей в целом
положительном числе, кроме младших разрядов. Введите
число.’)
n =
int (input
())
while n % 10 == 0:
n = n // 10
s =
0
while n > 0:
if n % 10 == 0:
s = s + 1
n = n // 10
print
(‘Количество нулей во введённом числе, кроме
младших разрядов:’, s)
Сохраним
написанный модуль и запустим его на выполнение. Введём число 107 003
500. Очевидно, что в этом числе 5 нулей, но 2 из них находятся в младших
разрядах. Поэтому программа вывела значение 3. Снова запустим программу на
выполнение и зададим число 32 007. В этом числе действительно 2 нуля, и ни один
из них не находится в младшем разряде, поэтому программа вывела 2. Снова запустим
программу и введём число 125. В этом числе нет нулей, поэтому программа вывела
значение 0. Программа работает правильно, задача решена.
Программа,
которую мы написали, содержит два цикла. Они располагаются один за другим. И вполне
понятно, что они работают независимо друг от друга, однако возможна и другая
ситуация, когда один цикл может работать в составе другого. Такой цикл
называется вложенным.
Решим
простую задачу с использованием вложенного цикла. Написать программу, которая
выводит на экран таблицу Пифагора для целых чисел от единицы до десяти. Таблицей
Пифагора называется таблица, в которой в каждой ячейке содержится произведение
номеров её строки и столбца.
Начнём
написание программы для решения задачи. Сначала с помощью инструкции print
выведем на экран сообщение «Таблица Пифагора:». Теперь запишем цикл для
перебора номеров строк. Это будет цикл для параметра i,
изменяющегося в диапазоне от 1 до 10 с шагом 1, который записывается функцией range
(1, 11), так как число одиннадцать не будет включено в
диапазон. Тело этого цикла будет содержать ещё один цикл для перебора номеров
столбцов. Это будет цикл с параметром j,
изменяющимся в диапазоне от 1 до 11, не включая последнее значение, с шагом 1.
Тело этого цикла будет содержать единственную инструкцию print,
которая будет выводить на экран значение произведения номеров строки и столбца.
Для того, чтобы эти значения выводились в одну строку, в составе функции print
изменим параметр end. Это строка,
которая выводится по завершении работы инструкции print.
По умолчанию эта строка содержит единственный символ перехода на следующую
строку. Зададим вместо него пустую строку. Для того, чтобы наши столбцы
получились ровными с помощью функции Формат выделим для каждого из них по
четыре знаковых позиции. После того, как мы описали цикл для вывода очередной
строки значений, нам нужно перейти на следующую строку. Для этого запишем
инструкцию print без параметров.
Написание модуля завершено.
print (‘Таблица Пифагора:’)
for i in range (1, 11):
for j in range (1, 11):
print (‘{:4d}’.format
(i * j), end = »)
print ()
Сохраним
написанный модуль и запустим его на выполнение. Программа действительно вывела
на экран таблицу Пифагора. Программа работает правильно. Задача решена.
Обратим
внимание на цикл для решения задачи. Очевидно, что тело внешнего цикла
выполнилось в программе 10 раз, а тело внутреннего цикла при каждом выполнении
внешнего выполнялось 10 раз. Таким образом, тело внутреннего цикла было
выполнено в программе 10 раз по 10, то есть 100 раз. Стало быть, при использовании
вложенных циклов стоит заранее продумать, сколько раз они будут выполняться в
программе, так как от этого зависит время выполнения программы.
Рассмотрим
задачу посложнее. Написать программу, выводящую для заданного целого положительного
n все целые числа, которые меньше его
самого, сумма цифр которых равнялась бы сумме цифр n.
Если ни одного такого числа не найдено, программа должна вывести на экран
сообщение об этом.
Для
решения этой задачи мы сначала рассчитаем сумму цифр числа n.
После чего мы будем перебирать все целые числа от 1 до n,
не включая n, и рассчитывать суммы их
цифр, сравнивать с сумой цифр n
и выводить те числа, в которых сумма цифр будет равной сумме цифр n.
Начнём
написание программы для решения задачи. Сначала с помощью инструкции print
выведем на экран сообщение о том, что это программа поиска чисел, меньших n,
сумма цифр которых совпадает с суммой цифр n.
С помощью следующей инструкции print
выведем
запрос на ввод n без перехода на
следующую строку. Для этого в составе инструкции присвоим параметру end
пустую символьную строку. Далее считаем значение переменной n
с клавиатуры. Так как по условию это целое число, при считывании будем
преобразовывать его значение в целочисленный тип int.
Теперь рассчитаем сумму цифр числа n.
Так как само число n
нам ещё понадобится, создадим для расчёта суммы цифр его копию в переменной copy_n.
Сумму цифр n будем хранить в
переменной s_n.
Так как мы ещё не учли ни одной цифры, присвоим ей значение 0. Теперь запишем цикл
для расчёта суммы цифр n.
Это будет цикл while,
повторяющийся до тех пор, пока в переменной copy_n
ещё есть цифры, то есть пока она больше нуля. В теле цикла мы будем выделять
правую цифру значения переменной copy_n,
добавлять её к значению переменной s_n,
после чего убирать её из числа. Для этого переменным s_n
и copy_n
будем присваивать соответственно значения s_n
+ copy_n
% 10,
а также n // 10.
После
того, как мы рассчитали сумму цифр числа n,
в переменной i мы будем искать
числа, сумма цифр которых равна значению s_n.
Для начала, мы объявим переменную p,
которая будет содержать истинность утверждения о том, что такие числа есть. Предположим,
что их нет, и присвоим p
значение False. Дальше запишем
цикл с параметром i,
изменяющимся в диапазоне от 1 до n,
не включая последнее. В этом цикле мы будем вычислять сумму цифр для каждого
значения i. Но так как в теле цикла
мы не можем изменять значение i,
мы создадим его копию в переменной c
и будем вычислять сумму цифр c
в переменной s таким же образом,
как мы это делали ранее для числа n.
Далее мы запишем ветвление, сравнивающее сумму цифр i,
которая хранится в переменной s,
со значением переменной s_n.
Если они совпадают, то мы проверим, является ли число i
первым найденным. Для этого запишем ветвление с условием not
p. Оно будет выполняться
только тогда, когда значение p
– False, то есть при
условии, что до этого не было найдено ни одного числа. Если это условие
выполняется, то мы выведем на экран поясняющее сообщение «Найденные числа»,
заканчивающееся двоеточием, и присвоим p
значение True. Таким образом,
это ветвление может сработать всего один раз, то есть тогда, когда мы найдём
первое число. После этого ветвления выведем на экран значение числа i.
Так мы найдём все числа, которые меньше n,
с суммой цифр равной сумме цифр n.
Теперь нам осталось только рассмотреть случай, когда таких чисел нет. Для этого
напишем ветвление с условием not
p, которое при условии,
что ни одного числа не было найдено, выведет на экран с помощью инструкции print
сообщение о том, что искомых чисел не найдено.
print
(‘Программа поиска чисел меньших n, сумма цифр
которых совпадает с суммой цифр n.’)
print (‘n = ‘, end = »)
n =
int (input
())
copy_n
= n
s_n
= 0
while copy_n > 0:
s_n, copy_n = s_n + copy_n % 10, copy_n // 10
p =
False
for i in range (1, n):
c = i
s = 0
while c > 0:
s, c = s + c % 10, c // 10
if s == s_n:
if not p:
print (‘Найденные числа:’)
p = True
print (i)
if not p:
print (‘Искомых чисел не
найдено.’)
Описание
модуля завершено. Сохраним его и запустим на выполнение. Введём n
= 43. Его сумма цифр равна 7, поэтому программа вывела все числа, которые меньше
43, с суммой цифр равной 7: 7, 16, 25 и 34. Снова запустим программу на
выполнение и введём число 99. Его сумма цифр равна 18. Положительных чисел,
сумма цифр которых равна 18 и которые были бы меньше 99, нет. Программа вывела,
что таких чисел не найдено. Программа работает правильно. Задача решена.
Мы
узнали:
· Вложенными
циклами называются циклы, которые выполняются в составе
других циклов.
· При
использовании вложенных циклов важно продумывать количество повторений внешнего
цикла и вложенного в нём, так как общее количество повторений вложенного
цикла в программе равно их произведению.
План урока:
Понятие циклического алгоритма
Программирование циклического алгоритма
Операторы цикла
Решение задач с использованием операторов while, repeat, for
Понятие циклического алгоритма
В жизни людей очень часто встречаются циклы. Будь то жизнь маленького ребёнка или взрослого человека, а то и пожилых людей. Эти циклы можно расписать как выполнение одних и тех же действий, пока выполняется определённое условие. К примеру, взрослый человек находится на работе до момента, когда наступит время его ухода. И так изо дня в день, однако, есть и исключения в виде выходных. В жизни детей можно привести такой пример, как обязанность каждый день ходить в школу до момента, когда наступят выходные или каникулы.
Циклические алгоритмы – это алгоритмы, в которых некоторая часть операций повторяется многократно.
Цикл – конструкция с оператором, который повторяется определённое или неопределённое заранее количество раз. Действия, выполняющиеся последовательно внутри цикла, называют телом цикла.
В разных средах программирования циклические конструкции могут быть реализованы по-разному, но неизменным остается главный признак, отличающий циклы от линейных операций и ветвлений – возможность перемещения по программе не только «сверху-вниз», но и «снизу-вверх», для возврата к уже выполненным ранее действиям.
Циклы разделяют на три типа в зависимости от метода организации повторений:
- Цикл, в котором задано условие окончания работы;
- Когда известно условие продолжения работы цикла;
- Когда известно число повторений цикла.
Программирование циклического алгоритма
Выбрав среду программирования Паскаль необходимо познакомиться с операторами, с помощью которых можно разработать программу с циклом. Ими являются while, repeat, for. Оператор while был разобран ещё на прошлом уроке, однако забывать о нём нельзя.
Цикл с предусловием
Цикл с предусловием реализует циклический алгоритм, записанный на языке программирования, с использованием определённого условия, истинность которого проверяется перед каждой итерацией цикла. Выполнение цикла прекращается, когда условие становится ложным.
Цикл с постусловием
Цикл с постусловием – это алгоритм циклической структуры, в котором проверка условия продолжения осуществляется после выполнения тела цикла.
Тело цикла с постусловием всегда выполняется как минимум один раз, независимо от истинности или ложности условия. Это его ключевое отличие от цикла с предусловием.
Такие циклы удобны, когда в условии используется результат выполнения тела цикла. Например, если мы хотим найти в тексте слово «стоп», мы должны сначала прочитать очередное слово, и только потом проверить, является ли оно искомым или следует продолжить поиск.
Цикл с заданным числом повторений
Этот вид цикла вместо логического условия выполнения использует параметр (счетчик) – специальную переменную, которая на каждом шаге цикла получает очередное значение из определенного диапазона. Цикл повторяется до тех пор, пока не будут перебраны все элементы диапазона. Таким образом, определяя диапазон, мы определяем заранее заданное число повторений.
Операторы цикла
Для программирования циклических алгоритмов и корректного выполнения программ с их использованием, необходимо знать операторы цикла. Чаще всего, в языке Паскаль используют операторы цикла: for, repeat и while. Разберем их подробнее.
Оператор while
Оператор while используется, когда нужно создать цикл с предусловием. Его схема в циклическом алгоритме выглядит следующим образом:
Если переводить его дословно, то можно сказать, что он работает по принципу «пока <условие> выполнять действие <оператор 1>», а заканчивается при переходе программы на слово end. Перед выполнением операторов внутри цикла условие обязательно проверяется и уже дальше, в зависимости от его истинности, программа либо выполняет тело цикла, либо переходит к последующим операторам.
Решение задач с использованием оператора while
Для более чёткого понимания решения задач нужно разобрать циклические алгоритмы, примеры которых приведены в решениях.
Задача 1. На вход подаются целые числа. До тех пор, пока не будет введено число, которое больше 17, программа должна вывести сумму полученного числа и числа 8. Когда вводимое число будет больше 17, то после выполнения программы цикл завершается.
Решение.
Шаг 1. Для начала необходимо дать программе название.
Шаг 2. Учитывая, что на вход подаётся целое число, указать тип данных, в данном случае – integer.
Шаг 3. Запись командного блока. Нужно написать слово, обозначающее начало, begin.
Шаг 4. Нужно дать переменной a значение 1, чтобы цикл начался автоматически.
Шаг 5. Запись цикла. Поскольку известно условие окончания работы, для этой задачи необходимо написать «пока a меньше или равно 17» и сделать переход к последующим операторам путём написания составного цикла.
Шаг 6. Первоначальный вывод программы. Необходимо написать то, что программа будет выдавать в первую очередь. В данном случае, она будет запрашивать целое число, запрос так и пишется: «Введите целое число: » .
Шаг 7. Запись необходимых операторов. Используя оператор readln программа считывает данные и переводит курсор на новую строку. Далее она производит операции над поступившими данными.
Шаг 8. Запись суммы. Исходя из условия задачи необходимо сделать так, чтобы программа выводила сумму входящего числа и числа 8. Осуществить это можно используя оператор writeln.
Шаг 9. Запись вывода программы после цикла. После того, как программа выполнит свою работу в цикле, необходимо показать, что она из него вышла. Можно просто попрощаться, как в данном случае.
Шаг 10. Проверка правильности записи алгоритма. В конце программного блока, после слова end нельзя забывать точку, её обязательно нужно поставить.
Оператор repeat
Оператор цикла repeat until используется для создания циклического алгоритма с постусловием. Его схема выглядит так:
Дословно оператор Паскаля repeat можно перевести как «повторяй <оператор 1>, до <условие>». В зависимости от истинности условия, либо происходит переход на повторение «оператора 1», либо осуществляется выход из цикла к последующим операторам.
Оператор repeat имеет два важных отличия от оператора while:
- в операторе repeat сначала выполняется тело, а затем проверяется условие;
- в операторе repeat прописывается условие завершения цикла, тогда как в операторе while – условие его продолжения.
Решение задач с использованием оператора repeat
Задача 1. Придумать алгоритм и написать по нему программу, результатом выполнения которой будет вывод последовательности натуральных чисел от 1 до введенного пользователем числа.
Решение.
Шаг 1. Название программы. В данном случае — «задача 1».
Шаг 2. Учитывая, что на вход подаются целые числа, требуется указать тип данных – integer.
Шаг 3. Командный блок. Запись начального слова begin.
Шаг 4. Вывод запроса программы. Поскольку программе необходимо целое число, нужно попросить пользователя ввести его. Осуществляется это с помощью процедуры writeln и текста «Введите целое число, которое больше 1: ».
Шаг 5. Необходимо присвоить переменной i значение 1 для того, чтобы последовательность начиналась с натурального числа.
Шаг 6. Запись цикла. Учитывая, что используется цикл с постусловием, необходимо сначала записать оператор, который будет повторяться, затем увеличить i на 1, чтобы образовывалась последовательность, и уже после этого прописать условие повторения. В данной задаче цикл перестаёт повторяться тогда, когда переменная i принимает значение больше введённого числа, которое является последним членом последовательности.
Шаг 7. Проверка программы на правильность в выводе. В результате своей работы программа должна вывести последовательность натуральных чисел от 1 до n, через пробел.
Оператор for
Используя оператор for можно задать нужное количество повторений одних и тех же действий. По-другому его называют оператором циклов с известным числом повторений. Он имеет два соединительных слова – это to и downto. Различие между ними в том, что при использовании первого к предыдущему значению переменной цикла прибавляется единица, а при написании второго – вычитается единица. Схемы оператора имеют следующий вид:
Дословно его можно перевести как «для переменной в значении от начального к конечному выполнять <оператор 1> ».
Решение задач с использованием оператора for
Рассмотреть пример с оператором for можно при написании короткого алгоритма для следующей задачи.
Задача 1. Напишите на одном из языков программирование алгоритм, который выводит квадраты чисел от 1 до 10.
Решение.
Шаг 1. Необходимо дать программе название.
Шаг 2. Поскольку на вход числа не подаются, тип указывается в зависимости от данных, которые изначально находятся в программе. В данном случае – это целые числа.
Шаг 3. Запись блока с командами алгоритма.
Шаг 4. Перебор последовательности чисел осуществляется в цикле for, в котором счетчик i пробегает значения от 1 до 10, а расчет и вывод квадратов осуществляется в процедуре write.
Решение задач с использованием операторов while, repeat, for
Задача 1 Разработать алгоритм программы, которая выведет таблицу умножения чисел от 1 до 10 на 9.
Решение
Для решения можно написать два вида кода. Однако, этапы разработки программы, задачи, которые ей необходимо выполнить, очень похожи на прошлые примеры, и она ничем не отличается от решения обычной задачи. Поскольку различие в этих двух кодах лишь в использованном операторе while и for, то рассматривать их по-отдельности нет смысла. Последовательность написания первого кода выглядит так:
Шаг 1. Нужно назвать программу.
Шаг 2. Так как пользователь не вводит никаких данных, то их можно ввести в сам код программы. Тип используемых данных в данном случае – это integer.
Шаг 3. Написание команд. Изначально нужно сделать так, чтобы программа вывела название того, для чего она предназначена. В данной задаче это «Таблица умножения на 9».
Шаг 4. Запись цикла for. С помощью него программа будет последовательно умножать числа от 1 до 10 на 9 и составлять таблицу умножения путём вывода каждого значения по схеме «9x, i, =, p», где i – умножаемое на 9 число, p – результат произведения 9 и i.
Шаг 6. Программа завершает свою работу. Необходимо проверить правильность выведенных данных и, если это необходимо, поправить код для более корректной работы.
Цель: изучение алгоритмической структуры циклы, создание моделей и алгоритмов для решения практических задач.
Ход урока
I. Актуализация знаний
- Повторить понятие алгоритма, основные конструкции алгоритмического языка.
- Уметь разрабатывать математическую модель, алгоритм и блок схему решения задачи.
- Иметь понятие о языках программирования и их назначении.
- Уметь работать в среде программирования.
- Знать структуры программы.
- Уметь записывать выражения, содержащие числовые и символьные величины.
- Знать структуры операторов и особенности их работы.
- Уметь применять операторы при написании программ с линейными и ветвящимися структурами.
- Уметь на компьютере создавать и запускать программы на отладку.
II. Теоретический материал урока
Большинство практических задач требует многократного повторения одних и тех же действий, т. е. повторного использования одного или нескольких операторов. (Презентация)
Пусть требуется ввести и обработать последовательность чисел. Если чисел всего пять, можно составить линейный алгоритм. Если их тысяча, записать линейный алгоритм можно, но очень утомительно и нерационально. Если количество чисел к моменту разработки алгоритма неизвестно, то линейный алгоритм принципиально невозможен.
Другой пример. Чтобы найти фамилию человека в списке, надо проверить первую фамилию списка, затем вторую, третью и т.д. до тех пор, пока не будет найдена нужная или не будет достигнут конец списка. Преодолеть подобные трудности можно с помощью циклов.
Циклом называется многократно исполняемый участок алгоритма (программы). Соответственно циклический алгоритм — это алгоритм, содержащий циклы.
Различают два типа циклов: с известным числом повторений и с неизвестным числом повторений. При этом в обоих случаях имеется в виду число повторений на стадии разработки алгоритма.
Существует 3 типа циклических структур:
- Цикл с предусловием;
- Цикл с послеусловием;
- Цикл с параметром;
Иначе данные структуры называют циклами типа «Пока», «До», «Для».
Графическая форма записи данных алгоритмических структур:
Цикл с предусловием (иначе цикл пока) имеет вид:
| Форматы записи операторов алгоритма | Блок-схема | Форматы записи операторов на Паскале |
| Пока (условие) нц серия команд кц |
 |
while условие do begin серия команд; end; |
где
условие – выражение логического типа.
Цикл может не выполняться ни разу, если значение логического выражения сразу же оказывается ложь.
Серия команд, находящихся между begin и end, выполняются до тех пор, пока условие истинно.
Для того чтобы цикл завершился, необходимо, чтобы последовательность инструкций между BEGIN и END изменяла значение переменных, входящих в условие.
Цикл с постусловием (иначе цикл до) имеет вид:
| Форматы записи операторов алгоритма | Блок-схема | Форматы записи операторов на Паскале |
| В алгоритмическом языке нет команды которая могла бы описать данную структуру, но ее можно выразить с помощью других команд (Например, ветвления). |  |
repeat серия команд until условие |
где
условие – выражение логического типа.
Обратите внимание:
Последовательность инструкций между repeat и until всегда будет выполнено хотя бы один раз;
Для того чтобы цикл завершился, необходимо, чтобы последовательность операторов между repeat и until изменяла значения переменных, входящих в выражение условие.
Инструкция repeat, как и инструкция while, используется в программе, если надо провести некоторые повторяющиеся вычисления (цикл), однако число повторов заранее не известно и определяется самим ходом вычисления.
Цикл с параметром (иначе цикл для) имеет вид:
| Форматы записи операторов алгоритма | Блок-схема | Форматы записи операторов на Паскале |
| Для i от а до b шаг h делай Нц Серия команд кц |
 |
h = +1 for i:= a to b do begin серия команд end; h = -1 for i:= b downto a do begin Cерия команд; end; |
где
i – параметр цикла;
a – начальное значение цикла;
b – конечное значение цикла;
h – шаг изменения параметра.
Структура данного цикла иначе называют циклом i раз.
Эта команда выполняется таким образом: параметру i присваивается начальное значение а, сравнивается с конечным значением b и, если оно меньше или равно конечному значению b, выполняется серия команд. Параметру присваивается значение предыдущего, увеличенного на величину h – шага изменения параметра и вновь сравнивается с конечным значением b.
На языке программирования Паскаль шаг изменения параметра может быть равным одному или минус одному.
Если между begin и end находится только один оператор, то операторные скобки можно не писать. Это правило работает для цикла типа «Пока» и «Для».
Рассмотрим пример решения задач с использованием данных структур
Пример.
Вычислить произведение чисел от 1 до 5 используя различные варианты цикла
Математическая модель:
Р= 1· 2· 3· 4· 5=120
Составим алгоритм в виде блок-схемы.
Для проверки правильности алгоритма заполним трассировочную таблицу.
| Шаг | Операция | Р | i | Проверка условия |
| 1 | P:=1 | 1 | ||
| 2 | i:=1; | 1 | 1 | |
| 3 | i<=5 P:=P*I i:=i+1 |
1 | 1 | 1<=5, да (истина) |
| 4 | i<=5 P:=P*I i:=i+1 |
2 | 2 | 2<=5, да (истина) |
| 5 | i<=5 P:=P*I i:=i+1 |
6 | 3 | 3<=5, да (истина) |
| 6 | i<=5 P:=P*I i:=i+1 |
24 | 4 | 4<=5, да (истина) |
| 7 | i<=5 P:=P*I i:=i+1 |
120 | 5 | 5<=5, да (истина) |
| 8 | i<=5 P:=P*I i:=i+1 |
6<=5, нет (ложь) |
Проверка условия происходит в несколько шагов: проверка условия и выполнение команд на одной из ветвей. Поэтому в трассировочной таблице записываются не команды алгоритма, а отдельные операции, выполняемые компьютером на каждом шаге.
Шаг первый: Р присваивается значение один.
Шаг второй: i присваивается значение один.
Шаг третий: при i равном единице проверяем условие один меньше или равен пяти, да, условие истинно, значит Р присваивается значение один умноженное на один, будет два. Для i: один плюс один, будет два.
Шаг четвертый: при i равном двум проверяем условие два меньше или равен пяти, да, условие истинно, значит Р присваивается значение 2 умноженное на один, будет 2. Для i: два плюс один, будет три.
Шаг пятый: при i равном трем проверяем условие три меньше или равен пяти, да, условие истинно, значит Р присваивается значение два умноженное на три, будет шесть. Для i: три плюс один, будет четыре.
Шаг шестой: при i равном четырем проверяем условие четыре меньше или равен пяти, да, условие истинно, значит Р присваивается значение шесть умноженное на четыре, будет двадцать четыре. Для i: четыре плюс один, будет пять.
Шаг седьмой: при i равном пяти проверяем условие пять меньше или равен пяти, да ,условие истинно, значит Р присваивается значение двадцать четыре умноженное на пять, будет сто двадцать. Для i: пять плюс один, будет шесть.
Шаг восьмой: при i равном шести проверяем условие шесть меньше или равен пяти, нет, условие ложно, тогда мы выходим из цикла, а в результате получаем последнее значение равное сто двадцати.
Program Pr1;
Var i: integer;
Begin
P:=1;
i:=1;
While i<=5 do
begin
P:=P*i;
i:=i+1;
end;
Write (‘P=’, P);
end.
Для цикла с постусловием построим блок-схему и трассировочную таблицу. (слайд16)
В результате получаем последнее значение равное сто двадцати на седьмом шаге
И для Цикла с параметром построим блок-схему и трассировочную таблицу. (слайд17)
В результате получаем последнее значение равное сто двадцати на шестом шаге
Задача:
Вывести на экран числа от 1 до 5 в:
- прямом порядке;
- обратном порядке.
Математическая модель:
- 1 2 3 4 5;
- 5 4 3 2 1.
Блок-схема и программа решения задачи представлена для чисел в прямом порядке и обратном порядке.
(слайд 21)
Запишем рассмотренные алгоритмы на языке программирования Паскаль.
(слайд 22)
III. Подведение итогов урока
И так мы рассмотрели следующие вопросы:
- Алгоритмическая структура цикл;
- Виды алгоритмических структур:
- Цикл с предусловием;
- Цикл с послеусловием;
- Цикл с параметром;
- Рассмотрели способы записи данных структур;
- Разобрали примеры решения задач с помощью этих структур.