2

シングルパスでプロシージャを実装することは、非再帰的であることを意味しますか？それとも、同じ情報に対して手順が2回繰り返されてはならないという意味ですか？

最初の定義だと思っていたので聞いてみましたが、再帰を使わないとわからない宿題の問題に出くわし、「1回のパスで完結」と言いました。

4

2 に答える 2

3

シングルパスとは、セットを1回だけ反復する場合です（各要素に1回だけ触れる）。

このような単純な反復でこれを達成できます

for n from 0 to set length
 interact with set item n

または、再帰することもできます（c＃）

public int total(int[] numbers,int index)
    {
     if (index == numbers.Length - 1) return numbers[index];
     return numbers[index] + total(numbers, index + 1);
    }

int[] someInts = {1,2,3,4};
int intTotal = total(someInts,0);
于 2012-10-28T22:38:45.743 に答える
3

「シングルパス」とは、要素のコレクション（リスト、配列、セット、ベクトル、マップ、ツリー、グラフ、文字列など）の各要素にアクセスすることを意味します（「反復」 over "）一度だけ-手順が再帰的であるか反復的であるかは関係ありません。たとえば、Schemeの次の再帰的プロシージャは、リスト内のすべての要素を1回のパスで追加します。

(define (sum lst)
  (if (null? lst)
      0
      (+ (car lst)
         (sum (cdr lst)))))

同じプロシージャを末尾再帰的に記述できます。つまり、再帰呼び出しが別のプロシージャ内で発生した場合、それが最後のアクションになります。戻り値が生成される場合があり、その値は呼び出し元のプロシージャによってすぐに返されます。とにかく、リスト内の要素に対して実行されるパスは1つだけです。

(define (sum lst)
  (let loop ((lst lst)
             (acc   0))
    (if (null? lst)
        acc
        (loop (cdr lst) (+ (car lst) acc)))))

上記の2つの例をJavaのこのコードと比較してください。これは反復法ですが、もう一度、配列に対して1回のパスが実行されます。

int sum(int[] array) {
    int acc = 0;
    for (int x : array)
        acc += x;
    return acc;
}
于 2012-10-28T23:32:01.997 に答える