Мое хобби – преподавание математики и информатики школьникам. В этом процессе очень важным является вопрос мотивации, поэтому приходится очень тщательно подходить к качеству подачи материала. После перебора различных методов чтения материала, родилась идея проекта «Одна задача», в котором на примере решения всего одной задачи читается лекция с подачей разнообразного нового материала. Итак, демонстрирую первый материал данного проекта.
Задача: имеются плитки размером 1х1 и 1х2 метра. Сколько существует способов замощения этими плитками прямоугольника 1х15 метров?
Человеку без опыта решения подобных комбинаторных задач обычно непросто предложить решение данной задачи. Поэтому стоит свести ее к более простым, чтобы получить рабочую гипотезу. Давайте начнем перебирать способы замощения меньших прямоугольников.
Прямоугольник 1х1 можно замостить лишь одним способом. Прямоугольник 2х2 – двумя. Составим таблицу для более простых прямоугольников:
| Размер | Количество вариантов |
| 1х1 | 1 |
| 1х2 | 2 |
| 1х3 | 3 |
| 1х4 | 5 |
| 1х5 | 8 |
На всякий случай перечислим все варианты для прямоугольника 1х5, где цифра 1 – плитка 1х1, цифра 2 – плитка 1х2:
1. 1
2. 11 2
3. 111 12 21
4. 1111 112 121 211 22
5. 11111 1112 1121 1211 2111 122 212 221
Нетрудно заметить, что в таблице во втором столбце находятся числа Фибоначчи. Их появление явно не случайно. Давайте задумаемся, откуда они могут взяться.
Представим, что мы занимаемся замощением прямоугольника слева направо. Тогда получить прямоугольник 1xN можно добавив плитку 1х1 к прямоугольнику 1х(N-1) или же плитку 1х2 к прямоугольнику 1х(N-2). Значит, каждое замощение 1х(N-1) и 1х(N-2) соответствует одному замощению 1х(N). Если обозначить количество вариантов замощения прямоугольника 1хN за P(N), то получим формулу P(N)=P(N-1)+P(N-2), которая является формулой чисел Фибоначчи.
Давайте теперь попробуем написать программу, которая бы вычисляла числа Фибоначчи. Очевидно, что формула этих чисел рекуррентная, поэтому решим задачу двумя способами: циклом и через рекурсию.
program Project2;
{$APPTYPE CONSOLE}
uses
SysUtils;
var a: array[1..15] of integer;
i: integer;
function p(n: integer): integer;
begin
if n<3 then p:=n else p:=p(n-1)+p(n-2);
end;
begin
a[1]:=1;
a[2]:=2;
for i:=3 to 15 do a[i]:=a[i-1]+a[i-2];
writeln(a[15]);
writeln(p(15));
readln;
end.
А теперь посчитаем, сколько раз в этом алгоритме вызывается рекурсивная функция для каждого аргумента. Обозначим за p(n) количество вызовов функции p с аргументом n. Очевидно, что p(15)=1 и p(14)=1. А вот p(n)=p(n+1)+(n+2). То есть мы снова получаем всю ту же последовательность Фибоначчи. Исключением является только p(1)=p(3). Таким образом мы с Вами доказали замечательный факт: сложность рекурсивного алгоритма вычисления чисел Фибоначчи измеряется суммой чисел Фибоначчи.
Автор: ElGatoAhuecado
