Циклические алгоритмы

Предисловие

Цикл - это специальное выражение в тексте программы, которое позволяет выполнять часть кода несколько раз.

Циклы очень полезны в программировании, поскольку они позволяют не прописывать вручную одну и ту же операцию несколько раз.

Допустим нам надо вывести на экран числа от 0 до 14. Как бы это выглядело без цикла:

print(0)
print(1)
print(2)
print(3)
print(4)
print(5)
print(6)
print(7)
print(8)
print(9)
print(10)
print(11)
print(12)
print(13)
print(14)

однако с циклом код будет выглядеть следующим образом:

for i in range(0,15):
  print(i)

В этом случае команда

print(i)

выполнится раз подряд для значений от до включительно.

Команда в данном случае является телом цикла. В общем случае тело цикла может содержать множество команд, условий и других циклов (в таком случае называемых вложенными циклами).

Каждый запуск команды называется шагом цикла. То есть шаг цикла - очередной запуск команд тела цикла.

Рассмотрим различные типы циклов.

Цикл с предусловием (while)

Цикл с предусловием заключается в том, что перед выполнением повторяющихся команд (тело цикла) проверяется условие. В случае, если оно выполняется, то тело цикла выполняется. Если условие не выполняется, то начинает выполняться следующий за циклом код.

Общая схема цикла с предусловием (while)

В данной схеме тело цикла (блок действие) будет выполняться до тех пор, пока выполняется условие. Вместо одного блока действия может быть целое множество различных блоков.

Задача с предусловием (while)

Рассмотрим задачу с предусловием.

Задача: Спортсмен-лыжник начал тренировки пробежав в первый день distance км. Каждый следующий день он увеличивал длину пробега на 50 процентов от пробега предыдущего дня. Какого значения достигнет дневной пробег лыжника (distance) в день, когда его суммарный пробег total_distance за все дни превысит целевой суммарный пробег goal_distance, км?

Определим константы

1. DAILY_INCREASE=1.5

Определим переменные

1. distance=20
2. goal_distance=200
3. total_distance=0

В виду того, что условие, заданное в задаче, total_distance < goal_distance может выполнится сразу же в первый день, для решения подходит цикл с предусловием. То есть тело цикла гипотетически может не выполниться ни разу.

До программирования задачи можно построить алгоритм решения задачи в виде таблицы.

Таблица значений:

Напишем код решения такой задачи с помощью цикла с предусловием:

Код решения:

DAILY_INCREASE = 1.5

distance = 20
goal_distance = 200
total_distance = distance

while total_distance < goal_distance:
    print("{0:.1f} \t {1:.1f}".format(distance, total_distance))
    distance *= DAILY_INCREASE
    total_distance += distance

print(f"Дневной пробег равен {distance}")
print(f"Общий пробег равен {total_distance}")

Результат выполнения программы:

20.0     20.0
30.0     50.0
45.0     95.0
67.5     162.5
Дневной пробег равен 101.25
Общий пробег равен 263.75

Запустите программу с другими входными условиями.

Цикл с счётчиком (for)

Цикл с счётчиком является частным случаем цикла с предусловием.

Отличительными чертами такого цикла являются:

1. задаётся счётчик - переменная, которая изменяется от шага к шагу цикла по заранее известному закону. Указывается начальное значение счётчика, конечное значение и инкремент (или декремент) - величина, на которую счётчик увеличивается (или уменьшается) на каждом шаге цикла.
2. перед выполнением цикла известно сколько раз цикл будет запущен (если нет дополнительных условий выхода из цикла).

В данном случае предусловием является достижением заранее заданной величины.

Общая схема цикла с счётчиком

Вместо одного блока действия может быть целое множество различных блоков.

Также блок-схема с счётчиком может иметь вид:

Такая схема полностью идентична предыдущей схеме.

Простой пример цикла:

for a in range(6):
  print(a)

Результат работы цикла:

0
1
2
3
4
5

Задача с счётчиком (for)

Задача: Посчитать сумму первых n членов ряда:

где:

Переменные:

1. n = 10
2. summa = 0

Ввиду того, что заранее известно, сколько будет шагов цикла, то удобно использовать цикл с счётчиком для данной задачи.

До программирования задачи можно построить алгоритм решения задачи в виде таблицы.

Таблица значений:

Код решения:

import math

n = 10
summa = 0.0

for i in range(1, n + 1):
    ai = (-1)**(i + 1)/i
    summa += ai

print(f"Сумма ряда равна {summa}")

Цикл с постусловием (until)

Цикл с постусловием аналогичен циклу с предусловием, но условие проверяется после тела цикла. В таком случае тело цикла выполнится, как минимум, один раз. Другим отличием является то, что в данном случае проверяется не условие продолжения цикла, а условие его прекращения.

Задача с постусловием

Задача: Реализовать ввод пользователем положительного числа с помощью проверки на положительность.

Решение такой задачи на языке Pascal выглядит следующим образом: Решение на Pascal:

program z;
var x:integer;
begin
  repeat
    write('Введите положительное число: ');
    readln(x);
  until x>0;
  ...
end.

В данном случае условие until (от англ. - до тех пор, пока) - является частью языка, поэтому цикл реализуется естественным образом. В отличие от Pascal в Python цикла repeat-until нет. Но его можно реализовать с помощью дополнительного оператора break, который прерывает цикл в том месте, где он вызван.

Таким образом решение с помощью цикла с постусловием на Python выглядит следующим образом:

while True:
  x = int(input("Введите положительное число: "))
  if x > 0:
      break
...

Можно заметить, что тут используется цикл while, однако условием цикла является значение True, которое никогда не изменяется и всегда выполняется. Таким образом реализуется бесконечный цикл. Для выхода из цикла используется оператор break, который вызывается при выполнении условия if.

Операторы управления циклом

Операторы break и continue

break - выход из цикла
Пример: ввод числа в диапазоне [0, 1]

while True:
  x = float(input("Введите число от 0 до 1: "))
  if x >= 0 and x <= 1:
      break

continue - переход к следующей итерации
Пример: бесконечный калькулятор квадратного корня

while True:
  x = int(input("Введите число: "))
  if x < 0:
      continue
  print(math.sqrt(x))

Реализуйте примеры с различными входными данными и проверьте корректность их выполнения.

Оператор else в циклах

Задача: Посчитать сумму первых членов сходящегося ряда до точности :

Решение:

EPS = 1e-3
n = 1000
i = 1
summa = 0
while i < n:
  a_i = (-1)**(i + 1) / i
  summa += a_i
  if abs(a_i) < EPS:
    print(f"На {i}-м шаге получена сумма {summa} точностью {EPS}")
    break
  i += 1
else:
  print(f"По окончанию цикла был получен результат {summa}")

В данном случае есть два условия окончания цикла:

1. достижения -ого члена ряда,
2. достижение указанной точности.

Если указанная точность была достигнута:

if abs(a_i) < EPS:

то произойдёт вывод сообщения с указанием точности и выход из цикла:

print(f"На {i}-м шаге получена сумма {summa} точностью {EPS}")

Если же это условие не выполнится, то цикл просто закончится, когда счётчик достигнет последнего значения, то есть условие

while i < n:

перестанет выполняться. В таком случае нужно вывести сообщение без указания точности, для этого используется оператор else:

else:
  print(f"По окончанию цикла был получен результат {summa}")

Стоит отметить, что если проверки, в рамках которой условие не выполнилось, не произошло, например при срабатывании break, то else выполняться не будет, т.к. это часть цикла, а break полностью завершает цикл.

Реализуйте пример с различными входными данными и проверьте корректность выполнения.

Цикл с перебором массива (for each)

Цикл for each, как следует из названия, перебирает объекты в наборе и для каждого объекта выполняется команды из тела цикла.

Классический вариант перебора значений заключается в том, что происходит обращение к каждому значению набора по его номеру. То есть используется цикл for.

Цикл for each является частным случаем цикла for и заключается в том, что счётчик работает в неявном виде и скрыт от разработчика. Разработчик же имеет доступ только к определённому объекту из набора на соответствующем шаге цикла.

Задача с перебором массива

Задача: По массиву долгов студентов посчитать количество студентов на отчисление, у которых 3 и более долгов.

Решение на Java (классический for):

import static java.lang.System.out;

public class Doljniki {
    public static void main(String[] args) {
        int[] debts = {5, 0, 1, 0, 9, 0, 0, 3, 0, 0, 0, 0, 1};
        int studentsToExplusion = 0;

        for (int i = 0; i < debts.length; i++) {
            if (debts[i] >= 3) {
                studentsToExplusion++;
            }
        }
        out.printf("На отчисление " + studentsToExplusion + " студентов")
    }
}

Решение на Java (for each):

import static java.lang.System.out;

public class Doljniki {
    public static void main(String[] args) {
        int[] debts = {5, 0, 1, 0, 9, 0, 0, 3, 0, 0, 0, 0, 1};
        int studentsToExplusion = 0;

        for (int debt : debts) {
            if (debt >= 3) {
                studentsToExplusion++;
            }
        }
        out.printf("На отчисление " + studentsToExplusion + " студентов")
    }
}

Решение на Python:

debts = [5, 0, 1, 0, 9, 0, 0, 3, 0, 0, 0, 0, 1]
students_to_explusion = 0

for debt in debts:
    if debt >= 3:
        students_to_explusion += 1

print(f"На отчисление {students_to_explusion} студентов")

Реализуйте пример с различными входными данными и проверьте корректность выполнения.

Задачи для самостоятельного решения

Зачада №1

Посчитать выражение:

Зачада №2

Дано разложение функции через ряд Маклорена:

Задача №3

Дана формула корня -й степени:

При этом начальное значение (первое приближение) равно с условием:

Напишите функцию koren, в которой определяется и возвращается только одно значение корня на основе введенного текущего значения корня и степени.

Начальное значение в функции koren не задаётся.

Написать программу, вычисляющую корень -ой степени введённого пользователем числа, в качестве остановки итерационной процедуры использовать условие: