怎么用Java遞歸方法實(shí)現(xiàn)漢諾塔

這篇文章主要介紹“怎么用Java遞歸方法實(shí)現(xiàn)漢諾塔”，在日常操作中，相信很多人在怎么用Java遞歸方法實(shí)現(xiàn)漢諾塔問題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”怎么用Java遞歸方法實(shí)現(xiàn)漢諾塔”的疑惑有所幫助！接下來，請(qǐng)跟著小編一起來學(xué)習(xí)吧！

遞歸（recursion）：程序調(diào)用自身的編程技巧。

1. 反復(fù)執(zhí)行的過程（調(diào)用自身）

2. 有跳出反復(fù)執(zhí)行過程的條件（遞歸出口）

import com.lifeibigdata.algorithms.leetcode.TreeNode;
public class Recursive {

    public static void main(String[] args) {
//        System.out.println(factorial(3));
//        tower(2,'A','B','C');
//        perm(new int[]{1,2,3},0,2);
//        System.out.println(fib(2));
//        System.out.println(fib_i(1,1,7));
        System.out.println(factorial_tail(3,1,1));
//        System.out.println(is_palindereme(""));
//        System.out.println(binary_search(new int[]{1,2,3,4,5},4));
//        System.out.println(binSearch(new int[]{1,2,3,4,5},0,4,6));
    }

    /**
     * 階乘
     * n! = n * (n-1) * (n-2) * ...* 1(n>0)
     *
     */
    static int factorial(int x){
        if (0 == x){
            return 1;
        } else {
            return x*factorial(x - 1);
        }
    }

    // 迭代計(jì)算過程
    static int factorial2(int n){
        return factIterator(1, 1, n);
    }

    static int factIterator(int result, int counter, int maxCount){
        if(counter > maxCount){
            return result;
        }
        return factIterator((counter * result), counter + 1, maxCount);
    }

    /**
     * 漢諾塔問題
     *
     *當(dāng)n=1時(shí)，將A上的盤子直接移動(dòng)到C上
     *當(dāng)n>=2時(shí)：
     *1，將A上n-1個(gè)盤子移動(dòng)到B上（此步驟的解決辦法與移動(dòng)n階盤子的方法完全一樣,只是問題的規(guī)模減小1階)
     *2，將A上的一個(gè)盤子移動(dòng)到C
     *3，將B上的n-1個(gè)盤子移動(dòng)到C上。
     *
     */
    public static void tower(int n,char one,char two,char three){
        if(n==1){
            move(one,three,1);
        }else{
            tower(n-1,one,three,two);   //把第1個(gè)移動(dòng)到第2個(gè)
            move(one,three, n);         //將第n個(gè)盤,從第1個(gè)移動(dòng)到第3個(gè)柱子
            tower(n-1,two,one,three);   //把第2個(gè)移動(dòng)到第3個(gè)
        }
        System.out.println("---");
        /**
         *
         A的第1盤移動(dòng)到C
         A的第2盤移動(dòng)到B
         C的第1盤移動(dòng)到B

         A的第3盤移動(dòng)到C
         B的第1盤移動(dòng)到A
         B的第2盤移動(dòng)到C
         A的第1盤移動(dòng)到C
         */
    }
    //輸出
    public static void move(char x,char y, int n){
        System.out.println(x+"的第"+n+"盤移動(dòng)到"+y);
    }


    /**
     * 全排列問題
     * http://blog.csdn.net/xiazdong/article/details/7986015
     */
    static void swap(int a,int b,int arr[])
    {
        int temp=arr[a];
        arr[a]=arr[b];
        arr[b]=temp;
    }
    public static void perm(int arr[], int begin,int end) {
        if(end==begin){         //一到遞歸的出口就輸出數(shù)組，此數(shù)組為全排列
            for(int i=0;i<=end;i++){
                System.out.print(arr[i]+" ");
            }
            System.out.println();
            return;
        }
        else{
            for(int j=begin;j<=end;j++){
                swap(begin,j,arr);      //for循環(huán)將begin~end中的每個(gè)數(shù)放到begin位置中去
                perm(arr,begin+1,end);  //假設(shè)begin位置確定，那么對(duì)begin+1~end中的數(shù)繼續(xù)遞歸
                swap(begin,j,arr);      //換過去后再還原
            }
        }
    }


    /**
     * 斐波納契數(shù)列，又稱黃金分割數(shù)列
     *
     * 這個(gè)數(shù)列從第三項(xiàng)開始，每一項(xiàng)都等于前兩項(xiàng)之和
     * 斐波那契數(shù)列這樣定義：f(0) = 0, f(1) = 1, 對(duì)n > 1, f(n) = f(n-1) + f(n-2)
     * 1、1、2、3、5、8、13
     */
    static long fib(int n) {
        if (n == 0)
            return 1;
        if (n == 1)
            return 1;
        if (n > 1)
            return fib(n-1) + fib(n-2);
        return 0;
    }

    static int fib_i(int a, int b , int n)
    {
        if(n == 2)
            return a+b;
        else
            return fib_i(b, a+b, n-1);
    }

    static int factorial_tail(int n,int acc1,int acc2)
    {
        if (n < 2)
        {
            return acc1;
        }
        else
        {
            return factorial_tail(n-1,acc2,acc1+acc2);
        }
    }

    /**
     *
     fibonacci(n-1,acc2,acc1+acc2)真是神來之筆，原本樸素的遞歸產(chǎn)生的棧的層次像二叉樹一樣，以指數(shù)級(jí)增長(zhǎng)，但是現(xiàn)在棧的層次卻像是數(shù)組，變成線性增長(zhǎng)了，
     實(shí)在是奇妙，總結(jié)起來也很簡(jiǎn)單，原本棧是先擴(kuò)展開，然后邊收攏邊計(jì)算結(jié)果，現(xiàn)在卻變成在調(diào)用自身的同時(shí)通過參數(shù)來計(jì)算。
     小結(jié)
     尾遞歸的本質(zhì)是：將單次計(jì)算的結(jié)果緩存起來，傳遞給下次調(diào)用，相當(dāng)于自動(dòng)累積。
     在Java等命令式語言中，尾遞歸使用非常少見，因?yàn)槲覀兛梢灾苯佑醚h(huán)解決。而在函數(shù)式語言中，尾遞歸卻是一種神器，要實(shí)現(xiàn)循環(huán)就靠它了。
     */
//    def Fib(n,b1=1,b2=1,c=3):
//
//            if n <= 2:
//            return 1
//
//            else:
//            if n==c:
//            return b1+b2
//
//    else:
//            return Fib(n,b1=b2,b2=b1+b2,c=c+1)



    /**
     *
     *返回一個(gè)二叉樹的深度
     */

    int depth(TreeNode t){
        if(t == null) return 0;
        else {
            int a=depth(t.right);
            int b=depth(t.left);
            return (a>b)?(a+1):(b+1);
        }
    }

    /**
     *
     *判斷一個(gè)二叉樹是否平衡
     */
    int isB(TreeNode t){
        if(t == null) return 0;
        int left=isB(t.left);
        int right=isB(t.right);
        if( left >=0 && right >=0 && left - right <= 1 || left -right >=-1)
            return (left<right)? (right +1) : (left + 1);
        else return -1;
    }

    /**
     * 求數(shù)組中的最大值
     *
     *
     * 用遞歸算法求數(shù)組中的最大值
     * @param a 數(shù)組
     * @param low 數(shù)組下標(biāo)
     * @param heigh 數(shù)組上標(biāo)
     * @return
     */
    public static int Max(int[] a, int low, int heigh) {
        int max;
        if(low > heigh-2) {
            if(a[low] > a[heigh]) max = a[low];
            else max = a[heigh];
        }else {
            int mid = (low + heigh)/2;
            int max1 = Max(a, low, mid);
            int max2 = Max(a, mid+1, heigh);
            max = max1>max2 ? max1 : max2;
        }
        return max;
    }
    /**
     * 數(shù)字塔問題
     *
     *
     * 用遞歸算法求解數(shù)字塔問題
     * @param n 數(shù)字塔的行數(shù)
     * @return 數(shù)字塔的字符串
     */
    public static String tourData(int n) {
        String str = new String();
        if(1 == n) {
            str = rowData(n) + "\n";
            return str;
        }
        else {
            str = tourData(n-1) + rowData(n) + "\n";
        }
        return str;
    }
    private static String rowData(int n) {
        String str = new String();
        for(int i=0; i<n; i++) {
            str = str+ n + "      ";
        }
        return str;
    }

    /**
     * 判斷是否是回文
     * @param str
     * @return
     */
    static boolean is_palindereme(String str){
        if (str.isEmpty() || str.length() < 2){
            return true;
        } else {
//            char[] chars = str.toCharArray();
//            if (chars[0] == chars[chars.length -1]){
            if (str.charAt(0) == str.charAt(str.length() - 1)){
                return is_palindereme(str.substring(1,str.length()-1));
            }
        }
        return false;
    }

    /**
     * 已排序數(shù)組的二分查找算法
     */

    static boolean binary_search(int[] arr,int target){
        int mid = arr.length /2;
        if (arr[mid] == target){
            return true;
        } else if (arr[mid] > target){
            int[] narr = new int[arr.length - mid];
            System.arraycopy(arr,0,narr,0,arr.length - mid);
            return binary_search(narr,target);
        } else if (arr[mid] < target){
            int[] narr = new int[arr.length - mid];
            System.arraycopy(arr,mid,narr,0,arr.length - mid);
            return binary_search(narr,target);
        }
        return false;
    }

    /**
     * 遞歸方法實(shí)現(xiàn)二分查找法.
     * @param low 數(shù)組第一位置
     * @param high 最高
     * @param key 要查找的值.
     * @return 返回值.
     */
    static int binSearch(int[] Array,int low,int high,int key)
    {
        if (low<=high)
        {
            int mid = (low+high)/2;
            if(key == Array[mid])
                return mid;
            else if(key<Array[mid])
                //移動(dòng)low和high
                return binSearch(Array,low,mid-1,key);
            else if(key>Array[mid])
                return binSearch(Array,mid+1,high,key);
        }
        return -1;
    }
//    static boolean binary_search(int[] arr,int arrlength,int target){
//        int mid;
//        if (arrlength == 1) {
//            return arr[0] == target;
//        } else {
//            mid = arrlength/2;
//            if (arr[mid-1] == target){
//                return true;
//            } else if (arr[mid - 1] > target){
//                return binary_search(arr,mid,target);
//            } else {
//                return binary_search(arr,arrlength - mid,target);
//            }
//        }
//    }
    /**
     * 兔子產(chǎn)子問題
     */
    /**
     * 走樓梯問題
     */
    /**
     * 在二元樹中找出和為某一值的所有路徑
     * http://z466459262.iteye.com/blog/1115316
     *
     */
/**
 * 純遞歸問題的難易主要糾結(jié)于一些條件表達(dá)式的構(gòu)造以及初值的設(shè)置（上面的為直接表達(dá)式值的設(shè)定）
 * 遞歸分兩步，遞和歸
 *
 * 遞歸算法的一般形式：
 void   func(mode){
 if(endCondition){
 constExpression       //基本項(xiàng)
 }
 else
 {
 accumrateExpreesion /歸納項(xiàng)
 mode=expression //步進(jìn)表達(dá)式
 func(mode) / /調(diào)用本身，遞歸
 }
 }
 */
}

到此，關(guān)于“怎么用Java遞歸方法實(shí)現(xiàn)漢諾塔”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！