Семинар Доом. Применение графов к решению логических задач.
(Новая: Основой применения графов для решения логических задач служит выявление и последовательное исклю...) |
|||
| (не показаны 2 промежуточные версии 1 участника) | |||
| Строка 1: | Строка 1: | ||
| − | + | [[участник: Болонина Людмила Александровна, 022.]] | |
| − | + | ||
| − | + | ||
Основой применения графов для решения логических задач служит выявление и последовательное исключение логических возможностей, задаваемых условиями задач. Это выявление и исключение логических возможностей часто может быть истолковано с помощью построения и рассмотрения соответствующих графов. | Основой применения графов для решения логических задач служит выявление и последовательное исключение логических возможностей, задаваемых условиями задач. Это выявление и исключение логических возможностей часто может быть истолковано с помощью построения и рассмотрения соответствующих графов. | ||
| Строка 12: | Строка 10: | ||
Если в данной задаче ребро графа будет соответствовать месту, занимаемому тем или иным человеком, то нам могут представиться следующие возможности. | Если в данной задаче ребро графа будет соответствовать месту, занимаемому тем или иным человеком, то нам могут представиться следующие возможности. | ||
| − | + | [[Изображение:risyn1.bmp]]<br><br> | |
Рассмотрим первую возможность. Если «правдолюб» стоит слева, то рядом с ним, судя по его ответу, находится «правдолюб». У нас же стоит лжец. Рассмотрев таким образом все остальные возможности, мы придем к выводу, что расстановка «дипломат», «лжец», «правдолюб» удовлетворяет задаче. Действительно, если «правдолюб» стоит справа, то, по его ответу, рядом с ним «лжец», что выполняется. Стоящий в центре заявляет, что он «дипломат», и следовательно, лжет, а стоящий справа также лжет. Таким образом все условия задачи выполнены. В качестве задачи второго типа можно предложить следующую. | Рассмотрим первую возможность. Если «правдолюб» стоит слева, то рядом с ним, судя по его ответу, находится «правдолюб». У нас же стоит лжец. Рассмотрев таким образом все остальные возможности, мы придем к выводу, что расстановка «дипломат», «лжец», «правдолюб» удовлетворяет задаче. Действительно, если «правдолюб» стоит справа, то, по его ответу, рядом с ним «лжец», что выполняется. Стоящий в центре заявляет, что он «дипломат», и следовательно, лжет, а стоящий справа также лжет. Таким образом все условия задачи выполнены. В качестве задачи второго типа можно предложить следующую. | ||
| Строка 22: | Строка 20: | ||
Составим граф: | Составим граф: | ||
| − | |||
| + | [[Изображение:risyn2.bmp]]<br><br> | ||
| − | + | '''Ответ:''' №1-Г; №2-А или №2-Б; №3-Д; №4-В; №5-Б или №5-А | |
Возникает вопрос: так ли уж нужны были графы в этой задаче? Разве нельзя прийти к решению логическим путем? Можно, но графы придали условия наглядность, упростили решение. | Возникает вопрос: так ли уж нужны были графы в этой задаче? Разве нельзя прийти к решению логическим путем? Можно, но графы придали условия наглядность, упростили решение. | ||
| Строка 31: | Строка 29: | ||
В обеденный перерыв предприниматели разговорились, кто сколько газет читает. Выяснилось, что каждый выписывает и читает две и только две газеты, каждую газету читают пять человек, и любая комбинация читается одним человеком. Сколько названий газет выписывают предприниматели? Сколько всего было человек? | В обеденный перерыв предприниматели разговорились, кто сколько газет читает. Выяснилось, что каждый выписывает и читает две и только две газеты, каждую газету читают пять человек, и любая комбинация читается одним человеком. Сколько названий газет выписывают предприниматели? Сколько всего было человек? | ||
| − | |||
| − | |||
| − | |||
'''Решение:''' | '''Решение:''' | ||
| + | |||
| + | [[Изображение:risyn3.bmp]]<br><br> | ||
Решение этой задачи достигается построением следующего графа, где каждая вершина обозначает соответствующую газету и соответственно 5 подписчиков, а каждое ребро будет соответствовать одному подписчику. | Решение этой задачи достигается построением следующего графа, где каждая вершина обозначает соответствующую газету и соответственно 5 подписчиков, а каждое ребро будет соответствовать одному подписчику. | ||
| Строка 43: | Строка 40: | ||
Полезно решать логические задачи разными методами. Например, следующую задачу можно решить способом логических квадратов и с помощью графов. | Полезно решать логические задачи разными методами. Например, следующую задачу можно решить способом логических квадратов и с помощью графов. | ||
| − | '''Задача | + | '''Задача 4.''' |
Три ученицы - Аня, Валя. Катя - участвовали в новогоднем бале - маскараде. Одна из них была в красном костюме, другая - в белом, третья - в синем. Если сказать, что Аня была в красном, Валя – не в красном, и Катя –не в синем, то одно из этих утверждений будет верным, а два других –неверными. В каком костюме была каждая из учениц? | Три ученицы - Аня, Валя. Катя - участвовали в новогоднем бале - маскараде. Одна из них была в красном костюме, другая - в белом, третья - в синем. Если сказать, что Аня была в красном, Валя – не в красном, и Катя –не в синем, то одно из этих утверждений будет верным, а два других –неверными. В каком костюме была каждая из учениц? | ||
| − | |||
'''Решение:''' | '''Решение:''' | ||
| Строка 57: | Строка 53: | ||
Синее 1 0 0 | Синее 1 0 0 | ||
| − | Графы для этой задачи имеют вид. | + | Графы для этой задачи имеют вид. |
| + | |||
| + | [[Изображение:risyn4.bmp]]<br><br> | ||
| + | |||
И в том, и в другом случае получаем ответ: Валя была в красном платье, Катя – в белом и Аня - в синем. | И в том, и в другом случае получаем ответ: Валя была в красном платье, Катя – в белом и Аня - в синем. | ||
Ребята оценивают достоинства и недостатки каждого из этих способов. | Ребята оценивают достоинства и недостатки каждого из этих способов. | ||
| + | |||
| + | [[Категория:Проект ДООМ 2007-2008 (1 цикл)]] | ||
Текущая версия на 15:11, 10 января 2008
участник: Болонина Людмила Александровна, 022.
Основой применения графов для решения логических задач служит выявление и последовательное исключение логических возможностей, задаваемых условиями задач. Это выявление и исключение логических возможностей часто может быть истолковано с помощью построения и рассмотрения соответствующих графов.
Задача 1.
Из трех человек, стоящих рядом, один всегда говорит правду (правдивый), другой всегда лжет (лжец), а третий, смотря по обстоятельствам, говорит правду или ложь («дипломат»). У стоящего слева спросили: «Кто стоит рядом с тобой?» Он ответил: «Правдолюб». Стоящему в центре, задали вопрос: «Кто ты?», и он ответил: «Я дипломат». Когда у стоящего справа спросили: «Кто стоит рядом с тобой?», он ответил: «Лжец». Кто где стоял?
Решение:
Если в данной задаче ребро графа будет соответствовать месту, занимаемому тем или иным человеком, то нам могут представиться следующие возможности.
Файл:Risyn1.bmp
Рассмотрим первую возможность. Если «правдолюб» стоит слева, то рядом с ним, судя по его ответу, находится «правдолюб». У нас же стоит лжец. Рассмотрев таким образом все остальные возможности, мы придем к выводу, что расстановка «дипломат», «лжец», «правдолюб» удовлетворяет задаче. Действительно, если «правдолюб» стоит справа, то, по его ответу, рядом с ним «лжец», что выполняется. Стоящий в центре заявляет, что он «дипломат», и следовательно, лжет, а стоящий справа также лжет. Таким образом все условия задачи выполнены. В качестве задачи второго типа можно предложить следующую.
Задача 2.
В пяти корзинах лежали яблоки пяти разных сортов. Яблоки первого сорта лежат в корзинах Г и Д; яблоки второго сорта - в корзинах А. Б, Г; в корзинах А, Б, В имеются яблоки пятого сорта, в корзине В имеются к тому же яблоки четвертого сорта, а в корзине Д-третьего. Пронумеруйте каждую корзину так, чтобы в корзине №1 были яблоки первого сорта (хотя бы одно); в корзине № 2-второго и т.д.
Решение:
Составим граф:
Ответ: №1-Г; №2-А или №2-Б; №3-Д; №4-В; №5-Б или №5-А
Возникает вопрос: так ли уж нужны были графы в этой задаче? Разве нельзя прийти к решению логическим путем? Можно, но графы придали условия наглядность, упростили решение.
Задача 3.
В обеденный перерыв предприниматели разговорились, кто сколько газет читает. Выяснилось, что каждый выписывает и читает две и только две газеты, каждую газету читают пять человек, и любая комбинация читается одним человеком. Сколько названий газет выписывают предприниматели? Сколько всего было человек?
Решение:
Решение этой задачи достигается построением следующего графа, где каждая вершина обозначает соответствующую газету и соответственно 5 подписчиков, а каждое ребро будет соответствовать одному подписчику. Суть метода решения этой и подобных ей задач состоит в установлении связей между множеством вершин и множеством ребер графа. Следовательно, в данной задаче предприниматели выписывают шесть наименований газет. Всего предпринимателей: 6*(6-1)/2=15 чел. Полезно решать логические задачи разными методами. Например, следующую задачу можно решить способом логических квадратов и с помощью графов.
Задача 4.
Три ученицы - Аня, Валя. Катя - участвовали в новогоднем бале - маскараде. Одна из них была в красном костюме, другая - в белом, третья - в синем. Если сказать, что Аня была в красном, Валя – не в красном, и Катя –не в синем, то одно из этих утверждений будет верным, а два других –неверными. В каком костюме была каждая из учениц?
Решение:
Логический квадрат для этого случая имеет вид:
Аня Валя Катя Красное 0 1 0 Белое 0 0 1 Синее 1 0 0
Графы для этой задачи имеют вид.
И в том, и в другом случае получаем ответ: Валя была в красном платье, Катя – в белом и Аня - в синем.
Ребята оценивают достоинства и недостатки каждого из этих способов.
