Шешімі: Рекурсивное вычисление функции
Алгоритм вычисления значения функции $F(n)$, где $n$ — целое неотрицательное число, задан следующими соотношениями: $F(n)=0$ при $n\leq 1$; $F(n)=2\cdot F(n-1)+2$, если $n>1$ и $n$ нечётно; $F(n)=n/2+F(n-1)$, если $n>1$ и $n$ чётно. Чему равно значение функции $F(28)$?
При вычислении значения $F(n)$ используется операция целочисленного деления.
Шешімін қадамдап көрсету
4 қадамНачальные значения: $F(0)=F(1)=0$. Последовательно применяем рекуррентные формулы.
$$F(2)=1$$Для нечётных аргументов значение удваивается и увеличивается на 2, для чётных прибавляется половина аргумента. После последовательного вычисления получаем:
$$F(24)=12272,\quad F(25)=2\cdot12272+2=24546$$Вычисляем следующие значения:
$$F(26)=13+24546=24559,\quad F(27)=2\cdot24559+2=49120$$Число $28$ чётное, поэтому:
$$F(28)=\frac{28}{2}+F(27)=14+49120=49134$$Где здесь ошибаются
Использование формулы для нечётного числа при вычислении $F(28)$.
Забывают прибавить $n/2$ при чётном значении $n$.
Начинают рекурсию с неверного базового значения вместо $F(0)=F(1)=0$.