我正在嘗試構建一個函式，我可以將它作為引數給出一個數學運算式，例如“x**3 bx-c”，然后通過牛頓方法回傳給定函式的根。
我在思考下面這個例子，其中 'r0' 是一個非零的初始亂數，dfunc 是函式的導數。我不知道我將如何評估導數，但我想首先知道我想用運算式作為引數做什么。
double * roots (double r0, <type> func) {
double *r = alloc(100, sizeof(double));
r[0] = r0;
for (int i = 1; i <= 100; i ) {
r[i]=r[i-1]-func(r[i-1])/dfunc(r[i-1]);
};
return r;
};
uj5u.com熱心網友回復：
其他人建議使用函式點，我同意這可能是正確的解決方案，但您確實要求提供一種為函式提供運算式的方法。當然，您可以這樣做，但您必須自己實作運算式。
您可以為您想要的各種子運算式創建一個結構，它可能如下所示：
struct expr
{
int refcount; // GC; exprs share sub-expressions
enum
{
CONS, VAR, MINUS, /* unary minus */
ADD, SUB, /* binary subtraction */
MUL, /* more... */
} type;
union {
struct { double x; } cons;
struct { int idx; /* index in var vector */ } var;
struct { struct expr *x; } unary;
struct { struct expr *x, *y; } binary;
};
};
我只是在這里堅持一些簡單的。
在下面的派生代碼中，我需要在乘法規則中保留運算式（如果你實作它，你需要對鏈式規則做同樣的事情），所以我用參考計數器處理記憶體管理。
struct expr *incref(struct expr *expr)
{
expr->refcount ;
return expr;
}
void free_expr(struct expr *);
struct expr *decref(struct expr *expr)
{
expr->refcount--;
if (expr->refcount > 1)
return expr;
free_expr(expr);
return 0;
}
我回傳一個指向我修改的物件的指標，因為我需要它用于incref. 我不將它用于decref，但我更喜歡保持兩個函式的介面一致。
創建運算式實體沒有什么。您只需在其中分配和設定值。
struct expr *new_const(double x)
{
struct expr *expr = malloc(sizeof *expr);
assert(expr); // handle alloc errors
*expr = (struct expr){.refcount = 1, .type = CONS, .cons = {x}};
return expr;
}
struct expr *new_var(int idx)
{
struct expr *expr = malloc(sizeof *expr);
assert(expr); // handle alloc errors
*expr = (struct expr){.refcount = 1, .type = VAR, .var = {idx}};
return expr;
}
struct expr *new_minus(struct expr *x)
{
struct expr *expr = malloc(sizeof *expr);
assert(expr); // handle alloc errors
*expr = (struct expr){.refcount = 1, .type = MINUS, .unary = {x}};
return expr;
}
struct expr *new_add(struct expr *x, struct expr *y)
{
struct expr *expr = malloc(sizeof *expr);
assert(expr); // handle alloc errors
*expr = (struct expr){.refcount = 1, .type = ADD, .binary = {x, y}};
return expr;
}
struct expr *new_sub(struct expr *x, struct expr *y)
{
struct expr *expr = malloc(sizeof *expr);
assert(expr); // handle alloc errors
*expr = (struct expr){.refcount = 1, .type = SUB, .binary = {x, y}};
return expr;
}
struct expr *new_mul(struct expr *x, struct expr *y)
{
struct expr *expr = malloc(sizeof *expr);
assert(expr); // handle alloc errors
*expr = (struct expr){.refcount = 1, .type = MUL, .binary = {x, y}};
return expr;
}
對于對它們起作用的函式，您可以使用switch：
void print_expr(struct expr *expr)
{
switch (expr->type)
{
case CONS:
printf("%f", expr->cons.x);
break;
case VAR:
printf("x%d", expr->var.idx);
break;
case MINUS:
printf("-(");
print_expr(expr->unary.x);
printf(")");
break;
case ADD:
printf("(");
print_expr(expr->binary.x);
printf(" ");
print_expr(expr->binary.y);
printf(")");
break;
case SUB:
printf("(");
print_expr(expr->binary.x);
printf(" - ");
print_expr(expr->binary.y);
printf(")");
break;
case MUL:
printf("(");
print_expr(expr->binary.x);
printf(" * ");
print_expr(expr->binary.y);
printf(")");
break;
/* more here ... */
}
}
使用函式指標，您可以實作多型性以避免切換，但這在這里可能有點過頭了。
如果要計算運算式，則需要為變數提供值，一個簡單的解決方案是使用陣列。這就是為什么上面的變數包含一個索引而不是一個字串或類似的。索引被解釋為變數值陣列的偏移量。
double eval_expr(struct expr *expr, double *x)
{
switch (expr->type)
{
case CONS:
return expr->cons.x;
case VAR:
return x[expr->var.idx];
case MINUS:
return -eval_expr(expr->unary.x, x);
case ADD:
return eval_expr(expr->binary.x, x) eval_expr(expr->binary.y, x);
case SUB:
return eval_expr(expr->binary.x, x) - eval_expr(expr->binary.y, x);
case MUL:
return eval_expr(expr->binary.x, x) * eval_expr(expr->binary.y, x);
/* more here ... */
}
}
為了計算導數，你根據導數規則來實作變換規則（這就是我在這里保持簡單運算式的原因；我不想為鏈式規則或除法之類的代碼撰寫代碼；我是一個非常懶惰的人）。
struct expr *derivative(struct expr *expr, int var)
{
switch (expr->type)
{
case CONS:
return new_const(0);
case VAR:
return (expr->var.idx == var) ? new_const(1) : new_const(0);
case MINUS:
return new_minus(derivative(expr->unary.x, var));
case ADD:
return new_add(derivative(expr->binary.x, var), derivative(expr->binary.y, var));
case SUB:
return new_sub(derivative(expr->binary.x, var), derivative(expr->binary.y, var));
case MUL:
return new_add(new_mul(incref(expr->binary.x), derivative(expr->binary.y, var)),
new_mul(derivative(expr->binary.x, var), incref(expr->binary.y)));
/* more here ... */
}
}
我incref在乘法規則中使用，所以我可以重用傳入的運算式并且仍然安全地釋放記憶體。釋放運算式非常簡單：
void free_expr(struct expr *expr)
{
switch (expr->type)
{
case CONS:
case VAR:
break;
case MINUS:
decref(expr->unary.x);
break;
case ADD:
case SUB:
case MUL:
decref(expr->binary.x);
decref(expr->binary.y);
break;
/* more here ... */
}
free(expr);
}
您可以像這樣使用這些運算式：
int main(void)
{
struct expr *expr =
new_mul(
new_add(
new_const(3.5),
new_minus(new_var(0))),
new_sub(new_const(1.4),
new_var(1)));
print_expr(expr);
putchar('\n');
double x[] = {2.0, 42.0}; // variables
printf("value: %f\n", eval_expr(expr, x));
struct expr *deriv = derivative(expr, 0);
printf("derivative with respect to x0:\n");
print_expr(deriv);
putchar('\n');
printf("derivative value: %f\n", eval_expr(deriv, x));
free_expr(deriv);
deriv = derivative(expr, 1);
printf("derivative with respect to x1:\n");
print_expr(deriv);
putchar('\n');
printf("derivative value: %f\n", eval_expr(deriv, x));
free_expr(deriv);
free_expr(expr);
return 0;
}
這段代碼中很可能存在錯誤，我只是快速地整理了一下，但它應該可以讓您了解如何使用運算式。
uj5u.com熱心網友回復：
鑒于 OP 的函式類似于double function(double x)，將該函式的地址傳遞給roots()。
創建一個func(x)從 2 個附近值呼叫的導數例程來確定斜率。
OP 的for回圈只迭代找到 1 個根。需要額外的代碼才能找到更多。
double在尋找一個根時也不需要分配一個陣列。足以跟蹤 currentx和 previous x。
extern func(double func(double), x);
double root(double r0, double func(double x)) {
double x =r0;
for (int i = 1; i < 100; i ) {
double better_x = x - func(x)/dfunc(func, x);
x = better_x;
};
return x;
}
// Usage
double y = root(0.0, function);
OP 對Netwon 方法的應用值得檢測零斜率、過度迭代、比簡單迭代計數更好的停止標準等。
此外，對于一般 double function(double x)（而不僅僅是多項式）找到N 1根，需要額外的代碼。
IMO，OP show 只關注多項式根并創建以下形式的函式：
complex double *polynomial_roots(size_t n, const double coefficients[n 1]);
參見Bairstow 方法。
IAC，OP 的目標多根目標非常重要。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/367312.html