Прямоугольники для мозаичного покрытия
У вас две головоломки. Сколько способов заполнить прямоугольник размером 1 на n, используя смесь квадратов 1 на 1 и прямоугольников 1 на 2? Сколько способов заполнить прямоугольник размером 2 на n, используя прямоугольники 1 на 2?
CHALLENGE
Почему эти две головоломки дают одинаковые ответы? Каковы ответы, когда заполняемые прямоугольники имеют длину 10? А когда их длина составляет 20?
РАЗВЕДКА
Чем похожи эти две задачи друг на друга и на предыдущие головоломки? Как изменится головоломка 1 на n, если мы будем использовать вместо фигур фигуры 1 на 1 и 1 на 3? Как изменится головоломка 1 на n, если мы будем использовать фигуры 1 на 1, 1 на 2 и 1 на 3?
Заметки
CHALLENGE
Умение применять ранее полученные результаты к части или ко всей новой задаче — очень ценный навык.
Эти две головоломки абсолютно одинаковы по своей сути. Вертикальные элементы в прямоугольнике 2 x n соответствуют элементам 1 x 1 в прямоугольнике 1 x n, а горизонтальные элементы в прямоугольнике 2 x n соответствуют элементам 1 x 2 в прямоугольнике 1 x n. Таким образом, между этими двумя головоломками нет никакой существенной разницы.
Кроме того, головоломка с прямоугольником 1хn в точности повторяет головоломку с шагами в «Фибоначчи – 2». Шаг за шагом — это как вставка квадрата 1х1, а шаг за шагом — это как вставка прямоугольника 1х2. Две головоломки одинаковы, поэтому анализ и результаты тоже одинаковы.
РАЗВЕДКА
Если мы используем прямоугольники 1 на 1 и 1 на 3, многое меняется. Посмотрите на первые несколько значений и подумайте, как они вычисляются. Первые несколько значений — это 1, 1, 2, 3, 4, 6 и 9. В общем случае следующее значение — это сумма текущего значения и значения, полученного двумя шагами ранее. Вычислить это достаточно просто, но это уже не последовательность Фибоначчи.
Если мы будем использовать последовательности 1 к 1, 1 к 2 и 1 к 3, ситуация изменится еще более кардинально. Теперь первые несколько значений будут 1, 2, 4, 7, 13 и 24. Следующее значение в последовательности — это сумма предыдущих трех значений.
Последовательности, в которых следующие члены определяются заданной формулой, включающей предыдущие члены, называются рекурсивными последовательностями. Числа Фибоначчи — не единственная рекурсивная последовательность, но, вероятно, самая известная.