Java中常用算法及示例-分治、迭代、递归、递推、动态规划、回溯、穷举、贪心

这篇具有很好参考价值的文章主要介绍了Java中常用算法及示例-分治、迭代、递归、递推、动态规划、回溯、穷举、贪心。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

场景

1、分治算法的基本思想是将一个计算复杂的问题分成规模较小、计算简单的小问题求解,

然后综合各个小问题,得到最终答案。

2、穷举(又称枚举)算法的基本思想是从所有可能的情况中搜索正确的答案。

3、迭代法(Iterative Method) 无法使用公式一次求解,而需要使用重复结构(即循环)重复执行

一段代码来得到答案。

4、递归调用是一个方法在其方法体内调用其自身方法。

5、递推算法是一种理性思维模式的代表,其根据已有的数据和关系,逐步推导而得到结果。

6、动态规划法(Dynamic Programming Algorithm,DPA)类似于分治法,动态规划法的主要做法:

如果一个问题的答案与子问题相关,就能将大问题拆解成各个小问题,

其中与分治法最大的不同是可以让每一个子问题的答案被存储起来,以供下次求解时直接取用。

这样的做法不仅可以减少再次计算的时间,而且可以将这些解组合成大问题的解,可以解决重复计算的问题。

7、回溯法也是枚举法的一种,它的特点就是在搜索过程中寻找问题的解,当发现不满足求解条件时就回溯(返回),

尝试别的路径,避免无效搜索。

8、贪心法(Greed Method)又称贪婪算法,从某一起点开始,在每一个解决问题的步骤使用贪心原则,

即采用在当前状态下最有利或最优化的选择,不断地改进该解答,持续在每一个步骤中选择最佳的方法,

并且逐步逼近给定的目标,当达到某一个步骤不能再继续前进时,算法就停止,以尽可能快的方法求得更好的解。

注:

博客:
霸道流氓气质的博客_CSDN博客-C#,架构之路,SpringBoot领域博主

实现

1、分治算法

举个例子:要以人工的方式将散落在地上的打印纸从第一个排序整理到第100页,一种方式是逐一捡起稿纸,

按照页码顺序插入到正确的位置。这样的排序和整理的过程比较复杂且浪费时间,可以采用分治法的原理,

先将页码1到10放在一起,页码11到20放到一起,以此列推,将原来的100页分类成10个页码区间,

然后对10堆页码进行整理,最后从页码小到大的分组合并。

代码实例-求最大值

    public static int getMax(int[] a,int begin,int end){
        //元素小于2个,直接找出最大值
        if(end -begin <=1){
            if(a[begin]>a[end])
                return a[begin];
            else
                return a[end];
        //否则进入递归
        }else {
            int center = (begin+end)/2;
            int left = getMax(a,begin,center);
            int right = getMax(a,center,end);
            return  left>right?left:right;
        }
    }

    public static void main(String[] args) {
        int[] a = new int[]{2,5,8,45,65,2,44,532,33};
        System.out.println("最大值:"+getMax(a,0,a.length-1));
    }

2、穷举实例-鸡兔同笼

    static int chichen; //鸡的个数
    static int habbit; //兔的个数

    public static int qiongju(int head,int foot){
        int re,i,j;
        re= 0;
       for(i=0;i<=head;i++){
            j = head - i;
            if(i*2 + j*4 == foot)
            {
                re = 1;
                chichen = i;
                habbit = j;
            }
        }
        return re;
    }

    public static void main(String[] args) {
        int re,head,foot;
        System.out.print("输入头数:");
        Scanner input = new Scanner(System.in);
        head = input.nextInt();
        System.out.print("输入脚数:");
        foot = input.nextInt();
        re = qiongju(head,foot);
        if (re ==1){
            System.out.println("鸡有"+chichen+"只,兔有"+habbit+"只。");
        }else {
            System.out.println("无法求解");
        }
    }

3、迭代实例-for循环计算n!

    public static void main(String[] args) {
        int sum =1;
        for(int i =1;i<8;i++){
            for(int j =i;j>0;j--){
                sum = sum * j;
            }
            System.out.println(i+"!="+sum);
            sum =1;
        }
    }

4、递归调用

    static long fact(int n){
        if(n<=1)
            return 1;
        else
            return n*fact(n-1);
    }

    public static void main(String[] args) {
        int i;
        System.out.print("请输入一个要阶乘的数:");
        Scanner input = new Scanner(System.in);
        i = input.nextInt();
        System.out.println(i+"的阶乘结果为:"+fact(i));
    }

5、递推算法

    1、根据已知结果和关系,求解中间结果。
    2、判断是否达到要求,如果没有达到,则继续根据已知结果和关系求解中间结果;如果满足要求,则表示寻找到一个正确的答案
    数学里面的斐波那契数列是使用递推算法的经典例子
    兔子产仔问题:如果一对两个月大的兔子以后每一个月都可以生一对小兔子,而一对新生的兔子出生两个月后才可以生小兔子。
    也就是说,1月份出生,3月份才可产仔。那么假定一年内没有发生兔子死亡事件,那么一年后共有多少对兔子?

    第一个月:1对兔子
    第二个月:1对兔子
    第三个月:2对兔子
    第四个月:3对兔子
    第五个月:5对兔子

    从第三个月开始,每个月的兔子总对数等于前两个月兔子数的综合

    public static int fibonacci(int n){
        int t1,t2;
        if(n==1 || n ==2){
            return 1;
        }else{
            t1 = fibonacci(n-1);//递归调用
            t2 = fibonacci(n-2);
            return t1+t2;
        }
    }

    public static void main(String[] args) {
        System.out.print("请先输入时间:");
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int num = fibonacci(n);
        System.out.println("经过"+n+"月的时间,共繁殖成"+num+"对兔子");
    }

6、动态规划-斐波那契优化

    public static int output[] = new int[1000];

    public static int fib(int n)
    {
        int result;
        result = output[n];
        if(result==0){
            if(n==0)
                return 0;
            if(n==1)
                return 1;
            else
                return (fib(n-1)+fib(n-2));
        }
        output[n] = result;
        return result;
    }

    public static void main(String[] args) {
        int fib = fib(8);
        System.out.println(fib);
    }

7、回溯法示例-老鼠走迷宫

老鼠走迷宫,采用尝试错误的方法找到出口,在走错路时就退回来并把走过的路记下来,避免下次走重复的路,就这样找到出口为止。

老鼠需要遵守以下三个原则:

1、一次只能走一格。

2、遇到墙无法往前走则退回一步,寻找其它路。

3、走过的路不再走第二次。

使用二维数组代表地图,值为1则代表不能通行,值为0则代表可以通行。

假设老鼠从左上角[1][1]进入,从右下角[8][10]出来。

可以使用链表来记录走过的位置,并且将走过的位置所对应的数组元素内容标记为2,然后将这个位置放入堆栈,再进行下一个方向

或路的选择。如果走到死胡同并且还没有抵达终点,就退回到上一个位置,再选择其他的路。由于每次新加入的位置必定会在堆栈的

顶端,因此堆栈顶端指针所指向的方格编号就是当前老鼠的位置,如此重复直至走到迷宫出口为止。

public class HuiSu {
    // 记录老鼠迷宫的行进路径
    public static int ExitX= 8;			//定义出口的X坐标在第8列
    public static int ExitY= 10;		//定义出口的Y坐标在第10行
    public static int [][] MAZE= {//声明迷宫数组
            {1,1,1,1,1,1,1,1,1,1,1,1},
            {1,0,0,0,1,1,1,1,1,1,1,1},
            {1,1,1,0,1,1,0,0,0,0,1,1},
            {1,1,1,0,1,1,0,1,1,0,1,1},
            {1,1,1,0,0,0,0,1,1,0,1,1},
            {1,1,1,0,1,1,0,1,1,0,1,1},
            {1,1,1,0,1,1,0,1,1,0,1,1},
            {1,1,1,1,1,1,0,1,1,0,1,1},
            {1,1,0,0,0,0,0,0,1,0,0,1},
            {1,1,1,1,1,1,1,1,1,1,1,1}
    };

    public static void main(String args[]) throws IOException
    {
        int i,j,x,y;
        TraceRecord path=new TraceRecord();
        x=1;
        y=1;
        System.out.print("[迷宫的路径(0的部分)]\n");
        for(i=0;i<10;i++)
        {
            for(j=0;j<12;j++)
                System.out.print(MAZE[i][j]);
            System.out.print("\n");
        }
        while(x<=ExitX&&y<=ExitY)
        {
            MAZE[x][y]=2;
            if(MAZE[x-1][y]==0)
            {
                x -= 1;
                path.insert(x,y);
            }
            else if(MAZE[x+1][y]==0)
            {
                x+=1;
                path.insert(x,y);
            }
            else if(MAZE[x][y-1]==0)
            {
                y-=1;
                path.insert(x,y);
            }
            else if(MAZE[x][y+1]==0)
            {
                y+=1;
                path.insert(x,y);
            }
            else if(chkExit(x,y,ExitX,ExitY)==1)
                break;
            else
            {
                MAZE[x][y]=2;
                path.delete();
                x=path.last.x;
                y=path.last.y;
            }
        }
        System.out.print("[老鼠走过的路径(2的部分)]\n");
        for(i=0;i<10;i++)
        {
            for(j=0;j<12;j++)
                System.out.print(MAZE[i][j]);
            System.out.print("\n");
        }
    }

    public static int chkExit(int x,int y,int ex,int ey)
    {
        if(x==ex&&y==ey)
        {
            if(MAZE[x-1][y]==1||MAZE[x+1][y]==1||MAZE[x][y-1] ==1||MAZE[x][y+1]==2)
                return 1;
            if(MAZE[x-1][y]==1||MAZE[x+1][y]==1||MAZE[x][y-1] ==2||MAZE[x][y+1]==1)
                return 1;
            if(MAZE[x-1][y]==1||MAZE[x+1][y]==2||MAZE[x][y-1] ==1||MAZE[x][y+1]==1)
                return 1;
            if(MAZE[x-1][y]==2||MAZE[x+1][y]==1||MAZE[x][y-1] ==1||MAZE[x][y+1]==1)
                return 1;
        }
        return 0;
    }

    static class Node
    {
        int x;
        int y;
        Node next;
        public Node(int x,int y)
        {
            this.x=x;
            this.y=y;
            this.next=null;
        }
    }
    static class TraceRecord
    {
        public Node first;
        public Node last;
        public boolean isEmpty()
        {
            return first==null;
        }
        public void insert(int x,int y)
        {
            Node newNode=new Node(x,y);
            if(this.isEmpty())
            {
                first=newNode;
                last=newNode;
            }
            else
            {
                last.next=newNode;
                last=newNode;
            }
        }

        void delete()
        {
            Node newNode;
            if(this.isEmpty())
            {
                System.out.print("[队列已经空了]\n");
                return;
            }
            newNode=first;
            while(newNode.next!=last)
                newNode=newNode.next;
            newNode.next=last.next;
            last=newNode;

        }
    }
}

即迷宫路线如下

java递推,Java,算法,java,动态规划

运行结果

java递推,Java,算法,java,动态规划

8、贪心算法示例-零钱最少找零

    public static void greedMoney(int money){
        System.out.println("需要找零:"+money);
        int[] moneyLevel = {1,5,10,20,50,100};
        for(int i =moneyLevel.length -1;i>=0;i--){
            int num = money/moneyLevel[i];
            int mod = money % moneyLevel[i];
            money = mod;
            if(num>0)
                System.out.println("需要"+num+"张"+moneyLevel[i]+"块");
        }
    }

    public static void main(String[] args) {
        greedMoney(1562);
    }

    //输出结果:
    //需要找零:1562
    //需要15张100块
    //需要1张50块
    //需要1张10块
    //需要2张1块

如果不限制纸币的金额,那这种情况还适合用贪心算法么。

 比如1元,2元,3元,4元,8元,15元的纸币,用来支付K元,至少多少张纸币?

经我们分析,这种情况是不适合用贪心算法的,因为我们上面提供的贪心策略不是最优解。

比如,纸币1元,5元,6元,要支付10元的话,按照上面的算法,至少需要1张6元的,4张1元的,而实际上最优的应该是2张5元的。

所以贪心算法是一种在某种范围内,局部最优的算法。文章来源地址https://www.toymoban.com/news/detail-719298.html

到了这里,关于Java中常用算法及示例-分治、迭代、递归、递推、动态规划、回溯、穷举、贪心的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 五大常用算法——分治法,动态规划,回溯法,分支界限法,贪心算法

    (1) 分治法 将一个难以直接解决的大问题,分割成一些规模较小的相同问题 快速排序 快排也是分治的一个实例,快排每一趟会选定一个数,将比这个数小的放左面,比这个数大的放右面, 然后递归分治求解两个子区间,当然快排因为在分的时候就做了很多工作, 当全部分到

    2024年02月04日
    浏览(39)
  • 「算法小记」-2:矩阵链相乘的方案数【迭代/递归/动态规划/区域化DP/记忆化搜索】(C++ )

    😎 作者介绍:我是程序员洲洲,一个热爱写作的非著名程序员。CSDN全栈优质领域创作者、华为云博客社区云享专家、阿里云博客社区专家博主、前后端开发、人工智能研究生。公粽号:程序员洲洲。 🎈 本文专栏:本文收录于洲洲的《算法小记》系列专栏,该专栏记录了许

    2024年02月05日
    浏览(49)
  • LeetCode 0746. 使用最小花费爬楼梯:动态规划(原地)——不用什么从递归到递推

    力扣题目链接:https://leetcode.cn/problems/min-cost-climbing-stairs/ 给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。 请你计算并返回达到楼

    2024年02月03日
    浏览(40)
  • 力扣 53. 最大子数组和(C语言+分治递归、动态规划)

            给你一个整数数组  nums  ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 子数组  是数组中的一个连续部分。         示例 1:         示例 2:         示例 3: (1)分治递归         分治法的核心部分。

    2024年02月07日
    浏览(35)
  • 算法:分治思想处理归并递归问题

    利用归并思想进行分治也是很重要的一种思路,在解决逆序对的问题上有很大的需求空间 于是首先归并排序是首先的,归并排序要能写出来: 以上为归并排序基本算法原理,基于这个原理可以解决逆序对问题,逆序对问题通常问法是,给定某一个数据,在整个数组中找比这

    2024年02月10日
    浏览(40)
  • 【LeetCode: 53. 最大子数组和 | 暴力递归=>记忆化搜索=>动态规划 | 分治法 】

    🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨ 🌲 作者简介:硕风和炜,CSDN-Java领域新星创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文

    2023年04月21日
    浏览(84)
  • 算法——动态规划(DP)——递推

    动态规划常用于解决优化问题。 动态规划通常以自底向上或自顶向下的方式进行求解。 自底向上的动态规划从最简单的子问题开始,逐步解决更复杂的问题,直到达到原始问题。 自顶向下的动态规划则从原始问题出发,分解成子问题,并逐步求解这些子问题。 动态规划算法

    2024年01月20日
    浏览(54)
  • 算法:分治思想处理快排递归以及快速选择/最小K个数问题

    分治的原理就是分而治之,从原理上讲,就是把一个复杂的问题划分成子问题,再将子问题继续划分,直到可以解决 基于分治的原理进行快速排序,区别于传统的快速排序,这里对快速排序进行改良,成为更优先的三路划分算法,可以处理一些极端场景,使快速排序的适用性

    2024年02月10日
    浏览(51)
  • 【Algorithm】动态规划和递归问题:动态规划和递归有什么区别?如何比较递归解决方案和它的迭代版本?

    动态规划(Dynamic Programming,DP)和递归(Recursion)是解决复杂问题的两种不同方法,它们在计算机科学中常用于解决具有重叠子问题和最优子结构特性的问题。 1.1 递归 (Recursion)定义及优缺点 递归是一种通过将问题分解为更小的子问题来解决问题的方法。在递归中,一个函数

    2024年03月17日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包