Пример 1
Алгоритм вычисления функции F(n)
задан следующими соотношениями:
F(n) = n при n ≤ 3
F(n) = F(n–3) + F(n/3) + n, если n > 3 и кратно трём,
F(n) = F(n–1) + F(n–2), если n > 3 и не кратно трём.
Чему равно значение функции F(50) + F(65)
?
Знак / обозначает
операцию целочисленного деления.
Решить данное задание проще всего с использованием программы. Необходимо просто переписать данное рекуррентное соотношение в виде рекурсивной функции.
Базовым случаем является случай, когда
n ≤ 3
, в этом случае функция должна вернуть просто значение
n
.
Две другие строчки: вычисляющие
F(n)
, будут рекурсивными случаями, когда мы будем вызывать саму функцию с другими параметрами, зависящими от предыдущих и возвращать результат вычисления.
Основная программа будет вызывать рекурсивную функцию со значением
F(50)
и
F(65)
. Результаты вычисления функции с этими параметрами складываются и выводится на экран.