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

Содержание

• 
  Слайд 1

  Исполнитель Водолей

  1

• 
  Слайд 2

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

  2 1. наполни A 2. вылей A 3. перелей из A в B A B A B A B A B A A A A A A

• 
  Слайд 3

  Метод перебора

  3 (0,0) (5,0) (0,3) (2,3) (3,0) (3,3) (5,1) (2,0) (0,3) (5,3) +A +B B→A B→A +B +B A→B -B -A -A +A +A граф -A -A -A -B +A A B Граф – это набор узлов и соединяющих их рёбер (дуг)! ! Дерево – это граф без циклов! !

• 
  Слайд 4

  Метод бильярда

  4 0 1 2 3 B 0 1 2 3 4 5 A наполни B перелей из B в A перелей из A в B вылей A вылей B наполни A Есть 5-литровый сосуд (A) и 3-литровый (B). Отмерьте 1 литр воды. наполни B перелейиз B в A наполни B перелейиз B в A

• 
  Слайд 5

  Общий алгоритм (бильярд)

  5 пока (X A) и (X B) если B пуст, то наполни B если A полон, то вылей A перелейиз B в A конец 0 1 2 3 B 0 1 2 3 4 5 A цикл Второй путь? ?

• 
  Слайд 6

  Табличная запись решения

  6 Есть 5-литровый сосуд (A) и 3-литровый (B). Отмерьте 1 литр воды. наполни B перелейиз B в A наполни B перелейиз B в A 0 3 3 0 3 3 5 1 +B BA +B BA

• 
  Слайд 7

  Ещё один пример

  7 Есть 6-литровый сосуд (A) и 3-литровый (B). Отмерьте 2 литра воды. Если объемы A и B имеют наибольший общий множитель X, то можно отмерить только объем, кратный X! ! Если объемы A и B – взаимно-простые числа (имеют НОД=1), то можно отмерить любой объем ≤ max(A ,B)! ! 0 1 2 3 B 0 1 2 3 4 5 A 6

• 
  Слайд 8

  Программа для Водолея в Кумире

  8 использовать Водолей алг А1 нач наполни B перелейиз B в A наполни B перелейиз B в A кон начало алгоритма конец алгоритма подключить исполнителя название алгоритма

• 
  Слайд 9

  Задача

  9 11 л 2 л A B Есть 11-литровый сосуд (A) и 2-литровый (B). Отмерьте 1 литр воды. наполни A перелейиз A в B вылей B перелейиз A в B вылей B перелейиз A в B вылей B перелейиз A в B вылей B перелейиз A в B A B 11 0 9 2 9 0 7 2 7 0 5 2 5 0 3 2 3 0 1 2 вылей B

• 
  Слайд 10

  Цикл

  10 Цикл – это многократное выполнение одинаковых действий. начало конец A=1? наполни A перелей из A в B вылей B цикл с условием нет да Когда остановиться? ? A:=11 A:=A-2 При каком объеме A работает? ? записать значение в ячейку А уменьшить значение ячейки А на 2

• 
  Слайд 11

  Программа в Кумире

  11 использовать Водолей алг А2 нач цел А наполни A A:=11 нц пока A>1 перелейиз A в B вылей B A:=A-2 кц кон начало цикла конец цикла объем А объявление переменной А Переменная – это величина, имеющая имя, которая может изменяться. изменение количества жидкости в А

• 
  Слайд 12

  Ввод значений с клавиатуры

  12 использовать Водолей алг А3 нач цел А, B ввод А, B наполни A нц пока A>1 перелейиз A в B вылей B A:=A–B кц кон ввод переменных объявление переменных А и B

• 
  Слайд 13

  Вычисление количества шагов

  13 A л 2 л A B Есть сосуд A (его объем – нечетное число)и 2-литровый сосуд (B). Отмерьте 1 литр воды. A N 1 0 3 1 5 2 7 3 9 4 11 5 N:=div(A,2) разделить A на 2 нацело Сколько шагов цикла нужно сделать? ?

• 
  Слайд 14

  Цикл«N раз»

  14 начало конец N=0? наполни A перелей из A в B вылей B N:=N-1 цикл «N раз» нет да вычислить число шагов уменьшить счетчик N на 1 N:=div(A,2) Всегда ли можно вычислить число шагов? ?

• 
  Слайд 15

  Цикл «N раз»

  15 использовать Водолей алг А4 нач цел А,N А:=11 наполни A N:=div(A,2); нцN раз перелейиз A в B вылей B A:=A–2 кц кон число шагов

• 
  Слайд 16

  Конец фильма

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