Лекция 03. Итеративные алгоритмы

1. Базовые управляющие структуры

2. Базовые управляющие структуры

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

3. Линейный алгоритм

• Алгоритм состоит из нескольких шагов, которые выполняются
строго последовательно, один раз
• Пример: вычислить площадь квадрата, если известен его
периметр
• Алгоритм:
• вход: p
• a p / 4 # посчитать длину стороны квадрата
• s a*a
• вывести s

4. Ветвящийся алгоритм

• Полное ветвление:
• если <условие>, то <действие 1>, иначе <действие 2>
• Сокращенное ветвление:
• если <условие>, то <действие>
• Случай, когда вариантов больше двух:
• если <условие 1>, то <действие 1>,
• иначе, если <условие 2>, то <действие 2>,
•…
• иначе <действие _по_умолчанию>
• Оператор выбора
Условие – это
выражение, которое
может принимать
значение True
(истина) или False
(ложь)

5. Ветвящийся алгоритм. Пример

• В соревновании участвовали 3 человека. Они набрали a, b и c
баллов соответственно. Сколько баллов набрал победитель?
• Алгоритм:
• Ввод a, b, c
• если (a>=b) и (a>=c), то вывод a
• иначе, если b>=c, то вывод b
• иначе вывод c

6. Классические итеративные алгоритмы

7. Итеративные алгоритмы

• Какие в алгоритме есть повторяющиеся действия? Что нужно
делать в цикле?
• Сколько раз (или до наступления какого события) нужно повторить
цикл?
• Что нужно сделать до начала цикла?
• В конце каждой итерации все ли готово для начала следующей
итерации?
• Где будет результат (ответ) после завершения цикла? Нужно ли
сделать какие-то действия после завершения цикла?

8. Нахождение чисел Фибоначчи

• Числа Фибоначчи – это последовательность чисел a0, a1, a2, …, ak, …,
в которой a0=0, a1=1, а все последующие числа определяются по
формуле ak=ak-2+ak-1, то есть далее каждое следующее число равно
сумме двух предыдущих
• Начинается эта последовательность так: 0, 1, 1, 2, 3, 5, 8, 13, 21, …
• Задача. Дано: целое неотрицательное число n. Найти: n-е число
Фибоначчи.
• Идея алгоритма – последовательно вычислять все числа по
формуле, пока не дойдем до нужного числа
• Формула используется одна и та же, вычисления повторяются,
значит мы можем использовать цикл

9. Нахождение чисел Фибоначчи

• a0=0, a1=1, далее ak=ak-2+ak-1
• Дано: n. Найти: an.
• Вспомогательные переменные, которые потребуются в цикле:
• prev – для хранения предыдущего числа (ak-1)
• prev2 – для хранения пред-предыдущего числа (ak-2)
• ak – для хранения вычисляемого числа

10. Нахождение чисел Фибоначчи

• a0=0, a1=1, далее ak=ak-2+ak-1
• Дано: n. Найти: an.
• Вспомогательные переменные: prev, prev2, ak
• Алгоритм:

11. Нахождение чисел Фибоначчи

• a0=0, a1=1, далее ak=ak-2+ak-1
• Дано: n. Найти: an.
• Вспомогательные переменные: prev, prev2, ak
• Алгоритм:
• Вход: n
• Если n=0, то вернуть 0, конец алгоритма
• Если n=1, то вернуть 1, конец алгоритма
• Цикл для k от 2 до n:
• ak prev2 + prev

12. Нахождение чисел Фибоначчи

• a0=0, a1=1, далее ak=ak-2+ak-1
• Дано: n. Найти: an.
• Вспомогательные переменные: prev, prev2, ak
• Алгоритм:
• Вход: n
• Если n=0, то вернуть 0, конец алгоритма
• Если n=1, то вернуть 1, конец алгоритма
• Цикл для k от 2 до n :
• ak prev2 + prev
Что нужно сделать до начала цикла?

13. Нахождение чисел Фибоначчи

• a0=0, a1=1, далее ak=ak-2+ak-1
• Дано: n. Найти: an.
• Вспомогательные переменные: prev, prev2, ak
• Алгоритм:
• Вход: n
• Если n=0, то вернуть 0, конец алгоритма
• Если n=1, то вернуть 1, конец алгоритма
• prev2 0, prev 1
• Цикл для k от 2 до n :
• ak prev2 + prev
В конце каждой итерации все ли готово для начала следующей итерации?

14. Нахождение чисел Фибоначчи

• a0=0, a1=1, далее ak=ak-2+ak-1
• Дано: n. Найти: an.
• Вспомогательные переменные: prev, prev2, ak
• Алгоритм:
• Вход: n
• Если n=0, то вернуть 0, конец алгоритма
• Если n=1, то вернуть 1, конец алгоритма
• prev2 0, prev 1
• Цикл для k от 2 до n :
• ak prev2 + prev
• prev2 prev
Где будет результат (ответ) после завершения цикла?
• prev ak

15. Нахождение чисел Фибоначчи

• a0=0, a1=1, далее ak=ak-2+ak-1
• Дано: n. Найти: an.
• Вспомогательные переменные: prev, prev2, ak
• Алгоритм:
• Вход: n
• Если n=0, то вернуть 0, конец алгоритма
• Если n=1, то вернуть 1, конец алгоритма
• prev2 0, prev 1
• Цикл для k от 2 до n :
• ak prev2 + prev
• prev2 prev
• prev ak
• Вернуть ak

16. Нахождение суммы ряда

• Задача. Дано: целое неотрицательное число n. Найти: сумму всех
целых неотрицательных чисел от 1 до n, то есть S=1+2+…+n.
• Тривиальный алгоритм
• S 0
• для i от 1 до n: S S+i
• вывести S
• Тривиальный алгоритм выполняет количество операций,
пропорциональное n. Существует более эффективный алгоритм:

17. Нахождение суммы ряда

• Задача. Дано: целое неотрицательное число n. Найти: сумму всех
целых неотрицательных чисел от 1 до n, то есть S=1+2+…+n.
• Тривиальный алгоритм
• S 0
• для i от 1 до n: S S+i
• вывести S
• Тривиальный алгоритм выполняет количество операций,
пропорциональное n. Существует более эффективный алгоритм:
• S n*(n+1)/2
• вывести S

18. Алгоритм обработки цифр числа (например, нахождения суммы цифр)

• Задача. Дано: целое неотрицательное число n. Найти: сумму всех
цифр числа n.
• Алгоритм
• S 0
• пока n > 0:
• d (n % 10)
• S S+d
• n n / 10
• вывести S
# знак % будет означать остаток от деления
# или совершить иное действие с цифрой d

19. Возведение числа в степень

• Задача. Дано: целое число a и целое неотрицательное число n.
Найти: an.
• Тривиальный алгоритм
• b 1
• для i от 1 до n: b b*a
• вывести b
• Тривиальный алгоритм выполняет количество операций,
пропорциональное n. Существует более эффективный алгоритм

20. Эффективный алгоритм возведения в степень

• Основан на представлении числа n в двоичном виде
• Пусть n10 = (nknk-1…n1n0)2, то есть n = nk∙2k+…+n1∙21+n0∙20