問題：斐波那契數列,第1項和第2項都為1，后面每一項都為相鄰的前倆項的和,求第n個數

解法：每一個數都為前倆個數之和，第1項和第2項都為1，所以寫 方法f1(n)即為求第n個數，那么f1(n-1)為求第n-1個數，f(n-2)為第n-2個數。所以f1(n)=f1(n-1)+f1(n-2)，然后設置出口，n=1或者n=2時返回1。

public class Test2 {public static void main(String[] args) {System.out.println(f1(6));}//斐波那契數列,第1項和第2項都為1，后面每一項都為相鄰的前倆項的和,求第n個數//f1為求第n個數，第n個數為第n-1個數加上第n-2個數static int f1(int n){if(n==1||n==2)return 1;return f1(n-1)+f1(n-2);}
}

問題：求m和n的最大公約數，m>n

解法：若m%n=0，則n即最大公約數，若為k，則m與n的最大公約數可轉換為?n與k的最大公約數

public class Test2 {public static void main(String[] args) {System.out.println(f2(36, 24));}//斐波那契數列,第1項和第2項都為1，后面每一項都為相鄰的前倆項的和,求第n個數//f1為求第n個數，第n個數為第n-1個數加上第n-2個數static int f2(int m,int n){if(m%n==0)return n;return f2(n,m%n);}
}

問題：對無序數組arr進行排序，arr數組大小為k

解法：對無序數組arr排序 等價于 對前k-1個元素排序后，在對第k個元素插入排序。先進行第1個元素和第2個元素的排序，然后對第3個元素插入排序，然后對第4個元素插入排序....不斷遞歸。

public class Test2 {public static void main(String[] args) {int[] arr= new int[]{9,9,7,6,5,4,3,2,1};f3(arr,arr.length-1);for (int i : arr) {System.out.println(i);}}static void f3(int[] arr,int k){if(k==0)return;//對前k-1個元素進行排序f3(arr,k-1);//把位置k的元素插到前面int x=arr[k];int index=k-1;while(index>=0 && x<arr[index]){arr[index+1]=arr[index];index--;}arr[index+1]=x;}
}

問題：漢諾塔

將1～N從a移動到c，b作為輔助
等價于：將1～N-1從a移動到b，將N移動到c，這時a為空，c為空（此時c有N但因為N不用動了，所以看作為空），然后在把1～N-1移動到c，a為輔助。

public class Test2 {public static void main(String[] args) {f4(3,"A","C","B");}//N個小盤子，from初始柱子，to目標柱子，help輔助柱子static void f4(int n,String from,String to,String help){if(n==1){System.out.println("move"+n+"from"+from+"to"+to);}else {f4(n-1,from,help,to); //把前n-1個盤子移到輔助柱子上System.out.println("move"+n+"from"+from+"to"+to);//n號盤子可以到達目標柱子f4(n-1,help,to,from); //n-1個盤子回到目標柱子}}
}

問題：上樓梯、一共n階，一次性可以上1階、2階或3階，問多少種走樓梯的方法

?上第n階時，有三種情況，它可以從第n-1階上1階、從第n-2階上2階、從第n-3階上3階。

所有f(n)=f(n-1)+f(n-2)+f(n-3)。

public class Test2 {public static void main(String[] args) {System.out.println(f1(8));}static int f1(int n){if(n==1)return 1;if(n==2)return 2;if(n==3)return 4;return f1(n-3)+f1(n-2)+f1(n-1);}
}

問題：旋轉數組，把一個遞增數組的前若干個序列搬到該數組的最后，比如{1,2,3,4,5}->{3,4,5,1,2}，求該數組的最小值

解法：最小值一定在無序的那一半中。

public class Test2 {public static void main(String[] args) {}//最小值一定在無序的那一半中。static int f2(int[] arr){int begin=0,end=arr.length-1;//考慮沒有旋轉這種特殊旋轉if(arr[begin]<arr[end])return arr[begin];while(begin+1<end){int mid=begin+((end-begin)>>1);if(arr[mid]>arr[begin]){ //左側為有序begin=mid;}else{ //右側有序end=mid;}}return arr[end];}
}

問題：在給定一個無序的數組中，找出最長連續遞增的子序列

解法：找到第一個遞增子序列的長度，然后遞歸下一個遞增子序列的長度，直到遍歷完數組

public class Test2 {public static void main(String[] args) {int[] arr = new int[]{1,9,4,5,6,7,8,9,3,6,7};int[]ans=f4(arr,0);for(int i=0;i<ans.length;i++){System.out.println(ans[i]);}}static int[] f4(int[] arr,int start){if(start>=arr.length)return new int[]{};int count=1,index=start;while(index<arr.length-1 &&arr[index+1]>arr[index]){index++;count++;}int[] ans= new int[count];for(int i=start;i<start+count;i++){ans[i-start]=arr[i];}int[] a=f4(arr,start+count);return count>a.length?ans:a;}
}

問題：設計一個高效的求a的n次冪的算法

public class Test2 {public static void main(String[] args) {int n = -3int ans=f5(2,Math.abs(n));System.out.println(n>=0?ans:("1/"+ans));}static int f5(int a,int n){if(n==0)return 1;int ans=a;int ex=1;//指數while((ex<<1)<=n){ans*=ans;ex<<=1;}//差n-ex次方ans*=f5(a,n-ex);return ans;}
}