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

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

Система команд 1. наполни A 2. вылей A 3. перелей из A в B

Метод перебора Граф – это набор узлов и соединяющих их рёбер (дуг)! Дерево – это граф без циклов!

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

Общий алгоритм (бильярд) пока (X <> A) и (X <> B) если B пуст, то наполни B если A полон, то вылей A перелей из B в Aконец Второй путь?

Табличная запись решения Есть 5-литровый сосуд (A) и 3-литровый (B). Отмерьте 1 литр воды. наполни Bперелей из B в Aнаполни Bперелей из B в A

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

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

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

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

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

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

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

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

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

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