Решение задачи №87 от UniLecs

formation.hs

-- Решение напрямую
data Variant = Chosen | Skipped
    deriving (Eq)

type Row = [Variant]

isValid :: Row -> Bool
isValid [] = True
isValid (x:[]) = True
isValid (x:y:ys) = ((x, y) /= (Chosen, Chosen)) && (isValid (y:ys))

isNoChoose :: Row -> Bool
isNoChoose = all (== Skipped)

seed :: [Row]
seed = [[]]

expandRow :: Row -> [Row]
expandRow x = [Chosen:x, Skipped:x]

rows = iterate (concatMap expandRow) seed

countCorrect = length . filter id . map (\x -> isValid x && (not . isNoChoose) x)

-- Бесконечный список ответов
values = map countCorrect $ rows

answer n = values !! n

-- Решение по формуле
fibs = 0:1:zipWith (+) fibs (tail fibs)

values' = map (\x -> x - 1) . drop 2 $ fibs

answer' n = values' !! n

-- Вспомогательные функции для тестирования
assert cond =
    if cond
    then return ()
    else error "Assertion violated"
    
assertEq x y =
    if x == y
    then return ()
    else error $ "Assertion violated: first argument is " ++ show x ++ " but second argument is " ++ show y
    
assertEq' = uncurry assertEq

testThreshold = 20

main = do
    -- Тесты избранных вариантов
    assertEq' (answer  1, 1)
    assertEq' (answer  2, 2)
    assertEq' (answer  3, 4)
    assertEq' (answer' 1, 1)
    assertEq' (answer' 2, 2)
    assertEq' (answer' 3, 4)
    -- Проверка того, что первые testTreshold ответов,
    -- полученные разными способами, совпадают
    mapM_ assertEq' . take testThreshold $ zip values values'
    print "All tests passed"

Обоснование:
Назовём строку длины n из 0 и 1 правильной, если в ней нет двух идущих подряд 1. Легко доказать, что любая непрерывная подпоследовательность правильной последовательности сама является правильной, из чего следует, что невозможно из неправильной последовательности получить правильную приписыванием числа.
Обозначим через right(n) число правильных последовательностей длины n.
Теорема 1: для всех неотрицательных n справедливо right(n) = F(n+2), где F(n) — n-ое число Фибоначчи.
Доказательство: для небольших n значения right(n) можно подсчитать непосредственно:

right(1) = 2 = F(1 + 2) {0, 1}
right(2) = 3 = F(2 + 2) {00, 01, 10}

Допустим, нам известно значение right(k - 2) и right(k - 1). Найдём, исходя из этого, right(k).
Рассмотрим множество всех правильных последовательностей длины k - 1. Из каждой последовательности этого множества можно получить правильную последовательность, приписав к концу цифру, не совпадающую с последней. Этот вариант даёт нам right(k - 1) последовательностей. Приписать же цифру, совпадающую с последней, можно только в том случае, если последняя цифра 0. Условие окончания правильной последовательности на 0 не налагает никаких дополнительных ограничений на последовательность, поэтому этот вариант даёт нам right(k - 1 - 1) = right(k - 2) последовательностей. Т. к. рассматриваемые варианты взаимно исключают друг друга и исчерпывают все возможности получения правильных последовательностей длины k, получаем

right(k)
= right(k - 1) + right(k - 2)
= F(k - 1 + 2) + F(k - 2 + 2)
= F(k + 1) + F(k)
= F(k + 2)

Используя принцип математической индукции, доказываем требуемое для всех неотрицательных n. ◼

Обозначим через answer(n) ответ на вопрос задачи, т. е. количество способов выбрать из шеренги в n человек нескольких так, чтобы среди них не было стоящих рядом.
Теорема 2: для любого натурального n справедливо answer(n) = F(n + 2) - 1.
Доказательство: для каждого подобного выбора, где n > 0, можно построить последовательность из 1 и 0, где i-тая цифра равна 1, если человек под этим номером выбран, и 0, если верно противное. Из условия задачи следует, что соответствующая последовательность является правильной. Таким образом, существует инъективное отображение из множества выборов во множество правильных последовательностей. Обратное не верно — для последовательности, состоящей из одних нулей, нет прообраза во множестве выборов, поэтому answer(n) = right(n) - 1. Используя теорему 1, получаем answer(n) = F(n + 2) - 1.
Для n = 0, очевидно, число выборов равно нулю, но
F(0 + 2) - 1 = 1 - 1 = 0
Т. о., получаем, что формула из условия теоремы верна для любых натуральных n. ◼