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

Содержание

• 
  Слайд 1

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

  1

• 
  Слайд 2

  Алгоритмы

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

• 
  Слайд 3

  Система команд

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

• 
  Слайд 4

  Обратная задача (составление программы)

  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 3 5 29 9 7 15 11 27 9 21 17 45 13 33 81 1 2 1

• 
  Слайд 5

  Обратная задача (решение «с конца»)

  5 29 нельзя делить на 3! 27 25 9 23 7 3 1 1 1 2 2 2 2 1 Ответ: 221 Почему решение «с конца» короче? ? Решение «с конца» короче, если в списке команд есть необратимая операция (каждое целое число можно умножить на 3, но не каждое делится на 3)! ! 3 5 29 9 7 15 11 27 9 21 17 45 13 33 81

• 
  Слайд 6

  Ещё пример

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

• 
  Слайд 7

  Удвоитель

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

• 
  Слайд 8
  

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

• 
  Слайд 9
  

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

• 
  Слайд 10

  Длина оптимальной программы

  10 0 1 1 6 7 21 3 1 4 5 2 1 10 11 21 14 15 21 30 31 21 62 63 21 22 23 21 46 47 21 94 95 21 Минимальное число, для которого оптимальная программасодержит ровно Nкоманд: первая команда – 1 (0 1) программа оканчивается на 1 (прибавь 1) при «обратном ходе» команды 1 и 2 чередуются 2 1 2

• 
  Слайд 11

  Раздвоитель

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

• 
  Слайд 12

  Раздвоитель (ветвление)

  12 Алгоритм: чётное? начало конец раздели на 2 вычти 1 Блок-схема: Что получится для числа: 35 44 77 88 34 22 76 44 да нет если четное то раздели на 2 иначе вычти 1 все

• 
  Слайд 13

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

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

• 
  Слайд 14
  

  14 чётное? начало конец раздели на 2 вычти 1 Блок-схема: да нет да нет тело цикла сделали 5 раз?

• 
  Слайд 15
  

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

• 
  Слайд 16
  

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

• 
  Слайд 17
  

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

• 
  Слайд 18
  

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

• 
  Слайд 19

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

  19 a:=a*2 b:=b+a a:=1 b:=1 да нет a=4? Что будет при a=3?a=4? a=5? ?

• 
  Слайд 20
  

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

• 
  Слайд 21
  

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

• 
  Слайд 22

  Алгоритм Евклида

  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.

• 
  Слайд 23

  Модифицированный алгоритм Евклида

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

• 
  Слайд 24

  Алгоритм Евклида

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

• 
  Слайд 25

  Конец фильма

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