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

• 1 слайд

  1
  Исполнители Удвоитель, Раздвоитель, Калькулятор
  

• 2 слайд

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

• 3 слайд

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

• 4 слайд

  4
  Обратная задача (составление программы)
  Используя команды:
  1. прибавь 1
  2. умножь на 2
  написать программу, которая из 3 получает 13.
  Ответ: 221
  3
  4
  13
  1
  дерево вариантов
  6
  5
  8
  7
  12
  6
  10
  9
  16
  8
  14
  24
  2
  1
  1
  1
  1
  1
  2
  2
  2
  2
  2
  2
  2
  1
  2
  1
  3
  4
  13
  6
  5
  8
  7
  12
  6
  10
  9
  16
  8
  14
  24
  

• 5 слайд

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

• 6 слайд

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

• 7 слайд

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

• 8 слайд

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

• 9 слайд

  9
  Обратная задача (составление программы)
  Используя команды:
  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
  

• 10 слайд

  10
  Обратная задача (решение «с конца»)
  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
  

• 11 слайд

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

• 12 слайд

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

• 13 слайд

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