有没有办法解决一个简单的线性方程，比如
-x+3 = x+5
使用二分查找？或任何其他数值方法？
背景：我的问题来了，
因为我想解决像"2x+5-(3x+2)=x+5"可能的运算符是：*，-和。+brackets
我首先想到将它转换为等式两边的中缀符号，然后执行某种二进制搜索。
您如何看待这种方法？我应该在面试中不到 40 分钟解决这个问题。
问问题
1755 次
4 回答
1
编写一个简单的解析器，将 $-x+3 -(x+5) = 0$ 或任何其他类似的表达式以代数方式求解为 $a*x + b = 0$ 对于累积常量 $a$ 和 $b 并不难美元。然后，可以很容易地计算出精确解为 $x = -b/a$。
如果你真的想要一个数值方法，观察两边都描述了他们自己的线性函数图，即左边的 $y_l = -x_l+3$ 和右边的 $y_r = x_r + 5$。因此，找到该方程的解与找到两个函数的交点相同。因此，您可以从任何值 $x=x_l=x_r$ 并计算两边得到对应的左右 $y$-值 $y_l$ 和 $y_r$。如果它们的差是 $0$，那么您找到了一个解决方案（幸运的唯一交点，或者两条线相等，如 $2x = 2x$）。否则，检查例如位置$x+1$。如果新的差 $y_l - y_r$ 与之前没有变化，则两条线是平行的（例如 $2x = 2x + 7$）。否则，差异会变得更远或更接近 0（从正面或负面）。所以，现在你已经拥有了对进一步的点 $x$ 进行数值测试所需的一切（例如，以二分搜索方式，如果你首先寻找一些 $x$ 实现了正的 $y$-difference 和另一个 $x$获得负的$y$-差值，然后在它们之间运行二分查找）来近似$x$-值，其中$y_l - y_r$ 的差值为$0$。
因此，数值方法在这里非常荒谬，但它激发了这种算法的思维方式。
于 2013-03-08T20:28:29.977 回答
0
如果你需要二分查找，那么它很容易实现（但它太可悲了，lol）
对于当前x的二分搜索，解析和计算方程的左右部分。然后，根据left > right表达式更改搜索范围。
这很容易获得，如果您将所有内容移到左侧（现在右侧部分等于 0），如果x < 0您将所有内容乘以-1. 然后，很明显，如果这个带有 current 的表达式x是expr > 0，那么你需要更x小，否则 - 更大。
但是……你为什么需要那个？=D
于 2013-03-08T20:36:31.527 回答
0
你真的需要用数值方法来解决它吗？我很确定你可以，但解析表达式以解析解决它并不难。我的意思是，如果它确实是一个线性方程，那么只要发现 x 的系数是多少，当方程被简化时，自由项是多少。在这个问题的 26 分钟内，我手工制作了一个简单的解析器：
import re, sys, json
TOKENS = {
'FREE': '[0-9]+',
'XTERM': '[0-9]*x',
'ADD': '\+',
'SUB': '-',
'POW': '\^',
'MUL': '\*',
'EQL': '=',
'LPAREN': '\(',
'RPAREN': '\)',
'EOF': '$'
}
class Token:
EOF = lambda p: Token('EOF', '', p)
def __init__(self, name, raw, position):
self.name = name
self.image = raw.strip()
self.raw = raw
self.position = position
class Expr:
def __init__(self, x, c):
self.x = x
self.c = c
def add(self, e):
return Expr(self.x + e.x, self.c + e.c)
def sub(self, e):
return Expr(self.x - e.x, self.c - e.c)
def mul(self, e):
return Expr(self.x * e.c + e.x * self.c, self.c * e.c)
def neg(self):
return Expr(-self.x, -self.c)
class Scanner:
def __init__(self, expr):
self.expr = expr
self.position = 0
def match(self, name):
match = re.match('^\s*'+TOKENS[name], self.expr[self.position:])
return Token(name, match.group(), self.position) if match else None
def peek(self, *allowed):
for match in map(self.match, allowed):
if match: return match
def next(self, *allowed):
token = self.peek(*TOKENS)
self.position += len(token.raw)
return token
def maybe(self, *allowed):
if self.peek(*allowed):
return self.next(*allowed)
def following(self, value, *allowed):
self.next(*allowed)
return value
def expect(self, **actions):
token = self.next(*actions.keys())
return actions[token.name](token)
def evaluate(expr, variables={}):
tokens = Scanner(expr)
def Binary(higher, **ops):
e = higher()
while tokens.peek(*ops):
e = ops[tokens.next(*ops).name](e, higher())
return e
def Equation():
left = Add()
tokens.next('EQL')
right = Add()
return left.sub(right)
def Add(): return Binary(Mul, ADD=Expr.add, SUB=Expr.sub)
def Mul(): return Binary(Neg, MUL=Expr.mul)
def Neg():
return Neg().neg() if tokens.maybe('SUB') else Primary()
def Primary():
return tokens.expect(
FREE = lambda x: Expr(0, float(x.image)),
XTERM = lambda x: Expr(float(x.image[:-1] or 1), 0),
LPAREN = lambda x: tokens.following(Add(), 'RPAREN'))
expr = tokens.following(Equation(), 'EOF')
return -expr.c / float(expr.x)
print evaluate('2+2 = x')
print evaluate('-x+3 = x+5')
print evaluate('2x+5-(3x+2)=x+5')
于 2013-03-08T20:34:29.657 回答