Задача “Отбор в разведку” (Рекуррентное соотношение с одним параметром)

Условие задачи: ссылка
Основная идея:  Обозначим K(N) – ответ на задачу, а именно количество групп из 3 человек, которых можно послать в разведку из первоначальных N человек. Определим терминальное условие: K(1) = 0; K(2) = 0; K(3) = 1. Теперь рассмотрим шеренгу солдат для N=6 и N=7. Пусть N будет равно 6. Занумеруем солдат слева направо в порядке возрастания:

Полная шеренга(N=6):	1 2 3 4 5 6
Только четные:	2 4 6
Только нечетные:	1 3 5

Полная шеренга (N=7)	1 2 3 4 5 6 7
Только четные:	2 4 6
Только нечетные:	1 3 5 7

Вывод можно сделать однозначный. Если N-четное, то K(N) = K(N/2) + K(N/2) = 2*K(N/2).  В качестве первого слагаемого была шеренга, составленная из четных солдат, в качестве второго – из нечетных. Т.е. K(6) = 2*K(3) = 2*1 = 2.
Если N-нечетное, то можно формулу можно записать так: K(N) = K(N/2) + K(N-N/2). Слагаемые такие же и в первом случае. Т.е. K(7)= K(3) + K(4) = K(3) + K(2) + K(2) = 1 + 0 + 0 = 1.
Справедливости ради стоит заметить, что формула полученная для нечетного N также работает и для четного N.
Исходный код: здесь