Исполнители Удвоитель, Раздвоитель, Калькулятор
Алгоритмы
Удвоитель
Обратная задача (составление программы)
Обратная задача (решение «с конца»)
Удвоитель
Раздвоитель
Исполнитель Калькулятор
Обратная задача (составление программы)
Обратная задача (решение «с конца»)
Ещё пример
Удвоитель
Удвоитель
Длина оптимальной программы
Количество программ
Табличный метод
Задача
Задача
Раздвоитель (ветвление)
Раздвоитель (циклы)
Раздвоитель (циклы)
Раздвоитель (циклы)
Раздвоитель (циклы)
Раздвоитель (циклы)
Раздвоитель (циклы)
Анализ блок-схем
Анализ блок-схем
Анализ блок-схем
Анализ блок-схем
Анализ блок-схем
Анализ блок-схем
Алгоритм Евклида
Модифицированный алгоритм Евклида
Алгоритм Евклида
Конец фильма
1.71M
Категория: ПрограммированиеПрограммирование

Исполнители: удвоитель, раздвоитель, калькулятор

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
English     Русский Правила