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

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

1
Исполнитель
Водолей
Урок 0. Знакомство с
исполнителем Водолей
К. Поляков, 2010 -2011
http://kpolyakov.narod.ru

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

Исполнитель Водолей
2
Система команд
1. наполни A
A
A
A
A
2. вылей A
A
A
3. перелей из A в B
A
B
К. Поляков, 2010-2011
A
B
A
B
A
B
http://kpolyakov.narod.ru

3. Задачи из папки «Водолей»

Исполнитель Водолей
3
Задачи из папки «Водолей»
«3»: 1.vod (за 4 шага)
«4»: 1.vod (за 4 шага)
2.vod (за 4 шага)
«5»: 1.vod (за 4 шага)
2.vod (за 4 шага)
3.vod (за 8 шагов)
«6»: 1.vod
2.vod
3.vod
4.vod
К. Поляков, 2010-2011
(за 4 шага)
(за 4 шага)
(за 8 шагов)
(за 10 шагов)
http://kpolyakov.narod.ru

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

4
Исполнитель
Водолей
Урок 1. Как решать задачи
для Водолея?
К. Поляков, 2010 -2011
http://kpolyakov.narod.ru

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

Исполнитель Водолей
5
Метод перебора
Есть 5-литровый сосуд (A) и 3-литровый (B).
Отмерьте 1 литр воды.
A
B
-A
+A
+A
+B
A→B
-B
(2,0)
+A
граф
+B
(5,0)
(2,3)
-B
(0,0)
(0,3)
-A
B→A
(5,3)
-A
(0,3)
-A
(3,0)
+A
+B
-A
!
Граф – это набор
узлов и соединяющих
их рёбер (дуг)!
(3,3)
B→A
(5,1)
К. Поляков, 2010-2011
http://kpolyakov.narod.ru

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

Исполнитель Водолей
6
Метод бильярда
Есть 5-литровый сосуд (A) и 3-литровый (B).
Отмерьте 1 литр воды.
3
B
1.наполни
2.перелей
3.наполни
4.перелей
2
1
0
0
1
2
3
4
B
из B в A
B
из B в A
5
A
наполни A
вылей A
К. Поляков, 2010-2011
наполни B
перелей
из A в B
перелей
из B в A
вылей B
http://kpolyakov.narod.ru

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

Исполнитель Водолей
8
Табличная запись решения
Есть 5-литровый сосуд (A) и 3-литровый (B).
Отмерьте 1 литр воды.
1.наполни
2.перелей
3.наполни
4.перелей
B
из B в A
B
из B в A
1
2
3
4
+B
B A
+B
B A
A (5 л)
0
3
3
5
B (3 л)
3
0
3
1
К. Поляков, 2010-2011
http://kpolyakov.narod.ru

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

Исполнитель Водолей
9
Ещё один пример
Есть 6-литровый сосуд (A) и 3-литровый (B).
Отмерьте 2 литра воды.
3
B
2
1
0
!
!
0
1
2
3
A
4
5
6
Если объемы A и B имеют наибольший общий множитель X,
то можно отмерить только объем, кратный X!
Если объемы A и B – взаимно-простые числа (имеют НОД=1),
то можно отмерить любой объем ≤ max(A ,B)!
К. Поляков, 2010-2011
http://kpolyakov.narod.ru

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

Исполнитель Водолей
10
Программа для Водолея в Кумире
подключить
исполнителя
начало
алгоритма
конец
алгоритма
К. Поляков, 2010-2011
использовать
алг Отмерить
нач
наполни B
перелей из
наполни B
перелей из
кон
Водолей
1 литр
название
алгоритма
B в A
B в A
http://kpolyakov.narod.ru

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

Исполнитель Водолей
11
Задачи из практикума «Водолей»
Урок 1. Линейные алгоритмы
«3»: 1-1, 1-2
«4»: 1-1, 1-2
1-3, 1-4
«5»: 1-1, 1-2
1-3, 1-4
1-5, 1-6
К. Поляков, 2010-2011
http://kpolyakov.narod.ru

11. Задачи из практикума «Водолей»

12
Исполнитель
Водолей
Урок 2. Циклы
К. Поляков, 2010 -2011
http://kpolyakov.narod.ru

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

13
Задача
Есть 3-литровый сосуд (A) и 2-литровый (B).
Отмерьте 1 литр воды.
наполни A
перелей из A в B
A
B
3л
2л
К. Поляков, 2010-2011
A
3
1
B
0
2
http://kpolyakov.narod.ru

13. Задача

Исполнитель Водолей
14
Задача
Есть 7-литровый сосуд (A) и 2-литровый (B).
Отмерьте 1 литр воды.
наполни
перелей
вылей B
перелей
вылей B
перелей
вылей B
A
B
7л
2л
К. Поляков, 2010-2011
A
из A в B
из A в B
из A в B
A
7
5
5
3
3
1
1
B
0
2
0
2
0
2
0
команды повторяются
3 раза
http://kpolyakov.narod.ru

14. Задача

Исполнитель Водолей
15
Цикл
Цикл – это многократное выполнение одинаковых
действий.
начало
наполни A
?
цикл
да
перелей из A в B
вылей B
К. Поляков, 2010-2011
петля
конец
сделали
3 раза?
Когда
остановиться?
нет
loop
?
В каких случаях работает?
В каких – нет?
http://kpolyakov.narod.ru

15. Цикл

Исполнитель Водолей
16
Цикл «N раз»
Есть сосуд A (его объем – 7 литров) и
2-литровый сосуд (B). Отмерьте 1 литр воды.
?
A
B
7л
2л
К. Поляков, 2010-2011
использовать Водолей
Сколько шагов цикла нужно сделать?
алг Отмерить 1 литр
нач
наполни A
Esc, Р
нц 3 раз
перелей из A в B
вылей B
кц
кон
?
Подходит ли для других задач?
http://kpolyakov.narod.ru

16. Цикл «N раз»

Исполнитель Водолей
17
Вычисление количества шагов
Есть сосуд A (его объем – нечетное число) и
2-литровый сосуд (B). Отмерьте 1 литр воды.
?
A
Aл
Сколько шагов цикла нужно сделать?
размер A
1
3
5
7
9
B
11
2л
К. Поляков, 2010-2011
N
0
1
2
3
4
5
разделить размер A
на 2 нацело
div(размер A, 2)
размер B
http://kpolyakov.narod.ru

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

Исполнитель Водолей
18
Задачи из практикума «Водолей»
Урок 2. Циклы «N раз»
«3»: 2-1, 2-2, 2-3
«4»: 2-1, 2-2, 2-3
2-4, 2-5, 2-6
«5»: 2-1, 2-2, 2-3
2-4, 2-5, 2-6,
2-7, 2-8
К. Поляков, 2010-2011
http://kpolyakov.narod.ru

18. Задачи из практикума «Водолей»

19
Исполнитель
Водолей
Урок 3. Циклы с условием
К. Поляков, 2010 -2011
http://kpolyakov.narod.ru

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

20
Задача
Есть 7-литровый сосуд (A) и 2-литровый (B).
Отмерьте 1 литр воды.
наполни
перелей
вылей B
перелей
вылей B
перелей
вылей B
A
B
7л
2л
К. Поляков, 2010-2011
A
из A в B
из A в B
из A в B
A
7
5
5
3
3
1
1
B
0
2
0
2
0
2
0
при каком условии остановить цикл?
!
Повторять пока в сосуде А <> 1!
http://kpolyakov.narod.ru

20. Задача

Исполнитель Водолей
21
Цикл
начало
наполни A
в сосуде А <> 1?
цикл
нет
loop
петля
конец
да
перелей из A в B
вылей B
К. Поляков, 2010-2011
?
В каких случаях работает?
В каких – нет?
http://kpolyakov.narod.ru

21. Цикл

Исполнитель Водолей
22
Программа в Кумире
начало
цикла
конец
цикла
?
использовать Водолей
алг Отмерить 1 литр
нач
Esc, П
наполни A
нц пока в сосуде A <> 1
перелей из A в B
вылей B
кц
кон
? Как избежать
зацикливания?
если размер A = 12
размер B = 2 ?
К. Поляков, 2010-2011
зацикливание
http://kpolyakov.narod.ru

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

Исполнитель Водолей
23
Задачи из практикума «Водолей»
Урок 3. Циклы «пока»
«3»: 3-1, 3-2
«4»: 3-1, 3-2
3-3, 3-4
«5»: 3-1, 3-2
3-3, 3-4
3-5, 3-6
К. Поляков, 2010-2011
http://kpolyakov.narod.ru

23. Задачи из практикума «Водолей»

24
Исполнитель
Водолей
Урок 4. Переменные
К. Поляков, 2010 -2011
http://kpolyakov.narod.ru

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

25
Задача
Есть 7-литровый сосуд (A) и 2-литровый (B).
Отмерьте 1 литр воды.
1) использовать цикл пока
2) не использовать команду
в сосуде А
!
A
B
7л
2л
К. Поляков, 2010-2011
Нужно запоминать, как меняется
объем воды в сосуде А!
в сосуде
7 ←
5 ←
3 ←
1 ←
А
размер А
уменьшить на 2
уменьшить на 2
уменьшить на 2
http://kpolyakov.narod.ru

25. Задача

Исполнитель Водолей
26
Как хранить данные?
ячейка памяти
Оперативная память
12
112
23
переменная
целого типа
5
62
77
25
?
7
5
812
32
65
321 132
нач
новое значение
цел N
переменной
N:= 25
N:= размер А
N:= N - 2
уменьшить на 2
кон
Переменная – это величина, имеющая имя, тип и
значение. Значение переменной может изменяться
во время работы программы.
К. Поляков, 2010-2011
http://kpolyakov.narod.ru

26. Как хранить данные?

Исполнитель Водолей
27
Переменные
использовать Водолей
алг Отмерить 1 литр
нач
цел N
наполни A
N := размер A
нц пока N > 1
перелей из A в B
вылей B
N:= N - 2
кц
кон
объявление
целой
переменной
запись нового
значения в
переменную
?
К. Поляков, 2010-2011
Для каких задач работает?
http://kpolyakov.narod.ru

27. Переменные

Исполнитель Водолей
28
Трассировка
Трассировка – это отслеживание изменения
значений переменных во время работы программы.
F8 – выполнить один шаг.
эта команда
еще не
выполнялась
К. Поляков, 2010-2011
получено на
предыдущем
шаге цикла
http://kpolyakov.narod.ru

28. Трассировка

Исполнитель Водолей
29
Задачи из практикума «Водолей»
Урок 4. Переменные
«3»: 4-1, 4-2
«4»: 4-1, 4-2
4-3, 4-4
«5»: 4-1, 4-2
4-3, 4-4
4-5, 4-6
К. Поляков, 2010-2011
http://kpolyakov.narod.ru

29. Задачи из практикума «Водолей»

30
Исполнитель
Водолей
Урок 5. Ветвления
К. Поляков, 2010 -2011
http://kpolyakov.narod.ru

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

31
Задача
Есть два сосуда, один из них (неизвестно какой)
имеет объем 3 литра, а другой – 2 литра.
Отмерьте 1 литр воды.
A
B
3л
2л
наполни A
перелей из A в B
?
К. Поляков, 2010-2011
или
или
A
B
2л
3л
наполни B
перелей из B в A
Как выбрать из двух вариантов?
http://kpolyakov.narod.ru

31. Задача

Исполнитель Водолей
32
Ветвление на блок-схеме
начало
да
размер B = 2?
наполни A
перелей из A в B
ветвление
нет
наполни B
перелей из B в A
конец
Ветвление – это выбор одного из двух вариантов в
зависимости от выполнения некоторого условия.
К. Поляков, 2010-2011
http://kpolyakov.narod.ru

32. Ветвление на блок-схеме

Исполнитель Водолей
33
Ветвление в программе
использовать Водолей
алг Отмерить 1 литр
условие
нач
если размер B = 2
то
если условие
Esc, Е
наполни A
выполнено (истинно)
перелей из A в B
иначе
если условие НЕ
наполни B
выполнено (ложно)
перелей из B в A
все
кон
К. Поляков, 2010-2011
http://kpolyakov.narod.ru

33. Ветвление в программе

Исполнитель Водолей
34
Задачи из практикума «Водолей»
Урок 5. Ветвления
«3»: 5-1, 5-2
«4»: 5-1, 5-2
5-3, 5-4
«5»: 5-1, 5-2
5-3, 5-4
5-5, 5-6
«6»: 5-1,
5-3,
5-5,
5-7,
К. Поляков, 2010-2011
5-2
5-4
5-6
5-8
http://kpolyakov.narod.ru

34. Задачи из практикума «Водолей»

Исполнитель Водолей
35
Конец фильма
ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики высшей категории,
ГОУ СОШ № 163, г. Санкт-Петербург
[email protected]
В практикуме использованы разработки
Д.П. Кириенко (http://server.179.ru)
К. Поляков, 2010-2011
http://kpolyakov.narod.ru