c++ - 用 d&c 方法求解方程

Question

我想用分治法计算这个等式中 x 的值到小数点后 4 位。输入 p、q、r、s、t、u 的值。如何做到？

时间限制:1 秒

内存限制:64 MB

float results[10000];
int n = 0;
for( float step = 0; i < 1; i+=0.00001 )
{
    results[n] = callProblem( i );
}
some divide and conquer approach

float x = 0;
float diff = 1;//Startvalue
while( )
{
    result = callProblem(x);
    if( result > 0 )
    {
        x -= diff;
        diff = diff/2;
        result = callProblem(x);
    }
    else
    {
        x += diff;
        diff = diff/2;
        result = callProblem(x);
    }
}

Answer 1

我已经将二分法概括为一个未经测试的递归多分法:

#include <math.h>
#include <stdio.h>
#include <time.h>

#define P 1.0
#define q 2.0
#define r 3.0
#define s 1.0
#define t 5.0
#define u -6.0

//  number of sub-intervals in search interval
#define INTERVALS 10
//  accuracy limit for recursion
#define EPSILON 1.0e-4

double f(double x) {
     double y = P * exp(-x) + q*sin(x) + r*cos(x) + s*tan(x) + t*x*x + u;

     return y;
}

//  sign macro: -1 for val < 0, +1 for val > 0
#define SGN(val) ((0.0 < val) - (val < 0.0))

//  return approximate x for function(x)==0.0
//  "function" points to the function to be solved
double solve(double xMin, double xMax, double (*function)(double)) {
     double arguments[INTERVALS + 1];
     double values[INTERVALS + 1];
     int prevSign;
     int sign;

     if (fabs(xMax - xMin) < EPSILON) {
        //  interval quite tight already
        return (xMax + xMin) / 2.0;
     }

     //  split the interval into sub-intervals
     //  evaluate the function for INTERVALS+1 equidistant points
     //  across our search interval
     for (int i = 0; i <= INTERVALS; i++) {
         double x = xMin + i*((xMax - xMin) / INTERVALS);

        arguments[i] = x;
        values[i] = function(x);
     }

    //  look for adjacent intervals with opposite function value signs
    //  if f(Xi) and f(Xi+1) have different signs, the root must be
    //  between Xi and Xi+1
    prevSign = SGN(values[0]);
    for (int i = 1; i <= INTERVALS; i++) {
        sign = SGN(values[i]);

        if (sign * prevSign == -1) {
            //  different signs! There must be a solution
            //  Shrink search interval to the detected sub-interval
            double x = solve(arguments[i - 1], arguments[i], function);

            return x;
        }
        //  remember sign for next round
        prevSign = sign;
    }

    //  no solution found: return not-a-number
    return NAN;
  }

int main(unsigned argc, char **argv) {   
    clock_t started = clock();
    clock_t stopped;
    double x = solve(0.0, 1.0, &f);

    if (isnan(x)) {
        printf("\nSorry! No solution found.\n");
    } else {
        printf("\nOK! Solution found at f(%f)=%f\n", x, f(x));
    }

    stopped = clock();
    printf("\nElapsed: %gs", (stopped - started) / (double)CLOCKS_PER_SEC);

    //  wait for user input
    getchar();
 }