version itérative de l'algorithme récursif facile

Question

J'ai une question assez simple, je pense. J'ai ce problème, qui peut être résolu très facilement avec une fonction récursive, mais que je n'ai pas pu résoudre itérativement.

Supposons que vous ayez une matrice booléenne, comme:

M:

111011111110 
110111111100 
001111111101 
100111111101 
110011111001 
111111110011 
111111100111 
111110001111 

je sais que ce n'est pas une matrice booléenne ordinaire, mais il est utile pour mon exemple. Vous pouvez noter qu'il ya une sorte de zéros là-dedans ...

Je veux faire une fonction qui reçoit cette matrice et un point où un zéro est stocké et qui transforme chaque zéro dans la même zone en 2 (supposons que la matrice peut stocker tout entier même est d'abord booléenne)

(tout comme lorsque vous peignez une zone dans Paint ou tout autre éditeur d'image)

suppose que j'appelle la fonction avec cette matrice M et la coordonnée le coin supérieur droit zéro, le résultat serait:

111011111112 
110111111122 
001111111121 
100111111121 
110011111221 
111111112211 
111111122111 
111112221111 

bien, ma question est de savoir comment faire cette itérativement ... espoir que je ne l'ai pas gâcher trop

Merci à l'avance!

Manuel

ps: Je vous en serais reconnaissant si vous pouviez montrer la fonction en C, S, python, ou pseudo-code, s'il vous plaît: D

Answer 1

Pseudo-code:

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) 

Answer 2

Pour cela, j'utiliserais un objet Stack ou Queue. Ceci est mon pseudo-code (python-like):

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) 

Answer 3

La meilleure façon de convertir une fonction récursive en une fonction itérative est d'utiliser la structure de données de pile pour stocker les données au lieu de stocker sur le appel empiler en appelant récursivement.

Code Pseudo:

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*/) 

Answer 4

Il est une technique standard pour la conversion de certains types d'algorithmes récursifs dans les itératives. Il est appelé tail-recursion.

La version récursif de ce code ressemblerait (code de pseudo - sans vérification de limites):

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); 
    } 
} 

Ce n'est pas simple queue récursif (plus d'un appel récursif) de sorte que vous devez ajouter une sorte de structure de pile pour gérer la mémoire intermédiaire. Une version ressemblerait à ceci (pseudo code, java-esque, encore une fois, aucune vérification de limites):

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));    
     }   
    } 
} 

Answer 5

ne sont pas tous les algorithmes récursifs peuvent être convertis en un algorithme itératif. Normalement, seuls les algorithmes linéaires avec une seule branche peuvent.Cela signifie que les algorithmes d'arbre qui ont deux ou plusieurs branches et des algorithmes 2d avec plus de chemins sont extrêmement difficiles à transférer en récursif sans utiliser une pile (qui consiste à tricher).

Exemple:

récursive:

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

Iteration:

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

Recursion:

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

itération partielle (essayer):

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 

Comme vous le voyez, il y a deux chemins (gauche et droite). Il est possible de transformer un de ces chemins dans l'itération, mais pour traduire l'autre dans l'itération vous devez préserver l'état qui peut être fait en utilisant une pile:

Iteration (avec pile):

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 

Cela fonctionne, mais un algorithme récursif est beaucoup plus facile à comprendre.

Answer 6

Si vous le faites est itérativement plus important que la performance, je voudrais utiliser l'algorithme suivant:

1. Régler la première 2
2. Analyser la matrice pour trouver un 0 à proximité d'un 2
3. Si une telle 0 est trouvé, modifiez-le à 2 et relancez l'analyse à l'étape 2.

Ceci est facile à comprendre et ne nécessite aucune pile, mais prend beaucoup de temps.

Answer 7

Une façon simple de le faire est d'utiliser une file d'attente de manière itérative.

1. insert point de départ dans la file
2. obtenir premier élément de la file
3. ensemble à 2
4. mettre tous les voisins qui sont toujours 0 dans la file d'attente
5. si la file d'attente n'est pas vide saut à 2.