Консультации

Задача №111837. Количество вызовов функции Фиббоначи

Задача №111837. Количество вызовов функции Фиббоначи

от Павел Войтович -
Number of replies: 3
Как вообще решить эту задачу?
Не могу понять логики, перепробовал многие варианты. В учебнике - ни намёка на верное решение.
"Используйте оптимизированный вариант" - всё, что там сказано.
Помогите кто-нибудь понять, чего хочет автор.
In reply to Павел Войтович

Re: Задача №111837. Количество вызовов функции Фиббоначи

от Peter Cherepanov -
Начнем с количества вызовов рекурсивной функции.
Для вычисления F(0) функцию надо вызвать 1 раз.
Для вычисления F(1) функцию надо вызвать 1 раз.
Эти числа представляют базис индукции.

Для вычисления F(n), рекурсивная функция должна быть вызваной сама и вычислить F(n-1) и F(n-2). Вопрос, как связана полученная последовательность с числами Фиббоначи?

Вычислять числа Фиббоначи можно методом динамического программирования. Этого может оказаться достаточно, чтобы уложиться в ограничения во времени. Нужно только исползовать быстрый язык программирования и написать эффективную длинную арифметику.

А не получится, есть очень быстрый матричный способ вычисления числа Фиббоначи, описанный, например, в Википедии.
In reply to Peter Cherepanov

Re: Задача №111837. Количество вызовов функции Фиббоначи

от Peter Cherepanov -
Я попробовал реализовать то, что насоветовал (посылка 1867-4222) и ничего не получилось.
Число вызовов рекурсивной функции = k*F(n), где к - небольшое число.
Ответ из примера для n=100 мне не получить. У меня выходит много больше.

Вообще, никто эту задачу пока не решил.

Уложиться по времени тоже не получилось. На Питоне со всеми трюками у меня получается около 4 секунд. Дома - 1.8 секунды.
In reply to Peter Cherepanov

Re: Задача №111837. Количество вызовов функции Фиббоначи

от Павел Войтович -
Решал на Java, т.к. на этот язык ориентирован курс от 1С. Но разными вариантами к решению прийти не удалось. Числа намного больше (в принципе, получались те же ответы, то и у других решавших эту задачу).
Пробовал менять формулы, применять коэффициенты, вобщем, хотя бы как-то логически прийти к решению. Особенно, на последних тестах, где ответ почти равен N / 2. Иногда вместо 2 получается 1,99..., иногда 2,01..., но всегда разное значение.
Если кто-нибудь из моих школьников найдёт способ решения этой задачи, сразу же выложу решение.

Самое интересное, что в учебнике нет конкретной наводки к правильному решению, что должно было означать, то задача элементарна.