математика — Рекурсивный алгоритм для разложения в ряды Тейлора Переполнение стека

Недавно я написал экзамен по информатике, где они попросили нас дать рекурсивное определение для расширения серии cos taylor. Это серия

cos (x) = 1 — x ^ 2/2! + х ^ 4/4! + х ^ 6/6! …

и подпись функции выглядит следующим образом

float cos(int n , float x)

где n представляет число в серии, которое пользователь хотел бы вычислить до, а x представляет значение x в функции cos

Я, очевидно, не правильно понял этот вопрос, и я пытался выяснить это в течение последних нескольких дней, но я ударил кирпичную стену

Кто-нибудь сможет помочь мне начать где-нибудь?

2

Решение

Все ответы до сих пор пересчитывают факториал каждый раз. Я бы точно не стал этого делать. Вместо этого вы можете написать:

float cos(int n, float x)
{
if( n > MAX )
return 1;
return 1-x*x/( (2*n-1)*2*n ) * cos(n+1, x);
}

Учтите, что cos возвращает следующее (извините за положение точек):

формула функции cos

Вы можете видеть, что это верно для n> MAX, n = MAX и так далее. Знак чередования и степени х легко увидеть.

Наконец, при n = 1 вы получите 0! = 1, так звонит cos(1, x) получает первые максимальные условия расширения Тейлора cos.

Разрабатывая (легче увидеть, когда у него мало терминов), вы можете увидеть, что первая формула эквивалентна следующей:

переформулировка, потому что формула

Для n> 0 вы делаете в cos (n-1, x) деление на (2n-3) (2n-2) предыдущего результата и умножаете на x². Вы можете видеть, что когда n = MAX + 1, эта формула равна 1, с n = MAX, то это 1-x²/((2MAX-1)2MAX) и так далее.

Если вы разрешите себе вспомогательные функции, то вы должны изменить подпись вышеупомянутого на float cos_helper(int n, float x, int MAX) и назовите это так:

float cos(int n, float x) { return cos_helper(1, x, n); }


Изменить: чтобы изменить смысл n от степени оцениваемого термина (как в этом ответе до сих пор) до количества терминов (как в вопросе и ниже), но все равно не пересчитывать суммарный факториал каждый раз, я бы предложил использовать двухчленное отношение.

Давайте определим тривиально cos(0,x) = 0 а также cos(1,x) = 1и попытаться получить в общем случае cos (n, x) сумму n первых членов ряда Тейлора.

Тогда для каждого n> 0 мы можем записать cos (n, x) из cos (n-1, x):

cos (n, x) = cos (n-1, x) + x2n / (2n)!

теперь при n> 1 мы пытаемся сделать так, чтобы последний член cos (n-1, x) появился (потому что это ближайший к тому члену, который мы хотим добавить):

cos (n, x) = cos (n-1, x) + x² / ((2n-1) 2n) * (x2n-2 / (2n-2)! )

Комбинируя эту формулу с предыдущей (адаптируя ее к n-1 вместо n):

cos (n, x) = cos (n-1, x) + x² / ((2n-1) 2n) * (cos (n-1, x) — cos (n-2, x))

Теперь у нас есть чисто рекурсивное определение cos (n, x), без вспомогательной функции, без пересчета факториала и с n числом членов в сумме разложения Тейлора.

Однако я должен подчеркнуть, что следующий код будет работать ужасно:

  • производительность, если только некоторая оптимизация не позволяет переоценить cos(n-1,x) который был оценен на предыдущем этапе как cos( (n-1) - 1, x)
  • точность, из-за эффектов отмены: точность, с которой мы получаем х2n-2 / (2n-2)! очень плохо

Теперь этот отказ от ответственности на месте, вот код:

float cos(int n, float x)
{
if( n < 2 )
return n;
float c = x * x / ( 2 * (n-1) * 2 * n );
return (1-c) * cos(n-1, x) + c * cos(n-2, x);
}
2

Другие решения

Вы можете использовать цикл или рекурсию, но я бы порекомендовал цикл. В любом случае, если вы должны использовать рекурсию, вы можете использовать что-то вроде кода ниже

#include <iostream>

using namespace std;

int fact(int n) {
if (n <= 1) return 1;
else return n*fact(n-1);
}

float Cos(int n, float x) {
if (n == 0) return 1;
return Cos(n-1, x) + (n%2 ? -1 : 1) * pow (x, 2*n) / (fact(2*n));
}

int main()
{
cout << Cos(6, 3.14/6);

}
0

Просто сделай это как сумма.

соз

Параметр n в float cos(int n , float x) это l а теперь просто сделай это …
Какой-то псевдокод:

float cos(int n , float x)
{
//the sum-part
float sum = pow(-1, n) * (pow(x, 2*n))/faculty(2*n);

if(n <= /*Some predefined maximum*/)
return sum + cos(n + 1, x);
return sum;
}
0

Обычная техника, когда вы хотите выполнить рекурсию, но аргументы функции не содержат нужной вам информации, — это ввести вспомогательная функция сделать рекурсию.

У меня сложилось впечатление, что в мире Lisp принято называть такую ​​функцию something-aux (Короче для вспомогательный), но это могло быть просто ограниченной группой в старые времена.

Во всяком случае, главная проблема здесь в том, что n представляет естественную конечную точку для рекурсии, базовый случай, и что вам также понадобится некоторый индекс, который работает до n, Итак, это хороший кандидат на дополнительный аргумент для вспомогательной функции. Другой кандидат связан с рассмотрением того, как один член ряда относится к предыдущему.

0
По вопросам рекламы [email protected]