6

我想知道是否有一种简单的算法来重新排列简单的符号代数表达式。理想情况下，我希望能够在左侧仅使用一个变量来重写任何此类表达式。例如，给定输入：

m = (x + y) / 2

...我希望能够x根据mandy或y根据xand来询问m，并得到这些：

x = 2*m - y
y = 2*m - x

当然，多年来我们都在纸上完成了这个算法。但我想知道它是否有名字。这似乎很简单，但如果有人已经对各种“陷阱”进行了分类，那会让生活更轻松。

出于我的目的，我不需要它来处理二次方程。

（是的，CAS 系统可以做到这一点，是的，我知道我可以将它们用作库。我想在我的应用程序中避免这种依赖关系。我真的很想知道是否有命名算法来解决这个问题.)

4

4 回答 4

2

似乎您感兴趣的是维护一个线性方程组，然后在任何时候都能够根据所有其他变量求解一个变量。如果您将关系编码为矩阵，那么您似乎可以将矩阵简化为某种不错的形式（例如，简化的行梯形形式）以获得变量之间“最简单”的依赖关系（对于“最简单”的一些很好的定义。 ") 一旦你有了这样的数据，你应该能够通过查看某个行的相关变量的非零条目来读取所有依赖关系，然后对其进行归一化，使变量的系数为 1。

注意 - 通常，您不会总是为每个变量获得唯一的解决方案。例如，给定平凡的方程

x = y
x = z

然后求解 z 可能会产生“z = x”或“z = y”，具体取决于您想要多少简化。或者，在类似的设置中

x = 2y + 3w
x = 9z

返回 x 的值可以返回任何一个表达式，或者它们的总和超过 2，或者一大堆其他在技术上都是正确但不一定有用的东西。我不确定你会如何处理这个问题，但根据你的方程的形式，你可能会找到一种处理它的方法。

于 2011-01-02T09:29:17.543 回答
2

你想要的是方程求解算法。但我敢打赌，这是一个巨大的话题。一般情况下，可能有：

  • 方程组
  • 方程可能是非线性的，因此需要额外的算法，例如方程分解。
  • 需要知道如何反转函数，例如 => sin(x) + 10 = z，求解 x 我们反转 sin()，即 arcsin()。（并非所有功能都是可逆的！）
  • 最后，即使对于 CAS，某些方程也可能难以求解，例如 sin(x)+x=y求解 x。

硬的答案是——你最好的办法是获取一些 CAS 的源代码——例如，你可以看看用 LISP 编写的 MAXIMA CAS 源代码。并找到负责方程求解的代码。

简单的答案 - 如果您只需要求解线性且仅由基本运算符 +-*/ 组成的方程。那么你已经知道答案了——使用旧的好纸方法——想想我们在纸上使用了什么规则，然后将这些规则重写为操作方程字符串的符号算法。

祝你好运 ！

于 2011-01-02T21:12:45.097 回答
1

将您的表达式转换为反向波兰表示法的数据结构（树）。你的树由节点组成，每个节点都有一个操作，一个左和一个右。左右各可以是一个符号（例如：“x”）或另一个节点。例如：

(x + (a + b))

会成为：

(+ x (+ a b))

或者在 JSON 中：

["+", "x", ["+", "a", "b"]]

您的原始表达式m = (x + y) / 2如下所示：

m = ["/", ["+", "x", "y"], "2"]

您想要的表达式之一（求解 x）如下所示：

x = ["-", ["*", "m", "2"], "y"]

你能看到表达式树已经被翻过来并且每个运算符都被颠倒了吗？“-”是“+”的反面，现在包裹着“*”，它是“/”的反面。这：

["+", "x", "y"]

变成：

["-", (something), "y"]

where (something) 是外部表达式的递归反转。尝试解释该过程：a）递归地降低表达式树，直到找到包含要求解的符号的节点，b）创建一个包含此节点操作反向的新节点，c）替换您想要的符号用反向的外部表达式求解，当你向外前进时递归地这样做。

于 2021-03-03T23:04:53.197 回答
0

有多种简单的方法可以修改初始方程，以正确的顺序执行正确的修改将导致正确的解。那么如何将其视为搜索甚至寻路问题呢？

于 2011-09-05T12:33:30.487 回答