Ряд Тейлора по методу Горнера с использованием рекурсии
Наш профессор научил нас находить ряд Тейлора с помощью рекурсии, используя статическую переменную суммирования, которая накапливает сумму каждого члена, а затем умножает сама себя на каждой итерации.
#include <stdio.h>
double t(int n,int m){
static double a = 1.0;
if (m==0)
return a;
a = 1+(double)n/m*a;
return t(n,m-1);
}
int main(){
printf("%lf\n",t(4,1500));
}
Это дает желаемую точность и результат.
Я попытался реализовать код, используя один оператор возврата:
#include <stdio.h>
double e(int x, int m){
if (m==0)
return 1.0;
return 1+((double)x/m)*e(x,m-1);
}
int main(){
printf("%lf\n",e(4,1500));
}
Это дает результат 1.002674.
Какая разница между двумя? Что заставляет этот код привести к такой неточности?
Не отмечайте это как dsa. Тег dsa предназначен для Digital Signature Algorithm.
Ответы 1
- Пункт списка
Дело не в неточности. Выражение, которое вычисляется, отличается.
Давайте заменим второй аргумент (1500) всего на 3. Итак, t(4, 3) и e(4, 3). Логика t(4, 3) вычисляет это выражение:
a = 1
a = 1 + (4 / 3) * a
a = 1 + (4 / 2) * a
a = 1 + (4 / 1) * a
Это распространяется на:
1 + (4 / 1) * (1 + (4 / 2) * (1 + (4 / 3) * 1))
= 23.66666...
а e(4, 3) рассчитывается следующим образом:
e(4, 0) = 1
e(4, 1) = 1 + (4 / 1) * e(4, 0)
e(4, 2) = 1 + (4 / 2) * e(4, 1)
e(4, 3) = 1 + (4 / 3) * e(4, 2)
который расширяется до:
1 + (4 / 3) * (1 + (4 / 2) * (1 + (4 / 1) * 1))
=15.66666...
На этом небольшом примере вы можете увидеть, как дроби вычисляются в обратном порядке. Из-за операции 1+ для каждого промежуточного результата другой порядок дает другой результат.
Возможно, важно понимать, что в первой версии переменная a достигла своего конечного значения к моменту достижения базового случая.
Коррекция
Я понимаю, что вы захотите провести рефакторинг первой функции, поскольку использование переменной static может оказаться невозможным, когда функция будет вызвана второй раз на верхнем уровне. В этом случае вы бы хотели, чтобы значение a было сброшено до 1, но это не так.
Вы можете заменить его дополнительным параметром, которому вы передаете начальное значение 1,0. Это не проблема, но вы можете опустить явное приведение к double, поставив a в качестве первого операнда выражения, которое требует деления с плавающей запятой. Я назвал функцию f:
double f_recur(int n, int m, double a) {
if (m == 0)
return a;
return f_recur(n, m - 1, 1 + a * n / m);
}
double f(int n, int m) {
return f_recur(n, m, 1.0);
}
Вы также можете сделать это итеративным способом, что предпочтительнее, поскольку не используется дополнительное пространство стека. На этот раз позвонил g:
double g(int n, int m) {
double a = 1.0;
for (int i = m; i > 0; i--) {
a = 1 + a * n / i;
}
return a;
}
C не имеет необязательных аргументов
@Шон, спасибо, я по ошибке использовал C++. Исправлено сейчас.
Исходный код обновляется
aна каждом этапе рекурсии. Ваш новый код вычисляет выражение на выходе из рекурсии.