最代码广告位
追风少年111的gravatar头像
追风少年1112020-03-03 15:08:49

用java如何实现递归算法

用java如何实现递归算法

所有回答列表(4)
jianboluo的gravatar头像
jianboluo LV33月4日

6.1斐波那契数列
山西十一选五_[官网入口]     斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波纳契数列以如下被以递推的方法定义:F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=3,n∈N*)在现代物理、准晶体结构、化学等领域,斐波纳契数列都有直接的应用,为此,美国数学会从1963年起出版了以《斐波纳契数列季刊》为名的一份数学杂志,用于专门刊载这方面的研究成果。

public class FibonacciDemo {

    // 全局变量sum1记录第一个方法调用的次数,sum2记录第二个方法调用的次数
    static int sum1;
    static int sum2;

    public static void main(String[] args) {
        // n代表数列的长度 、 a代表数列的第一项 、 b代表数列的第二项
        int n = 10;
        int a = 1;
        int b = 1;
        long algResult = fibonacci(n);
        // 使用未优化的递归算法得到值
        System.out.println("使用未优化的递归算法得到值:" + algResult + "方法调用次数为:" + sum1);
        // 使用优化的递归算法,减少冗余的方法调用得到的值
        long algEvoResult = fibonacciEvolution(a, b, n);
        System.out.println("使用已经优化的递归算法得到值:" + algEvoResult + "方法调用次数为:" + sum2);

    }

    public static long fibonacci(int n) {
        // 记录调用方法次数
        sum1++;
        if (n < 2) {
            return n;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static long fibonacciEvolution(int a, int b, int n) {
        // 记录调用方法次数
        sum2++;
        if (n > 2) {
            return fibonacciEvolution(a + b, a, n - 1);
        }
        return a;
    }
}
6.2阶层
    阶乘是基斯顿·卡曼(Christian Kramp,1760~1826)于 1808 年发明的运算符号,是数学术语。一个正整数的阶乘(factorial)是所有小于及等于该数的正整数的积,并且0的阶乘为1。自然数n的阶乘写作n!。山西十一选五_[官网入口]1808年,基斯顿·卡曼引进这个表示法。亦即n!=1×2×3×...×n。阶乘亦可以递归方式定义:0!=1,n!=(n-1)!×n。

public class FactorialDemo {
    // 全局变量sum,记录方法调用的次数
    static int sum;

    public static void main(String[] args) {
        int n = 10;
        int result = factorial(n);
        System.out.println("n的阶乘为:" + result + ";调用方法次数为:" + sum);
    }

    public static int factorial(int n) {
        sum++;
        // 0 和 1 的阶乘都是1
        if (n == 1 || n == 0) {
            return 1;
        }
        int result = n * factorial(n - 1);
        return result;
    }
}
6.3归并排序
山西十一选五_[官网入口]    归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。 用途: (速度仅次于快速排序,为稳定排序算法,一般用于对总体无序,但是各子项相对有序的数列,应用见2011年普及复赛第3题“瑞士轮”的标程)

public class MergingSortDemo {
// private static long sum = 0;

    /**
     * * <pre>
     * * 二路归并
     * * 原理:将两个有序表合并和一个有序表
     * * </pre>
     * *
     * * @param a
     * * @param s
     * * 第一个有序表的起始下标
     * * @param m
     * * 第二个有序表的起始下标
     * * @param t
     * * 第二个有序表的结束下标
     * *
     */
    private static void merge(int[] a, int s, int m, int t) {
        int[] tmp = new int[t - s + 1];
        int i = s, j = m, k = 0;
        while (i < m && j <= t) {
            if (a[i] <= a[j]) {
                tmp[k] = a[i];
                k++;
                i++;
            } else {
                tmp[k] = a[j];
                j++;
                k++;
            }
        }
        while (i < m) {
            tmp[k] = a[i];
            i++;
            k++;
        }
        while (j <= t) {
            tmp[k] = a[j];
            j++;
            k++;
        }
        System.arraycopy(tmp, 0, a, s, tmp.length);
    }

    /**
     * *
     * * @param a
     * * @param s
     * * @param len
     * * 每次归并的有序集合的长度
     */
    public static void mergeSort(int[] a, int s, int len) {
        int size = a.length;
        int mid = size / (len << 1);
        int c = size & ((len << 1) - 1);
        // -------归并到只剩一个有序集合的时候结束算法-------//
        if (mid == 0)
            return;
        // ------进行一趟归并排序-------//
        for (int i = 0; i < mid; ++i) {
            s = i * 2 * len;
            merge(a, s, s + len, (len << 1) + s - 1);
        }
        // -------将剩下的数和倒数一个有序集合归并-------//
        if (c != 0)
            merge(a, size - c - 2 * len, size - c, size - 1);
        // -------递归执行下一趟归并排序------//
        mergeSort(a, 0, 2 * len);
    }

    public static void main(String[] args) {
        int[] a = new int[]{4, 3, 6, 1, 2, 5};
        mergeSort(a, 0, 1);
        for (int i = 0; i < a.length; ++i) {
            System.out.print(a[i] + " ");
        }
    }
}

6.4快速排序
    快速排序(Quicksort)是对冒泡排序的一种改进。快速排序由C. A. R. Hoare在1962年提出。它的基本思想是: 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小, 然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

public class QuickSortDemo {

    // 分区
    private static int partition(int[] arr, int start, int end) {
        // 得到数组中第一个元素的值
        int key = arr[start];
        // 判断数组长度
        while (start < end) {
            while (arr[end] >= key && end > start)
                end--;
            arr[start] = arr[end];
            while (arr[start] <= key && end > start)
                start++;
            arr[end] = arr[start];

        }
        arr[start] = key;
        return start;
    }

    // 快排
    public static void quickSort(int arr[], int start, int end) {
        if (start < end) {
            int index = partition(arr, start, end);
            // 递归调用
            quickSort(arr, start, index - 1);
            quickSort(arr, index + 1, end);
        }
    }

    // 测试
    public static void main(String[] args) {
        int arr[] = {12, 32, 41, 90, 8, 68, 44, 31, 33, 9};
        // start:arr数组第一个元素的下标
        // end  :arr数组最后一个元素的下标
        int start = 0;
        int end = arr.length - 1;
        quickSort(arr, start, end);
        System.err.println("排序后为:" + Arrays.toString(arr));

    }
}
6.5二分查找
    二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。

public class BinarySearchDemo {

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        int key = 11;
        int index = binarySearch(arr, key);
        System.out.println("二分查找元素的下标为:" + index);
        int index1 = recursionBinarySearch(arr, key - 2, 0, arr.length - 1);
        System.out.println("递归二分查找元素的下标为:" + index1);
    }

    // 二分查找 key为目标元素 返回查找元素的下标
    public static int binarySearch(int arr[], int key) {
        int low = 0;
        int high = arr.length - 1;
        int middle;

        while (low <= high) {
            middle = (low + high) / 2;
            if (arr[middle] > key) {
                // 比关键字大则关键字在左区域
                high = middle - 1;
            } else if (arr[middle] < key) {
                // 比关键字小则关键字在右区域
                low = middle + 1;
            } else {
                return middle;
            }
        }
        System.err.println("不存在此元素");
        return -1;
    }

    // 递归实现二分查找
    public static int recursionBinarySearch(int[] arr, int key, int low, int high) {

        if (key < arr[low] || key > arr[high] || low > high) {
            return -1;
        }

        int middle = (low & high) + ((low ^ high) >> 1);  //初始中间位置
        if (arr[middle] > key) {
            //比关键字大则关键字在左区域
            return recursionBinarySearch(arr, key, low, middle - 1);
        } else if (arr[middle] < key) {
            //比关键字小则关键字在右区域
            return recursionBinarySearch(arr, key, middle + 1, high);
        } else {
            return middle;
        }

    }
}

6.6树的遍历和许多树的问题:中序遍历、前序遍历、后序遍历
package com.wxt.recursive;

import com.wxt.pojo.Node;

/**
 * @description: 使用递归方法演示前序、中序、后续遍历
 * @author: Mr.Wang
 * @create: 2019-01-04 22:58
 **/
public class BinaryTree {
    public Node init() {
        //注意必须逆序建立,先建立子节点,再逆序往上建立,因为非叶子结点会使用到下面的节点,而初始化是按顺序初始化的,不逆序建立会报错
        Node J = new Node(8, null, null);
        Node H = new Node(4, null, null);
        Node G = new Node(2, null, null);
        Node F = new Node(7, null, J);
        Node E = new Node(5, H, null);
        Node D = new Node(1, null, G);
        Node C = new Node(9, F, null);
        Node B = new Node(3, D, E);
        Node A = new Node(6, B, C);
        //返回根节点
        return A;
    }

    // 得到当前节点
    public void printNode(Node node) {
        int data = node.getData();
        String result = String.valueOf(data);
        System.out.print(result);
    }

    // The former sequence traversal - 前序遍历
    public void firstTraversal(Node root) {
        printNode(root);
        // 使用递归算法遍历左节点
        if (root.getLeftNode() != null) {
            firstTraversal(root.getLeftNode());
        }
        // 使用递归算法遍历右节点
        if (root.getRightNode() != null) {
            firstTraversal(root.getRightNode());
        }
    }

    // In the sequence traversal - 中序遍历
    public void inOtherTraversal(Node root) {
        if (root.getRightNode() != null) {
            inOtherTraversal(root.getRightNode());
        }

        printNode(root);

        if (root.getLeftNode() != null) {
            inOtherTraversal(root.getLeftNode());
        }

    }

    // The former sequence traversal - 后续遍历
    public void postOtherTraversal(Node root) {
        if (root.getRightNode() != null) {
            postOtherTraversal(root.getRightNode());
        }
        if (root.getLeftNode() != null) {
            postOtherTraversal(root.getLeftNode());
        }
        printNode(root);
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        // 初始化二叉树
        Node root = tree.init();
        System.out.println("先序遍历:");
        tree.firstTraversal(root);
        System.out.println("");
        System.out.println("中序遍历:");
        tree.inOtherTraversal(root);
        System.out.println("");
        System.out.println("后序遍历:");
        tree.postOtherTraversal(root);
        System.out.println("");
    }

}

评论(0)最佳答案
947335690的gravatar头像
947335690 LV13月4日

三角数字

 

【1,3,6,10,15......】

 

规律:f(n) = f(n-1) + n;

 

结束条件:f(1) = 1;

 

package cn.itcast;

 

public class Recursion {

public static int getNumber(int n) {

        // 结束条件

if (n == 1) {

return 1;

}

        // 规律

return getNumber(n - 1) + n;

}

}

斐波那契数列

 

 【1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89......】

 

规律:f(n) = f(n-1) + f(n-2);

 

结束条件:f(1) = 1;f(2) = 1;

 

package cn.itcast;

 

public class Recursion {

public static int getNumber(int n) {

        // 结束条件

if (n == 1 || n == 2) {

return 1;

}

        // 规律

return getNumber(n - 1) + getNumber(n - 2);

}

}

hbsoft2008的gravatar头像
hbsoft2008 LV23月7日

好算法,学习了

startleback的gravatar头像
startleback LV14月1日

看看评论区,学习学习

顶部客服微信二维码底部
>扫描二维码关注最代码为好友扫描二维码关注最代码为好友

页面底部区域 foot.htm