Рубрики

Алгоритмы | Рекурсия | Вопрос 8

Предсказать вывод следующей программы

#include <stdio.h>

int f(int n)

{

    if(n <= 1)

        return 1;

    if(n%2 == 0)

        return f(n/2);

    return f(n/2) + f(n/2+1);

}

  

  

int main()

{

    printf("%d", f(11));

    return 0;

}

(A) Переполнение стека
(Б) 3
(С) 4
(D) 5

Ответ: (Д)
Пояснение: При последовательной рекурсии F (11) будет разложен на
F (5) + F (6) -> F (2) + F (3) + F (3)
-> F (1) + 2 * [F (1) + F (2)] -> 1 + 2 * [1 + F (1)]
-> 1 + 2 * (1 + 1) -> 5.

Следовательно, вариант D является правильным ответом, т. Е. 5.
Тест на этот вопрос

Рекомендуемые посты:

Алгоритмы | Рекурсия | Вопрос 8

0.00 (0%) 0 votes