3

我想我有一个很简单的问题。我有这个问题，可以用递归函数很容易地解决，但我无法迭代地解决。

假设您有任何布尔矩阵，例如：

男：

111011111110
110111111100
001111111101
100111111101
110011111001
111111110011
111111100111
111110001111

我知道这不是一个普通的布尔矩阵，但它对我的示例很有用。你可以注意到那里有某种零路径......

我想创建一个函数来接收这个矩阵和一个存储零的点，并将同一区域中的每个零转换为 2（假设矩阵可以存储任何整数，即使它最初是布尔值）

（就像在 Paint 或任何图像编辑器中绘制区域时一样）

假设我用这个矩阵 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);
   }
}

这不是简单的尾递归（不止一个递归调用），因此您必须添加某种堆栈结构来处理中间内存。一个版本看起来像这样（伪代码，java-esque，再次，没有边界检查）：

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

伪代码：

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 回答
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

并非所有递归算法都可以转换为迭代算法。通常只有具有单个分支的线性算法可以。这意味着具有两个或多个分支的树算法和具有更多路径的 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

如您所见，有两条路径（左和右）。可以将这些路径之一转换为迭代，但要将另一个转换为迭代，您需要保留可以使用堆栈完成的状态：

迭代（带堆栈）：

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 回答
0

如果迭代执行比性能更重要，我会使用以下算法：

  1. 设置初始 2
  2. 扫描矩阵以在 2 附近找到 0
  3. 如果找到这样的 0，请将其更改为 2，然后在步骤 2 中重新开始扫描。

这很容易理解并且不需要堆栈，但是非常耗时。

于 2009-01-19T10:58:14.487 回答
0

迭代地执行此操作的一种简单方法是使用队列。

  1. 将起点插入队列
  2. 从队列中获取第一个元素
  3. 设置为 2
  4. 将所有仍为 0 的邻居放入队列
  5. 如果队列不为空，则跳转到 2。
于 2009-02-03T22:27:31.700 回答