JAVA新手小试牛刀之遍历递归树求递推数列通项
程序员文章站
2022-07-05 12:00:40
考虑K阶变系数线性递推方程： 现给定初值a1,a2, ,ak和n>k,要求编程打印an,an-1, ,ak+1的值 该问题用常规的迭代法非常容易解决，现在要考虑的是用遍历递归调用树的方法求解。n=7,k=3时，递归调用树为 图中每一个数字代表对应下标的an 为了求a4,a5,a6,a7需要遍历该递归 ......
考虑K阶变系数线性递推方程：
现给定初值a1,a2,---,ak和n>k,要求编程打印an,an-1,---,ak+1的值
该问题用常规的迭代法非常容易解决，现在要考虑的是用遍历递归调用树的方法求解。n=7,k=3时，递归调用树为
图中每一个数字代表对应下标的an
为了求a4,a5,a6,a7需要遍历该递归树，从最底层的叶子a1,a2,a3开始逐层向上累加，直到累加完第一层，这样就得到了a4,a5,a6,a7的值。
n=7,k=3,f(n)=n,bk(n)=n+k,a1=1,a2=2,a3=3时解决该问题的JAVA代码如下：
程序一：
1 package programm; //遍历递归树中所有节点，相同值会重复计算
2 import java.util.*;
3
4 public class RecursionTree
5 {
6
7 public static void main(String[] args)
8 {
9 final int K=3;
10 final int N=7;
11 int[] initial=new int[K];
12 for (int i=0; i<K; i++)
13 initial[i]=i+1;
14
15 Stack<Node> stack=new Stack<Node>();
16 stack.push(new Node(0, 0, N));
17 boolean TF=true;
18 int sign=0, n=stack.getTop().getIndex();
19
20 while(!stack.isEmpty())
21 {
22 if (1<=n&&n<=K)
23 {
24 stack.getTop().setSum(stack.getTop().getSum()+initial[n-1]*(stack.getTop().getIndex()+stack.getTop().getFlag()));
25 TF=false;
26 n=stack.getTop().getIndex();
27 }
28 else
29 {
30 if (TF==false)
31 {
32 stack.getTop().setFlag(stack.getTop().getFlag()+1);
33
34 if (stack.getTop().getFlag()>K)
35 {
36 Node temp=stack.pop();
37 temp.setSum(temp.getSum()+temp.getIndex());
38
39 if (stack.isEmpty())
40 {
41 System.out.println("The "+temp.getIndex()+"nd item is "+temp.getSum());
42 }
43 else
44 {
45 if (stack.getTop().getFlag()==1 && temp.getIndex()>sign)
46 {
47 sign=temp.getIndex();
48 System.out.println("The "+temp.getIndex()+"nd item is "+temp.getSum());
49 }
50
51 stack.getTop().setSum(stack.getTop().getSum()+temp.getSum()*(stack.getTop().getIndex()+stack.getTop().getFlag()));
52 n=stack.getTop().getIndex();
53 TF=false;
54 }
55 }
56 else
57 {
58 if ((n=stack.getTop().getIndex()-stack.getTop().getFlag())>K)
59 {
60 stack.push(new Node(0, 0, n));
61 TF=true;
62 }
63 else
64 {
65 continue;
66 }
67 }
68 }
69 else
70 {
71 stack.getTop().setFlag(stack.getTop().getFlag()+1);
72 if ((n=stack.getTop().getIndex()-1)>K)
73 {
74 stack.push(new Node(0, 0, n));
75 TF=true;
76 }
77 else
78 {
79 continue;
80 }
81 }
82 }
83 }
84 }
85
86 }
87
88 class Node
89 {
90 private int sum;
91 private int flag;
92 private int index;
93
94 public Node(int sum, int flag, int index)
95 {
96 this.sum=sum;
97 this.flag=flag;
98 this.index=index;
99 }
100
101 public int getSum()
102 {
103 return sum;
104 }
105
106 public void setSum(int sum)
107 {
108 this.sum=sum;
109 }
110
111 public int getFlag()
112 {
113 return flag;
114 }
115
116 public void setFlag(int flag)
117 {
118 this.flag=flag;
119 }
120
121 public int getIndex()
122 {
123 return index;
124 }
125 }
126
127 class Stack<E>
128 {
129 ArrayList<E> list=new ArrayList<E>();
130
131 public boolean isEmpty()
132 {
133 return list.isEmpty();
134 }
135
136 public int getSize()
137 {
138 return list.size();
139 }
140
141 public E getTop()
142 {
143 return list.get(getSize()-1);
144 }
145
146 public E pop()
147 {
148 E interval=list.get(getSize()-1);
149 list.remove(getSize()-1);
150 return interval;
151 }
152
153 public void push(E Ob)
154 {
155 list.add(Ob);
156 }
157 }
运行结果：
以上方法的问题是，相同的项会被重复计算多次，如a4被重复计算了三次，所以以上方法需要改进。用数组保存已求出项的值，遍历
到相同项时直接从数组中找到并使用其值即可。要实现这一点，需要修改源程序41行，48行，60-61行。修改后的代码如下：
程序二：
1 package programm; //不遍历递归树中所有节点,相同值不会重复计算
2 import java.util.*;
3
4 public class RecursionTree
5 {
6
7 public static void main(String[] args)
8 {
9 final int K=3; //递推方程阶数
10 final int N=7; //要求的部分数列中下标最大的项的下标
11 int[] initial=new int[K]; //初值a1----ak
12 for (int i=0; i<K; i++) //令初值a1----ak分别为1,2---,k
13 initial[i]=i+1;
14
15 Stack<Node> stack=new Stack<Node>(); //建立Node类型栈对象
16 stack.push(new Node(0, 0, N)); //递归树根节点压入栈，该节点flag=sum=0，index=N
17 boolean TF=true; //true向前进至下一层,false回溯至上一层
18 int sign=0, n=stack.getTop().getIndex(); //sign记录当前已遍历节点中下标最大的节点,n初始化为根节点下标
19 int[] result=new int[N-K]; //记录ak+1---aN项值的数组
20
21 while(!stack.isEmpty()) //栈不空
22 {
23 if (1<=n&&n<=K) //到达递归树中可直接写出值的叶子结点
24 {
25 stack.getTop().setSum(stack.getTop().getSum()+initial[n-1]*(stack.getTop().getIndex()+stack.getTop().getFlag())); //将叶子结点值乘以系数累加至父节点
26 TF=false;
27 n=stack.getTop().getIndex(); //回溯
28 }
29 else
30 {
31 if (TF==false)
32 {
33 stack.getTop().setFlag(stack.getTop().getFlag()+1); //当前节点flag增一，试探下一子节点
34
35 if (stack.getTop().getFlag()>K) //当前节点所有子节点均试探完毕
36 {
37 Node temp=stack.pop(); //从栈中弹出当前节点
38 temp.setSum(temp.getSum()+temp.getIndex()); //加上尾数f(n),得到当前节点的值
39
40 if (stack.isEmpty()) //栈空,temp引用根节点，根节点值已求出，存放在temp的sum中
41 {
42 result[N-K-1]=temp.getSum(); //在数组result中存放根节点即aN的值
43 System.out.println("The "+temp.getIndex()+"nd item is "+temp.getSum()); //打印aN的值
44 }
45 else
46 {
47 if (stack.getTop().getFlag()==1 && temp.getIndex()>sign) //找到当前已遍历节点中下标最大节点
48 {
49 sign=temp.getIndex(); //设置新的最大下标
50 result[temp.getIndex()-K-1]=temp.getSum(); //当前节点值存放至result数组中
51 System.out.println("The "+temp.getIndex()+"nd item is "+temp.getSum()); //打印当前节点值
52 }
53
54 stack.getTop().setSum(stack.getTop().getSum()+temp.getSum()*(stack.getTop().getIndex()+stack.getTop().getFlag())); //当前节点值乘以系数累加至父节点
55 n=stack.getTop().getIndex();
56 TF=false; //回溯
57 }
58 }
59 else
60 {
61 if ((n=stack.getTop().getIndex()-stack.getTop().getFlag())>K) //前进至非叶子结点
62 {
63 stack.getTop().setSum(stack.getTop().getSum()+result[n-K-1]*(stack.getTop().getIndex()+stack.getTop().getFlag())); //当前节点值之前已算出，从数组result中找出该值乘以系数累加至父节点
64 n=stack.getTop().getIndex();
65 TF=false; //回溯
66 }
67 else
68 {
69 continue; //直接进至下一轮循环，累加叶子节点值和系数乘积至父节点
70 }
71 }
72 }
73 else
74 {
75 stack.getTop().setFlag(stack.getTop().getFlag()+1); //进至新的一层,当前节点flag增一试探下一层节点
76 if ((n=stack.getTop().getIndex()-1)>K) //下一层第一个节点非叶子
77 {
78 stack.push(new Node(0, 0, n)); //该节点压入栈
79 TF=true;
80 }
81 else
82 {
83 continue; //同上
84 }
85 }
86 }
87 }
88 }
89
90 }
91
92 class Node //递归树节点类
93 {
94 private int sum; //当前节点值
95 private int flag; //当前节点的父节点下标和当前节点下标之差
96 private int index; //当前节点下标
97
98 public Node(int sum, int flag, int index) //构造方法
99 {
100 this.sum=sum;
101 this.flag=flag;
102 this.index=index;
103 }
104
105 public int getSum()
106 {
107 return sum;
108 }
109
110 public void setSum(int sum)
111 {
112 this.sum=sum;
113 }
114 //访问器和修改器
115 public int getFlag()
116 {
117 return flag;
118 }
119
120 public void setFlag(int flag)
121 {
122 this.flag=flag;
123 }
124
125 public int getIndex()
126 {
127 return index;
128 }
129 }
130
131 class Stack<E> //泛型栈类
132 {
133 ArrayList<E> list=new ArrayList<E>();
134
135 public boolean isEmpty()
136 {
137 return list.isEmpty();
138 }
139
140 public int getSize()
141 {
142 return list.size();
143 }
144
145 public E getTop()
146 {
147 return list.get(getSize()-1);
148 }
149
150 public E pop()
151 {
152 E interval=list.get(getSize()-1);
153 list.remove(getSize()-1);
154 return interval;
155 }
156
157 public void push(E Ob)
158 {
159 list.add(Ob);
160 }
161 }
可以验证运行结果和程序一相同，但是节省了运行时间
删掉程序一37行，修改24行和51行可以得到程序三，用于计算递推数列an=an-1+---an-kn>k a1=1---ak=k当给定n>k时an,---,ak+1的值。
程序三(n=7, k=2, a1=1, a2=2)：
1 package programm; //an=an-1+---an-k型递归式求解，遍历所有节点
2 import java.util.*;
3
4 public class RecursionTree
5 {
6
7 public static void main(String[] args)
8 {
9 final int K=2;
10 final int N=7;
11 int[] initial=new int[K];
12 for (int i=0; i<K; i++)
13 initial[i]=i+1;
14
15 Stack<Node> stack=new Stack<Node>();
16 stack.push(new Node(0, 0, N));
17 boolean TF=true;
18 int sign=0, n=stack.getTop().getIndex();
19
20 while(!stack.isEmpty())
21 {
22 if (1<=n&&n<=K)
23 {
24 stack.getTop().setSum(stack.getTop().getSum()+initial[n-1]);
25 TF=false;
26 n=stack.getTop().getIndex();
27 }
28 else
29 {
30 if (TF==false)
31 {
32 stack.getTop().setFlag(stack.getTop().getFlag()+1);
33
34 if (stack.getTop().getFlag()>K)
35 {
36 Node temp=stack.pop();
37
38 if (stack.isEmpty())
39 {
40 System.out.println("The "+temp.getIndex()+"nd item is "+temp.getSum());
41 }
42 else
43 {
44 if (stack.getTop().getFlag()==1 && temp.getIndex()>sign)
45 {
46 sign=temp.getIndex();
47 System.out.println("The "+temp.getIndex()+"nd item is "+temp.getSum());
48 }
49
50 stack.getTop().setSum(stack.getTop().getSum()+temp.getSum());
51 n=stack.getTop().getIndex();
52 TF=false;
53 }
54 }
55 else
56 {
57 if ((n=stack.getTop().getIndex()-stack.getTop().getFlag())>K)
58 {
59 stack.push(new Node(0, 0, n));
60 TF=true;
61 }
62 else
63 {
64 continue;
65 }
66 }
67 }
68 else
69 {
70 stack.getTop().setFlag(stack.getTop().getFlag()+1);
71 if ((n=stack.getTop().getIndex()-1)>K)
72 {
73 stack.push(new Node(0, 0, n));
74 TF=true;
75 }
76 else
77 {
78 continue;
79 }
80 }
81 }
82 }
83 }
84
85 }
86
87 class Node
88 {
89 private int sum;
90 private int flag;
91 private int index;
92
93 public Node(int sum, int flag, int index)
94 {
95 this.sum=sum;
96 this.flag=flag;
97 this.index=index;
98 }
99
100 public int getSum()
101 {
102 return sum;
103 }
104
105 public void setSum(int sum)
106 {
107 this.sum=sum;
108 }
109
110 public int getFlag()
111 {
112 return flag;
113 }
114
115 public void setFlag(int flag)
116 {
117 this.flag=flag;
118 }
119
120 public int getIndex()
121 {
122 return index;
123 }
124 }
125
126 class Stack<E>
127 {
128 ArrayList<E> list=new ArrayList<E>();
129
130 public boolean isEmpty()
131 {
132 return list.isEmpty();
133 }
134
135 public int getSize()
136 {
137 return list.size();
138 }
139
140 public E getTop()
141 {
142 return list.get(getSize()-1);
143 }
144
145 public E pop()
146 {
147 E interval=list.get(getSize()-1);
148 list.remove(getSize()-1);
149 return interval;
150 }
151
152 public void push(E Ob)
153 {
154 list.add(Ob);
155 }
156 }
运行结果：
显然，所求得的即为斐波那契数列的第4-8项
为了便于读者理解程序一二三，下面给出一个经过简化的程序四，实现思想和程序一二三基本相同且功能和程序三相同
程序四（n=7, k=2, a1=1, a2=2）:
1 package RecursionTree; //简化版的an=an-1+---an-k型递归式求解，遍历所有节点
2 import java.util.*;
3
4 public class recursiontree
5 {
6 public static void main(String[] args)
7 {
8 final int K=2;
9 final int N=7;
10 int[] initial=new int[K];
11 for (int i=0; i<K; i++)
12 initial[i]=i+1;
13
14 Stack<Node> stack=new Stack<Node>();
15 stack.push(new Node(0, N));
16 boolean TF=true;
17 int sum=0;
18
19 while (!stack.isEmpty())
20 {
21 if (1<=stack.getTop().getIndex() && stack.getTop().getIndex()<=K)
22 {
23 sum+=initial[stack.getTop().getIndex()-1];
24 stack.pop();
25 TF=false;
26 }
27 else
28 {
29 if (TF==false)
30 {
31 stack.getTop().setFlag(stack.getTop().getFlag()+1);
32 if (stack.getTop().getFlag()>K)
33 {
34 stack.pop();
35 TF=false;
36 }
37 else
38 {
39 stack.push(new Node(0, stack.getTop().getIndex()-stack.getTop().getFlag()));
40 TF=true;
41 }
42 }
43 else
44 {
45 stack.getTop().setFlag(stack.getTop().getFlag()+1);
46 stack.push(new Node(0, stack.getTop().getIndex()-1));
47 TF=true;
48 }
49 }
50 }
51 System.out.println("The "+N+"nd item is "+sum);
52 }
53 }
54
55 class Node
56 {
57 private int flag;
58 private int index;
59
60 public Node(int flag, int index)
61 {
62 this.flag=flag;
63 this.index=index;
64 }
65
66 public int getFlag()
67 {
68 return flag;
69 }
70
71 public void setFlag(int flag)
72 {
73 this.flag=flag;
74 }
75
76 public int getIndex()
77 {
78 return index;
79 }
80 }
81
82 class Stack<E>
83 {
84 ArrayList<E> list=new ArrayList<E>();
85
86 public boolean isEmpty()
87 {
88 return list.isEmpty();
89 }
90
91 public int getSize()
92 {
93 return list.size();
94 }
95
96 public E getTop()
97 {
98 return list.get(getSize()-1);
99 }
100
101 public E pop()
102 {
103 E interval=list.get(getSize()-1);
104 list.remove(getSize()-1);
105 return interval;
106 }
107
108 public void push(E Ob)
109 {
110 list.add(Ob);
111 }
112 }
不难验证运行结果和程序三是一致的