Исполнитель калькулятор

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

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

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

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

Программа 12211

2

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

4

12

36

38

40

1

2

2

1

1

результат

на 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

программу, которая из 2 получает 15.

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

Программа 2112

x

2x

2

1

1

2

2x+1

2x+2

4x+4

x+1

1

2

2
Задания:
Какие числа можно получить из 0?
Как из числа 5 получить

2
Докажите, что:
любое число, меньшее 10, можно получить из 0 за

N команд:
первая команда – 1 (0 →1)
программа оканчивается на

2
Задания:
Какие числа можно получить из положительного числа N?
Какие числа можно

44
77
88
34
22
76
44




да
нет
если четное
то раздели на

50
60
0
1
3
3
6




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


нц 5 раз

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

конец цикла

тело цикла

начало цикла

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

Раздвоитель (циклы)
Алгоритм:
Задание: нарисуйте блок-схему.
Сколько шагов

7
5
8

кц
вычти 1
кц

Раздвоитель (циклы)
Алгоритм получения 0 из

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

на 2
кц
кц

Раздвоитель (циклы)
Алгоритм получения 0 из

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

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

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

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

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

с клавиатуры. Заполните таблицу:
вывод "a=", a, "b=", b
вывод a, b
вывод

клавиатуры. Что она вычисляет?
a:=64168
b:=82678

= НОД(a, b-a)
Заменяем большее из двух чисел разностью

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

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

Пример:

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

= НОД (7, 7) = 7

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

НОД(a, mod(b,a))
Заменяем большее из двух чисел остатком от деления большего

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

Пример:

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



«5»: Подсчитать число шагов алгоритма.

163, г. Санкт-Петербург
kpolyakov@mail.ru
Использованы материалы Д. Кириенко, школа № 179, г.