Логические задачи, решаемые с помощью графов.
Особенно большую помощь графы оказывают при решении логических задач. Представляя изучаемые объекты в наглядной форме, «графы» помогают держать в памяти многочисленные факты, содержащиеся в условии задачи, устанавливать связь между ними.
Графом называется любое множество точек, некоторые из которых соединены линиями или стрелками. Точки, изображающие элементы множества, называют вершинами графа, соединяющие их отрезки – рёбрами графа. Точки пересечения рёбер графа не являются его вершинами. Во избежание путаницы вершины графа часто изображают не точками, а маленькими кружочками. Рёбра иногда удобнее изображать не прямолинейными отрезками, а дугами
Задача 1. Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?
Если подсчитать число ребер графа, изображенного на рисунке 4, то это число и будет равно количеству совершенных рукопожатий между пятью молодыми людьми. Их 10.
Задачи- игры, стратегии.
Задачи игры предполагают некоторую стратегию, т.е. последовательность ходов, которая для каждого игрока может привести к выигрышу или проигрышу.
Стратегия наз выигрышной если независимо от ходов одного из игроков второй при выбранной стратегии выигрывает
В задачах-играх имеет место понятие выигрышной или проигрышной позиции.
|
|
|
«Правильной игрой» в задачах этого класса называется выигрышная — стратегия, придерживаясь которой игрок выиграет при любых ответных действиях противника.
В задачи-играх используются самые разные методы решения, однако есть несколько часто повторяющихся идей:
1. инвариант — один из игроков каждым своим ходом приводит состояние игры в некоторое состояние (например, сумма оставшихся незанятыми полей) и такое состояние является выигрышным.
2. выигрышность доказывается «с конца», с использованием идей динамического программирования: сначала доказывается, что находясь в одном из «предпоследних положений» можно попасть в «последнее» (выигрышное), затем — что из некоторого множества «предпредпоследних» можно попасть только в «предпоследнее» и так далее, пока не докажем, что «предпред…предпоследнее» положение является начальным.
3. если в игре с двумя участниками доказать невозможность выигрышной стратегии одного из участников, значит второй выиграет.
Пример:
Имеется прямоугольный стол каждый из двух игроков по очереди кладет на стол манету. Проигрывает тот, кому некуда положить монету (кол-во монет не ограничено, все монеты равные).
Решение: 1-ый кладет монету в центр прямоугольника, тогда при любом выборе 2-го игрока 1-ый всегда найдет место куда положить монету. Выигрывает при такой игре 1-ый.
|
|
|
Принцип Дирихле.
При решении задач на док-ва часто пользуются принципом дирихле. в самой простой форме его можно сформулировать так:"нельзя посадить 3 кролика в 2 клетки так, чтобы в каждой клетке находилось не более 1 кролика".
В общем виде:"Если в n клетках сидят не меньше n+1 кроликов, то найдется клетка в которой сидит не меньше двух кроликов. Если же в 3-х клетках сидят 2 кролика, то хотя бы 1 клетка пуста".
Роль клеток и кроликов могут выполнять разные объекты. Главное понять что в задаче кролики, а что клетки.
Общий принцип Дирихле
Если в n-клетках сидит не менее kn+1 – кроликов, найдется клетка в которой сидят хотя бы k+1 кроликов.
Задача 1. В мешке лежат шарики 2-х разных цветов (много белых и много черных). Какое наименьшее количество шариков надо на ощупь вынуть из мешка, чтобы среди них заведомо оказались два одного цвета.
Решение: 3 шарика. Это - просто применение принципа Дирихле: кроликами будут взятые шарики, а клетками - черный и белый цвета. Клеток две, поэтому если кроликов хотя бы три, то какие-то два попадут в одну клетку (будет 2 одноцветных шарика). С другой стороны, взять два шарика мало, потому что они могут быть двух разных цветов.
Дата добавления: 2018-05-13; просмотров: 790; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!