tapis Sierpinski utiliser une pile au lieu de la récursivité

Question

J'ai mis en œuvre une solution pour résoudre le problème Sierpinski carpet en utilisant la récursivité. Maintenant, je veux utiliser une pile au lieu de la méthode récursive pour résoudre le tapis Sierpinski. J'essaie de traduire ma méthode récursive dans la pile, mais j'ai des problèmes quand j'appuie sur les variables de ma méthode récursive. Ceci est le morceau de code que je dois pousser et pop drawGasket(x + i * sub, y + j * sub, sub);

Lorsque vous appelez drawGasket (0, 0, 729), vous devriez voir ce qui suit à l'écran:

récursive méthode:

public void drawGasket(int x, int y, int side) { 
    int sub = side/3; 

    //Draw center square 
    g2d.fill(new Rectangle2D.Double(x + sub, y + sub, sub - 1, sub - 1)); 

    if(sub >= 3) { 
     //Draw 8 surrounding squares 
     for (int i = 0; i < 3; i++){ 
      for (int j = 0; j < 3; j++){ 
       if (j!=1 || i != 1) 
        drawGasket(x + i * sub, y + j * sub, sub); 
      } 
     } 
    } 
} 

mise en œuvre de la pile:

public void stack (int x, int y, int side){ 
    GenericStack<Integer> s = new GenericStack<>(); 

    int sub = side /3; 
    g2d.fill(new Rectangle2D.Double(x + sub, y + sub, sub - 1, sub - 1)); 

    while (!s.isEmpty()){ 
     x=s.pop(); 
     if (sub >=3){ 
      for (int i = 0; i < 3; i++){ 
       for (int j = 0; j < 3; j++){  
        if (j!=1 || i != 1){ 
         int operation = x+i*sub; 
         s.push(operation); 
         int operation2 = y+j*sub; 
         s.push(operation2); 
         s.push(sub); 
        } 
       } 
      } 
     } 
    } 
} 

My Stack Classe:

public class GenericStack<T> { 

private int size; // size 
private Node<T> head; // node head 

public GenericStack() { // constructor 
    head = null; // head is null 
    size = 0; // size is zero 
} 

public void push(T element) { 
    if(head == null) { // if head is null 
     head = new Node(element); // head is node 
    } else { 
     Node<T> newNode = new Node(element); 
     newNode.next = head; 
     head = newNode; 
    } 

    size++; 
} 

public T pop() { 
    if(head == null) 
     return null; 
    else { 
     T topData = head.data; 

     head = head.next; 
     size--; 

     return topData; 
    } 
} 

public T top() { 
    if(head != null) 
     return head.data; 
    else 
     return null; 
} 

public int size() { 
    return size; 
} 

public boolean isEmpty() { 
    return size == 0; 
} 

private class Node<T> { 
    private T data; 
    private Node<T> next; 

    public Node(T data) { 
     this.data = data; 
    } 

} 

Answer 1

Si vous pouvez imaginer la version récursive comme déjà être basée sur la pile, vous devriez être en mesure de traduire votre code correctement. Si vous pensez à tous les appels récursifs à drawGasket(x + i * sub, y + j * sub, sub); en poussant trois valeurs sur une pile, et chaque première étape "à l'intérieur" de la méthode drawGasket en retirant trois valeurs de cette pile, puis en poussant et déplaçant explicitement ces mêmes valeurs sur votre GenericStack dans un solution itérative devrait suivre le même modèle. Fondamentalement, tout comme dans la solution récursive, vous devez pousser, pousser, pousser des valeurs successives sur la pile jusqu'à ce que vous manquiez de valeurs à pousser; et puis vous devez pop, pop, pop les valeurs successives de la pile et "dessiner" un rectangle approprié pour les valeurs juste sauté jusqu'à ce que la pile est vide.