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

Факультативы
Алгори́тмика — раздел информатики, наука об алгоритмах. Круг задач алгоритмики включает создание алгоритмов, доказательство их правильности и выполнимости, изучение их свойств и также исследование различных исполнителей. Алгоритмика -- это первое, что мы изучаем с учениками на факультативах по информатики.
Шкурин Дмитрий Николаевич
Содержимое публикации

Переливания

ПРИМЕР 

Однажды Винни-Пух захотел полакомиться медом и пошел к пчелам в гости. По дороге он нарвал цветов, чтобы подарить труженицам пчелкам. Пчелки очень обрадовались, увидев мишку с букетом цветов, и сказали: "У нас есть большая бочка с медом. Мы дадим тебе меда, если ты сможешь с помощью двух сосудов вместимостью 3 л и 5 л налить себе 4 л. Помогите Винни разобраться. 

РЕШЕНИЕ

Наполняем из бочки пятилитровый сосуд медом (1 шаг). Наполняем трехлитровый сосуд, переливая мед из пятилитрового. В итоге в пятилитровом сосуде остается 2л (2 шаг). Выливаем весь мед из трехлитрового сосуда обратно в бочку (3 шаг). Теперь из пятилитрового выливаем 2 л в трехлитровый сосуд (4 шаг). Из бочки наполняем пятилитровый сосуд (5 шаг). И наполняем трехлитровый сосуд доверху из пятилитрового (6 шаг). В итоге в пятилитровом сосуде остается 4 л.

Бензин

У мастера есть большая бочка с бензином и два ведра — на 14 литров и на 6 литров. 

Начало формы

Какое наименьшее количество литров бензина он сможет отмерить?

Конец формы

Решение задачи

Поскольку обе емкости вмещают четное количество бензина, то, как ни переливай, нечетное количество литров отмерить не получится. А вот два литра отмерить можно, например, так:

наполним ведро в 14 литров

перельем из большого ведра бензин в 6-тилитровое ведро, в 14-тилитровом осталось 8 литров

выльем все из шестилитрового ведра обратно в бочку

наполним шестилитровое ведро полностью бензином из 14-тилитрового — в 14-тилитровом осталось ровно 2 литра бензина

Три литра в кастрюле

У мамы есть кастрюля, вмещающая ровно 4 литра воды и пятилитровая банка, а также водопроводный кран, откуда можно наливать воду, и раковина, куда можно выливать воду. Ей нужно, чтобы в кастрюле оказалось ровно 3 литра воды. Какое наименьшее количество переливаний ей для этого потребуется сделать?

Налить воду из раковины — переливание, вылить воду из кастрюли в банку или обратно — переливание, вылить воду из чего-либо в раковину — тоже переливание.

Обратите внимание на то, что нам нужно, чтобы получилось ровно 3 литра, поэтому наливать воду "на глазок" не получится, можно ошибиться.

Решение задачи

Наполним кастрюлю (первое переливание), выльем из нее всю воду в банку (второе переливание). Опять наполним кастрюлю (третье переливание). Дольем водой из кастрюли банку до краев (четвертое переливание). В кастрюле ровно 3 литра воды.

Это решение можно проиллюстрировать такой таблицей:

Кастрюля (4 литра)

Банка (5 литров)

4

0

0

4

4

4

3

5

Молоко пополам

У доярки есть 10 литров молока в десятилитровой бочке и два пустых кувшина – на 3 и на 7 литров. Ей нужно отмерить ровно 5 литров молока, сделав как можно меньшее количество переливаний. Сколько переливаний ей для этого понадобится? За одно переливание можно полностью наполнить какой-либо сосуд, либо полностью из него вылить молоко в любой другой сосуд. “На глазок” переливать нельзя.

Решение задачи

Наполним молоком кувшин на 7 литров. Дальше будем переливать молоко в маленький кувшин, наполняя его полностью, затем выливаем молоко из маленького обратно в бочку и снова наполняем большой.

 

3

7

Первое переливание

0

7

Второе переливание

3

4

Третье переливание

0

4

Четвертое переливание

3

1

Пятое переливание

0

1

Шестое переливание

1

0

Седьмое переливание

1

7

Восьмое переливание

3

5

Песочные часы

У Бабы-Яги есть песочные часы на 3 и на 7 минут. А также 7 рецептов зелий, требующих варки в течение 1 минуты, 2 минут, 3 минут, 4 минут, 5 минут, 6 минут и 7 минут. Выберите те из них, время для варки которых она сможет отмерить с помощью своих часов.

Решение задачи

Баба-Яга сможет сварить все зелья.

1. Чтобы отмерить 1 минуту, нужно поставить часы одновременно. Когда из маленьких высыплется весь песок, опять их перевернуть. 

От момента, когда из маленьких второй раз высыплется весь песок, до момента, когда из больших высыплется весь песок, пройдет 1 минута.

2. Чтобы отмерить 2 минуты, нужно поставить часы одновременно. Когда из маленьких высыплется весь песок, опять их перевернуть, а когда песок высыплется второй раз, еще раз их перевернуть. 

От момента, когда из больших высыплется весь песок, до момента, когда из маленьких в третий раз высыплется весь песок, пройдет 2 минуты.

3. Чтобы отмерить 3 минуты, надо поставить маленькие часы.

4. Чтобы отмерить 4 минуты, нужно поставить часы одновременно. От момента, когда из маленьких высыплется весь песок, до момента, когда из больших высыплется весь песок, как раз и пройдет 4 минуты.

5. Чтобы отмерить 5 минут, нужно поставить часы одновременно. Когда из маленьких высыплется весь песок, опять их перевернуть, а когда песок высыплется второй раз, еще раз их перевернуть. 

Когда из больших высыплется весь песок, их тоже надо еще раз перевернуть.

От момента, когда из маленьких в третий раз высыплется весь песок, до момента, когда из больших во второй раз высыплется весь песок, пройдет 5 минут.

6. Надо два раза подряд поставить маленькие часы.

7. Чтобы отмерить 7 минут, надо поставить большие часы.

Минимум переливаний

Какое наименьшее число переливаний необходимо для того, чтобы с помощью семилитровой канистры,  11-литрового ведра и крана с водой отмерить 2 л?

Комментарий. Не забудьте, что в задачах на переливание "переливанием" называется любое действие с водой — наполнение любого сосуда или опустошение.

Решение задачи

Начнем с большого сосуда:

 

 

11

7

Исходно

0

0

Первое переливание

 0

Второе переливание

 7

Третье переливание

7

Четвертое переливание

11

Пятое переливание

 0

Шестое переливание

3

Седьмое переливание

3

7

Восьмое переливание

 10

Девятое переливание

 10

Десятое переливание

 11

Одиннадцатое переливание

 0

Двенадцатое переливание

 6

Тринадцатое переливание

 6

Четырнадцатое переливание

11

2

Комментировать
Свидетельство участника экспертной комиссии
Оставляйте комментарии к работам коллег и получите документ бесплатно!
Подробнее
Также Вас может заинтересовать
Информатика
Презентации по информатики для 6 класса «Логика и модель»
Информатика
Факультативы по информатики для 6 класса «Дополнительная общеразвивающая программа "Юный оператор"»
Информатика
Информатика
Презентации по информатики для 11 класса «Открытый урок»
Информатика
Планирование по информатики для 2 класса «Рабочая программа по курсу "Информатика и ИКТ" 2 - 4 классы»
Комментарии
Добавить
публикацию
После добавления публикации на сайт, в личном кабинете вы сможете скачать бесплатно свидетельство и справку о публикации в СМИ.
Cвидетельство о публикации сразу
Получите свидетельство бесплатно сразу после добавления публикации.
Подробнее
Свидетельство за распространение педагогического опыта
Опубликует не менее 15 материалов и скачайте бесплатно.
Подробнее
Рецензия на методическую разработку
Опубликуйте материал и скачайте рецензию бесплатно.
Подробнее
Свидетельство участника экспертной комиссии
Стать экспертом и скачать свидетельство бесплатно.
Подробнее
Помощь