Просто для удовольствия - начать с хитрой логической проблемы PHP

Question

В качестве средства повышения квалификации в качестве разработчика PHP я часто сталкиваюсь с проблемами с сайта Программирование Praxis .99% времени я могу решить загадки самостоятельно, но я застрял на этом и нуждаюсь в некотором руководстве о том, как начать.Загадка называется «Несколько жилищ».Вот проблема:

Бейкер, Купер, Флетчер, Миллер и Смит живут на разных этажах многоквартирного дома, в котором всего пять этажей.Бейкер не живет на верхнем этаже.Купер не живет на нижнем этаже.Флетчер не живет ни на верхнем, ни на нижнем этаже.Миллер живет на более высоком этаже, чем Купер.Смит не живет на полу рядом с Флетчером.Флетчер не живет на полу рядом с Купером.Где все живут?

Моя основная проблема заключается в следующем: я не понимаю, как тестировать и оценивать различные логические ситуации.Например, если мы хотим проверить, принадлежит ли Бейкер на первом этаже, как лучше всего «заполнить» тестовые позиции для каждого из 4 оставшихся людей?Все мои (многие) попытки закончились разочарованием в недрах массивных деревьев If / else if / else.

Это не домашняя работа, деньги или слава - просто загадка, которую я мог бы использовать, чтобы немного помочьНачало работы!

Обновлено - Вот мое решение!Всем спасибо за вклад, не обязательно оптимизированный, но, по крайней мере, теперь я это понимаю:

<?php

    function testThisOne ($testList) {
        $MillerFloor = "";
        $CooperFloor = "";
        $SmithFloor = "";
        $FletcherFloor = "";

        foreach ($testList as $key => $person) if ($person == "Miller") $MillerFloor = $key;
        foreach ($testList as $key => $person) if ($person == "Cooper") $CooperFloor = $key;
        foreach ($testList as $key =>$person) if ($person == "Smith") $SmithFloor = $key;
        foreach ($testList as $key => $person) if ($person == "Fletcher") $FletcherFloor = $key;

        if ($testList[4] == "Baker") return false;
        if ($testList[0] == "Cooper") return false;
        if ($testList[0] == "Fletcher" || $testList[4] == "Fletcher") return false;
        if ($MillerFloor < $CooperFloor) return false;
        if (abs($SmithFloor - $FletcherFloor) == 1 || abs($CooperFloor - $FletcherFloor) == 1) return false;

        return true;
    }

    function puzzleSolve1() {
        $people = array("Baker","Cooper","Fletcher","Miller","Smith");
        do {
            shuffle($people);
        } while (!testThisOne($people));
        return $people;
    }

?>

Answer 1

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

Поскольку вы просто хотели начать, я не собираюсь писать какой-либо реальный код, я просто обрисую способ, которым я подхожу к его решению:

1. Поскольку все жильцы живут на разных этажах, вам нужно использовать алгоритм «перестановок» для генерации всех их возможных вариантов. То есть вы начинаете с набора, подобного {1, 2, 3, 4, 5}, где каждый элемент представляет номер пола одного человека, скажем, в порядке Бейкера, Купера, Флетчера, Миллера, Смита. Вам нужно найти любую другую возможную договоренность. Алгоритм в Википедии довольно прост и должен быть прост в реализации.

2. Для каждой генерируемой вами перестановки вам необходимо проверить, все ли условия выполняются. Если какое-либо из условий ложно, прекратите тестирование и переходите к следующей перестановке. Если все условия выполнены, все готово. Все условия довольно легко проверить, например:

   «Бейкер не живет на верхнем этаже». >> $baker != 5

   «Миллер живет на более высоком этаже, чем Купер». >> $miller > $cooper

   и т. Д.

Answer 2

Итак, давайте назовем людей BCFM S.

Обычно каждый может жить где угодно, поэтому у нас есть такая стартовая ситуация:

[BCFMS] [BCFMS] [BCFMS] [BCFMS] [BCFMS]

Теперь вы говорите

Бейкер не живет на верхнем этаже.

Так что у нас будет

[BCFMS] [BCFMS] [BCFMS] [BCFMS] [CFMS]

Купер не живет на нижнем этаже.

Таким образом, мы получаем:

[BFMS] [BCFMS] [BCFMS] [BCFMS] [CFMS]

Флетчер не живет ни на верхнем, ни на нижнем этаже.

Ookay:

[BMS] [BCFMS] [BCFMS] [BCFMS] [CMS]

Миллер живет на более высоком этаже, чем Купер.

Хорошо, поэтому М не может быть на более низкой позиции, чем С:

[BS] [BCFS] [BCFMS] [BCFMS] [CMS]

А также, C не может быть на последнем этаже, потому что M должен быть над ним:

[BS] [BCFS] [BCFMS] [BCFMS] [MS]

(A): Смит не живет на полу рядом с Флетчером.

(B): Флетчер не живет на полу рядом с Купером.

Так что на соседних «ящиках» (этажах) нет SF, FS, FC или CF.

И мы также знаем, что

(C): жить на разных этажах многоквартирного дома

В соответствии с (C), у нас есть две возможные ситуации, первый этаж - B или S

Давайте рассмотрим второй случай (потому что мы знаем (A) о нем)

[S] [BCFS] [BCFMS] [BCFMS] [MS]

Согласно (A):

[S] [BC] [BCF] [BCF] [M]

Итак, мы также знаем, что M живет выше C (предыдущий шаг уже верен,как мы точно знаем, что М сейчас находится на последнем этаже):

[S] [BC] [BCF] [BCF] [M]

Согласно (B), ни F, ни C не могут находиться на 3-м этаже и под влиянием (C),в итоге мы получаем единственную возможную перестановку из-за дальнейших сокращений (только один человек на этаж):

[S] [C] [B] [F] [M]

Итак, вот решение:

Смит, Купер, Бейкер,Флетчер, Миллер

Answer 3

Полагаю, вы могли бы отформатировать этот набор линейных (в) уравнений.

B < 5
C > 1
F < 5
F > 1
M > C
|S - F| > 1
|F - C| > 1

Эти плюсы: B! = C! = F! = S! = M

Сейчаспередать это в симплексный алгоритм и все готово:)

РЕДАКТИРОВАТЬ: Но если вы хотите решить это программно, я думаю, что тестирование всех перестановок для этих условий будет гораздо проще - есть только5!из них.