Помогите определить рекурентное соотношение и написать функцию на с++
Вот такое задание:
Определить закономерность формирования последовательности, записать рекуррентное соотношение для n-го члена последовательности. Реализовать рекурсивную функцию вычисления n-го члена последовательности. Вычислить 7-й член последовательности. Оценить сложность алгоритма.
Сама последовательность: 1,1,2,9,737
int sequence(long int n) {
if (n == 1 || n == 2)
return 1;
return pow(sequence(n - 1), 3) + pow(sequence(n - 2), 3);
}
int main(){
long int counter = 4;
sequence(counter);
return 0;
}
Ответы (1 шт):
Хотя вопрос был написать на C++, но в цитате самого задания не говорится про язык, кроме того как оказывается 7-й элемент последовательности это 26-значное число 64151935432803278787493321, для его вычисления C++ с его стандартной библиотекой не достаточно, т.к. нужна длинная арифметика, в наибольший 64-битный uint64_t тип число не влезет.
Поэтому предлагаю решение на языке Python, т.к. он имеет встроенную целочисленную длинную арифметику, извините за несоответствие запроса на C++.
def seq(n):
if n <= 2:
return 1
return pow(seq(n - 1), 3) + pow(seq(n - 2), 3)
print(seq(7))
Вывод:
64151935432803278787493321