3

非常に単純な質問があると思います。この問題は、再帰関数で非常に簡単に解決できますが、繰り返し解決することはできませんでした。

次のようなブール行列があるとします。

母：

111011111110
110111111100
001111111101
100111111101
110011111001
111111110011
111111100111
111110001111

これが通常のブール行列ではないことはわかっていますが、私の例では役に立ちます。そこには一種のゼロパスがあることに注意してください...

このマトリックスとゼロが格納されているポイントを受け取り、同じ領域内のすべてのゼロを 2 に変換する関数を作成したい (マトリックスは、最初はブール値であっても任意の整数を格納できると仮定します)

(ペイントやその他の画像エディターでゾーンをペイントするときと同じように)

この行列 M と右上隅のゼロの座標で関数を呼び出すと、結果は次のようになります。

111011111112
110111111122
001111111121
100111111121
110011111221
111111112211
111111122111
111112221111

さて、私の質問は、これを繰り返し行う方法です...あまり台無しにしないことを願っています

前もって感謝します！

マヌエル

ps: 関数を C、S、Python、または疑似コードで示していただければ幸いです:D

4

7 に答える 7

6

特定のタイプの再帰アルゴリズムを反復アルゴリズムに変換する標準的な手法があります。これは末尾再帰と呼ばれます。

このコードの再帰バージョンは次のようになります (疑似コード - 境界チェックなし):

paint(cells, i, j) {
   if(cells[i][j] == 0) {
      cells[i][j] = 2;
      paint(cells, i+1, j);
      paint(cells, i-1, j);
      paint(cells, i, j+1);
      paint(cells, i, j-1);
   }
}

これは単純な末尾再帰 (複数の再帰呼び出し) ではないため、中間メモリを処理するために何らかのスタック構造を追加する必要があります。1 つのバージョンは次のようになります (疑似コード、Java 風、境界チェックなし):

paint(cells, i, j) {
    Stack todo = new Stack();
    todo.push((i,j))
    while(!todo.isEmpty()) {
       (r, c) = todo.pop();
       if(cells[r][c] == 0) {
          cells[r][c] = 2;
          todo.push((r+1, c));
          todo.push((r-1, c));
          todo.push((r, c+1));
          todo.push((r, c-1));              
       }          
    }
}
于 2009-01-19T09:13:20.080 に答える
1

再帰関数を反復関数に変換する最も簡単な方法は、再帰的に呼び出してコール スタックにデータを格納する代わりに、スタック データ構造を利用してデータを格納することです。

擬似コード:

var s = new Stack();

s.Push( /*upper right point*/ );

while not s.Empty:

    var p = s.Pop()        
    m[ p.x ][ p.y ] = 2

    s.Push ( /*all surrounding 0 pixels*/ )
于 2009-01-19T09:10:19.227 に答える
1

すべての再帰アルゴリズムを反復アルゴリズムに変換できるわけではありません。通常、分岐が 1 つの線形アルゴリズムのみが可能です。これは、2 つ以上の分岐を持つツリー アルゴリズムと、より多くのパスを持つ 2D アルゴリズムを、スタックを使用せずに再帰的に変換するのが非常に難しいことを意味します (これは基本的に不正行為です)。

例：

再帰的:

listsum: N* -> N
listsum(n) ==
  if n=[] then 0 
          else hd n + listsum(tl n)

反復:

listsum: N* -> N
listsum(n) ==
  res = 0;
  forall i in n do
    res = res + i
  return res

再帰：

treesum: Tree -> N
treesum(t) ==
  if t=nil then 0
  else let (left, node, right) = t in
    treesum(left) + node + treesum(right)

部分的な反復 (試行):

treesum: Tree -> N
treesum(t) ==
  res = 0
  while t<>nil 
    let (left, node, right) = t in
      res = res + node + treesum(right)
      t = left
  return res

ご覧のとおり、2 つのパス (左と右) があります。これらのパスの 1 つを反復に変換することは可能ですが、他のパスを反復に変換するには、スタックを使用して実行できる状態を保持する必要があります。

反復 (スタックあり):

treesum: Tree -> N
treesum(t) ==
  res = 0

  stack.push(t)
  while not stack.isempty()
    t = stack.pop()
    while t<>nil 
      let (left, node, right) = t in
        stack.pop(right)
        res = res + node + treesum(right)
        t = left

  return res

これは機能しますが、再帰アルゴリズムの方がはるかに理解しやすいです。

于 2009-01-19T09:19:16.010 に答える
1

擬似コード:

Input: Startpoint (x,y), Array[w][h], Fillcolor f

Array[x][y] = f
bool hasChanged = false;
repeat
  for every Array[x][y] with value f:
    check if the surrounding pixels are 0, if so:
      Change them from 0 to f
      hasChanged = true
until (not hasChanged)
于 2009-01-19T09:04:04.717 に答える
1

これには、Stack ou Queue オブジェクトを使用します。これは私の擬似コードです（pythonのような）：

stack.push(p0)
while stack.size() > 0:
    p = stack.pop()
    matrix[p] = 2
    for each point in Arround(p):
       if matrix[point]==0:
          stack.push(point)
于 2009-01-19T09:10:05.030 に答える
0

これを繰り返し行う簡単な方法は、キューを使用することです。

  1. 開始点をキューに挿入する
  2. キューから最初の要素を取得する
  3. 2に設定
  4. まだ 0 であるすべてのネイバーをキューに入れる
  5. キューが空でない場合は 2 にジャンプします。
于 2009-02-03T22:27:31.700 に答える
0

繰り返し実行することがパフォーマンスよりも重要である場合、次のアルゴリズムを使用します。

  1. イニシャル2をセット
  2. 行列をスキャンして、2 の近くにある 0 を見つけます
  3. そのような 0 が見つかった場合は、それを 2 に変更し、ステップ 2 でスキャンを再開します。

これは理解しやすく、スタックも必要ありませんが、非常に時間がかかります。

于 2009-01-19T10:58:14.487 に答える