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

Что такое цикл?
Цикл – это многократное выполнение одинаковых действий.
Два вида циклов:
цикл с известным числом шагов (сделать 10 раз)
цикл с неизвестным числом шагов (делать, пока не надоест)
Задача. Вывести на экран 10 раз слово «Привет».

Повторения в программе
print("Привет“)
print("Привет")
...
print("Привет")

Блок-схема цикла
начало
конец
да
нет
тело цикла

Как организовать цикл?
счётчик = 0
пока счётчик < 10:
print("Привет“)
увеличить счётчик на 1
счётчик = 10
пока счётчик > 0:
print("Привет")
уменьшить счётчик на 1
✔
результат операции автоматически сравнивается с нулём!

Цикл с условием
Задача. Определить количество цифр в десятичной записи целого положительного числа, записанного в переменную n.
счётчик = 0
пока n > 0:
отсечь последнюю цифру n
увеличить счётчик на 1
n = n // 10
счётчик = счётчик + 1
счётчик += 1

Считаем цифры
count = 0
while :
n = n // 10
count += 1
тело цикла
начальное значение счётчика
n > 0
условие продолжения
заголовок цикла

Максимальная цифра числа
n = int(input())
M = -1
while n > 0:
d = n % 10
if d > M:
M = d
n = n // 10
print( M )
отсечь последнюю цифру
последняя цифра
пока остались цифры
поиск максимума
Задача. Определить максимальную цифру в десятичной записи целого положительного числа, записанного в переменную n.

Цикл с условием
k = 0
while k < 10:
print ( "привет" )
k += 1
При известном количестве шагов:
k = 0
while k < 10:
print ( "привет" )
Зацикливание:

Сколько раз выполняется цикл?
a = 4; b = 6
while a < b: a += 1
2 раза
a = 6
a = 4; b = 6
while a < b: a += b
1 раз
a = 10
a = 4; b = 6
while a > b: a += 1
0 раз
a = 4
a = 4; b = 6
while a < b: b = a - b
1 раз
b = -2
a = 4; b = 6
while a < b: a -= 1
зацикливание

Задачи
«A»: Напишите программу, которая получает два целых числа A и B (0 < A < B) и выводит квадраты всех натуральных чисел в интервале от A до B.
Пример:
Введите два целых числа:
10 12
10*10=100
11*11=121
12*12=144
«B»: Напишите программу, которая получает два целых числа и находит их произведение, не используя операцию умножения. Учтите, что числа могут быть отрицательными.
Пример:
Введите два числа:
10 -15
10*(-15)=-150

Задачи
«C»: Ввести натуральное число N и вычислить сумму всех чисел Фибоначчи, меньших N. Предусмотрите защиту от ввода отрицательного числа N.
Пример:
Введите число N:
10000
Сумма 17709

Задачи-2
«A»: Ввести натуральное число и найти сумму его цифр.
Пример:
Введите натуральное число:
12345
Сумма цифр 15.
«B»: Ввести натуральное число и определить, верно ли, что в его записи есть две одинаковые цифры, стоящие рядом.
Пример:
Введите натуральное число:
12342
Нет.
Пример:
Введите натуральное число:
12245
Да.

Задачи-2
«C»: Ввести натуральное число и определить, верно ли, что в его записи есть две одинаковые цифры (не обязательно стоящие рядом).
Пример:
Введите натуральное число:
12342
Да.
Пример:
Введите натуральное число:
12345
Нет.

Алгоритм Евклида
Алгоритм Евклида. Чтобы найти НОД двух натуральных чисел, нужно вычитать из большего числа меньшее до тех пор, пока они не станут равны. Это число и есть НОД исходных чисел.
НОД(14,21) = НОД(14,7) = НОД(7, 7) = 7
пока a != b:
если a > b:
a -= b # a = a - b
иначе:
b -= a # b = b - a
while a != b:
if a > b:
a -= b
else:
b -= a
НОД(1998,2) =
НОД(1996,2) = … = НОД(2, 2) = 2

Алгоритм Евклида
Модифицированный алгоритм Евклида. Заменять большее число на остаток от деления большего на меньшее до тех пор, пока меньшее не станет равно нулю. Другое (ненулевое) число и есть НОД чисел.
НОД(1998,2) = НОД(0,2) = 2
пока ???:
если a > b:
a = a % b
иначе:
b = b % a
a!=0 and b!=0:
если a != 0:
вывести a
иначе:
вывести b

Задачи
«3»: Ввести с клавиатуры два натуральных числа и найти их НОД с помощью алгоритма Евклида.
Пример:
Введите два числа:
21 14
НОД(21,14)=7
«4»: Ввести с клавиатуры два натуральных числа и найти их НОД с помощью модифицированного алгоритма Евклида. Заполните таблицу:

Задачи
«5»: Ввести с клавиатуры два натуральных числа и сравнить количество шагов цикла для вычисления их НОД с помощью обычного и модифицированного алгоритмов Евклида.
Пример:
Введите два числа:
1998 2
НОД(1998,2)=2
Обычный алгоритм: 998
Модифицированный: 1

Цикл с постусловием
while True:
if n > 0: break
условие выхода
print ( "Введите положительное число:" )
n = int ( input() )
тело цикла
при входе в цикл условие не проверяется
цикл всегда выполняется хотя бы один раз
Задача. Обеспечить ввод положительного числа в переменную n.
бесконечный цикл
прервать цикл

Программирование на языке Python
§ 58. Циклы по переменной

Цикл с переменной
Задача. Вывести 10 раз слово «Привет!».
while :
print("Привет!")
i = 0
i < 10
i += 1
for :
print("Привет!")
i in range(10)
в диапазоне [0,10)
Цикл с переменной:
range(10) → 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

Цикл с переменной
Задача. Вывести все степени двойки от 21 до 210.
while : print ( 2**k )
k = 1
k <= 10
k += 1
for :
print ( 2**k )
k in range(1,11)
в диапазоне [1,11)
Цикл с переменной:
range(1,11) → 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Цикл с переменной: другой шаг
100
81
64
49
36
25
16
9
4
1
1
9
25
49
81
for :
print ( k**2 )
k in range(1,11,2)
for :
print ( k**2 )
k in range(10,0,-1)
шаг
10,9,8,7,6,5,4,3,2,1
1,3,5,7,9

Сколько раз выполняется цикл?
a = 1
for i in range( 3): a += 1
a = 4
a = 1
for i in range( 3,1): a += 1
a = 1
a = 1
for i in range( 1,3,-1): a += 1
a = 1
a = 1
for i in range( 3,1,-1): a += 1
a = 3

Задачи
«A»: Найдите все пятизначные числа, которые при делении на 133 дают в остатке 125, а при делении на 134 дают в остатке 111.
«B»: Натуральное число называется числом Армстронга, если сумма цифр числа, возведенных в N-ную степень (где N – количество цифр в числе) равна самому числу. Например, 153 = 13 + 53 + 33. Найдите все трёхзначные Армстронга.

Задачи
«С»: Натуральное число называется автоморфным, если оно равно последним цифрам своего квадрата. Например, 252 = 625. Напишите программу, которая получает натуральное число N и выводит на экран все автоморфные числа, не превосходящие N.
Пример:
Введите N:
1000
1*1=1
5*5=25
6*6=36
25*25=625
76*76=5776

Вложенные циклы
Задача. Вывести все простые числа в диапазоне
от 2 до 1000.
сделать для n от 2 до 1000
если число n простое то
вывод n
число n простое
нет делителей [2.. n-1]: проверка в цикле!
for n in range(2, 1001):
if число n простое:
print( n )

Вложенные циклы
for n in range(2, 1001):
count = 0
if count == 0:
print( n )
for k in range(2,n):
if n % k == 0:
count += 1
вложенный цикл

Вложенные циклы
for i in range(1,4):
for k in range(1,4):
print( i, k )
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

Вложенные циклы
for i in range(1,5):
for k in range(1,i+1):
print( i, k )
1 1
2 1
2 2
3 1
3 2
3 3
4 1
4 2
4 3
4 4

Поиск простых чисел – как улучшить?
count = 0
k = 2
while :
if n % k == 0:
count += 1
k += 1
while k <= math.sqrt(n):
…
while k*k <= n:
if n % k == 0: break
k += 1
if k*k > n:
print ( n )
k*k <= n
выйти из цикла
если вышли по условию

Задачи
«A»: Напишите программу, которая получает натуральные числа A и B (A выводит все простые числа в интервале от A до B.
Пример:
Введите границы диапазона:
10 20
11 13 17 19
«B»: В магазине продается мастика в ящиках по 15 кг,
17 кг, 21 кг. Как купить ровно 185 кг мастики, не вскрывая ящики? Сколькими способами можно это сделать?