0

次のような単純な線形方程式を解く方法はありますか

 -x+3 = x+5

二分探索を使用していますか？または他の数値的方法？

背景:私の質問は、 、、およびのような
方程式を解きたいためです。"2x+5-(3x+2)=x+5"*-+brackets

まず、方程式の両辺を中置表記に変換してから、ある種の二分探索を実行することを考えました。

このアプローチについてどう思いますか？面接で 40 分以内にこれを解決することになっています。

4

4 に答える 4

1

  1. $-x+3 -(x+5) = 0$ またはその他の同様の式を、累積定数 $a$ および $b に対して代数的に $a*x + b = 0$ に解く単純なパーサーを作成することは難しくありません。 $. 次に、正確な解を $x = -b/a$ と簡単に計算できます。

  2. 本当に数値的なアプローチが必要な場合は、両側が独自の線形関数グラフを記述していることに注意してください。つまり、左側が $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 に向かって遠ざかったり、0 に近づきます。これで、さらなる点 $x$ を数値的にテストするために必要なすべてが揃いました (たとえば、正の $y$ 差を達成するいくつかの $x$ と、負の $y$ 差を達成し、それらの間で二分探索を実行します) 差 $y_l - y_r$ が $0$ である $x$ 値を概算します。

したがって、数値的なアプローチはここでは非常にばかげていますが、このアルゴリズム的な考え方の動機となっています。

于 2013-03-08T20:28:29.977 に答える
0

二分探索が必要なら、実装は簡単です（しかし、それはとても哀れです、笑）

現在xのバイナリ検索では、方程式の左部分と右部分を解析して計算します。次に、left > right式に応じて検索範囲を変更します。

これは、すべてを左の部分 (現在は右の部分が 0 に等しい) に移動し、x < 0すべてを で乗算すると、簡単に取得できます-1。そして、明らかに、電流を伴うこの式が である場合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 に答える
-1

まず、質問はSolving Binary Treeに関連している必要があります。使用できる方法は、バイナリを作成して、ルートを最も優先度の高い演算子に置き、次に優先度の低い演算子と操作をリーフ ノードにすることです。この方法については、方程式を解くことで学ぶことができます。

于 2013-03-08T20:20:11.903 に答える