JAVA新手小試牛刀之遍歷遞歸樹求遞推數列通項

考慮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()>