[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Решение_задачи_Эйнштейна.



Задача Эйнштейна: правильное проведение границ.

(Данный текст иллюстрирует проведение границ на
примере задачи Эйнштейна о пяти жильцах.
Слово "правильно" здесь - "то как я понимаю".)

Задача такая:

В пяти домах живут пять жильцов. Все имеют разную
национальность, курят разные сигареты, пьют разные
напитки, держат разных животных.

Дополнительно известно, что:

1) Англичанин живет в красном доме,
2) Швед держит собаку,
3) Датчанин пьет чай,
4) Зеленый дом стоит слева от белого,
5) Жилец зеленого дома пьет кофе,
6) Человек, который курит PallMall, держит птицу,
7) Жилец среднего дома пьет молоко,
8) Жилец из желтого дома курит Dunhill,
9) Норвежец живет в первом доме,
10) Курильщик Marlboro живет около того, кто держит
кошку,
11) Человек, который содержит лошадь, живет около
того, кто курит Dunhill,
12) Курильщик Winfield пьет пиво,
13) Норвежец живет около голубого дома,
14) Немец курит Rothmans,
15) Курильщик Marlboro живет по соседству с человеком,
который пьет воду.

Нужно определить, кто держит дома рыбу.

Для начала приведу свое первое решение, а потом
объясню, чем оно, с моей точки зрения, плохо, несмотря
на правильный ответ.

Для начала определим, в каком порядке стоят дома:
9,13 => 2-й дом голубой, (*)
5,7 => средний дом не зеленый,

Итого: 2-й дом голубой, 4-й дом зеленый, 5-й белый.
1 => 3-й дом красный.
Значит, 1-й дом желтый.

Теперь будем рисовать таблицу. В таблице 5 столбцов:
для пяти параметров (национальность, цвет+номер,
сигареты, напиток, животное)
Очень удобно использовать для этой цели электронные
таблицы (типа Excel - привет, Глеб ! ;-b)

Просматривая условия, будем добавлять новые строки в
таблицу.
Например:
"1) Англичанин живет в красном доме"
Добавляем строку, и в соответствующие графы
пишем "Англичанин" и
"Красный(N3)"

"2) Швед держит собаку"
Добавляем строку, пишем "Швед", "Собака", "Не красный
(N3)"

В первую строку пишем - "Не собака"

И так далее.
Перед тем как начать обрабатывать новый пункт, нужно
выжать все из имеющихся.
(каждый раз строить "транзитивное замыкание" таблицы).
Комментарии типа "рядом с кошкой" можно писать в
дополнительный столбец, а можно - в подходящюю графу:
в данном случае "животное".

Если одна строка логически следует из другой (является
подмножеством), то ее можно убрать.
Если две графы (кроме дополнительных) в разных строках
совпадают, строки можно объединить.
Будут моменты, когда методом исключения можно
заполнить графу.
Таким образом, число строк будет уменьшаться, пока не
станет равным 5.

Получится, что рыбу держит немец, который живет в
зеленом доме, курит Rothmans и пьет кофе.


Получив ответ, я был доволен, и теперь мне стыдно.
Решение получилось корявым, неоднородным (сначала
определять порядок, потом рисовать таблицу) и чересчур
конкретным: при других данных решать придется по-
другому.

Главный вопрос: ну, хорошо, я догадался упорядочить
цвета...
А почему не национальности? Не животных? Просто
повезло: удачно сработал стереотип.

Следовательно, хоть и получен ответ, но задача как
класс не решена.
Причиной тому - неправильно проведенные границы.
Иначе - алгоритм решения был бы сразу очевиден, его бы
не приходилось вытягивать интуицией.

Неправильность заключается в следующей посылке:
"Нужно распределить пять параметров по пяти позициям."

На самом деле параметров 6. Шестой параметр - это
номер. Именно это в данном случае и есть границы -
правильно определить распределяемые аргументы.

Теперь ясно, как НУЖНО решать задачу: столбцов будет
6, а порядок решения - тот же самый.


Home | Date Index | Thread Index | Author Index

Klein-by Mailing List Archive
October 2001