1

方程式を微分してリストとして画面に出力する関数があります。今作りたいのは、'(+ (* x 0) (* 2 1)) のように返される式を取り、答えを単純化する関数です。x*0 は常にゼロに評価され、2*1 を 2 に置き換え、2 + 0 は 2 であるため、最終的には 2 のみを返すため、x*0 を取り除きます。始めていただければ幸いです。

(define (simplify expr)
  (if (not (list? expr))
      expr
      (if (null? (cdr expr)) 
          (car expr)
          (case (car expr)
           ((+
               ))

       ))
4

2 に答える 2

3

演算子として '* および '+ を使用した 2 項式があると仮定すると、単純化される式の再帰的降下を使用して代数の基本ルールをエンコードするのは簡単です。そのとおり：

(define (simplify exp)
 (cond ((number? exp) exp)
       ((symbol? exp) exp)
       ((list?   exp)
        (assert (= 3 (length exp)))
        (let ((operator  (list-ref exp 0))
              (operand-1 (simplify (list-ref exp 1)))   ; recurse
              (operand-2 (simplify (list-ref exp 2))))  ; recurse
          (case operator
            ((+)
             (cond ((and (number? operand-1) (= 0 operand-1)) operand-2)
                   ((and (number? operand-2) (= 0 operand-2)) operand-1)
                   ((and (number? operand-1) (number? operand-2)) 
                    (+ operand-1 operand-2))
                   (else `(,operator ,operand-1 ,operand-2))))

            ((*)
             (cond ((and (number? operand-1) (= 0 operand-1)) 0)
                   ((and (number? operand-2) (= 0 operand-2)) 0)
                   ((and (number? operand-1) (= 1 operand-1)) operand-2)
                   ((and (number? operand-2) (= 1 operand-2)) operand-1)
                   ((and (number? operand-1) (number? operand-2)) 
                    (* operand-1 operand-2))
                   (else `(,operator ,operand-1 ,operand-2))))
            (else 'unknown-operator))))
       (else 'unknown-expression)))

これは、式に対して 1 つのパスのみを実行します。通常、結果が変わらなくなるまでパスを実行する必要があります。

于 2013-03-28T14:31:05.037 に答える
3

この種の問題の一般的な解決策はそれほど単純ではありません。手始めに、書き換えルールの使用について考え、記事A Hacker's Introduction to Partial Evaluation のsimplifyセクション 4 に示されている手順を見てください。

We can use rewrite rules to simplify algebraic expressions. For example,

> (simplify '(+ (* 3 x) (* x 3)))
; (* 6 x)

This works by applying a list of rules to all parts of the subject expression
repeatedly until no more simplifications are possible:

(define *simplification-rules*
  '(((+ ?x ?x)          (* 2 ?x))
    ((* ?s ?n)          (* ?n ?s))
    ((* ?n (* ?m ?x))   (* (* ?n ?m) ?x))
    ((* ?x (* ?n ?y))   (* ?n (* ?x ?y)))
    ((* (* ?n ?x) ?y)   (* ?n (* ?x ?y)))))

The left hand column has patterns to match, while the right hand holds responses. 
The first rule says, if you see (+ foo foo), rewrite it into (* 2 foo). Variables 
like ?x can match anything, while ?m and ?n can only match numbers.
于 2013-03-28T13:39:13.350 に答える