Дистанционная подготовка: Задача №111837. Количество вызовов функции Фиббоначи
Задача №111837. Количество вызовов функции Фиббоначи
от Павел Войтович - Воскресенье 23 Ноябрь 2014, 01:22
111837. Количество вызовов функции Фиббоначи
  Как вообще решить эту задачу?
Не могу понять логики, перепробовал многие варианты. В учебнике - ни намёка на верное решение.
"Используйте оптимизированный вариант" - всё, что там сказано.
Помогите кто-нибудь понять, чего хочет автор.
Re: Задача №111837. Количество вызовов функции Фиббоначи
от Peter Cherepanov - Воскресенье 23 Ноябрь 2014, 02:17
  Начнем с количества вызовов рекурсивной функции.
Для вычисления F(0) функцию надо вызвать 1 раз.
Для вычисления F(1) функцию надо вызвать 1 раз.
Эти числа представляют базис индукции.

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

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

А не получится, есть очень быстрый матричный способ вычисления числа Фиббоначи, описанный, например, в Википедии.
Re: Задача №111837. Количество вызовов функции Фиббоначи
от Peter Cherepanov - Воскресенье 23 Ноябрь 2014, 05:19
  Я попробовал реализовать то, что насоветовал (посылка 1867-4222) и ничего не получилось.
Число вызовов рекурсивной функции = k*F(n), где к - небольшое число.
Ответ из примера для n=100 мне не получить. У меня выходит много больше.

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

Уложиться по времени тоже не получилось. На Питоне со всеми трюками у меня получается около 4 секунд. Дома - 1.8 секунды.
Re: Задача №111837. Количество вызовов функции Фиббоначи
от Павел Войтович - Суббота 29 Ноябрь 2014, 14:18
  Решал на Java, т.к. на этот язык ориентирован курс от 1С. Но разными вариантами к решению прийти не удалось. Числа намного больше (в принципе, получались те же ответы, то и у других решавших эту задачу).
Пробовал менять формулы, применять коэффициенты, вобщем, хотя бы как-то логически прийти к решению. Особенно, на последних тестах, где ответ почти равен N / 2. Иногда вместо 2 получается 1,99..., иногда 2,01..., но всегда разное значение.
Если кто-нибудь из моих школьников найдёт способ решения этой задачи, сразу же выложу решение.

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