Презентация, доклад на тему Исполнители Удвоитель, Раздвоитель, Калькулятор

Содержание

АлгоритмыСвойства алгоритмадискретность: состоит из отдельных шагов (команд)понятность: должен включать только команды, известные исполнителю (входящие в СКИ)определенность: при одинаковых исходных данных всегда выдает один и тот же результатконечность: заканчивается за конечное число шаговмассовость: может применяться многократно при

Слайд 1Исполнители Удвоитель, Раздвоитель, Калькулятор

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

Слайд 2Алгоритмы
Свойства алгоритма
дискретность: состоит из отдельных шагов (команд)
понятность: должен включать только команды,

известные исполнителю (входящие в СКИ)
определенность: при одинаковых исходных данных всегда выдает один и тот же результат
конечность: заканчивается за конечное число шагов
массовость: может применяться многократно при различных исходных данных
корректность: дает верное решение при любых допустимых исходных данных

Алгоритм – это четко определенный план действий для исполнителя.

АлгоритмыСвойства алгоритмадискретность: состоит из отдельных шагов (команд)понятность: должен включать только команды, известные исполнителю (входящие в СКИ)определенность: при

Слайд 3Удвоитель
Исполнитель Удвоитель работает с одним числом и умеет выполнять с ним

две операции (команды):
1. прибавь 1
2. умножь на 2

Программа – это последовательность номеров команд, которые нужно выполнить.

Программа 12211

2

начальное число

3

6

12

13

14

1

2

2

1

1






результат

УдвоительИсполнитель Удвоитель работает с одним числом и умеет выполнять с ним две операции (команды): 1. прибавь 1

Слайд 4Обратная задача (составление программы)
Используя команды:
1. прибавь 1
2. умножь на

2
написать программу, которая из 3 получает 13.

Ответ: 221

3

4

13

1

дерево вариантов

6

5

8

7

12

6

10

9

16

8

14

24

2

1

1

1

1

1

2

2

2

2

2

2

2

1

2

1

Обратная задача (составление программы)Используя команды: 1. прибавь 1 2. умножь на 2написать программу, которая из 3 получает

Слайд 5Обратная задача (решение «с конца»)
13
нельзя делить на 2!
12
11
6
10
5
3
1
1
1
2
2
2
2
1
Ответ: 221

Обратная задача (решение «с конца»)13нельзя делить на 2!12116105311122221Ответ: 221

Слайд 6Удвоитель
У исполнителя есть команды:
1. прибавь 1
2. умножь на 2
Задания:

Какие числа можно получить из 0?
Как из числа 5 получить 105?
Как построить самую короткую программу для получения заданного числа N из 0?
УдвоительУ исполнителя есть команды: 1. прибавь 1 2. умножь на 2Задания: Какие числа можно получить из 0?

Слайд 7Раздвоитель
У исполнителя есть команды:
1. вычти 1
2. раздели на 2
Задания:
Какие

числа можно получить из положительного числа N?
Как быстрее всего получить 0 из положительного числа N?
РаздвоительУ исполнителя есть команды: 1. вычти 1 2. раздели на 2Задания:Какие числа можно получить из положительного числа

Слайд 8Исполнитель Калькулятор
Исполнитель Калькулятор работает с одним числом и умеет выполнять с

ним две операции (команды):
1. прибавь 2
2. умножь на 3

Программа – это последовательность номеров команд, которые нужно выполнить.

Программа 12211

2

начальное число

4

12

36

38

40

1

2

2

1

1






результат

Исполнитель КалькуляторИсполнитель Калькулятор работает с одним числом и умеет выполнять с ним две операции (команды): 1. прибавь

Слайд 9Обратная задача (составление программы)
Используя команды:
1. прибавь 2
2. умножь на

3
написать программу, которая из 3 получает 29.

Ответ: 221

3

5

29

1

дерево вариантов

9

7

15

11

27

9

21

17

45

13

33

81

2

1

1

1

1

1

2

2

2

2

2

2

2

1

2

1

Обратная задача (составление программы)Используя команды: 1. прибавь 2 2. умножь на 3написать программу, которая из 3 получает

Слайд 10Обратная задача (решение «с конца»)
29
нельзя делить на 3!
27
25
9
23
7
3
1
1
1
2
2
2
2
1
Ответ: 221

Обратная задача (решение «с конца»)29нельзя делить на 3!27259237311122221Ответ: 221

Слайд 11Ещё пример
Используя команды:
1. прибавь 2
2. умножь на 3
написать программу,

которая из 2 получает 15.
Ещё примерИспользуя команды: 1. прибавь 2 2. умножь на 3написать программу, которая из 2 получает 15.

Слайд 12Удвоитель
У исполнителя есть команды:
1. прибавь 1
2. умножь на 2
Дана

программа: 2112. Как можно сделать то же самое за 3 шага?

Программа 2112

x

2x

2

1

1

2





2x+1

2x+2

4x+4

x+1

1

2

УдвоительУ исполнителя есть команды: 1. прибавь 1 2. умножь на 2Дана программа: 2112. Как можно сделать то

Слайд 13Удвоитель
У исполнителя есть команды:
1. прибавь 1
2. умножь на 2
Докажите,

что:
любое число, меньшее 10, можно получить из 0 за 5 шагов
любое число, меньшее 100, можно получить из 0 за 12 шагов
УдвоительУ исполнителя есть команды: 1. прибавь 1 2. умножь на 2Докажите, что:любое число, меньшее 10, можно получить

Слайд 14Длина оптимальной программы
0
Минимальное число, для которого оптимальная программа содержит ровно N

команд:
первая команда – 1 (0 →1)
программа оканчивается на 1 (прибавь 1)
при «обратном ходе» команды 1 и 2 чередуются
Длина оптимальной программы0Минимальное число, для которого оптимальная программа содержит ровно N команд:первая команда – 1 (0 →1)

Слайд 15Количество программ
У исполнителя есть команды:
1. прибавь 1
2. умножь на

2
Сколько есть разных программ, с помощью которых можно из числа 1 получить число 6?

Сколько есть разных программ, с помощью которых можно из числа 4 получить число 12?

Сколько есть разных программ, с помощью которых можно из числа 8 получить число 18?

Количество программУ исполнителя есть команды: 1. прибавь 1 2. умножь на 2Сколько есть разных программ, с помощью

Слайд 16Табличный метод
1. прибавь 1
2. умножь на 2
N
если делится на

2!

Количество программ KN:

KN = KN-1 если N не делится на 2
KN = KN-1 + KN/2 если N делится на 2










K1+K1

K3+K2

K5+K3

K7+K4

K9+K5

+1

*2

для конечного числа N

одна пустая!

Табличный метод 1. прибавь 1 2. умножь на 2Nесли делится на 2!Количество программ KN:KN = KN-1

Слайд 17
Задача
У исполнителя есть команды:
1. прибавь 1
2. умножь на 3
Сколько

есть разных программ, с помощью которых можно из числа 4 получить число 20?




































KN = KN-1 если N не делится на 3
KN = KN-1 + KN/3 если N делится на 3

ЗадачаУ исполнителя есть команды: 1. прибавь 1 2. умножь на 3Сколько есть разных программ, с помощью которых

Слайд 18
Задача
У исполнителя есть команды:
1. прибавь 1
2. прибавь 2
2.

умножь на 2

Сколько есть разных программ, с помощью которых можно из числа 4 получить число 13?



















Количество программ:

KN = KN-1 + KN-2 если N не делится на 2
KN = KN-1 + KN-2 + KN/2 если N делится на 2

N

если N делится на 2!

ЗадачаУ исполнителя есть команды: 1. прибавь 1 2. прибавь 2 2. умножь на 2Сколько есть разных программ,

Слайд 19Раздвоитель (ветвление)
Алгоритм:
начало
конец
раздели на 2
вычти 1

Блок-схема:
Что получится для числа:
35

44
77
88

34
22
76
44





да

нет

если четное
то раздели на 2
иначе вычти 1
все

Раздвоитель (ветвление)Алгоритм:началоконецраздели на 2вычти 1Блок-схема:Что получится для числа:  35  44  77  8834227644данетесли четное

Слайд 20Раздвоитель (циклы)
Алгоритм:
Что получится:
10
20
30
50

60

0
1
3
3
6





Цикл – это повторение одинаковых действий.


нц 5 раз
если четное
то раздели на 2
иначе вычти 1
всё
кц

если четное
то раздели на 2
иначе вычти 1
всё

конец цикла

тело цикла

начало цикла

Раздвоитель (циклы)Алгоритм:Что получится:  10  20  30  50  6001336Цикл – это повторение одинаковых

Слайд 21
Раздвоитель (циклы)
начало
конец
раздели на 2
вычти 1

Блок-схема:
да
нет
да
нет
тело цикла

Раздвоитель (циклы)началоконецраздели на 2вычти 1Блок-схема:данетданеттело цикла

Слайд 22нц пока положительное
если четное
то раздели на 2

иначе вычти 1
всё
кц

Раздвоитель (циклы)

Алгоритм:

Задание: нарисуйте блок-схему.

Сколько шагов цикла выполнится для числа
15
16
128

7
5
8




нц пока положительное если четное  то раздели на 2   иначе вычти 1 всёкцРаздвоитель (циклы)Алгоритм:Задание:

Слайд 23нц пока положительное
нц пока четное
раздели на 2

кц
вычти 1
кц

Раздвоитель (циклы)

Алгоритм получения 0 из положительного числа:

Задание: нарисуйте блок-схему.

нц пока положительное нц пока четное  раздели на 2  кц   вычти 1кцРаздвоитель (циклы)Алгоритм

Слайд 24нц пока положительное
вычти 1
нц пока четное
раздели на

2
кц
кц

Раздвоитель (циклы)

Алгоритм получения 0 из положительного числа:

Задание: нарисуйте блок-схему.

1?

2?

3?

4?

нц пока положительное вычти 1 нц пока четное  раздели на 2  кц  кцРаздвоитель (циклы)Алгоритм

Слайд 25нц пока положительное
если нечетное
то вычти 1
всё
нц

пока четное
раздели на 2
кц
кц

Раздвоитель (циклы)

Алгоритм получения 0 из положительного числа:

Задание: нарисуйте блок-схему.

1?

2?

3?

4?

нц пока положительное если нечетное  то вычти 1 всё нц пока четное  раздели на 2

Слайд 26Анализ блок-схем





















Анализ блок-схем

Слайд 27Анализ блок-схем

Анализ блок-схем

Слайд 28Анализ блок-схем

x = 13
y = 20

Анализ блок-схемx = 13 y = 20

Слайд 29Анализ блок-схем



k = 7
x1 = 21
x2 = 13
z = 21

Анализ блок-схемk = 7x1 = 21 x2 = 13z = 21

Слайд 30Анализ блок-схем
Напишите программу, в которой a, b и c вводятся с

клавиатуры. Заполните таблицу:

вывод "a=", a, "b=", b

вывод a, b

вывод a, " ", b

Анализ блок-схемНапишите программу, в которой a, b и c вводятся с клавиатуры. Заполните таблицу:вывод

Слайд 31Анализ блок-схем

Напишите программу, в которой a и b вводятся с клавиатуры.

Что она вычисляет?

a:=64168
b:=82678


Анализ блок-схемНапишите программу, в которой a и b вводятся с клавиатуры. Что она вычисляет?a:=64168 b:=82678

Слайд 32Алгоритм Евклида
Евклид
(365-300 до. н. э.)
НОД(a,b)= НОД(a-b, b)

= НОД(a, b-a)

Заменяем большее из двух чисел разностью большего и меньшего до тех пор, пока они не станут равны. Это и есть НОД.

НОД (14, 21) = НОД (14, 21-14) = НОД (14, 7)

НОД (1998, 2) = НОД (1996, 2) = … = 2

Пример:

много шагов при большой разнице чисел:

= НОД (7, 7) = 7

Надо: вычислить наибольший общий делитель (НОД) чисел a и b.

Алгоритм ЕвклидаЕвклид(365-300 до. н. э.) НОД(a,b)= НОД(a-b, b)     = НОД(a, b-a)Заменяем большее из

Слайд 33Модифицированный алгоритм Евклида
НОД(a,b)= НОД(mod(a,b), b)
= НОД(a,

mod(b,a))

Заменяем большее из двух чисел остатком от деления большего на меньшее до тех пор, пока меньшее не станет равно нулю. Тогда большее — это НОД.

НОД (14, 21) = НОД (14, 7) = НОД (0, 7) = 7

Пример:

Модифицированный алгоритм ЕвклидаНОД(a,b)= НОД(mod(a,b), b)     = НОД(a, mod(b,a))Заменяем большее из двух чисел остатком

Слайд 34Алгоритм Евклида
Составить программу для вычисления НОД с помощью алгоритма Евклида и

заполнить таблицу:



«5»: Подсчитать число шагов алгоритма.
Алгоритм ЕвклидаСоставить программу для вычисления НОД с помощью алгоритма Евклида и заполнить таблицу:«5»: Подсчитать число шагов алгоритма.

Слайд 35Конец фильма
ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики высшей категории,
ГОУ СОШ № 163,

г. Санкт-Петербург
kpolyakov@mail.ru

Использованы материалы Д. Кириенко, школа № 179, г. Москва

Конец фильмаПОЛЯКОВ Константин Юрьевичд.т.н., учитель информатики высшей категории,ГОУ СОШ № 163, г. Санкт-Петербургkpolyakov@mail.ruИспользованы материалы Д. Кириенко, школа

Что такое shareslide.ru?

Это сайт презентаций, где можно хранить и обмениваться своими презентациями, докладами, проектами, шаблонами в формате PowerPoint с другими пользователями. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами.


Для правообладателей

Яндекс.Метрика

Обратная связь

Email: Нажмите что бы посмотреть