К. Поляков, Исполнитель Калькулятор

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

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

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

Исполнитель Калькулятор К. Поляков, Обратная задача (решение «с конца») 29 нельзя делить на 3! Ответ: 221 Почему решение «с конца» короче? ? Решение «с конца» короче, если в списке команд есть необратимая операция (каждое целое число можно умножить на 3, но не каждое делится на 3)! !

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

Исполнитель Калькулятор К. Поляков, Удвоитель У исполнителя есть команды: 1. прибавь 1 2. умножь на 2 Дана программа: Как можно сделать то же самое за 3 шага? Программа 2112 x2x x+12x+24x+4 x+1 1 2

Исполнитель Калькулятор К. Поляков, Удвоитель У исполнителя есть команды: 1. прибавь 1 2. умножь на 2 Задания: 1)Какие числа можно получить из 0? 2)Как из числа 5 получить 105? 3)Какие числа можно получить из отрицательного числа N? 4)Как построить самую короткую программу для получения заданного X из 0 ? 5)Найдите минимальное число, которое может быть получено из 0 только за 6 шагов.

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

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

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

Исполнитель Калькулятор К. Поляков, Раздвоитель (ветвление) Алгоритм : чётное? начало конец раздели на 2вычти 1 Блок-схема : Что получится для числа: данет если четное то раздели на 2 иначе вычти 1 все если четное то раздели на 2 иначе вычти 1 все

Исполнитель Калькулятор К. Поляков, Раздвоитель (циклы) Алгоритм : Что получится: Цикл – это повторение одинаковых действий. нц 5 раз если четное то раздели на 2 иначе вычти 1 всё кц нц 5 раз если четное то раздели на 2 иначе вычти 1 всё кц если четное то раздели на 2 иначе вычти 1 всё если четное то раздели на 2 иначе вычти 1 всё конец цикла тело цикла начало цикла

Исполнитель Калькулятор К. Поляков, Раздвоитель (циклы) чётное? начало конец раздели на 2вычти 1 Блок-схема : данет да нет тело цикла сделали 5 раз?

Исполнитель Калькулятор К. Поляков, нц пока положительное если четное то раздели на 2 иначе вычти 1 всё кц нц пока положительное если четное то раздели на 2 иначе вычти 1 всё кц 15 Раздвоитель (циклы) Алгоритм : Что получим? ? Задание: нарисуйте блок-схему. Сколько шагов цикла выполнится для числа

Исполнитель Калькулятор К. Поляков, нц пока положительное нц пока четное раздели на 2 кц вычти 1 кц нц пока положительное нц пока четное раздели на 2 кц вычти 1 кц 16 Раздвоитель (циклы) Алгоритм получения 0 из положительного числа : Всегда ли работает? ? Задание: нарисуйте блок-схему.

Исполнитель Калькулятор К. Поляков, нц пока положительное вычти 1 нц пока четное раздели на 2 кц нц пока положительное вычти 1 нц пока четное раздели на 2 кц 17 Раздвоитель (циклы) Алгоритм получения 0 из положительного числа : Всегда ли работает? ? Задание: нарисуйте блок-схему.

Исполнитель Калькулятор К. Поляков, нц пока положительное если нечетное то вычти 1 всё нц пока четное раздели на 2 кц нц пока положительное если нечетное то вычти 1 всё нц пока четное раздели на 2 кц 18 Раздвоитель (циклы) Алгоритм получения 0 из положительного числа : Всегда ли работает? ? Задание: нарисуйте блок-схему.

Исполнитель Калькулятор К. Поляков, Анализ блок-схем 19 a:= a * 2 b:= b + a a:= 1 b:= 1 да нет a = 4?a = 4? ab a:=1 1? b:=1 1 a = 4? нет a:=a*2 2 b:=b+a 3 a = 4? нет a:=a*2 4 b:=b+a 7 a = 4? да Что будет при a = 3 ? a = 4 ? a = 5 ? ?

Исполнитель Калькулятор К. Поляков, Анализ блок-схем 20 Напишите программу, в которой a, b и c вводятся с клавиатуры. Заполните таблицу: a:= a * 2 b:= b + a да нет a > c? ввод a,b,c Исходные данныеРезультат abcab Как вывести результат? ? вывод "a=", a, "b=", b вывод a, b85 вывод a, " ", b8 5 a=8 b=5

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

Исполнитель Калькулятор К. Поляков, Алгоритм Евклида 22 Евклид ( до. н. э.) НОД(a,b)= НОД(a-b, b) = НОД(a, b-a) НОД(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.

Исполнитель Калькулятор К. Поляков, Модифицированный алгоритм Евклида 23 НОД(a,b)= НОД(mod(a,b), b) = НОД(a, mod(b,a)) НОД(a,b)= НОД(mod(a,b), b) = НОД(a, mod(b,a)) Заменяем большее из двух чисел остатком от деления большего на меньшее до тех пор, пока меньшее не станет равно нулю. Тогда большее это НОД. НОД (14, 21) = НОД (14, 7) = НОД (0, 7) = 7 Пример:

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

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