X
Код презентации скопируйте его
Исполнитель калькулятор
Скачать эту презентацию
Презентация на тему Исполнитель калькулятор
Скачать эту презентациюCлайд 1
* Исполнитель Калькулятор К. Поляков, 2010 http://kpolyakov.narod.ru
Cлайд 2
* Алгоритмы Свойства алгоритма дискретность: состоит из отдельных шагов (команд) понятность: должен включать только команды, известные исполнителю (входящие в СКИ) определенность: при одинаковых исходных данных всегда выдает один и тот же результат конечность: заканчивается за конечное число шагов массовость: может применяться многократно при различных исходных данных корректность: дает верное решение при любых допустимых исходных данных Алгоритм – это четко определенный план действий для исполнителя. Исполнитель Калькулятор К. Поляков, 2010 http://kpolyakov.narod.ru
Cлайд 3
* Система команд Исполнитель Калькулятор работает с одним числом и умеет выполнять с ним две операции (команды): 1. прибавь 2 2. умножь на 3 Программа – это последовательность номеров команд, которые нужно выполнить. Программа 12211 2 начальное число 4 12 36 38 40 1 2 2 1 1 результат Исполнитель Калькулятор К. Поляков, 2010 http://kpolyakov.narod.ru
Cлайд 4
* Обратная задача (составление программы) Используя команды: 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 Исполнитель Калькулятор К. Поляков, 2010 http://kpolyakov.narod.ru
Cлайд 5
* Обратная задача (решение «с конца») 29 нельзя делить на 3! 27 25 9 23 7 3 1 1 1 2 2 2 2 1 Ответ: 221 Исполнитель Калькулятор К. Поляков, 2010 http://kpolyakov.narod.ru
Cлайд 6
* Ещё пример Используя команды: 1. прибавь 2 2. умножь на 3 написать программу, которая из 2 получает 15. Исполнитель Калькулятор К. Поляков, 2010 http://kpolyakov.narod.ru
Cлайд 7
* Удвоитель У исполнителя есть команды: 1. прибавь 1 2. умножь на 2 Дана программа: 2112. Как можно сделать то же самое за 3 шага? Программа 2112 x 2x 2 1 1 2 2x+1 2x+2 4x+4 x+1 1 2 Исполнитель Калькулятор К. Поляков, 2010 http://kpolyakov.narod.ru
Cлайд 8
* Удвоитель У исполнителя есть команды: 1. прибавь 1 2. умножь на 2 Задания: Какие числа можно получить из 0? Как из числа 5 получить 105? Какие числа можно получить из отрицательного числа N? Как построить самую короткую программу для получения заданного X из 0? Найдите минимальное число, которое может быть получено из 0 только за 6 шагов. Исполнитель Калькулятор К. Поляков, 2010 http://kpolyakov.narod.ru
Cлайд 9
* Удвоитель У исполнителя есть команды: 1. прибавь 1 2. умножь на 2 Докажите, что: любое число, меньшее 10, можно получить из 0 за 5 шагов любое число, меньшее 100, можно получить из 0 за 12 шагов Исполнитель Калькулятор К. Поляков, 2010 http://kpolyakov.narod.ru
Cлайд 10
Длина оптимальной программы * 0 Минимальное число, для которого оптимальная программа содержит ровно N команд: первая команда – 1 (0 1) программа оканчивается на 1 (прибавь 1) при «обратном ходе» команды 1 и 2 чередуются Исполнитель Калькулятор К. Поляков, 2010 http://kpolyakov.narod.ru
Cлайд 11
* Раздвоитель У исполнителя есть команды: 1. вычти 1 2. раздели на 2 Задания: Какие числа можно получить из положительного числа N? Какие числа можно получить из отрицательного числа N? Как быстрее всего получить 0 из положительного числа N? Исполнитель Калькулятор К. Поляков, 2010 http://kpolyakov.narod.ru
Cлайд 12
* Раздвоитель (ветвление) Алгоритм: начало конец раздели на 2 вычти 1 Блок-схема: Что получится для числа: 35 44 77 88 34 22 76 44 да нет если четное то раздели на 2 иначе вычти 1 все Исполнитель Калькулятор К. Поляков, 2010 http://kpolyakov.narod.ru
Cлайд 13
* Раздвоитель (циклы) Алгоритм: Что получится: 10 20 30 50 60 0 1 3 3 6 Цикл – это повторение одинаковых действий. нц 5 раз если четное то раздели на 2 иначе вычти 1 всё кц если четное то раздели на 2 иначе вычти 1 всё конец цикла тело цикла начало цикла Исполнитель Калькулятор К. Поляков, 2010 http://kpolyakov.narod.ru
Cлайд 14
* Раздвоитель (циклы) начало конец раздели на 2 вычти 1 Блок-схема: да нет да нет тело цикла Исполнитель Калькулятор К. Поляков, 2010 http://kpolyakov.narod.ru
Cлайд 15
нц пока положительное если четное то раздели на 2 иначе вычти 1 всё кц * Раздвоитель (циклы) Алгоритм: Задание: нарисуйте блок-схему. Сколько шагов цикла выполнится для числа 15 16 128 7 5 8 Исполнитель Калькулятор К. Поляков, 2010 http://kpolyakov.narod.ru
Cлайд 16
нц пока положительное нц пока четное раздели на 2 кц вычти 1 кц * Раздвоитель (циклы) Алгоритм получения 0 из положительного числа: Задание: нарисуйте блок-схему. Исполнитель Калькулятор К. Поляков, 2010 http://kpolyakov.narod.ru
Cлайд 17
нц пока положительное вычти 1 нц пока четное раздели на 2 кц кц * Раздвоитель (циклы) Алгоритм получения 0 из положительного числа: Задание: нарисуйте блок-схему. Исполнитель Калькулятор К. Поляков, 2010 http://kpolyakov.narod.ru
Cлайд 18
нц пока положительное если нечетное то вычти 1 всё нц пока четное раздели на 2 кц кц * Раздвоитель (циклы) Алгоритм получения 0 из положительного числа: Задание: нарисуйте блок-схему. Исполнитель Калькулятор К. Поляков, 2010 http://kpolyakov.narod.ru
Cлайд 19
Анализ блок-схем * a b 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? да Исполнитель Калькулятор К. Поляков, 2010 http://kpolyakov.narod.ru
Cлайд 20
Анализ блок-схем * Напишите программу, в которой a, b и c вводятся с клавиатуры. Заполните таблицу: вывод "a=", a, "b=", b вывод a, b вывод a, " ", b Исходные данные Результат a b c a b 2 3 4 5 12 100 3 25 999 111 222 9999 111 222 111 100 12 5 Исполнитель Калькулятор К. Поляков, 2010 http://kpolyakov.narod.ru
Cлайд 21
Анализ блок-схем * Напишите программу, в которой a и b вводятся с клавиатуры. Что она вычисляет? a:=64168 b:=82678 Исполнитель Калькулятор К. Поляков, 2010 http://kpolyakov.narod.ru
Cлайд 22
Алгоритм Евклида * Евклид (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. Исполнитель Калькулятор К. Поляков, 2010 http://kpolyakov.narod.ru
Cлайд 23
Модифицированный алгоритм Евклида * НОД(a,b)= НОД(mod(a,b), b) = НОД(a, mod(b,a)) Заменяем большее из двух чисел остатком от деления большего на меньшее до тех пор, пока меньшее не станет равно нулю. Тогда большее — это НОД. НОД (14, 21) = НОД (14, 7) = НОД (0, 7) = 7 Пример: Исполнитель Калькулятор К. Поляков, 2010 http://kpolyakov.narod.ru
Cлайд 24
Алгоритм Евклида * Составить программу для вычисления НОД с помощью алгоритма Евклида и заполнить таблицу: «5»: Подсчитать число шагов алгоритма. a 64168 358853 6365133 17905514 549868978 b 82678 691042 11494962 23108855 298294835 НОД(a,b) a 64168 358853 6365133 17905514 549868978 b 82678 691042 11494962 23108855 298294835 НОД(a,b) шагов Исполнитель Калькулятор К. Поляков, 2010 http://kpolyakov.narod.ru
Cлайд 25
* Конец фильма ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики высшей категории, ГОУ СОШ № 163, г. Санкт-Петербург kpolyakov@mail.ru Использованы материалы Д. Кириенко, школа № 179, г. Москва Исполнитель Калькулятор К. Поляков, 2010 http://kpolyakov.narod.ru
