首页 > > 程序设计 > Java技术 >

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

2018-06-18 03:22:22来源：未知阅读 ()

考虑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 }