Циклические алгоритмы
- Халикова Венера Рафкатовна, учитель
Разделы: Информатика, Конкурс «Презентация к уроку»
Презентация к уроку
Загрузить презентацию (329,2 кБ)
Внимание! Предварительный просмотр слайдов используется исключительно в ознакомительных целях и может не давать представления о всех возможностях презентации. Если вас заинтересовала данная работа, пожалуйста, загрузите полную версию.
Цель: изучение алгоритмической структуры циклы, создание моделей и алгоритмов для решения практических задач.
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 |
Источник: https://xn--i1abbnckbmcl9fb.xn--p1ai/%D1%81%D1%82%D0%B0%D1%82%D1%8C%D0%B8/598696/
Циклы в Си. Циклы с постусловием, предусловием, Цикл for со счётчиком
Си циклы. C loops. Цикл с постусловием. Цикл с предусловием. Цикл со сщётчиком. while. do while. for. break. continue
При решении практических задач постоянно возникает необходимость в повторении действия заданное количество раз, или до достижения какого-либо условия.
Например, вывести список всех пользователей, замостить плоскость текстурой, провести вычисления над каждым элементом массива данных и т.п.
В си для этих целей используются три вида циклов: с предусловием, постусловием и цикл for со счётчиком (хотя, это условное название, потому что счётчика может и не быть).
Любой цикл состоит из тела и проверки условия, при котором этот цикл должен быть прекращён. Тело цикла — это тот набор инструкций, который необходимо повторять. Каждое повторение цикла называют итерацией.
Рассмотрим цикл с предусловием.
int i = 0; while (i Этот цикл выполняется до тех пор, пока истинно условие, заданное после ключевого слова while.Тело цикла — это две строки, одна выводит число, вторая изменяет его.Очевидно, что этот цикл будет выполнен 10 раз и выведет на экран0123и так далее до 9.
Очень важно, чтобы условие выхода из цикла когда-нибудь выполнилось, иначе произойдёт зацикливание, и программа не завершится.К примеру
int i = 0; while (i В этом цикле не изменяется переменная i, которая служит для определения условия останова, поэтому цикл не завершится.
int i = 0; while (i > 0) { printf(«%d», i); i++;}
В этой программе цикл, конечно, завершится, но из-за неправильного действия он будет выполнен гораздо больше 10 раз. Так как си не следит за переполнением переменной, нужно будет ждать, пока переменная переполнится и станет меньше нуля.
int i; while (i У этого примера неопределённое поведение. Так как переменная i заранее не инициализирована, то она хранит мусор, заранее неизвестное значение. При различном содержимом переменной i будет меняться поведение.
Если тело цикла while содержит один оператор, то фигурные скобки можно опустить.
int i = 0; while (i Здесь мы инкрементируем переменную i при вызове функции printf.Следует избегать такого стиля кодирования. Отсутствие фигурных скобок, особенно в начале обучения, может приводить к ошибкам. Кроме того, код читается хуже, да и лишние скобки не сильно раздувают листинги.
Циклы с постусловием
Цикл с постусловием отличается от цикла while тем, что условие в нём проверяется после выполнения цикла, то есть этот цикл будет повторён как минимум один раз (в отличие от цикла while, который может вообще не выполняться). Синтаксис цикла
do { тело цикла} while(условие);
Предыдущий пример с использованием цикла do будет выглядеть как
int i = 0; do { printf(«%d», i); i++;} while(i Давайте рассмотрим пример использования цикла с постусловием и предусловием. Пусть нам необходимо проинтегрировать функцию.
Рис. 1 Численное интегрирование функции ∫ a b f x d x
Интеграл — это сумма бесконечно малых. Мы можем представить интеграл как сумму, а бесконечно малые значения просто заменить маленькими значениями.
∫ a b f x d x = ∑ i = a b f i h
Из формулы видно, что мы на самом деле разбили площадь под графиком на множество прямоугольников, где высота прямоугольника — это значение функции в точке, а ширина — это наш шаг. Сложив площади всех прямоугольников, мы тем самым получим значение интеграла с некоторой погрешностью.
Рис. 2 Численное интегрирование функции методом
левых прямоугольников
Пусть искомой функцией будет x 2 .Нам понадобятся следующие переменные. Во-первых, аккумулятор sum для хранения интеграла. Во-вторых, левая и правая границы a и b, в третьих — шаг h. Также нам понадобится текущее значение аргумента функции x.
Для нахождения интеграла необходимо пройти от a до b с некоторым шагом h, и прибавлять к сумме площадь прямоугольника со сторонами f(x) и h.#include#include int main() { double sum = 0.0; double a = 0.0; double b = 1.0; double h = 0.01; double x = a; while (x Программа выводит 0.328.
Решение
∫ 0 1 x 2 d x = x 3 3 | 0 1 = 1 3 ≈ 0.333
Если посмотреть на график, то видно, что каждый раз мы находим значение функции в левой точке. Поэтому такой метод численного интегрирования называют методом левых прямоугольников. Аналогично, можно взять правое значение. Тогда это будет метод правых прямоугольников.
while (x правых прямоугольников
Сумма в этом случае будет равна 0.338. Метод левых и правых прямоугольников не очень точен. Мы фактически аппроксимировали (приблизили) гладкий график монотонно возрастающей функции гистограммой.Если немного подумать, то аппроксимацию можно проводить не только суммируя прямоугольники, но и суммируя трапеции.
Рис. 4 Численное интегрирование функции методом
трапеций
Приближение с помощью трапеций на самом деле является кусочной аппроксимацией кривыми первого порядка (ax+b).
Мы соединяем точки на графике с помощью отрезков. Можно усложнить, соединяя точки не отрезками, а кусками параболы, тогда это будет метод Симпсона.
Если ещё усложнить, то придём к сплайн интерполяции, но это уже другой, очень долгий разговор.
Вернёмся к нашим баранам. Рассмотрим 4 цикла.
int i = 0;while ( i++ Если выполнить эти примеры, то будет видно, что циклы выполняются от двух, до четырёх раз. На это стоит обратить внимание, потому что неверное изменение счётчика цикла часто приводит к ошибкам.
Часто случается, что нам необходимо выйти из цикла, не дожидаясь, пока будет поднят какой-то флаг, или значение переменной изменится. Для этих целей служит оператор break, который заставляет программу выйти из текущего цикла.
Давайте решим простую задачу. Пользователь вводит числа до тех пор, пока не будет введено число 0, после этого выводит самое большое из введённых.Здесь есть одна загвоздка.
Сколько чисел введёт пользователь не известно. Поэтому мы создадим бесконечный цикл, а выходить из него будем с помощью оператора break.
Внутри цикла мы будем получать от пользователя данные и выбирать максимальное число.
#include#include int main() { int num = 0; int max = num; printf(«To quit, enter 0»); /*бесконечный цикл*/ while (1) { printf(«Please, enter number: «); scanf(«%d», &num); /*условие выхода из цикла*/ if (num == 0) { break; } if (num > max) { max = num; } } printf(«max number was %d», max); getch();}Напомню, что в си нет специального булевого типа. Вместо него используются числа. Ноль — это ложь, все остальные значения – это истина.Цикл while(1) будет выполняться бесконечно. Единственной точкой выхода из него является условие
if (num == 0)
В этом случае мы выходим из цикла с помощью break;Для начала в качестве максимального задаём 0. Пользователь вводит число, после чего мы проверяем, ноль это или нет. Если это не ноль, то сравниваем его с текущим максимальным.
Бесконечные циклы используются достаточно часто, так как не всегда заранее известны входные данные, либо они могут меняться во время работы программы.
Когда нам необходимо пропустить тело цикла, но при этом продолжить выполнение цикла, используется оператор continue. Простой пример: пользователь вводит десять чисел. Найти сумму всех положительных чисел, которые он ввёл.
#include#include int main() { int i = 0; int positiveCnt = 0; float sum = 0.0f; float input; printf(«Enter 10 numbers»); while (i Цикл for
Одним из самых используемых является цикл со счётчиком for. Его синтаксис
for (; ; ){ }
Например, выведем квадраты первых ста чисел.
int i;for (i = 1; i Одним из замечательных моментов цикла for является то, что он может работать не только с целыми числами.
float num;for (num = 5.3f; num > 0f; num -= 0.2) { printf(«%.2f «, num);}
Этот цикл выведет числа от 5.3 до 0.1. Цикл for может не иметь некоторых «блоков» кода, например, может отсутствовать инициализация, проверка (тогда цикл становится бесконечным) или изменение счётчика. Вот пример с интегралом, реализованный с применением счётчика for
#include#include int main() { double sum = 0.0; double a = 0.0; double b = 1.0; double h = 0.01; double x; for (x = a; x Давайте рассмотрим кусок кода
double x ; for (x = a; x Его можно изменить так
double x = a; for (; x Более того, используя оператор break, можно убрать условие и написать double x;for (x = a;; x += h){ if (x>b){ break; } sum += x*x*h;}
или так
double x = a;for (;;){ if (x > b){ break; } sum += x*x*h; x += h;}
кроме того, используя оператор «,», можно часть действий перенести
double x ;for (x = a; x
ЗАМЕЧАНИЕ: несмотря на то, что так можно делать, пожалуйста, не делайте так! Это ухудшает читаемость кода и приводит к трудноуловимым ошибкам.
Давайте решим какую-нибудь практическую задачу посложнее.Пусть у нас имеется функция f(x). Найдём максимум её производной на отрезке.Как найти производную функции численно? Очевидно, по определению). Производная функции в точке — это тангенс угла наклона касательной.
Рис. 5 Численное дифференцирование функции f x ′ = d x d y
Возьмём точку на кривой с координатами (x; f(x)), сдвинемся на шаг h вперёд, получим точку (x+h, f(x+h)), тогда производная будет
d x d y = f ( x + h ) — f x ( x + h — x ) = tg α
То есть, отношение малого приращения функции к малому приращению аргумента.Внимательный читатель может задать вопрос, почему мы двигаемся вперёд по функции, а не назад. Ну пойдёмте назад
d x d y = f x — f ( x — h ) h = tg β
Возьмём среднее от этих двух значений, получим
f ( x + h ) — f ( x — h ) 2h
В общем-то теперь задача становится тривиальной: идём от точки a до точки b и находим минимальное значение производной, а также точку, в которой производная принимает это значение.
Для решения нам понадобятся, как и в задаче с интегралом, переменные для границ области поиска a и b, текущее значение x и шаг h.
Кроме того, необходимо максимальное значение maxVal и координата maxX этого максимального значения.Для работы возьмём функцию x • sin x
#include#include#include int main() { double a = 0; double b = 3.0; double h = 0.001; double h2 = h * 2.0; double maxVal = a*sin(a); double maxX = a; double curVal; double x; // Проходим по всей области от a до b // и ищем максимум первой производной // Используем функцию x*sin(x) for (x = a; x maxVal) { maxVal = curVal; maxX = x; } } printf(«max value = %.3f at %.3f», maxVal, maxX); getch();}
На выходе программа выдаётmax value = 1.391 at 1.077
Рис. 6 График производной функции x*sin(x)
Численное решение даёт такие же (с точностью до погрешности) результаты, что и наша программа.
Вложенные циклы
Рассмотрим пример, где циклы вложены друг в друга. Выведем таблицу умножения.
#include#include#include int main() { int i, j; // Для каждого i for (i = 1; i В этом примере в первый цикл по переменной i вложен второй цикл по переменной j. Последовательность действий такая: сначала мы входим в цикл по i, после этого для текущего i 10 раз подряд осуществляется вывод чисел. После этого необходимо перейти на новую строку.Теперь давайте выведем только элементы под главной диагональю
for (i = 1; i i) { break; } printf(«%4d», i*j); } printf(«»);}
Как вы видите, оператор break позволяет выйти только из текущего цикла. Этот пример может быть переписан следующим образом
for (i = 1; i Источник: https://learnc.info/c/loop.html
Основные типы и пример циклических алгоритмов
Статья призвана дать базовые понятия о том, что такое циклический алгоритм, которые являются общими для любого языка программирования и уровня подготовки программиста.
Понятие алгоритма
Алгоритмом называется последовательность действий для достижения решения какой-либо вычислительной и иной задачи за конечное число шагов.
Действия (инструкции) по выполнению алгоритма могут исполняться одна за другой (последовательно), одновременно (параллельно) или в произвольном порядке, используя циклы и условия перехода.
Алгоритмы используются не только в программировании, а и в других сферах деятельности, например в управлении производственными и бизнес-процессами.
Циклические алгоритмы
Алгоритм называется циклическим, если в нем имеются действия или наборы действий, которые необходимо выполнить более одного раза. Повторяющиеся алгоритмические действия являются телом цикла. Дополнительно каждый цикл имеет условие, по которому выполнение циклического алгоритма заканчивается.
Виды циклических алгоритмов
Каждый циклический алгоритм имеет в своем составе условие цикла, т. е. логическое выражение, результат проверки которого определяет, будет выполняться тело цикла еще раз или цикл будет завершен. По способу обработки все циклические алгоритмы делятся на три группы.
Цикл с предусловием
В таких циклических алгоритмах условие продолжения проверяется до обработки тела цикла, т. е. наличествует необходимость повторения обработки цикла.
Рассмотрим вывод на печать чисел от -5 до 0 как пример циклических алгоритмов с предусловием:
Элементы алгоритма:
- Задаем начальное значение базовой переменной j, равное -5.
- Проверяем условие цикла. Условие положительное, и тело цикла выполняется первый раз.
- Далее прибавляем к переменной j единицу, снова проверяем условие цикла.
- Цикл продолжает выполняться, пока значение j меньше нуля или равно ему, в противном случае выходим из цикла по ветке FALSE
Цикл с постусловием
Проверка условия выполняется после первой обработки тела цикла и контролирует выход из него.
Разберем расчет суммы от 1 до числа n как пример циклических алгоритмов, в которых используются постусловие:
- Вводим конечное число расчета суммы n и задаем нулевые начальные значения итоговой суммы sum и счетчика цикла i.
- Цикл выполняется до первой проверки условия.
- Проверяем условие цикла, т. е. значение счетчика i меньше или равен n.
- Если результат условия положительный, выполняем цикл еще раз, иначе заканчиваем цикл и выводим сумму на дисплей или печать.
Безусловный цикл
Обычно используется в алгоритмах, когда нужное количество выполнений цикла заранее известно, и очень часто применяется при работе с массивами.
Такой алгоритм содержит три обязательных элемента:
- Стартовое значение, которое называют параметром цикла, т. к. именно эта переменная изменяется после каждого выполнения цикла и определяет момент его завершения.
- Значение, при котором цикл завершается.
- Шаг цикла.
На каждом шаге программа проверяет, не превосходит ли стартовое значение конечное. И если да, то цикл завершается. В противном случае к стартовому значению прибавляем величину шага и цикл повторяется. Особо следует отметить, что любой безусловный цикл можно заменить условным с пред- или постусловием.
При составлении циклических алгоритмов необходимо придерживаться двух обязательных условий. Первое: для окончания цикла необходимо, чтобы содержимое тела влияло на пост- или предусловие, иначе мы в итоге можем получить бесконечный цикл.
Но для некоторых программных задач такие циклы применяются. Как пример циклических алгоритмов, выполняющихся бесконечно, можно привести операционную систему Windows, где используется бесконечный цикл опроса положения мыши для определения действий пользователя.Второе: переменные, передаваемые в цикл, должны обеспечивать хотя бы одно его выполнение.
Расчет факториала
Для закрепления прочитанного приведем пример циклических алгоритмов для расчета факториала целого числа. Приведенный пример является циклом с предусловием, но возможна реализация любым видом циклического алгоритма.
- Исходные данные: data – целое число, для которого определяется факториал.
- Системные переменные: параметр цикла i, принимающий значения от 1 до data c шагом 1.
- Результат: переменная factorial – факториал числа data, являющийся произведением целых чисел от 1 до data.
Рассмотрим алгоритм по шагам:
- Алгоритм получил число data, для которого необходимо вычислить факториал.
- Переменной factorial, в которой будет храниться итоговый результат, присвоено значение единицы.
- Организовываем цикл с параметром i и стартовым значением 1. Конечным значением будет являться исходное число data. Как только значение счетчика i будет больше, цикл завершается.
- Выполняется цикл вычисления факториала – перемножаются текущие значения factorial и счетчика i.
- К значению счетчика добавляем единицу, проверям условие цикла и, если результат положительный, завершаем его.
- После завершения последней итерации цикла значение факториала data! остается в factorial и выводится на дисплей или печать.
Источник: http://fb.ru/article/147298/osnovnyie-tipyi-i-primer-tsiklicheskih-algoritmov