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

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

Этапы решения задач на компьютере
I. Постановка задачи:
исходные данные? результаты?
II. Формализация
выделение существенных данных
построение модели
запись на формальном языке
III. Разработка алгоритма
исходные данные → результаты
IV. Составление программы
= кодирование

Этапы решения задач на компьютере
V. Тестирование и отладка программы
Тестирование – проверка работы программы на тестовых данных с известным ответом.
Отладка – исправление ошибок.
VI. Выполнение расчётов
для данных, для которых ответ неизвестен
VII. Анализ результатов
не противоречит теории? здравому смыслу?

Алгоритм
Алгоритм — это точное описание последовательности действий некоторого исполнителя.
Дискретность — алгоритм состоит из отдельных команд, каждая из которых выполняется за конечное время.
Детерминированность (определённость) — при каждом запуске алгоритма с одними и теми же исходными данными получается один и тот же результат.
Понятность — алгоритм содержит только команды, входящие в систему команд исполнителя.
Свойства алгоритма:

Анализ алгоритмов: контрольная сумма
Задача 1. Контрольная сумма для пары 3-значных чисел:
768 156
14
11
8
контрольная сумма S
Найти: минимальное и максимальное значения контрольной суммы.
Min: первые цифры ≥ 1
S2 ≥ 2, S1 ≥ 0, S0 ≥ 0
100 100 ⇒ 20
Smin = 2

Анализ алгоритмов: контрольная сумма
Max:
..999.
Коллизия — разным данным соответствует одна и та же контрольная сумма.
900×900 ⇒ 20…991 (972)

Анализ алгоритмов: контрольная сумма
Задача 3. Сколько существует пар чисел, для которых контрольная сумма равна 421?
только 1+1
4=0+4=1+3=…=4+0
14=5+9=6+8=…=9+5

Анализ алгоритмов: контрольная сумма
Задача 3. Сколько существует пар чисел, для которых контрольная сумма равна 421?
10=1+9=2+8=…=9+1
9
11=2+9=3+8=…=9+2
8
18=9+9
12=3+9=4+8=…=9+3
7
...
1
10⋅1⋅45 = 450
9+8+7+6+5+4+3+2+1

Анализ алгоритмов: контрольная сумма
Задача 4. Приведите пример значения, которое контрольная сумма принимать НЕ МОЖЕТ.
.ab|c|.
Вариант 1. Сумма средних разрядов S1 < 10.
.a|bc|.
Вариант 2. Сумма средних разрядов 10 ≤ S1 ≤ 18.
.ab|1.
.a|b|1.
3, 15, 187
15, 310, 817
101, 121, 181
221, 371, 591
20, 100, 292, …

Анализ алгоритмов: бит чётности
Задача 6. К двоичному коду приписывается справа 0 или 1 так, чтобы количество единиц стало чётным.
1100110 1011001
данные
данные
Найдите блоки, переданные с ошибкой:
1100111 1001110 0011000

Алгоритмы и программирование
§ 52. Оптимальные линейные программы

Что такое оптимальная программа?
Оптимальная программа — это самая лучшая программа по какому-то показателю.

Составление программы
Используя команды:
1. прибавь 1
2. умножь на 2
написать самую короткую программу, которая из 6 получает 28.
Ответ: 122
6
7
25
1
дерево вариантов
12
8
14
13
24
9
16
15
28
14
26
48
2
1
1
1
1
1
2
2
2
2
2
1
1
2
2
2

Составление программы (с конца)
28
27
14
26
13
7
1
1
1
2
2
2
2
Ответ: 122
25
13
1
2
12
6
1
1
1
нельзя делить на 2!
дерево вариантов

Алгоритмы и программирование
§ 53. Анализ алгоритмов с ветвлениями и циклами

Вспомним всё
Цикл — это многократное выполнение одинаковых действий. Цикл состоит из заголовка и тела цикла — тех команд, которые находятся внутри цикла и выполняются несколько раз.
Ветвление — это выбор одного из двух вариантов действий в зависимости от выполнения некоторого условия.

Исполнитель Робот
Формальный исполнитель — это исполнитель, который одну и ту же команду всегда понимает однозначно и выполняет одинаково.

Анализ алгоритма для Робота
Робот выполнил программу и вернулся в ту же клетку. Откуда он мог начать движение?
ПОКА <снизу свободно> вниз
ПОКА <слева свободно> влево
ПОКА <сверху свободно> вверх
ПОКА <справа свободно> вправо
F4

Анализ алгоритма для Чертёжника
Чертёжник выполнил алгоритм (буквами n, a, b обозначены неизвестные числа) и вернулся в исходную точку. Укажите все возможные значения n.
сместиться на (-2, -11)
ПОВТОРИ n РАЗ
сместиться на (a, b)
сместиться на (27, 12)
сместиться на (-22, -7)
(-2, -11)
(dx, dy)
(-22, -7)
dx = 0 = -2 + n(a+27) – 22
dy = 0 = -11 + n(b+12) - 7
n(a+27)= 24
n(b+12)= 18
24: 1, 2, 3, 4, 6, 8, 12, 24
18: 1, 2, 3, 6, 9, 18

Анализ алгоритма для Редактора
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 68 идущих подряд цифр 8?
ПОКА нашлось (222) ИЛИ нашлось (888)
ЕСЛИ нашлось (222)
ТО заменить (222, 8)
ИНАЧЕ заменить (888, 2)
888888888…8
2
2
2
8
68 - 8·8 = 4
8888 → 28
2

Анализ алгоритмов для Редактора
1: ПОКА нашлось (222) ИЛИ нашлось (888)
ЕСЛИ нашлось (222)
ТО заменить (222, 8)
ИНАЧЕ заменить (888, 2)
2: ПОКА нашлось (222) ИЛИ нашлось (888)
ЕСЛИ нашлось (888)
ТО заменить (888, 2)
ИНАЧЕ заменить (222, 8)
8888888888888888888
2228888888888
⇒ 88888888888
8888888888888888888
⇒ 2222228

Конец фильма
ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики
ГБОУ СОШ № 163, г. Санкт-Петербург
[email protected]
ЕРЕМИН Евгений Александрович
к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО ПГГПУ, г. Пермь
[email protected]