Узнаем, что такое алгоритмы и какие они бывают. А также более подробно поговорим о циклических алгоритмах и о том, как они реализуются в программировании.
Что такое алгоритмы и какие они бывают
Прежде чем говорить о циклических алгоритмах, надо сначала разобраться в том, а что вообще такое алгоритмы и каких разновидностей они бывают. Алгоритм можно представить, как некую инструкцию, содержащую четкую последовательность действий для достижения определенного результата. Примеров алгоритмов в повседневной жизни великое множество: это и рецепты блюд и объяснения прохожего, как дойти до нужного торгового центра кратчайшим путем и, конечно же, описание способа решения квадратного уравнения через дискриминант.
Основные виды алгоритмов следующие:
- Линейные — это самые простые алгоритмы. Здесь действия идут строго друг за другом без всяких ветвлений и повторений. Инструкция типа того, как из точки А попасть в точку Б — это как раз и есть пример простого линейного алгоритма.
- Ветвящиеся — алгоритмы с условиями. Здесь какие-то действия выполняются только, если истинны определенные условия. Простой пример: если дискриминант квадратного уравнения равен нулю, то имеем 1 корень, если дискриминант больше нуля, то 2 корня, а если меньше нуля, то действительных корней нет.
- Циклические — о них поговорим более подробно немного позже. Эти алгоритмы содержат в себе цикл, то есть действия, которые могут повторяться какое-то количество раз, пока не будет достигнут желаемый результат. Количество повторений может быть строго фиксированным или зависеть от определенных условий.
Это не все виды алгоритмов. Помимо перечисленных есть еще рекурсивные и вероятностные. Подробнее об алгоритмах можно прочитать в этой статье.
Структура циклического алгоритма
Циклический алгоритм включает в себя следующие компоненты:
- Инициализация — здесь происходит присвоение переменным, которые нужны для работы алгоритма, их начальных значений.
- Условие выхода — при выполнении этого условия происходит выход из цикла. Если же условие не выполняется, то цикл повторяется. Выполнение условия выхода из цикла проверяется при каждом новом прохождении (итерации) цикла.
- Тело цикла — повторяемые при работе циклического алгоритма действия.
- Счетчик — переменная, которая увеличивает свое значение на единицу при каждой новой итерации.
Счетчик не обязательно должен входить в структуру каждого циклического алгоритма, а вот все остальные указанные компоненты обязательно должны присутствовать в составе любого циклического алгоритма.
Виды циклических алгоритмов
Циклические алгоритмы могут быть с предусловием, с постусловием и со счетчиком. Ниже более подробно рассмотрим каждую из этих разновидностей на примерах кода на популярных языках Python и Java.
Алгоритм со счетчиком
Такой алгоритм позволяет выполнять действия содержащиеся в теле цикла определенное количество раз. Для этого в алгоритме присутствует специальная переменная-счетчик. В общем виде такой алгоритм можно представить при помощи следующей блок-схемы:
Во многих языках программирования алгоритмы со счетчиком реализуются при помощи цикла for. Допустим, перед нами стоит задача вывести в консоль слово АЛГОРИТМ 6 раз. Как это сделать, например, на языке программирования Python? Очень просто! Потребуется написать всего две строчки кода:
for i in range(6):
print('АЛГОРИТМ')
Переменная i — это счётчик и она последовательно принимает значения от 0 до 5 при каждой итерации цикла. В итоге, в консоли получим такой вывод:
АЛГОРИТМ АЛГОРИТМ АЛГОРИТМ АЛГОРИТМ АЛГОРИТМ АЛГОРИТМ
Чтобы более наглядно проиллюстрировать изменения счетчика перепишем код:
for i in range(6):
print(f"Итерация {i}")
Вывод будет такой:
Итерация 0 Итерация 1 Итерация 2 Итерация 3 Итерация 4 Итерация 5
Функция range создает последовательность целых чисел от 0 до 5 и переменная-счетчик может принимать значения только внутри этого диапазона. То есть, если говорить о структуре алгоритма, то у нас имеется начальное значение (инициализация) счетчика (i = 0), условие выхода (i > 5), тело цикла и, собственно, сам счетчик (переменная i).
Еще более наглядно цикл for представлен в языке Java. Вот так в Java можно вывести последовательность чисел от 0 до 5:
public class Main {
public static void main(String[] args) {
for(int i = 0; i < 6; i++) {
System.out.println(i);
}
}
}
Пока переменная i меньше числа 6 цикл будет выполняться. В результате получим:
0 1 2 3 4 5
Шаг указывается при помощи третьего параметра (i++). В данном случае он равен единице, так как запись i++ эквивалентна записи i = i + 1. Давайте сделаем шаг равным 2:
public class Main {
public static void main(String[] args) {
for(int i = 0; i < 6; i = i + 2) {
System.out.println(i);
}
}
}
В этом случае к счетчику при каждой итерации будет уже прибавляться число 2, а не единица. Вывод в консоли будет такой:
0 2 4
Алгоритм с предусловием
Такой алгоритм выполняет действия снова и снова пока истинно некоторое условие. Причем условие проверяется до выполнения действий в теле цикла. Таким образом, команды в теле цикла могут вообще ни разу не выполниться, если условие окажется ложным. Блок-схема такого алгоритма в самом общем виде выглядит следующим образом:
В большинстве языков программирования алгоритмы с предусловием реализуются при помощи цикла while. Например, уже знакомый нам счетчик итераций на Python с применением цикла while будет выглядеть так:
counter = 0
while counter < 6:
print(f"Итерация {counter}")
counter += 1
В самом начале, перед запуском цикла, переменная counter инициализируется нулевым значением. На следующем шаге сразу же проверяется условие, и если переменная меньше числа 6, то выполняются команды в теле цикла. Последней командой переменная counter увеличивается на единицу и снова происходит проверка условия. В итоге получим тот же самый вывод в консоли:
Итерация 0 Итерация 1 Итерация 2 Итерация 3 Итерация 4 Итерация 5
В языке Java цикл while устроен так же, и вывод последовательности чисел от 0 до 5 происходит так:
public class Main {
public static void main(String[] args) {
int i = 0;
while (i < 6) {
System.out.println(i);
i++;
}
}
}
Как видим, здесь все то же самое: сначала происходит инициализация переменной (i = 0), дальше идет проверка условия (i < 6) и последней командой после вывода в консоль переменная увеличивается на единицу (i++). Разница только в синтаксисе.
Алгоритм с постусловием
Как можно понять по названию, в этом алгоритме условие проверяется после выполнения команд в теле цикла. Из-за этого тело цикла должно выполняться хотя бы один раз. Блок-схема алгоритма с постусловием:
Во многих языках программирования такие алгоритмы реализуются при помощи цикла do – while, но не во всех языках имеется встроенная поддержка этих алгоритмов. Например, ее нет в Python. И как тогда быть? Ведь иногда очень важно, чтобы команды в теле цикла выполнялись хотя бы единожды.
Это может быть полезно, например, для проверки введенных пользователем данных. Выход есть и он довольно простой. Вот так можно эмулировать цикл do – while при помощи цикла while и условного оператора if с оператором break:
while True:
number = int(input("Введите натуральное число: "))
if number > 0:
break
print("Число должно быть натуральным. Пожалуйста, попробуйте снова.")
print(f"Вы ввели натуральное число {number}")
Благодаря условию True мы получаем бесконечный цикл, в котором гарантировано выполнение действий в теле цикла как минимум один раз. Так как цикл бесконечный, то обязательно нужно условие выхода. Операторы if и break обеспечивают выход из цикла при истинности условия. Пример работы данного кода:
Введите натуральное число: 6 Вы ввели натуральное число 6
Еще пример:
Введите натуральное число: 0 Число должно быть натуральным. Пожалуйста, попробуйте снова. Введите натуральное число: -1 Число должно быть натуральным. Пожалуйста, попробуйте снова. Введите натуральное число: 12 Вы ввели натуральное число 12
Как видим, код отлично работает. Что касается языка Java, то там с реализацией алгоритмов с постусловием все прекрасно. В Java, в отличие от Python, имеется встроенный цикл do – while. Вот пример простой программы, которая выводит в консоль первые 6 нечетных чисел:
public class Main {
public static void main(String[] args) {
int number = 1;
do {
System.out.println(number);
number = number + 2;
}while(number < 12);
}
}
Сначала идет инициализация переменной number, далее выполняются команды в теле цикла и только потом происходит проверка условия. Вывод в консоли будет такой:
1 3 5 7 9 11
Еще пара примеров на языке Python
Выше мы рассмотрели самые простые примеры реализации циклических алгоритмов на двух самых популярных языках программирования. Ниже посмотрим на чуть более сложные примеры на языке Python.
Вычисление факториала
Факториал какого-либо натурального числа — это произведение всех натуральных чисел от 1 до самого этого числа включительно. Обозначается факториал восклицательным знаком. Примеры вычисления факториалов:
1!=1
2!=12=2
3!=123=6
Для вычисления факториала применим цикл while. Перед циклом создадим две переменные. В переменную number будет записано введенное пользователем число, а в переменную factorial_number запишем значение 1, так как факториал единицы равен 1. Команды в теле цикла будут выполняться пока number больше 1. Код программы:
number = int(input('Введите ваше число: '))
factorial_number = 1
while number > 1:
factorial_number = factorial_number * number
number = number - 1
print(factorial_number)
В самом цикле у нас две команды. Первая вычисляет факториал, а вторая с каждой новой итерацией уменьшает значение number на 1. Это значение в следующую итерацию идет как второй сомножитель для первой команды. А в первой команде для получения факториала переменная factorial_number умножает сама себя на постоянно уменьшающуюся number и таким образом на последней итерации мы получаем готовое значение факториала. Пример работы программы:
Введите ваше число: 3 6
Числа Фибоначчи
Числа Фибоначчи — это последовательность чисел, в которой каждое последующее число является суммой двух предыдущих, причем первые два числа этой последовательности 0 и 1. Ниже приводятся первые 15 чисел этой последовательности:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, …,
Применим цикл for для вычисления ряда Фибоначчи, но сначала нужно взять от пользователя желаемое количество чисел, которое программа должна вывести в консоль. Также нужно проинициализировать нулем и единицей две переменные. Это будут первые два числа последовательности. На следующем шаге выводим эти числа в консоль и запускаем цикл. Код программы:
n = int(input("Введите количество чисел: "))
fib1 = 0
fib2 = 1
print(fib1, fib2, end=' ')
for i in range(2, n):
fib1, fib2 = fib2, fib1 + fib2
print(fib2, end=' ')
В цикле for можно заметить уже знакомую нам функцию range. Только здесь она вызывается с двумя параметрами. Первый параметр — это стартовое число, то есть число, с которого должна начинаться последовательность, а второй параметр — это число, до которого последовательность должна генерироваться (само число не включается). Первая команда в теле цикла составлена в соответствии с определением ряда чисел Фибоначчи. Вторая команда выводит числа в консоль. Пример работы программы:
Введите количество чисел: 10 0 1 1 2 3 5 8 13 21 34
Задание для самостоятельного выполнения
Имеется следующий ряд чисел:
1, 5, -1, 9, -2, 18
Требуется найти в этом ряду наибольшее и наименьшее число при помощи циклического алгоритма реализованного на языке Python.
Решение:
Для решения этой задачи идеально подойдет цикл for. Предварительно нужно создать список указанных чисел:
numbers = [1, 5, -1, 9, -2, 18]
Далее инициализируем переменные для наибольшего и наименьшего числа:
maximum_number = numbers[0] minimum_number = numbers[0]
В обе переменные записываем первый элемент списка. Дальше проходимся циклом по всем элементам списка:
for number in numbers: if number > maximum_number: maximum_number = number if number < minimum_number: minimum_number = number
В теле цикла происходит сравнение переменной number с переменными maximum_number и minimum_number. В переменную number при каждой новой итерации записывается новой значение из списка numbers, и если это значение будет больше maximum_number, то это значение и записывается в maximum_number.
Также, если значение number меньше minimum_number, то это значение будет присвоено переменной minimum_number. На последнем шаге выводим найденные числа в консоль:
print(f"Наибольшее число: {maximum_number}")
print(f"Наименьшее число: {minimum_number}")
Весь код программы:
numbers = [1, 5, -1, 9, -2, 18]
maximum_number = numbers[0]
minimum_number = numbers[0]
for number in numbers:
if number > maximum_number:
maximum_number = number
if number < minimum_number:
minimum_number = number
print(f"Наибольшее число: {maximum_number}")
print(f"Наименьшее число: {minimum_number}")
В консоли получим следующий результат:
Наибольшее число: 18 Наименьшее число: -2
