首页 > itarticle > java新手小试牛刀之遍历递归树求递推数列通项

java新手小试牛刀之遍历递归树求递推数列通项

admin 11月 14, 2020 0

考虑K阶变系数线性递推方程：

现给定初值a1,a2,—,ak和n>k,要求编程打印an,an-1,—,ak+1的值

该问题用常规的迭代法非常容易解决，现在要考虑的是用遍历递归调用树的方法求解。n=7,k=3时，递归调用树为

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
 
package programm;           
import java.util.*;

public class  
{

    public static void main(String[] args)
    {
        final int K=3;
        final int N=7;
        int[] initial=new int[K];
        for (int i=0; i<K; i++)
            initial[i]=i+1;
        
        Stack<Node> stack=new Stack<Node>();
        stack.push(new Node(0, 0, N));
        boolean TF=true;
        int sign=0, n=stack.getTop().getIndex();
        
        while(!stack.isEmpty())
        {
            if (1<=n&&n<=K)
            {
                stack.getTop().setSum(stack.getTop().getSum()+initial[n-1]*(stack.getTop().getIndex()+stack.getTop().getFlag()));
                TF=false;
                n=stack.getTop().getIndex();
            }
            else
            { 
                if (TF==false)
                {
                    stack.getTop().setFlag(stack.getTop().getFlag()+1);
                    
                    if (stack.getTop().getFlag()>K)
                    {
                        Node temp=stack.pop();
                        temp.setSum(temp.getSum()+temp.getIndex());
                        
                        if (stack.isEmpty())
                        {
                            System.out.println("The "+temp.getIndex()+"nd item is "+temp.getSum());
                        }
                        else
                        {                
                            if (stack.getTop().getFlag()==1 && temp.getIndex()>sign)
                            {
                                sign=temp.getIndex();
                                System.out.println("The "+temp.getIndex()+"nd item is "+temp.getSum());
                            }
                        
                            stack.getTop().setSum(stack.getTop().getSum()+temp.getSum()*(stack.getTop().getIndex()+stack.getTop().getFlag()));
                            n=stack.getTop().getIndex();
                            TF=false;
                        }
                    }
                    else
                    {
                        if ((n=stack.getTop().getIndex()-stack.getTop().getFlag())>K)
                        {
                            stack.push(new Node(0, 0, n));
                            TF=true;
                        }
                        else
                        {
                            continue;
                        }
                    }
                }
                else
                {
                    stack.getTop().setFlag(stack.getTop().getFlag()+1);
                    if ((n=stack.getTop().getIndex()-1)>K)
                    {
                        stack.push(new Node(0, 0, n));
                        TF=true;
                    }
                    else
                    {
                        continue;
                    }
                }
            }
        }
    }

}

class Node
{
    private int sum;
    private int flag;
    private int index;    
    
    public Node(int sum, int flag, int index)
    {
        this.sum=sum;
        this.flag=flag;
        this.index=index;
    }
    
    public int getSum()
    {
        return sum;
    }
    
    public void setSum(int sum)
    {
        this.sum=sum;
    }
    
    public int getFlag()
    {
        return flag;
    }
    
    public void setFlag(int flag)
    {
        this.flag=flag;
    }
    
    public int getIndex()
    {
        return index;
    }
}

class Stack<E>
{
    ArrayList<E> list=new ArrayList<E>();
    
    public boolean isEmpty()
    {
        return list.isEmpty();    
    }
    
    public int getSize()
    {
        return list.size();
    }
    
    public E getTop()
    {
        return list.get(getSize()-1);
    }
    
    public E pop()
    {
        E interval=list.get(getSize()-1);
        list.remove(getSize()-1);
        return interval;
    }
    
    public void push(E Ob)
    {
        list.add(Ob);
    }
}

运行结果：

以上方法的问题是，相同的项会被重复计算多次，如a4被重复计算了三次，所以以上方法需要改进。用数组保存已求出项的值，遍历
到相同项时直接从数组中找到并使用其值即可。要实现这一点，需要修改源程序41行，48行，60-61行。修改后的代码如下：
程序二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
 
package programm;   //不遍历递归树中所有节点,相同值不会重复计算
import java.util.*;

public class  
{

    public static void main(String[] args)
    {
        final int K=3;   //递推方程阶数
        final int N=7;   //要求的部分数列中下标最大的项的下标
        int[] initial=new int[K];   //初值a1----ak
        for (int i=0; i<K; i++)    //令初值a1----ak分别为1,2---,k
            initial[i]=i+1;
        
        Stack<Node> stack=new Stack<Node>();   //建立Node类型栈对象
        stack.push(new Node(0, 0, N));     //递归树根节点压入栈，该节点flag=sum=0，index=N
        boolean TF=true;    //true向前进至下一层,false回溯至上一层
        int sign=0, n=stack.getTop().getIndex();   //sign记录当前已遍历节点中下标最大的节点,n初始化为根节点下标
        int[] result=new int[N-K];   //记录ak+1---aN项值的数组
        
        while(!stack.isEmpty())   //栈不空
        {
            if (1<=n&&n<=K)  //到达递归树中可直接写出值的叶子结点
            {
                stack.getTop().setSum(stack.getTop().getSum()+initial[n-1]*(stack.getTop().getIndex()+stack.getTop().getFlag()));  //将叶子结点值乘以系数累加至父节点
                TF=false;
                n=stack.getTop().getIndex();    //回溯
            }
            else
            { 
                if (TF==false)
                {
                    stack.getTop().setFlag(stack.getTop().getFlag()+1);   //当前节点flag增一，试探下一子节点
                    
                    if (stack.getTop().getFlag()>K)    //当前节点所有子节点均试探完毕
                    {
                        Node temp=stack.pop();   //从栈中弹出当前节点
                        temp.setSum(temp.getSum()+temp.getIndex());   //加上尾数f(n),得到当前节点的值
                        
                        if (stack.isEmpty())  //栈空,temp引用根节点，根节点值已求出，存放在temp的sum中
                        {
                            result[N-K-1]=temp.getSum();   //在数组result中存放根节点即aN的值
                            System.out.println("The "+temp.getIndex()+"nd item is "+temp.getSum());  //打印aN的值
                        }
                        else
                        {                
                            if (stack.getTop().getFlag()==1 && temp.getIndex()>sign)  //找到当前已遍历节点中下标最大节点
                            {
                                sign=temp.getIndex();   //设置新的最大下标
                                result[temp.getIndex()-K-1]=temp.getSum();  //当前节点值存放至result数组中
                                System.out.println("The "+temp.getIndex()+"nd item is "+temp.getSum());  //打印当前节点值
                            }
                        
                            stack.getTop().setSum(stack.getTop().getSum()+temp.getSum()*(stack.getTop().getIndex()+stack.getTop().getFlag()));  //当前节点值乘以系数累加至父节点
                            n=stack.getTop().getIndex();
                            TF=false;  //回溯
                        }
                    }
                    else
                    {
                        if ((n=stack.getTop().getIndex()-stack.getTop().getFlag())>K)  //前进至非叶子结点
                        {
                            stack.getTop().setSum(stack.getTop().getSum()+result[n-K-1]*(stack.getTop().getIndex()+stack.getTop().getFlag()));  //当前节点值之前已算出，从数组result中找出该值乘以系数累加至父节点
                            n=stack.getTop().getIndex();
                            TF=false;      //回溯
                        }
                        else
                        {
                            continue;  //直接进至下一轮循环，累加叶子节点值和系数乘积至父节点
                        }
                    }
                }
                else
                {
                    stack.getTop().setFlag(stack.getTop().getFlag()+1); //进至新的一层,当前节点flag增一试探下一层节点
                    if ((n=stack.getTop().getIndex()-1)>K) //下一层第一个节点非叶子
                    {
                        stack.push(new Node(0, 0, n));    //该节点压入栈
                        TF=true;  
                    }                                      
                    else
                    {
                        continue;    //同上
                    }
                }
            }
        }
    }

}

class Node    //递归树节点类
{
    private int sum;     //当前节点值
    private int flag;    //当前节点的父节点下标和当前节点下标之差
    private int index;    //当前节点下标
    
    public Node(int sum, int flag, int index)   //构造方法
    {
        this.sum=sum;
        this.flag=flag;   
        this.index=index;
    }
    
    public int getSum()
    {
        return sum;
    }
    
    public void setSum(int sum)
    {
        this.sum=sum;
    }
                                    //访问器和修改器
    public int getFlag()
    {
        return flag;
    }
    
    public void setFlag(int flag)
    {
        this.flag=flag;
    }
    
    public int getIndex()
    {
        return index;
    }
}

class Stack<E>            //泛型栈类
{
    ArrayList<E> list=new ArrayList<E>();
    
    public boolean isEmpty()
    {
        return list.isEmpty();    
    }
    
    public int getSize()
    {
        return list.size();
    }
    
    public E getTop()
    {
        return list.get(getSize()-1);
    }
    
    public E pop()
    {
        E interval=list.get(getSize()-1);
        list.remove(getSize()-1);
        return interval;
    }
    
    public void push(E Ob)
    {
        list.add(Ob);
    }
}

可以验证运行结果和程序一相同，但是节省了运行时间
删掉程序一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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
 
package programm;          //an=an-1+---an-k型递归式求解，遍历所有节点
import java.util.*;

public class  
{

    public static void main(String[] args)
    {
        final int K=2;
        final int N=7;
        int[] initial=new int[K];
        for (int i=0; i<K; i++)
            initial[i]=i+1;
        
        Stack<Node> stack=new Stack<Node>();
        stack.push(new Node(0, 0, N));
        boolean TF=true;
        int sign=0, n=stack.getTop().getIndex();
        
        while(!stack.isEmpty())
        {
            if (1<=n&&n<=K)
            {
                stack.getTop().setSum(stack.getTop().getSum()+initial[n-1]);
                TF=false;
                n=stack.getTop().getIndex();
            }
            else
            { 
                if (TF==false)
                {
                    stack.getTop().setFlag(stack.getTop().getFlag()+1);
                    
                    if (stack.getTop().getFlag()>K)
                    {
                        Node temp=stack.pop();
                        
                        if (stack.isEmpty())
                        {
                            System.out.println("The "+temp.getIndex()+"nd item is "+temp.getSum());
                        }
                        else
                        {                
                            if (stack.getTop().getFlag()==1 && temp.getIndex()>sign)
                            {
                                sign=temp.getIndex();
                                System.out.println("The "+temp.getIndex()+"nd item is "+temp.getSum());
                            }
                        
                            stack.getTop().setSum(stack.getTop().getSum()+temp.getSum());
                            n=stack.getTop().getIndex();
                            TF=false;
                        }
                    }
                    else
                    {
                        if ((n=stack.getTop().getIndex()-stack.getTop().getFlag())>K)
                        {
                            stack.push(new Node(0, 0, n));
                            TF=true;
                        }
                        else
                        {
                            continue;
                        }
                    }
                }
                else
                {
                    stack.getTop().setFlag(stack.getTop().getFlag()+1);
                    if ((n=stack.getTop().getIndex()-1)>K)
                    {
                        stack.push(new Node(0, 0, n));
                        TF=true;
                    }
                    else
                    {
                        continue;
                    }
                }
            }
        }
    }

}

class Node
{
    private int sum;
    private int flag;
    private int index;    
    
    public Node(int sum, int flag, int index)
    {
        this.sum=sum;
        this.flag=flag;
        this.index=index;
    }
    
    public int getSum()
    {
        return sum;
    }
    
    public void setSum(int sum)
    {
        this.sum=sum;
    }
    
    public int getFlag()
    {
        return flag;
    }
    
    public void setFlag(int flag)
    {
        this.flag=flag;
    }
    
    public int getIndex()
    {
        return index;
    }
}

class Stack<E>
{
    ArrayList<E> list=new ArrayList<E>();
    
    public boolean isEmpty()
    {
        return list.isEmpty();    
    }
    
    public int getSize()
    {
        return list.size();
    }
    
    public E getTop()
    {
        return list.get(getSize()-1);
    }
    
    public E pop()
    {
        E interval=list.get(getSize()-1);
        list.remove(getSize()-1);
        return interval;
    }
    
    public void push(E Ob)
    {
        list.add(Ob);
    }
}

运行结果：

显然，所求得的即为斐波那契数列的第4-8项
为了便于读者理解程序一二三，下面给出一个经过简化的程序四，实现思想和程序一二三基本相同且功能和程序三相同
程序四（n=7, k=2, a1=1, a2=2）:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
 
package RecursionTree;    //简化版的an=an-1+---an-k型递归式求解，遍历所有节点
import java.util.*;

public class recursiontree
{
    public static void main(String[] args) 
    {
        final int K=2;
        final int N=7;
        int[] initial=new int[K];
        for (int i=0; i<K; i++)
            initial[i]=i+1;
        
        Stack<Node> stack=new Stack<Node>();
        stack.push(new Node(0, N));
        boolean TF=true;
        int sum=0;
        
        while (!stack.isEmpty())
        {
            if (1<=stack.getTop().getIndex() && stack.getTop().getIndex()<=K)
            {
                sum+=initial[stack.getTop().getIndex()-1];
                stack.pop();
                TF=false;
            }
            else
            {
                if (TF==false)
                {
                    stack.getTop().setFlag(stack.getTop().getFlag()+1);
                    if (stack.getTop().getFlag()>K)
                    {
                        stack.pop();
                        TF=false;
                    }
                    else
                    {
                        stack.push(new Node(0, stack.getTop().getIndex()-stack.getTop().getFlag()));
                        TF=true;
                    }
                }
                else
                {
                    stack.getTop().setFlag(stack.getTop().getFlag()+1);
                    stack.push(new Node(0, stack.getTop().getIndex()-1));
                    TF=true;
                }
            }
        }
        System.out.println("The "+N+"nd item is "+sum);
    }
}

class Node
{
    private int flag;
    private int index;    
    
    public Node(int flag, int index)
    {
        this.flag=flag;
        this.index=index;
    }    
    
    public int getFlag()
    {
        return flag;
    }
    
    public void setFlag(int flag)
    {
        this.flag=flag;
    }
    
    public int getIndex()
    {
        return index;
    }
}

class Stack<E>
{
    ArrayList<E> list=new ArrayList<E>();
    
    public boolean isEmpty()
    {
        return list.isEmpty();    
    }
    
    public int getSize()
    {
        return list.size();
    }
    
    public E getTop()
    {
        return list.get(getSize()-1);
    }
    
    public E pop()
    {
        E interval=list.get(getSize()-1);
        list.remove(getSize()-1);
        return interval;
    }
    
    public void push(E Ob)
    {
        list.add(Ob);
    }
}

不难验证运行结果和程序三是一致的

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能