Презентация на тему: Исполнитель калькулятор

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Анализ блок-схем Что будет при a = 3? a = 4? a = 5?

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

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

Алгоритм Евклида Надо: вычислить наибольший общий делитель (НОД) чисел a и b. Заменяем большее из двух чисел разностью большего и меньшего до тех пор, пока они не станут равны. Это и есть НОД. НОД(a,b)= НОД(a-b, b) = НОД(a, b-a) Пример: НОД (14, 21) = НОД (14, 21-14) = НОД (14, 7)= НОД (7, 7) = 7Евклид(365-300 до. н. э.) много шагов при большой разнице чисел:НОД (1998, 2) = НОД (1996, 2) = … = 2

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

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

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