Прием моделирования с помощью графов
ОДп..04.
Информатика и ИКТ
Автомеханик
УРОК № 9
Группа: АМ-2-19
Дата: 21.10.2020 г.
Преподаватель: Л.Н.Иванова
ТЕМА УРОКА: МЕТОДЫ РЕШЕНИЯ ЛОГИЧЕСКИХ ЗАДАЧ
Цель урока: познакомиться с методами решения логических задач.
Основные методы решения логических задач:
· метод рассуждений; с помощью таблиц истинности;
· метод блок-схем;
· средствами алгебры логики (алгебры высказываний);
· графический (в том числе, «дерево логических условий», метод кругов Эйлера);
· метод математического бильярда;
· метод последовательных рассуждений;
· разновидность метода рассуждений — «с конца»; табличный способ.
Прием моделирования на полупрямой
Если в задаче имеется множество объектов и требуется установить взаимоотношение между элементами этого множества, то задачу можно решать на полупрямой.
Задача 1. На вечеринку собрались четверо друзей: Аня, Вика, Миша и Коля. Коля пришел раньше Ани, но не был первым. Определите, в какой последовательности друзья приходили к месту встречи, если Вика пришла последней.
Решение.
Построим модель описанной ситуации, считая обычный луч «линией времени». Условимся пришедшего на вечеринку раньше обозначать на полупрямой (первой буквой его имени) правее, пришедшего позже – левее. По порядку каждое условие отметим на полупрямой
|
|
|
а) Коля пришел раньше Ани:
б) Коля не был первым, то есть кто-то из друзей опередил Колю:
в) Вика пришла последней:
г) Значит, Миша пришел раньше всех: 
Ответ: Миша, Коля, Аня, Вика.
Задача 2. В очереди в школьный буфет стоят Вика, Соня, Боря, Денис и Алла. Вика стоит впереди Сони, но после Аллы; Боря и Алла не стоят рядом; Денис не находится рядом ни с Аллой, ни с Викой, ни с Борей. В каком порядке стоят ребята? (Математические олимпиады в школе. 5-11 классы / А.В. Фарков – М.: Айрис-пресс, 2008; задача № 9.11)
Решение.
а) Вика стоит впереди Сони, но после Аллы 
б) Денис не находится рядом ни с Аллой, ни с Викой, значит он – крайний слева
в) Боря и Алла не стоят рядом, Борис не находится рядом с Денисом, значит место Бориса – после Вики
Ответ: Алла, Вика, Борис, Соня, Денис.
Задача 3. При взвешивании животных в зоопарке выяснилось, что буйвол тяжелее льва, медведь легче буйвола, а рысь легче льва. Выберите утверждения, которые верны при указанных условиях.
1) Рысь тяжелее буйвола.
2) Буйвол самый тяжелый из всех этих животных.
3) Медведь тяжелее буйвола.
4) Рысь легче буйвола.
Решение.
Отметим данные задачи на полупрямой, причем с одной стороны полупрямой отметим однозначные данные, с другой стороны – неоднозначные.
|
|
|
М
М
М
Ответ: 24.
Прием моделирования с помощью таблицы
Если в процессе решения необходимо установить соответствие между элементами двух или нескольких различных множеств, то целесообразно использовать таблицу.
Задача 4. Перед соревнованиями по плаванию каждого из четырех участников А, Б, В, Г спросили, на какое место он рассчитывает. А сказал: «Я буду первым», Б сказал: «Я не буду последним», В сказал: «Я не буду ни первым, ни последним» и Г сказал: «Я буду последним». После заплыва оказалось, что только один из них ошибочно предсказал результат. Кто из пловцов ошибся?
Решение.
Составим таблицу, в которой знаком «плюс» укажем предполагаемые результаты.
| Пловец | Места | |||
| 1 | 2 | 3 | 4 | |
| А | + | |||
| Б | + | + | + | |
| В | + | + | ||
| Г | + | |||
Предположим, что ошибся А, тогда он мог занять 2-е или 3-е место (4-е место занял пловец Г, который, если ошибся А, правильно предсказал свой результат, так как по условию ошибся только один пловец).
В этом случае возможны следующие варианты распределения мест:
а) А – 2, Б – 1, В – 3, Г – 4;
б) А – 3, Б – 1, В – 2, Г – 4.
|
|
|
Докажем, что действительно ошибся пловец А. Если бы ошибся Б, т.е. занял 4-е место, то ошибся бы и пловец Г, что противоречит условию задачи. Если бы ошибся В, тогда он должен быть или первым или последним. В таком случае ошибся бы еще один пловец – А или Г. Если бы ошибся Г, то ошибся бы еще один пловец, в противном случае последнее место не занял бы никто. Так как по условию задачи мог ошибиться только один пловец, то Г не ошибся.
Ответ: ошибся пловец А.
Задача 5. В летний лагерь приехали отдыхать три друга: Миша, Володя и Петя. Известно, что каждый из них имеет одну из следующих фамилий: Иванов, Семенов, Герасимов. Миша – не Герасимов. Отец Володи – инженер. Володя учится в 6 классе, Герасимов учится в 5 классе. Отец Иванова – учитель. Какая фамилия у каждого из трех друзей?
Решение.
Начертим таблицу и заполним последний столбец таблицы, исходя из условий: Миша – не Герасимов, Володя учится в 6 классе, Герасимов – в 5 классе. Значит, Володя – не Герасимов.
| Имя | Фамилия | ||
| Иванов | Семенов | Герасимов | |
| Миша | - | ||
| Володя | - | ||
| Петя | |||
Следовательно, Герасимов – Петя. Поэтому ставим плюс на пересечении строки «Петя» со столбцом «Герасимов» и минусы – в остальных клетках строки «Петя».
|
|
|
| Имя | Фамилия | ||
| Иванов | Семенов | Герасимов | |
| Миша | - | ||
| Володя | - | ||
| Петя | - | - | + |
По условию отец Володи – инженер, отец Иванова – учитель. Значит Володя – не Иванов. Поставим минус в соответствующей клетке, увидим, что Володя – Семенов. Тогда Миша – Иванов.
| Имя | Фамилия | ||
| Иванов | Семенов | Герасимов | |
| Миша | + | - | - |
| Володя | - | + | - |
| Петя | - | - | + |
Ответ: Миша – Иванов, Володя – Семенов, Петя – Герасимов.
Задача 6. После традиционного вечера встречи с выпускниками школы в стенгазете появилась заметка о трех наших бывших учениках. В ней было сказано, что Иван, Андрей и Борис стали учителями. Теперь они преподают разные дисциплины: один из них - математику, второй – физику, а третий – химию. Живут они тоже в разных городах: Минске, Витебске, Харькове. В заметке было также написано, что их первоначальные планы осуществились не полностью:
1) Иван живет не в Минске;
2) Андрей – не в Витебске;
3) житель Минска преподает не математику;
4) Андрей преподает не физику;
5) повезло только жителю Витебска: он преподает любимую им химию.
Можно ли по этим данным определить, кто где живет и что преподает?
Решение.
По условиям задачи имеем:
| Имя | Город | Дисциплина | ||||
| Минск | Витебск | Харьков | Математика | Физика | Химия | |
| Иван | – | |||||
| Андрей | – | – | – | |||
| Борис | ||||||
Значит, Андрей преподает математику. Но математику не может преподавать житель Минска. Таким образом, Андрей – житель Харькова. Но тогда, ни Иван, ни Борис в Харькове не живут.
Отобразим наши рассуждения в таблице:
| Имя | Город | Дисциплина | |||||
| Минск | Витебск | Харьков | Математика | Физика | Химия | ||
| Иван | – | – | – | ||||
| Андрей | – | – | + | + | – | – | |
| Борис | – | – | |||||
Из таблицы видно, что Иван не живет ни в Минске, ни в Харькове. Следовательно, Иван – житель Витебска и преподает химию:
| Имя | Город | Дисциплина | |||||
| Минск | Витебск | Харьков | Математика | Физика | Химия | ||
| Иван | – | + | – | – | – | + | |
| Андрей | – | – | + | + | – | – | |
| Борис | – | – | – | – | |||
Значит, Борис – житель Минска и преподает физику. Окончательно получим:
| Имя | Город | Дисциплина | |||||
| Минск | Витебск | Харьков | Математика | Физика | химия | ||
| Иван | – | + | – | – | – | + | |
| Андрей | – | – | + | + | – | – | |
| Борис | + | – | – | – | + | – | |
Ответ: Андрей преподает математику и живет в Харькове, Борис – физику и живет в Минске, Иван – химию и является жителем Витебска.
Прием моделирования с помощью графов
Ситуации, в которых требуется найти соответствие между элементами различных множеств, можно моделировать с помощью графов. В этом случае элементы различных множеств будем обозначать точками (кружочками, прямоугольниками и т. п.), а соответствия между ними – отрезками (дугами).
Задача 7. Три товарища – Иван, Дмитрий и Степан преподают различные предметы (химию, биологию и физику) в школах Москвы, Тулы и Новгорода. О них известно следующее:
1. Иван работает не в Москве, а Дмитрий – не в Новгороде;
2. москвич преподает физику;
3. тот, кто работает в Новгороде, преподает химию;
4. Дмитрий и Степан преподают не биологию.
Какой предмет, и в каком городе преподает каждый
Решение.
В задаче можно выделить три множества: учебных предметов, городов, учителей. Каждое множество содержит по три элемента. Обозначим их точками – вершинами графа. 
В зависимости от условий задачи будем соединять точки отрезками, если имеет место соответствие между данными элементами, или пунктирной линией, если соответствия нет. Задача сводится к нахождению на графе трех сплошных треугольников с вершинами в разных множествах.
Так, используя условие 1), проведем пунктирную линию, соединяющую объекты Иван и Москва, Дмитрий и Новгород. В соответствии с условием 2) соединим сплошной линией вершины Москва и физика, а условие 3) выразим сплошной линией от точки Новгород до точки химия. По условию 4) Дмитрий и Степан преподают не биологию, соединим соответствующие вершины пунктирными линиями. 
Получается, что биологию преподает Иван. Известно, что химик живет в Новгороде, а физик – в Москве, значит, биолог живет в Туле. Проведем соответствующие сплошные линии. 
Обратим внимание на треугольник, образованный вершинами Иван, Тула, биология: в нем есть две сплошные стороны, значит, третью сторону (Иван – Тула) также можно выделить сплошной линией. В самом деле, если Иван преподает биологию, а биолог живет в Туле, то Иван живет в Туле.
Что известно про Дмитрия? Дмитрий не живет в Новгороде (по условию) и не живет в Туле (там живет Иван), значит, Дмитрий живет в Москве – проведем соответствующую сплошную линию. Но москвич преподает физику – эта линия тоже сплошная. В треугольнике с вершинами в точках Дмитрий, Москва и физика две стороны сплошные, следовательно, третью сторону тоже можно выделить сплошной линией.
Что же известно про Степана? Степан не живет в Туле (там живет Иван) и не живет в Москве (там живет Дмитрий), следовательно, Степан живет в Новгороде – проведем сплошную линию. Но тот, кто живет в Новгороде, преподает химию – эта линия тоже сплошная. Так появляется третий треугольник из сплошных линий.
Ответ: Иван преподает биологию и живет в Туле, Дмитрий – физику и живет в Москве, Степан – химию и является жителем Новгорода.
Задача 8. Однажды в туристическом лагере оказались вместе пять ребят. Их имена: Леонид, Сергей, Николай, Олег и Петр. Их фамилии: Антонов, Борисов, Васильев, Дроздов и Иванов. Кроме того, известно, что Петр знаком со всеми, кроме одного. Борисов знаком только с двумя. Леонид знает только одного из всех. Дроздов и Сергей не знакомы. Николай и Иванов хорошо знают друг друга. Сергей, Николай и Олег давно знакомы между собой. Антонов знаком только с Петром.
Попробуйте по этим сведениям узнать имена и фамилии всех мальчиков.
Решение.
Будем соединять отрезками объекты (ребят), которые знакомы между собой. По условию, что Сергей, Николай и Олег давно знакомы между собой, имеем:
Из условия: Антонов знаком только с Петром делаем вывод, что Леонид – Антонов и соединяем линией Леонида и Петра.
По условию задачи Дроздов и Сергей не знакомы. Следовательно, Петр – Дроздов.
Петр знаком со всеми, кроме одного. Выше сказано, что с Сергеем он не знаком, значит знаком с Леонидом, Николаем и Олегом.
Так как Борисов знаком только с двумя, делаем вывод: Сергей – Борисов. По условию Николай и Иванов хорошо знают друг друга, значит Олег – Иванов, Николай - Васильев.
Борисов
Васильев
Иванов
Ответ: Антонов Леонид, Борисов Сергей, Васильев Николай, Дроздов Петр, Иванов Олег.
Задача 9. 5 школьников приехали из 5 различных городов в Архангельск на областную математическую олимпиаду. «Откуда вы, ребята?» - спросили их хозяева. Вот что ответил каждый из них.
Андреев: «Я приехал из Онеги, а Григорьев живет в Каргополе».
Борисов: «В Каргополе живет Васильев. Я же прибыл из Коряжмы».
Васильев: «Я прибыл из Онеги, а Борисов – из Котласа».
Григорьев: «Я прибыл из Каргополя, а Данилов из Вельска».
Данилов: «Да, я действительно из Вельска, Андреев же живет в Коряжме».
Хозяева очень удивились противоречивости ответов приехавших гостей. Ребята объяснили им, что каждый из них высказал одно утверждение правильное, а другое ложное. Но по их ответам вполне можно установить, кто откуда приехал. Откуда приехал каждый школьник?
Решение.
Решим задачу, представив ее условие в виде графа.
Вершины графа – фамилии мальчиков и названия городов, откуда они приехали. Ребра графа – высказывания школьников:
мнение Андреева – жирные линии;
мнение Борисова – тонкие линии;
мнение Васильева – жирные пунктирные линии;
мнение Григорьева – тонкие пунктирные линии;
мнение Данилова – штрихпунктирные линии.
Так как каждый из мальчиков сделал только одно правильное заявление, то надо оставить только по одной линии каждого типа. Всего в графе должно остаться 5 линий разных типов.
Предположим, что у Андреева верно первое утверждение, то есть он из Онеги. Тогда надо удалить из графа ребра Григорьев – Каргополь (только одно утверждение Андреева верное), Андреев – Коряжма (он из Онеги), Васильев – Онега (из Онеги – Андреев). Значит, верно первое утверждение Данилова, что он из Вельска и ложно первое утверждение Григорьева, поэтому удаляем из графа ребро Григорьев – Каргополь, а также ребро Борисов – Коряжма (он из Котласа).
Итак, получилось, что Андреев из Онеги, Борисов из Котласа, Васильев из Каргополя, Данилов из Вельска, значит Григорьев из Коряжмы.
Рассмотрим второй возможный вариант. Пусть у Андреева второе утверждение правильное, тогда Григорьев приехал из Каргополя. Значит, Данилов приехал не из Вельска (ложное второе утверждение Григорьева), а Андреев не из Онеги. Тогда у Борисова первое утверждение ложное (в Каргополе живет Григорьев), значит, Борисов прибыл из Коряжмы.
Поэтому Андреев не из Коряжмы (в Коряжме живет Борисов) и получается, что верно первое высказывание Данилова – я из Вельска. Получили противоречие: Данилов из Вельска и не из Вельска. Значит, второй вариант невозможен.
Ответ: Андреев из Онеги, Борисов из Котласа, Васильев из Каргополя, Григорьев из Коряжмы, Данилов из Вельска.
Дата добавления: 2020-11-15; просмотров: 98; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!