黑马程序员技术交流社区

标题: 用栈将该递归程序转换成非递归程序： [打印本页]

---

作者: zhaoqiqi    时间: 2014-4-5 19:19
标题: 用栈将该递归程序转换成非递归程序：
已知如下一个递归程序，该程序的目的是输出给定字符的所有排列，请分析该程序的递归过程，然后将其用人工栈进行模拟，也就是将该递归程序转换成非递归程序：
public static void main(String[] args )
{
char myString[]={'a','b','c','d'};
permutation(myString,0,3);
}

public static void permutation(char[] list,int low,int high){
if(low==high){
  System.out.println(list);
  return ;
}
else{
  for(int i=low;i<=high;i++)
  {
   char temp=list[low];
   list[low]=list[i];
   list[i]=temp;
   permutation(list,low+1,high);
   temp=list[low];
   list[low]=list[i];
   list[i]=temp;
  }
}
}

---

作者: hyace    时间: 2014-4-6 12:25
非递归方法通常就是对递归方法的栈模拟。比如输出n个字符，可以将任务分成n个子任务。任务0：将0位和0位字符交换，之后产生一个新的子任务，就是1到n-1位字符的全排列；任务1，将0位和1位字符交换，之后产生一个新的子任务，就是2到n-1位字符的全排列，以此类推，直到第n-2个子任务，是将n-1位的一个元素全排列。每个子任务完成后要将两个元素再交换回来。可以设置一个任务栈，专门存放每个任务的状态，其中有三个成员，i：当前位，j：欲交换位，n：第几次出栈。每个任务会出两次栈，第一次处理该任务，判断是否输出，是否产生新的子任务。第二次交换回来位置。

1. import java.util.*;
   
2. 
   
3. public class StackTest {
   
4. 
   
5.         /**
   
6.          * @param args
   
7.          */
   
8.         public static void main(String[] args) {
   
9.                 List<Character> list = new ArrayList<Character>();
   
10.                 list.add('a');
    
11.                 list.add('b');
    
12.                 list.add('c');
    
13.                 list.add('d');
    
14.                 permutation(list);
    
15. 
    
16.         }
    
17. 
    
18.         public static void permutation(List<Character> list) {
    
19.                 Stack<State> stack = new Stack<State>();
    
20.                 int l = list.size();
    
21.                 State temp = new State(0, 0, 0);
    
22.                 for (int i = 0; i < l; i++)
    
23.                 // 初始化栈，l个任务
    
24.                         stack.push(new State(0, i, 0));
    
25.                         // 栈空则结束
    
26.                 while (!stack.isEmpty()) {
    
27.                         // 弹出一个当前任务
    
28.                         temp = stack.pop();
    
29.                         // 如果已排到最后队尾，则打印当前数组
    
30.                         if (temp.i == l - 1)
    
31.                                 System.out.println(list);
    
32.                         // 否则分解子任务
    
33.                         else {
    
34.                         //交换队列元素
    
35.                                 Collections.swap(list, temp.i, temp.j);
    
36.                                 if (temp.n == 0) {
    
37.                                         temp.n += 1;
    
38.                                         stack.push(temp);
    
39.                                         int k=temp.i+1;
    
40.                                         for (int x =k; x < l; ++x)
    
41.                                                 stack.push(new State(k, x, 0));
    
42.                                 }
    
43.                         }
    
44. 
    
45.                 }
    
46.         }
    
47. }
    
48. 
    
49. class State {
    
50.         public int i;
    
51.         public int j;
    
52.         public int n;
    
53. 
    
54.         public State(int i, int j, int n) {
    
55.                 this.i = i;
    
56.                 this.j = j;
    
57.                 this.n = n;
    
58.         }
    
59. }

复制代码

---

作者: zhaoqiqi    时间: 2014-4-10 12:41


已经解决了，谢谢你的回答

---

作者: zhaoqiqi    时间: 2014-4-10 12:46

hyace 发表于 2014-4-6 12:25
非递归方法通常就是对递归方法的栈模拟。比如输出n个字符，可以将任务分成n个子任务。任务0：将0位和0位字 ...

已经解决了，谢谢你的回答

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2