Алгоритм. Алгоритмы и программирование, 10 класс

1. Алгоритм

Алгоритмы и программирование, 10 класс
1
Алгоритм
Алгоритм — это точное описание последовательности
действий некоторого исполнителя.
Свойства алгоритма:
Дискретность — алгоритм состоит из отдельных
команд, каждая из которых выполняется за конечное
время.
Детерминированность (определённость) — при
каждом запуске алгоритма с одними и теми же
исходными данными получается один и тот же
результат.
Понятность — алгоритм содержит только команды,
входящие в систему команд исполнителя.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

2. Алгоритмы и программирование

2
Алгоритмы и
программирование
Оптимальные линейные
программы
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

3. Что такое оптимальная программа?

Алгоритмы и программирование, 10 класс
3
Что такое оптимальная программа?
Оптимальная программа — это самая лучшая
программа по какому-то показателю.
?
?
Как сравнить две программы?
Всегда ли оптимальная программа лучше
других по всем критериям?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

4. Составление программы

Алгоритмы и программирование, 10 класс
4
Составление программы
Используя команды:
1. прибавь 1
2. умножь на 2
написать самую короткую программу, которая из 6
получает 28.
дерево
6
вариантов
14
28
15
26
13
14
16
8
12
7
9
25
24
1
2
48
6
Ответ: 122
7
1
12
2
1
14
8
2
13
24
1
2
1
2
1
2
1
2
9
16
15
28
14
26
25
48
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

5. Составление программы (с конца)

Алгоритмы и программирование, 10 класс
5
Составление программы (с конца)
Ответ: 122
28
2
1
27
нельзя
делить
на 2!
!
25
26
27
14
1
2
13
7
1
26
1
2
25
13
дерево
вариантов
1
1
12
13
6
?
12
6
13
7
14
28
Почему решение
«с конца» короче?
Решение «с конца» короче, если в списке команд
есть необратимая операция (каждое целое число
можно умножить на 2, но не каждое делится на 2)!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru