вопрос рекурсии (2-я квадратура)

Итак, у меня есть программа, которая реализует адаптивное 2D трапециевидное правило для функции x ^ 2 + y ^ 2 < 1, но кажется, что рекурсия не работает — программа здесь представляет собой модифицированную форму (рабочего) трапециевидного 1D-метода, поэтому я не уверен, где код ломается, он должен возвращать PI:

double trapezoidal(d_fp_d f,
double a, double b,
double c, double d) { //helper function
return 0.25*(b-a)*(d-c)*
(f(a, c)+f(a, d) +
f(b, c)+f(b, d));
}

double atrap( double a, double b, double c, double d, d_fp_d f, double tol )
{// helper function

return atrap1(a, b, c, d, f, tol );
}
double atrap1( double a, double b, double c, double d, d_fp_d f, double tol)
{
//implements 2D trap rule
static int level = 0;
const static int minLevel = 4;
const static int maxLevel = 30;
++level;
double m1 = (a + b)/2.0;
double m2 = (c + d)/2.0;
double coarse = trapezoidal(f,a,b,c,d);
double fine =
trapezoidal(f, a, m1, c, m2)
+ trapezoidal(f, a, m1, m2, d)
+ trapezoidal(f, m1, b, c, m2)
+ trapezoidal(f, m1, b, m2, d);
++fnEvals;
if( level< minLevel
|| ( abs( fine - coarse ) > 3.0*tol && level < maxLevel ) ){

fine =  atrap1( a, m1, c, m2, f,tol/4.0)
+ atrap1( a, m1, m2, d, f, tol/4.0)
+ atrap1(m1, b, c, m2, f, tol/4.0)
+ atrap1(m1, b, m2, d, f,tol/4.0);

}

--level;
return fine;
}

где функция определяется как

double ucircle( double x, double y)
{
return x*x + y*y < 1 ? 1.0 : 0.0;
}

и моя основная функция

int main()
{
double a, b, c, d;
cout << "Enter a: " <<endl;
cin >> a;
cout << "Enter b: " <<endl;
cin >> b;
cout << "Enter c: " <<endl;
cin >> c;
cout << "Enter d: " <<endl;
cin >> d;

cout << "The approximate integral is: " << atrap( a, b, c, d, ucircle, 1.0e-5) << endl;

return 0;
}

0

Решение

На самом деле он не будет работать вечно, но на самом деле он будет работать очень долго, так как вы думаете, что он работает вечно, и в этом причина: в первом запуске level один и функция введите ваш if и он называет себя 4 раза, теперь рассмотрим первый раз: это также введите if и вызовите себя еще 4 раза и продолжите … для правильно выбранного ввода, такого как указанный вами, условие abs(fine - coarse) всегда true так что единственное, что может остановить поступление потока в if является level это будет увеличиваться, а затем уменьшаться, так что ваша функция будет вызываться почти 4^30 и это действительно большое число, которое вы не можете увидеть его конец через час или 2!

1

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

Как уже писал BigBoss, ваша программа должна завершиться, это займет много времени, так как 30 рекурсий означают 4^30 вызовы функций для atrap1, который 1152921504606846976, Просто позвольте этому числу войти.

Вот еще несколько вещей, чтобы рассмотреть:

  • Вы, вероятно, хотели использовать fabs вместо abs в «состоянии разрыва». (Я думаю, вы должны получить предупреждение для целочисленного преобразования — или что-то подобное — для этого) abs может вернуть непредсказуемые значения для float или же double параметры. Очень высокие значения.

  • tol кажется, переменная, которая представляет целевое значение точности. Однако с каждой рекурсией вы еще больше увеличиваете точность цели. На 10-й рекурсии речь идет уже о 1E-11, Не уверен, что это предназначено. Без разницы tol средства.

    Вы, вероятно, не хотите /4.0 ( .0 кстати избыточно) в ваших рекурсивных вызовах.

  • Вы компилируете это с оптимизацией, верно?

  • trapezoidal, minLevel, maxLevel может быть макросами.

  • Ваша функция не любит многопоточное выполнение из-за level быть статичным Вы должны сделать это параметром для atrap1,

0

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