常用的十种算法

2021-08-12

常用的十种算法

1.二分查找算法

二分查找有两种思想：一种是递归的思想，另一种是非递归的思想。

递归：

static int binarySearch(int[] arr,int start,int end,int target){
        //方法一：使用递归的方式
        //递归的方式就是首先找到中间位置，如果大于，那么往前找，否则往后找
        if (start <= end){
            int mid = (start + end) / 2;
            if (arr[mid] == target){
                return mid;
            }else if (target > arr[mid]){
                return binarySearch(arr,mid + 1,end,target);
            }else if (target < arr[mid]){
                return binarySearch(arr,start,mid - 1,target);
            }
        }
        return -1;
    }

非递归：

static int binarySearch1(int target,int[] arr){
        int start = 0;
        int end = arr.length - 1;
        while (start <= end){
            int mid = start + (end - start) / 2;
            if (target < arr[mid]){
                end = mid - 1;
            }else if (target > arr[mid]){
                start = mid + 1;
            }else {
                return mid;
            }
        }
        return -1;
    }

2.分治算法

分治算法的思想是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或者相似的子问题，再把子问题分成更小的子问题...直到最后子问题可以简单地直接求解，原问题的解即为子问题的解的合并。

分治算法的基本步骤 1.分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题 2.解决：将子问题规模较小而容易被解决则直接解，否则递归地解各个子问题 3.将各个子问题的解合并为原问题的解

eg. 汉诺塔问题 1) 如果是有一个盘，A->C 如果我们有n>=2的情况，我们总是可以看做是两个盘：1.最下边的盘 2.上面的盘

1.先把最上面的盘A->B 2.把最下边的盘A->C 3.把B塔所有的盘从B->C

代码：

package DividedandConquer;

/**
 * Created with IntelliJ IDEA.
 *
 * @Auther: ChrisPeng
 * @Date: 2021/08/12/10:26
 * @Description: 分治算法解决汉诺塔问题
 */
public class Demo {
    public static void main(String[] args) {
        hanoTower(5,'A','B','C');
    }
    //汉诺塔的移动方案
    //使用分治算法

    public static void hanoTower(int num,char a,char b,char c){
        //如果只有一个盘
        if (num == 1){
            System.out.println("第1个盘从"+a+"->"+c);
        }else {
            //如果我们有n>=2的情况，我们总是可以看做是两个盘，一个是最下边的盘，加上上面所有的盘
            //1.先把最上面所有的盘A->B,移动过程用到c
            hanoTower(num - 1,a,c,b);
            //2.把最下边的盘A->C
            System.out.println("第"+num+"个盘从"+a+"->"+c);
            //把B塔的所有盘B->C，移动过程中使用到A盘
            hanoTower(num - 1,b,a,c);
        }
    }
}

3.动态规划算法

简要介绍 1.动态规划算法的核心是：将大问题划分为小问题进行解决，进而一步步获取最优解的处理算法 2.动态规划算法与分治算法类似，其基本思想也是将待求解问题分解为若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 3.与分治算法不同的是，适用于用动态规划求解的问题，经分解得到子问题往往不是相互独立的，即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解。 4.动态规划可以通过填表的方式来逐步求解最优解。
动态规划解决背包问题算法主要思想：每次遍历到的第i个物品，根据w[i]和v[i]来确定是否需要将该物品放入背包中。即对于给定的n个物品，设v[i]、w[i]分别为第i个物品的价值和重量，C为背包的容量。再令v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值。则我们有下面的结果： (1)v[i][0] = v[0][j] = 0//表示填入表第一行和第一列是0 (2)当w[i] > j时：v[i][j] = v[i - 1][j]//当准备加入新增的商品的容量大于当前背包的容量时，就直接使用上一个单元格的装入策略 (3)当j>=w[i]时：v[i][j] = max{v[i - 1][j],v[i - 1][j - w[i]] + v[i]}

4. hungry算法

一共有n项任务，对应n个人承担，应该指派哪个人完成哪项任务使得完成效率最高。

指派问题的一般的模型：（特殊的0-1规划问题）

hungry算法的条件：（1）目标函数求最小值；（2）人数和任务数相等；（3）效率非负。

算法的本质：变换系数矩阵，找到n个不同行不同列的0元素，以求解指派问题的最优解。