2

私はSchemeにかなり慣れておらず、宿題の一部として関数を書くのに苦労しています。次の形式のリストとしてグラフGが提供されています：（（node1 node2 weight1）（node3 node4 weight2）...）。このグラフのすべてのノード（V）のリストを次の形式で返す関数を作成しようとしています：（node1 node2 node3 ...）。この関数は、グラフ（G）のみを入力として受け取ることができます。

したがって、G内のネストされた各リストの最初と2番目の要素をVに追加することで、これを再帰的に実行できると思いました。これが私が書いたものです。

    (define nodes-of
      (lambda (G)
        (if (null? G) 
            ()
            (begin (add-to-set (cadar G) (nodes-of (cdr G))) 
                   (add-to-set (caar G) (nodes-of (cdr G))))))

ただし、これは間違っていると思います。最初の再帰には（cadar G）のみが含まれ、2番目の再帰には（caar G）が含まれ、戻り値はbeginの下の2番目のステートメントによってのみ設定されます（私が間違っていない場合）。

add-to-setは、宿題のために以前に作成した関数です。リストに要素がまだ存在しない場合は、リストに要素を追加します。（例：add-to-set n S、これによりnがSに追加されます）

誰かがこれを手伝ってくれますか？（ところで、複数のlet's、let *、またはsetを使用することは許可されていません）

4

1 に答える 1

3

そうですね、再帰的に実行できるというのは正しいです。コードはかなり近いものです。すべての再帰手順には、答えがわかっている基本状態と、再帰のたびに問題の複雑さを軽減する方法が必要であることを思い出してください。

リストを処理する場合、基本ケースは空のリストです。そのため、null をチェックする必要があります。次に、リダクション式はリストの一部を分割し、残りの部分でプロシージャを呼び出します。だから、私が言ったように、あなたは近いです。

次に、データは規則的に構造化されているため、グラフを通常のリストとして扱うことができることに注意してください。リストのすべての要素に再帰する必要はありません。すべての要素に対して 2 つのアクションを実行し、結果をリストに入れたいだけです。

(define nodes-of
    (lambda (G)
        (if (null? G)   ;<-- have we reached the base case yet?
            '()         ;<-- if yes, return null so our cons will build a list
            (cons (caar G) (cons (cadar G) (nodes-of (cdr G))))))) ;<-- if not, keep building the list by grabbing the things we want from each element, then reducing the list

必要に応じて、を使用することもできletます。

(define nodes-of
    (lambda (G)
        (if (null? G)
             '()
             (let ((n1 (caar G))
                   (n2 (cadar G)))
               (cons n1 (cons n2 (nodes-of (cdr G))))))))

あなたの場合add-to-set、私が使用した場所を使用しconsます。基本ケースに到達すると、すべての呼び出しをadd-to-set最後の呼び出しから評価して、スタックを最初の呼び出しに戻すことができます。

|cons n3 '()           | 2    => (n3)
|cons n2 [result of 2] | 1    => (n2 n3)
|cons n1 [result of 1] | 0    => (n1 n2 n3)
于 2012-05-13T18:16:43.200 に答える