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

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

时间：2023-04-16 10:34:04浏览次数：45  
标签：Java 示例 int 兔子 return 算法 static 穷举 public


场景

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

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

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

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

一段代码来得到答案。

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

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

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

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

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

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

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

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

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

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

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

注：


实现

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中常用算法及示例-分治、迭代、递归、递推、动态规划、回溯、穷举、贪心_System_02

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元的。

所以贪心算法是一种在某种范围内，局部最优的算法。

标签：Java,示例,int,兔子,return,算法,static,穷举,public
From： https://blog.51cto.com/BADAOLIUMANGQZ/6193345

相关文章

  • Java中创建线程的方式以及线程池创建的方式、推荐使用ThreadPoolExecutor以及示例
    场景Java中创建线程的方式有三种1、通过继承Thread类来创建线程定义一个线程类使其继承Thread类，并重写其中的run方法，run方法内部就是线程要完成的任务，因此run方法也被称为执行体，使用start方法来启动线程。2、通过实现Runanle接口来创建线程首先定义Runnable接口，并重写Runnable接口......
  • Java面向对象编程中级
    IDEA常用快捷键删除当前行,默认是ctrl+Y自己配置ctrl+d复制当前行,自己配置ctrl+alt+向下光标补全代码alt+/添加注释和取消注释ctrl+/导入该行需要的类先配置autoimport,然后使用alt+enter即可快速格式化代码ctrl+alt+L快速运行程序自己定义alt+......
  • JavaScript运算符与表达式
    目录一、===二、||三、??与?.???.四、...五、[]{}[]{}一、===严格相等运算符，用作逻辑判断1==1 //返回true1=='1' //返回true，会先将右侧的字符串转为数字，再做比较1==='1' //返回false，类型不等，直接返回falsetypeof查看某个值的类型typeof1 //返回'number'ty......
  • JavaScript中 处理异步的几种方法
    1.回调函数回调（callback）是一个函数被作为一个参数传递到另一个函数里，在那个函数执行完后再执行。假定有两个函数f1和f2，f2等待f1的执行结果，f1()–>f2()；如果f1很耗时，可以改写f1，把f2（箭头函数）写成f1的回调函数：functionf1(callback){setTimeout(()=>{letname='小明'......
  • javaEE进阶小结与回顾(七)
    单元测试概述针对最小的功能单元(方法),编写测试代码对其进行正确性测试需要测试目前只能在main方法编写测试代码,去调用其他方法进行测试使用起来很不灵活,如果前面的方法测试有错,后面的方法就无法执行无法得到测试的报告,需要程序员自己去观察测试是否成功Jnuit单元测......
  • Java中的继承
    先看一段代码：classA{publicintx;}classB{publicvoidpri(){System.out.println(x);}}请问这时候调用x，可以得到值么？答案是否定的，因为x在A这个类当中，而这个A类和B类毫不相干，B类中没有x这个变量，所有代码会出现编译错误，但是通过继承，就可以访问的到A类里的x。......
  • java: 程序包org.springframework.web.bind.annotation不存在（已解决）
    今天在创建了一个新的SpringBoot模块后，和往常一样将文件从别的模块中复制过来，然后运行鑫模块就报错了：java:程序包org.springframework.web.bind.annotation不存在，第一反应是将文件所在的包Rebuild一下，但是这次并没有起到作用。然后就想着清除一下缓存，进行步骤：File-->Invalidat......
  • javascript基础练习
     本练习根据w3cschool:https://www.w3cschool.cn/javascript/javascript-conventions.html 1.javascript简介1.1JavaScript是脚本语言JavaScript是一种轻量级的编程语言。JavaScript是可插入HTML页面的编程代码。JavaScript插入HTML页面后，可由......
  • 8.for循环的场景示例
    1.通过一个文件，进行批量创建用户   1.for循环根据文件内容进行取值   2.判断该用户是否存在，存在则提示已存在，无需创建   3.不存在则创建   4.提示创建结果    2.根据读入文件内容，进行批量创建用户，user:pass      3.批量创建用......
  • Java NIO
       Server服务端importjava.io.IOException;importjava.net.InetSocketAddress;importjava.nio.ByteBuffer;importjava.nio.channels.SelectableChannel;importjava.nio.channels.SelectionKey;importjava.nio.channels.Selector;importjava.nio.channels.Ser......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99