programmingSimilar presentations:
Исполнители: удвоитель, раздвоитель, калькулятор
1. Исполнители Удвоитель, Раздвоитель, Калькулятор
1Исполнители
Удвоитель,
Раздвоитель,
Калькулятор
К. Поляков, 2010 -2012
http://kpolyakov.narod.ru
2. Алгоритмы
Исполнитель Калькулятор2
Алгоритмы
Алгоритм – это четко определенный план
действий для исполнителя.
Свойства алгоритма
• дискретность: состоит из отдельных шагов (команд)
• понятность: должен включать только команды,
известные исполнителю (входящие в СКИ)
• определенность: при одинаковых исходных данных
всегда выдает один и тот же результат
• конечность: заканчивается за конечное число шагов
• массовость: может применяться многократно при
различных исходных данных
• корректность: дает верное решение при любых
допустимых исходных данных
К. Поляков, 2010-2013
http://kpolyakov.spb.ru
3. Удвоитель
Исполнитель Калькулятор3
Удвоитель
Исполнитель Удвоитель работает с одним числом и
умеет выполнять с ним две операции (команды):
1. прибавь 1
2. умножь на 2
Программа – это последовательность номеров
команд, которые нужно выполнить.
Программа 12211
2
начальное
число
К. Поляков, 2010-2013
1
3
2
6
2
12
1
13
1
14
результат
http://kpolyakov.spb.ru
4. Обратная задача (составление программы)
Исполнитель Калькулятор4
Обратная задача (составление программы)
Используя команды:
1. прибавь 1
2. умножь на 2
написать программу, которая из 3 получает 13.
8
16
9
7
8
10
5
6
4
6
дерево
вариантов
3
14
13
12
1
2
24
3
Ответ: 221
4
1
6
1
2
8
5
2
7
12
1
2
1
2
1
2
1
2
6
10
9
16
8
14
13
24
К. Поляков, 2010-2013
http://kpolyakov.spb.ru
5. Обратная задача (решение «с конца»)
Исполнитель Калькулятор5
Обратная задача (решение «с конца»)
нельзя делить на 2!
13
Ответ: 221
12
1
9
9
5
29
27
81
3
2
11
10
7
33
11
15
21
1
1
13
45
17
6
1
2
5
3
? Почему решение
«с конца» короче?
! Решение «с конца» короче, если в списке команд
есть необратимая операция (каждое целое число
можно умножить на 2, но не каждое делится на 2)!
К. Поляков, 2010-2013
http://kpolyakov.spb.ru
6. Удвоитель
Исполнитель Калькулятор6
Удвоитель
У исполнителя есть команды:
1. прибавь 1
2. умножь на 2
Задания:
1) Какие числа можно получить из 0?
2) Как из числа 5 получить 105?
3)Как построить самую короткую программу для
получения заданного числа N из 0?
К. Поляков, 2010-2013
http://kpolyakov.spb.ru
7. Раздвоитель
Исполнитель Калькулятор7
Раздвоитель
У исполнителя есть команды:
1. вычти 1
2. раздели на 2
Задания:
1)Какие числа можно получить из положительного
числа N?
2)Как быстрее всего получить 0 из положительного
числа N?
К. Поляков, 2010-2013
http://kpolyakov.spb.ru
8. Исполнитель Калькулятор
8Исполнитель Калькулятор
Исполнитель Калькулятор работает с одним числом
и умеет выполнять с ним две операции (команды):
1. прибавь 2
2. умножь на 3
Программа – это последовательность номеров
команд, которые нужно выполнить.
Программа 12211
2
начальное
число
К. Поляков, 2010-2013
1
4
2
12
2
36
1
38
1
40
результат
http://kpolyakov.spb.ru
9. Обратная задача (составление программы)
Исполнитель Калькулятор9
Обратная задача (составление программы)
Используя команды:
1. прибавь 2
2. умножь на 3
написать программу, которая из 3 получает 29.
13
45
17
7
9
9
5
29
27
дерево
вариантов
3
33
11
15
21
1
81
2
3
Ответ: 221
5
1
9
1
2
15
7
2
11
27
1
2
1
2
1
2
1
2
9
21
17
45
13
33
29
81
К. Поляков, 2010-2013
http://kpolyakov.spb.ru
10. Обратная задача (решение «с конца»)
Исполнитель Калькулятор10
Обратная задача (решение «с конца»)
нельзя делить на 3!
29
1
Ответ: 221
27
1
1
23
45
17
33
11
15
21
7
9
2
25
13
9
5
29
27
81
3
9
1
2
7
3
? Почему решение
«с конца» короче?
! Решение «с конца» короче, если в списке команд
есть необратимая операция (каждое целое число
можно умножить на 3, но не каждое делится на 3)!
К. Поляков, 2010-2013
http://kpolyakov.spb.ru
11. Ещё пример
Исполнитель Калькулятор11
Ещё пример
Используя команды:
1. прибавь 2
2. умножь на 3
написать программу, которая из 2 получает 15.
! Не все задачи этого типа решаемы. Разрешимость
зависит от системы команд и начального числа.
К. Поляков, 2010-2013
http://kpolyakov.spb.ru
12. Удвоитель
Исполнитель Калькулятор12
Удвоитель
У исполнителя есть команды:
1. прибавь 1
2. умножь на 2
Дана программа: 2112. Как можно сделать то же
самое за 3 шага?
Программа 2112
2
x
К. Поляков, 2010-2013
1
1
2
2x
2x+1
2x+2
1
x+1
2
4x+4
http://kpolyakov.spb.ru
13. Удвоитель
Исполнитель Калькулятор13
Удвоитель
У исполнителя есть команды:
1. прибавь 1
2. умножь на 2
Докажите, что:
1)любое число, меньшее 10, можно получить из 0 за
5 шагов
2)любое число, меньшее 100, можно получить из 0
за 12 шагов
К. Поляков, 2010-2013
http://kpolyakov.spb.ru
14. Длина оптимальной программы
Исполнитель Калькулятор14
Длина оптимальной программы
Минимальное число, для которого оптимальная
программа содержит ровно N команд:
•первая команда – 1 (0 1)
•программа оканчивается на 1 (прибавь 1)
•при «обратном ходе» команды 1 и 2 чередуются
0
1
1
2
1
3
2
6
1
7
2
14
1
15
2
30
1
31
2
62
1
63
2
1
2
4
5
1
К. Поляков, 2010-2013
10
2
11
1
22
2
23
1
46
2
47
1
94
2
95
1
http://kpolyakov.spb.ru
15. Количество программ
Исполнитель Калькулятор15
Количество программ
У исполнителя есть команды:
1. прибавь 1
2. умножь на 2
Сколько есть разных программ, с помощью которых
можно из числа 1 получить число 6?
Сколько есть разных программ, с помощью которых
можно из числа 4 получить число 12?
Сколько есть разных программ, с помощью которых
можно из числа 8 получить число 18?
? Как решать, не выписывая все программы?
К. Поляков, 2010-2013
http://kpolyakov.spb.ru
16. Табличный метод
Исполнитель Калькулятор16
Табличный метод
? Как получить число N?
1. прибавь 1
2. умножь на 2
N-1 +1
если делится на 2!
N
N
2
*2
Количество программ KN:
для конечного
числа N
KN = KN-1
если N не делится на 2
KN = KN-1 + KN/2 если N делится на 2
N
1
2
3
4
5
6
7
8
KN
1
2
2
4
4
6
6
10 10 14
одна пустая! K1+K1
К. Поляков, 2010-2013
K3+K2
K5+K3
9
K7+K4
10
K9+K5
http://kpolyakov.spb.ru
17. Задача
Исполнитель Калькулятор17
Задача
У исполнителя есть команды:
1. прибавь 1
Какие формулы?
2. умножь на 3
Сколько есть разных программ, с помощью которых
можно из числа 4 получить число 20?
?
KN = KN-1
если N не делится на 3
KN = KN-1 + KN/3 если N делится на 3
N
KN
1
0
2
0
3
0
4
1
5
1
6
1
7
1
8
1
9
1
10 11 12
1 1 2
N
4
…
11 12
…
15
…
18
…
21
KN
1
1
1
2
3
3
4
4
5
К. Поляков, 2010-2013
2
http://kpolyakov.spb.ru
18. Задача
Исполнитель Калькулятор18
Задача
У исполнителя есть команды:
1. прибавь 1
N-1
2. прибавь 2
N-2
N
N/2
2. умножь на 2
если N делится на 2!
Сколько есть разных программ, с помощью которых
можно из числа 4 получить число 13?
Количество программ:
KN = KN-1 + KN-2
если N не делится на 2
KN = KN-1 + KN-2 + KN/2 если N делится на 2
N
KN
К. Поляков, 2010-2013
4
1
5
1
6
2
7
3
8
6
9
9
10 11 12 13
16 25 43 68
http://kpolyakov.spb.ru
19. Раздвоитель (ветвление)
Исполнитель Калькулятор19
Раздвоитель (ветвление)
Алгоритм:
если четное
то раздели на 2
иначе вычти 1
все
Блок-схема:
начало
да
чётное?
раздели на 2
Что получится для числа:
34
35
22
44
76
77
44
88
К. Поляков, 2010-2013
нет
вычти 1
конец
http://kpolyakov.spb.ru
20. Раздвоитель (циклы)
Исполнитель Калькулятор20
Раздвоитель (циклы)
Цикл – это повторение одинаковых действий.
Алгоритм:
начало цикла
тело цикла
нц 5 раз
если четное
то раздели на 2
иначе вычти 1
всё
кц
конец цикла
К. Поляков, 2010-2013
Что получится:
0
10
1
20
3
30
3
50
6
60
http://kpolyakov.spb.ru
21. Раздвоитель (циклы)
Исполнитель Калькулятор21
Раздвоитель (циклы)
Блок-схема:
начало
да
сделали 5 раз?
конец
нет
да
раздели на 2
чётное?
нет
вычти 1
тело цикла
К. Поляков, 2010-2013
http://kpolyakov.spb.ru
22. Раздвоитель (циклы)
Исполнитель Калькулятор22
Раздвоитель (циклы)
Алгоритм:
нц пока положительное
если четное
то раздели на 2
иначе вычти 1
всё
кц
? Что получим?
Задание: нарисуйте блок-схему.
Сколько шагов цикла выполнится для числа
7
15
5
16
8
128
К. Поляков, 2010-2013
http://kpolyakov.spb.ru
23. Раздвоитель (циклы)
Исполнитель Калькулятор23
Раздвоитель (циклы)
Алгоритм получения 0 из положительного числа:
нц пока положительное
нц пока четное
раздели на 2
кц
вычти 1
кц
? Всегда ли работает?
Задание: нарисуйте блок-схему.
К. Поляков, 2010-2013
http://kpolyakov.spb.ru
24. Раздвоитель (циклы)
Исполнитель Калькулятор24
Раздвоитель (циклы)
Алгоритм получения 0 из положительного числа:
нц пока положительное
1?
вычти 1
2?
нц пока четное
3?
раздели на 2
кц
4?
кц
? Всегда ли работает?
Задание: нарисуйте блок-схему.
К. Поляков, 2010-2013
http://kpolyakov.spb.ru
25. Раздвоитель (циклы)
Исполнитель Калькулятор25
Раздвоитель (циклы)
Алгоритм получения 0 из положительного числа:
нц пока положительное
1?
если нечетное
2?
то вычти 1
3?
всё
нц пока четное
4?
раздели на 2
кц
кц
? Всегда ли работает?
Задание: нарисуйте блок-схему.
К. Поляков, 2010-2013
http://kpolyakov.spb.ru
26. Анализ блок-схем
Исполнитель Калькулятор26
Анализ блок-схем
a:= 1
b:= 1
a:=1
a
b
1
?
1
b:=1
a = 4?
да
нет
a:= a * 2
b:= b + a
a:=a*2
К. Поляков, 2010-2013
2
3
b:=b+a
нет
a = 4?
a:=a*2
будет при a = 3?
? Что
a = 4? a = 5?
нет
a = 4?
4
7
b:=b+a
a = 4?
да
http://kpolyakov.spb.ru
27. Анализ блок-схем
Исполнитель Калькулятор27
Анализ блок-схем
a:=54;
b:=16;
a = b?
да
нет
нет
b:=b-a;
К. Поляков, 2010-2013
a > b?
да
a:=a-b;
http://kpolyakov.spb.ru
28. Анализ блок-схем
Исполнитель Калькулятор28
Анализ блок-схем
x:=10;
y:=15;
нет
y < 16?
да
x <= y?
да
x:=x+5;
y:=y-5;
нет
x:=x-3;
y:=y+5;
К. Поляков, 2010-2013
x = 13
y = 20
http://kpolyakov.spb.ru
29. Анализ блок-схем
Исполнитель Калькулятор29
Анализ блок-схем
k:=1;
k = 7
x1 = 21
x2 = 13
z = 21
x1:=1;
x2:=1;
z:=x1+x2;
x2:=x1;
x1:=z;
k:=k+1;
нет
К. Поляков, 2010-2013
k > 6?
да
http://kpolyakov.spb.ru
30. Анализ блок-схем
Исполнитель Калькулятор30
Анализ блок-схем
Напишите программу, в которой a, b и c вводятся с
клавиатуры. Заполните таблицу:
ввод a,b,c
Исходные данные
Результат
a
b
c
a
2
3
4
5
12
100
3
25
999
нет
111
222
9999
a:= a * 2
b:= b + a
111
222
111
100
12
5
a > c?
да
вывод a, b
? Как вывести результат?
b
85
вывод a, " ", b
8 5
вывод "a=", a, "b=", b
a=8 b=5
К. Поляков, 2010-2013
http://kpolyakov.spb.ru
31. Анализ блок-схем
Исполнитель Калькулятор31
Анализ блок-схем
a:=64168
b:=82678
a:=54;
b:=16;
a = b?
да
нет
нет
b:=b-a;
a > b?
да
a:=a-b;
Напишите программу, в которой a и b вводятся с
клавиатуры. Что она вычисляет?
К. Поляков, 2010-2013
http://kpolyakov.spb.ru
32. Алгоритм Евклида
Исполнитель Калькулятор32
Алгоритм Евклида
Надо: вычислить наибольший общий делитель (НОД)
чисел a и b.
Заменяем большее из двух чисел разностью
большего и меньшего до тех пор, пока они не
станут равны. Это и есть НОД.
НОД(a,b)= НОД(a-b, b)
= НОД(a, b-a)
Евклид
(365-300 до. н. э.)
Пример:
НОД (14, 21) = НОД (14, 21-14) = НОД (14, 7)
= НОД (7, 7) = 7
много шагов при большой разнице чисел:
НОД (1998, 2) = НОД (1996, 2) = … = 2
К. Поляков, 2010-2013
http://kpolyakov.spb.ru
33. Модифицированный алгоритм Евклида
Исполнитель Калькулятор33
Модифицированный алгоритм Евклида
Заменяем большее из двух чисел остатком от деления
большего на меньшее до тех пор, пока меньшее не
станет равно нулю. Тогда большее — это НОД.
НОД(a,b)= НОД(mod(a,b), b)
= НОД(a, mod(b,a))
Пример:
НОД (14, 21) = НОД (14, 7) = НОД (0, 7) = 7
К. Поляков, 2010-2013
http://kpolyakov.spb.ru
34. Алгоритм Евклида
Исполнитель Калькулятор34
Алгоритм Евклида
Составить программу для вычисления НОД с помощью
алгоритма Евклида и заполнить таблицу:
a
64168
358853
6365133
17905514
549868978
b
82678
691042
11494962
23108855
298294835
НОД(a,b)
«5»: Подсчитать число шагов алгоритма.
a
64168
358853
6365133
17905514
549868978
b
82678
691042
11494962
23108855
298294835
НОД(a,b)
шагов
К. Поляков, 2010-2013
http://kpolyakov.spb.ru
35. Конец фильма
Исполнитель Калькулятор35
Конец фильма
ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики высшей категории,
ГОУ СОШ № 163, г. Санкт-Петербург
[email protected]
Использованы материалы Д. Кириенко, школа № 179, г. Москва
К. Поляков, 2010-2013
http://kpolyakov.spb.ru