АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Решение с помощью графов

Читайте также:
  1. B) подготовка, системно построенная с помощью методов-упражнений, представляющая по сути педагогический организованный процесс управления развитием спортсмена
  2. B. Любая матричная игра имеет решение, по крайней мере, в смешанных стратегиях
  3. E) Обратиться за помощью к России
  4. XVII. Укажите номера предложений в которых –ing-форма переводится на русский язык с помощью слова «будучи» и страдательного причастия.
  5. а затем полное обоснованное решение и ответ
  6. Абсолютное изменение валового сбора под влиянием изменения структуры посевных площадей рассчитывается с помощью индексов
  7. Абсолютное изменение средней урожайности под влиянием изменения структуры посевных площадей рассчитывается с помощью индексов
  8. Азотной кислоты с помощью серной кислоты
  9. Анализ взаимосвязи коэффициентов на основе методики факторного анализа прибыли Дюпон и прогноз роста с помощью соотношений
  10. Анализ электорального поведения с помощью социологии политики Пьера Бурдье.
  11. Архитектурно строительное и конструктивное решение здания
  12. Архитектурное решение улиц и проездов

Задача 1. На соревнованиях по легкой атлетике Андрей, Боря, Сережа и Володя заняли первые четыре места. Но когда девочки стали вспоминать, как эти места распределились между победителями, то мнения разошлись:

Даша: Андрей был первым, а Володя — вторым.

Галя: Андрей был вторым, а Борис — третьим.

Лена: Боря был четвертым, а Сережа — вторым.

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

Кто из мальчиков какое место занял?

Решение с помощью графов:

 
 

 

 


Вершины графа — имена мальчиков и занятые ими места. Ребра графа — высказывания девочек:

мнение Даши — жирные линии (ребра А-1 и В-2);

мнение Гали — пунктирные линии (ребра А-2 и Б-3);

мнение Лены — тонкие линии (ребра С-2 и Б-4).

Ася сказала, что каждая девочка сделала только одно правильное заявление. Значит, надо оставить только по одной линии каждого типа. Всего в графе должно остаться 3 линии разных типов.

Предположим, что истинно высказывание, обозначенное реб­ром В-2, тогда нам следует удалить из графа ребра А-1 (Даша права только в одном предположении), А-2 и С-2 (только кто-то один может занять второе место). В графе останется по одной линии каждого вида, а именно ребра В-2, Б-3 и Б-4. Но это невозможно, так как Борис не мог одновременно занять третье и четвертое места. Значит, предположение об истинности высказывания, обозначен­ного ребром В-2, было неверным.

Одно предположение Даши (ребро В-2) неверно, значит, верно ее другое предположение (ребро А-1). Следовательно, ребро А-2 следует удалить, а из этого следует, что высказывание, обозначен­ное ребром Б-3, должно быть истинным. Тогда ребро Б-4 надо удалить. Отсюда следует, что вторую тонкую линию (С-2) надо оставить.

В результате получим следующий граф, который и дает ответ задачи:

 
 

 


Ответ: первое место занял Андрей, второе — Сережа, третье — Боря, четвертое — Володя.

 

Задача 2. В начале лета школьники организовали сельскохозяйствен­ную бригаду и избрали бригадира, заместителя бригадира и звеньевых первого, второго и третьего звеньев. Их имена: Аня, Боря, Вася, Гриша и Дина. Звеньевая первого звена решила по­дружиться со звеньевой второго звена. Дина удивилась, узнав, что бригадир и звеньевая второго звена — брат и сестра. Гриша дружит с бригадиром и его заместителем. У Васи нет сестер. На­зовите должности каждого из ребят.

Решите с ис­пользованием графа.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)