Помогите пожалуйсто понять мне математическую суть задачи

Функция f(n) для целых неотрицательных n определена так :

f(0) = 0, f(1) = 1, f(2n) = f(n), f(2n + 1) = f(n) + f(n + 1).

Вопрос у меня конкретно следующий : Чему будет равно скажем f(4) и f(9) и как их посчитать ?

ps программы не надо, нужно именно математическое объяснение, решить потом сам попробую ;)

Функция f(n) для целых неотрицательных n определена так :

f(0) = 0, f(1) = 1, f(2n) = f(n), f(2n + 1) = f(n) + f(n + 1).

Вопрос у меня конкретно следующий : Чему будет равно f(4) и f(9) и как их посчитать ?

Ответ:

так как f(2n) = f(n), тогда f(4)=f(2), f(2)=f(1), f(1)=1, то есть f(4)=1 (1-ый вопрос);

f(2n + 1) = f(n) + f(n + 1), f(2n + 1) , тогда f(9)=f(4) + f(4 + 1)=1+f(5)=1+f(2) + f(2 + 1)=

=1+1+f(3)=1+1+f(1)+f(1+1)=1+1+1+1=4, то есть f(9)=4 (2-ой вопрос);

Если нужно более глубоко разъяснить пиши на мыло <...> или на форум.
С уважением TS

А ты в следующий раз читай Правила Форума, прежде чем отвечать!

Спасибо понял, щас сделаю функцию , выложу в задачи на проверку ..