информатика и логика - Лекция 12. Методы решения логических задач.

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

Решение (способ 1, табличный) :

Решение лучше и удобнее оформить в виде таблицы:

Ходы	1	2	3	4	5	6
5 л	5	2	2	-	5	4
3 л	-	3	-	2	2	3

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

Более систематический подход к решению задач "на переливание" заключается в использовании блок-схем. Суть этого метода состоит в следующем. Сначала выделяются операции, которые позволяют нам точно отмерять жидкость. Эти операции называются командами. Затем устанавливается последовательность выполнения выделенных команд. Эта последовательность оформляется в виде схемы. Подобные схемы называются блок-схемами и широко используются в программировании. Составленная блок-схема является программой, выполнение которой может привести нас к решению поставленной задачи. Для этого достаточно отмечать, какие количества жидкости удается получить при работе составленной программы. При этом обычно заполняют отдельную таблицу, в которую заносят количество жидкости в каждом из имеющихся сосудов.

Пример:
Имеются два сосуда — трехлитровый и пятилитровый. Нужно, пользуясь этими сосудами, получить 1, 2, 3, 4, 5, 6, 7 и 8 литров воды. В нашем распоряжении водопроводный кран и раковина, куда можно выливать воду.

Решение (способ 2, метод блок-схем):

Перечислим все возможные операции, которые могут быть использованы нами, и введем для них следующие сокращенные обозначения:

НБ — наполнить больший сосуд водой из-под крана;
НМ — наполнить меньший сосуд водой из-под крана;
ОБ — опорожнить больший сосуд, вылив воду в раковину;
ОМ — опорожнить меньший сосуд, вылив воду в раковину;
Б→М — перелить из большего в меньший, пока больший сосуд не опустеет или меньший сосуд не наполнится;
М→Б — перелить из меньшего в больший, пока меньший сосуд не опустеет или больший сосуд не наполнится.

Выделим среди перечисленных команд только три: НБ, Б→М, ОМ. Кроме этих трех команд рассмотрим еще две вспомогательные команды: Б = 0? — посмотреть, пуст ли больший сосуд; М = З? — посмотреть, наполнен ли малый сосуд.

В зависимости от результатов этого осмотра мы переходим к выполнению следующей команды по одному из двух ключей - "да" или "нет". Такие команды в программировании принято называть командами "условного перехода" и изображать в блок-схемах в виде ромбика с двумя ключами-выходами.
Последовательность выполнения команд будет следующая: после Б→М будем выполнять ОМ всякий раз, как меньший сосуд оказывается наполненным, и НБ всякий раз, как больший сосуд будет опорожнен. Последовательность команд изобразим в виде блок-схемы:

Затем будем фиксировать, как меняется количество воды в сосудах, если действовать по приведенной схеме. Результаты оформим в виде таблицы.

Дальше эта последовательность будет полностью повторяться. Из таблицы видим, что количество воды в обоих сосудах вместе образует следующую последовательность: 0, 5, 2, 7, 4, 1, 6, 3, 0 и т.д. Таким образом, действуя по приведенной схеме, можно отмерить любое количество литров от 1 до 7. Чтобы отмерить еще и 8 литров, надо наполнить оба сосуда.

Решение (способ 3, метод бильярда):

Появившись до нашей эры в Индии и Китае, бильярд через много веков перекочевал в европейские страны – упоминание о нем имеется в английских летописях VI века. В России бильярд стал известен и распространился при Петре I. Подобно тому, как азартная игра в кости вызвала к жизни "исчисление" вероятностей, игра в бильярд послужила предметом серьезных научных исследований по механике и математике. Представьте себе горизонтальный бильярдный стол произвольной формы, но без луз. По этому столу без трения движется точечный шар, абсолютно упруго отражаясь от бортов стола. Спрашивается, какой может быть траектория этого шарика? Поиски ответа на этот вопрос и послужили появлению теории математического бильярда или теории траекторий.

Задачи на переливание жидкостей можно очень легко решать, вычерчивая бильярдную траекторию шара, отражающегося от бортов стола, имеющего форму параллелограмма.

В рассматриваемой задаче стороны параллелограмма должны иметь длины 3 и 5 единиц. По горизонтали будем откладывать количество воды в литрах в 5-литровом сосуде, а по вертикали – в 3-литровом сосуде. На всем параллелограмме нанесена сетка из одинаковых равносторонних треугольников.

Бильярдный шар может перемещаться только вдоль прямых, образующих сетку на параллелограмме. После удара о стороны параллелограмма шар отражается и продолжает движение вдоль выходящего из точки борта, где произошло соударение. При этом каждая точка параллелограмма, в которой происходит соударение, полностью характеризует, сколько воды находится в каждом из сосудов.

Пусть шар находится в левом нижнем углу и после удара начнет перемещаться вверх вдоль левой боковой стороны параллелограмма до тех пор, пока не достигнет верхней стороны в точке А. Это означает, что мы полностью наполнили водой малый сосуд. Отразившись упруго, шар покатится вправо вниз и ударится о нижний борт в точке В, координаты которой 3 по горизонтали и 0 по вертикали. Это означает, что в большом сосуде 3 литра воды, а в малом сосуде воды нет, то есть мы перелили воду из малого сосуда в большой сосуд.

Прослеживая дальнейший путь шара, и записывая все этапы его движения в виде отдельной таблицы, в конце концов, мы попадаем в точку Н, которая соответствует состоянию, когда малый сосуд пуст, а в большом сосуде 4 литра воды. Таким образом, получен ответ и указана последовательность переливаний, позволяющих отмерить 4 литра воды. Все 8 переливаний изображены схематически в таблице.

Является ли это решение самым коротким? Нет, существует второй путь, когда воду сначала наливают в пятилитровый сосуд. Если на диаграмме шар из точки О покатится вправо по нижней стороне параллелограмма и затем, отразившись от правой боковой стороны, в точку 2 на верхней стороне параллелограмма и т.д., то получим более короткое решение задачи. Можно показать, что полученное решение с 6 переливаниями уже является самым коротким.

Пример:

Среди 101 одинаковых по виду монет одна фальшивая, отличающаяся по весу. Как с помощью чашечных весов без гирь за два взвешивания определить, легче или тяжелее фальшивая монета? Находить фальшивую монету не требуется.

Решение:

Взвешиваем 50 и 50 монет: два случая.
1 случай. Равенство. Берем оставшуюся монету и ставим ее в левую кучку вместо одной из имеющихся там:
а) Левая кучка тяжелее, следовательно, фальшивая монета тяжелее;
б) Левая кучка легче, следовательно, фальшивая монета легче.
2 случай. Неравенство. Берем более тяжелую кучку и разбиваем ее на две кучки по 25 монет:
а) Вес кучек одинаковый, следовательно, фальшивая монета легче;
б) Вес кучек неодинаковый, следовательно, фальшивая монета тяжелее.

Назад Решать задачи

Форма входа

Поиск

Календарь

Статистика