Task 87. Построение

Задача: дети на уроке физкультуры стоят в шеренге. Необходимо посчитать кол-во способов, ктр можно выбрать несколько человек так, чтобы среди них не было стоящих в шеренге рядом.

Входные данные: N - кол-во детей в шернге.

Вывод: кол-во способов.

Пример:

N = 1; Answer = 1;

N = 2; Answer = 2;

N = 3; Answer = 4;

Идея: давайте обозначим за f(n) - кол-во способов для n детей. Очевидно, что 

f(1) = 1, f(2) = 2 : частные случаи, один из ребят выходит в шеренгу, т.е. шеренга состоит из 1го человека.

По сути нам нужно получить рекурентное соотношение используя частные случаи. Рассмотрим след.способы выхода в шеренгу для n:

• выходит в шеренгу n-й, а все остаются на месте.
• выходит n-й, тогда (n-1)-й должен остаться на месте. Дальше мы рассматриваем случай для (n-2) детей.
• n-й остается на месте. Тогда рекурсивно решаем задачу для (n-1) детей.

 В итоге получим след.соотношение:

 f(n) = f(n-1) + f(n-2) + 1

 f(2) = 2

 f(1) = 1

Реализация:

https://gist.github.com/unilecs/ed74ad45f9db71e0597355488969499e

Test:

https://dotnetfiddle.net/cYsyU6