美文网首页
递归(recursion)

递归(recursion)

作者: 今有所思 | 来源:发表于2017-03-01 14:09 被阅读27次

    如何设计递归算法

    1. 确定递归公式
    2. 确定边界条件

    1. Fibonacci

    public static int fibonacci(int n) {
        if(n == 0 || n == 1) {
            return n;
        } else {
            return fibonacci(n-1) + fibonacci(n-2);
        }
    }
    

    2. 快速排序(Quick Sort)

    public static int partition(int[] a, int p, int q) {
        int pivot = a[q];
        int index = 0;
        for(int i = p; i < q; i++) {
            if(a[i] <= pivot) {         
                int temp = a[i];
                a[i] = a[index];
                a[index] = temp;
                index++;
            }
        }
        int temp = a[index];
        a[index] = pivot;
        a[q] = temp;
        
        return index;
    }
    public static void quickSort(int[]a, int p, int q) {
        if(p < q) {// 如果p大于等于r 那么就程序不执行  
            int mid = partition(a, p, q);
            quickSort(a, p, mid-1);
            quickSort(a, mid+1, q);
        }
    }
    

    3. 归并排序(Merge Sort)

    public static void merge(int[] a, int left, int mid, int right) {
        int m = mid - left + 1;
        int n = right - mid;
        int[] leftArr = new int[m+1];
        int[] rightArr = new int[n+1];
        for(int i = 0; i < m; i++) {
            leftArr[i] = a[left+i];
        }
        for(int i = 0; i < n; i++) {
            rightArr[i] = a[mid+i+1];
        }
        leftArr[m] = Integer.MAX_VALUE;
        rightArr[n] = Integer.MAX_VALUE;
        int i = 0;
        int j = 0;
        for(int k = left; k <= right; k++) {
            if(leftArr[i] <= rightArr[j]) {
                a[k] = leftArr[i++];
            } else {
                a[k] = rightArr[j++];
            }
        }
    }
    public static void mergeSort(int[] a, int left, int right) {
        if(left < right) { //当left>=right 说明子数组最多只有一个元素,已经排好序了
            int mid = (left + right) / 2;
            mergeSort(a, left, mid);
            mergeSort(a, mid+1, right);
            merge(a, left, mid, right);
        }
    }
    

    4. 二分查找(Binary Search)

    public static int binarySearch(int[] arr, int key, int left, int right) {
        if(left > right)
            return -1;
        int mid = (left + right) / 2;
        if(arr[mid] == key) {
            return mid;
        } else if(arr[mid] > key) {
            return binarySearch(arr, key, left, mid-1);
        } else {
            return binarySearch(arr, key, mid+1, right);
        }
    }
    

    5. 全排列

    
    

    6. 欧几里得算法(辗转相除法)

    /*
     * m >= n
     */
    public static int gcd(int m, int n) {
        if(n == 0) {
            return m;
        } else {
            return gcd(n, m%n);
        }
    }
    

    7. 1加到n累加

    public static int sum(int n) {
        if(n == 1)
            return 1;
        else 
            return n+sum(n-1);
    }
    

    8. 求数组中的最大值

    public static int max(int[] a, int n) {
        if(n == 0)
            return a[0];
        else {
            if(a[n] > max(a, n-1)) {
                return a[n];
            } else {
                return max(a, n-1);
            }
        }
    }
    
        public static int maximum(int[] a, int low, int high) {
            int delt = high - low + 1;
            if(delt == 1) {
                return a[low];
            } else if(delt == 2) {
                return a[low] > a[high]? a[low]: a[high];
            } else {
                int mid = (low + high) / 2;
                int left = maximum(a, low, mid);
                int right = maximum(a, mid+1, high);
                return left > right? left: right;
            }
        }
    

    9. 八皇后

    
    

    相关文章

      网友评论

          本文标题:递归(recursion)

          本文链接:https://www.haomeiwen.com/subject/ctnqgttx.html