基本算法思想

亦凉 2022-10-07 11:56 193阅读 0赞

# 3. 基本算法思想 #

## 3.1 常用算法思想概述 ##

常用算法分类：

*  穷举算法思想
 *  递推算法思想
 *  递归算法思想
 *  分治算法思想
 *  概率算法思想

## 3.2 穷举算法思想 ##

### 3.2.1 穷举算法基本思想 ###

穷举算法的基本思想就是从所有可能的情况中搜索正确的答案，其执行步骤如下∶

1.  对于一种可能的情况，计算其结果。
2.  判断结果是否满足要求，如果不满足则进行执行第（1）步来搜索下一个可能的情况; 如果满足要求，则表示寻找到一个正确的答案。

在使用穷举算法时，需要明确问题的答案的范围，这样才可以在指定范围内搜索答案。指定范围之后，就可以使用循环语句和条件判断语句逐步验证候选答案的正确性，从而得到需要的正确答案。

### 3.2.2 穷举算法实例 ###

> 鸡兔同笼

**今有鸡兔同笼，上有三十五头，下有九十四足，问鸡兔各几何?**

这个问题的大致意思是;在一个笼子里关着若干只鸡和若干只兔，从上面数共有35 个头; 从下面数共有 94 只脚。问笼中鸡和兔的数量各是多少?

示例代码：

public class ChickenAndRabbit { 
    
        static int chicken, rabbit;
    
        /** * 穷举算法 * @param head 头的个数 * @param foot 脚的个数 * @return 0：无法匹配到相应的值；1：计算成功 */
        public static int exhaustion(int head, int foot) { 
            int result = 0;
            int i, j;
            for (i = 0; i < head; i++) { 
                j = head - i;
                if (i * 2 + j * 4 == foot) {      // i表示鸡的个数；j表示兔的个数
                    chicken = i;
                    rabbit = j;
                    result = 1;
                }
            }
            return result;
        }
    
        public static void main(String[] args) { 
            int flag = exhaustion(35, 94);
            if (flag==1){ 
                System.out.println("鸡有：" + chicken + "\n兔有：" + rabbit);
            }else { 
                System.out.println("无法匹配到相应的值!!!");
            }
        }
    
    }

## 3.3 递推算法思想 ##

### 3.3.1 递推算法基本思想 ###

递推算法是一种理性思维模式的代表，其根据已有的数据和关系，逐步推导而得到结果。递推算法的执行过程如下∶

1.  根据已知结果和关系，求解中间结果。
2.  判定是否达到要求，如果没有达到，则继续根据已知结果和关系求解中间结果;如果满足要求，则表示寻找到一个正确的答案。

递推算法往往需要用户知道答案和问题之间的逻辑关系。在许多数学问题中，都有着明确的计算公式可以遵循，因此往往可以采用递推算法来实现。

### 3.3.2 递推算法实例 ###

**13世纪意大利数学家斐波那契的《算盘书》中记载了兔子产仔问题。**

如果一对两个月大的兔子以后每一个月都可以生一对小兔子，而一对新生的兔子出生两个月后才可以生小兔子。也就是说，1月份出生，3月份才可产仔。那么假定一年内没有产生兔子死亡事件，那么1年后共有多少对兔子呢?

#### 分析 ####

第一个月：1对兔子；A  
第二个月：1对兔子；A  
第三个月：2对兔子；A，B  
第四个月：3对兔子；A，B，C  
第五个月：5对兔子；A，B，C，D，E

第n月的兔子F n \_\{n\} n = F n − 2 \_\{n-2\} n−2 \+ F n − 1 \_\{n-1\} n−1  
前两个月的兔子加上前一个月的兔子

实例代码如下：

public class BunnyGivesBirth { 
    
        /** * 递推 * @param n 月数 * @return */
        public static int recursion(int n){ 
            int m1,m2;  //m1:前一个月的数量，m2：前两个月的数量
    
            if (n ==1 || n == 2){ 
                return 1;
            }else{ 
                // 递归调用
                m1 = recursion(n-1);
                m2 = recursion(n-2);
                return m1 + m2;
            }
        }
    
        public static void main(String[] args) { 
            int n = 12*3;
            System.out.println("经过" + n + "月，兔子有：" + recursion(n)+"对");
        }
    }

## 3.4 递归算法思想 ##

### 3.4.1 递归算法基本思想 ###

递归调用是一个方法在其方法体内调用其自身的方法调用方式。这种方法也称为"递归方法”在递归方法中，主调方法又是被调方法。执行递归方法将反复调用其自身。每调用一次就进入新的一层。

方法的递归调用分两种情况∶

*  直接递归，即在方法中调用方法本身。
 *  间接递归，即间接地调用一个方法，如 func\_a 调用 func\_b，func\_b 又调用 func\_a。间接递归用得不多。

编写递归方法时，必须使用 if语句强制方法在未执行递归调用前返回。如果不这样做，在调用方法后，它将永远不会返回，这是一个很容易犯的错误。

> 优点

程序代码更简洁清晰，可读性更好。有的算法用递归表示要比用循环表示简洁精练，而且某些问题，特别是与人工智能有关的问题，更适宜用递归方法，如八皇后问题、汉诺塔问题等。有的算法，用递归能实现，而用循环却不一定能实现。

> 缺点

大部分递归例程没有明显地减少代码规模和节省内存空间。递归形式比非递归形式运行速度要慢一些。这是因为附加的方法调用增加了时间开销，例如需要执行一系列的压栈出栈等操作。但在许多情况下，速度的差别不太明显。如果递归层次太深，还可能导致堆栈溢出。

### 3.4.2 递归算法实例 ###

**求阶乘**  
对于n的阶乘：

n! = n*(n-1)*(n-2) * ......* 2* 1

对于n-1的阶乘：

(n-1)! = (n-1) * (n-2)* ......* 2* 1

示例代码如下：

public class FactorialDemo { 
    
        public static int fact(int n) { 
            if (n <= 1) { 
                return 1;
            } else { 
                // 递归调用
                return n * fact(n - 1);
            }
        }
    
        public static void main(String[] args) { 
            int x = 14;
            System.out.println(x + "的阶乘为：" + fact(x));
        }
    }

## 3.5 分治算法思想 ##

### 3.5.1 分治算法基本思想 ###

分治算法的基本思想是将一个计算复杂的问题分为规模较小，计算简单的小问题求解，然后综合各个小问题，而得到最终问题的答案。  
分治算法的执行过程如下∶

1.  对于一个规模为 N 的问题，若该问题可以容易地解决（比如说规模N 较小），则直接解决;否则执行下面的步骤。
2.  将该分解为 M个规模较小的子问题，这些子问题互相独立，并且与原问题形式相同。（3）递归地解这些子问题。
3.  然后，将各子问题的解合并得到原问题的解。

使用分治算法需要待求解问题能够化简为若干个小规模的相同问题，通过逐步划分，能够达到一个易于求解的阶段而直接进行求解。然后，程序中可以使用递归算法来进行求解。

### 3.5.2 分治算法实例 ###

**寻找假币问题**

操作步骤具体如下：

1.  首先为每个银币编号，然后可以将所有的银币等分为两份，放在天平的两边。这样就将区分 30 个硬币的问题，变为区别两堆硬币的问题。
2.  因为假银币的分量较轻，因此天平较轻的一侧中一定包含假银币。
3.  再将较轻的一侧中的硬银币等分为两份，重复上述的做法。
4.  直到剩下两枚硬银币，可用天平直接找出假银币来。

示例代码如下：

public class DivideAndRuleDemo { 
    
        public static int divide(int[] arr, int begin, int end) { 
            int i = 0;
            int resultIndex = 0;
            int sumBegin = 0, sumEnd = 0, sum = 0;
            if (begin + 1 == end) { 
                if (arr[begin] < arr[end]) { 
                    resultIndex = begin + 1;
                    return resultIndex;
                } else { 
                    resultIndex = end + 1;
                    return resultIndex;
                }
            }
            if ((end - begin + 1) % 2 == 0) { 
                // 偶数个
                // 前半段
                for (i = begin; i <= begin + ((end - begin) / 2); i++) { 
                    sumBegin += arr[i];
                }
                // 后半段
                for (i = begin + ((end - begin) / 2) + 1; i <= end; i++) { 
                    sumEnd += arr[i];
                }
                if (sumBegin > sumEnd) { 
                    resultIndex = divide(arr, begin + ((end - begin) / 2) + 1, end);
                } else if (sumEnd > sumBegin) { 
                    resultIndex = divide(arr, begin, begin + ((end - begin) / 2));
                    return resultIndex;
                }
            } else { 
                // 奇数个
                // 前半段
                for (i = begin; i <= begin + ((end - begin) / 2) - 1; i++) { 
                    sumBegin += arr[i];
                }
                // 后半段
                for (i = begin + ((end - begin) / 2) + 1 + 1; i <= end; i++) { 
                    sumEnd += arr[i];
                }
                // 中间的一个值
                sum = arr[begin + ((end - begin) / 2)];
    
                if (sumBegin > sumEnd) { 
                    resultIndex = divide(arr, begin + ((end - begin) / 2) + 1, end);
                } else if (sumEnd > sumBegin) { 
                    resultIndex = divide(arr, begin, begin + ((end - begin) / 2) - 1);
                    return resultIndex;
                }
    
                if (sumEnd + sum == sumBegin + sum) { 
                    resultIndex = begin + ((end - begin) / 2) + 1;
                    return resultIndex;
                }
            }
            return resultIndex;
        }
    
        public static void main(String[] args) { 
            int len = 100;
            int index = new Random().nextInt(100);
            int value = new Random().nextInt(100);
            int[] arr = new int[len];
            for (int i = 0; i < len; i++) { 
                arr[i] = value;
            }
    
            arr[index] = value - 1;
    
            int result = divide(arr, 0, len - 1);
            System.out.println(index+1);
            System.out.println(result);
        }
    }

## 3.6 概率算法 ##

### 3.6.1 概率算法基本思想 ###

概率算法执行的基本过程：

1.  将问题转化为相应的几何图形 S，S 的面积是容易计算的，问题的结果往往对应几何图形中某一部分S1 的面积。
2.  然后，向几何图形中随机撒点。
3.  统计几何图形S中和 S1中的点数。根据 S 的面积和 S1 面积的关系以及各图形中的点数来计算得到结果。
4.  判断上述结果是否在需要的精度之内，如果未达到精度则进行执行步骤（2）。如果达到精度，则输出近似结果。

概率算法大致分为如下4 种形式∶

*  数值概率算法;
 *  蒙特卡罗（Monte Carlo）算法;
 *  拉斯维加斯（Las Vegas）算法;
 *  舍伍德（Sherwood）算法;

### 3.6.2 概率算法实例 ###

> 蒙特卡罗π算法思想

一个半径为1的圆，如下图所示：

![在这里插入图片描述][20210618004711767.png_pic_center]

圆的面积公式如下：  
![在这里插入图片描述][20210618004540820.png_pic_center]

阴影面积公式如下：  
![在这里插入图片描述][20210618004624928.png_pic_center]  
正方形的面积为：  
![在这里插入图片描述][20210618004737134.png_pic_center]

这样，按照图示建立一个坐标系。如果均匀地向正方形内撒点，那么落入阴影部分的点数与全部的点数之比应该就是;  
![在这里插入图片描述][20210618004801101.png_pic_center]

通过这个原理，就可以计算圆周率的近似值。

蒙特卡罗算法计算规律：

*  均匀撒点;在C语言中可以使用随机方法来实现，产生\[0,1\]之间随机的坐标值\[x,y\]。
 *  区域判断：图中阴影部分的特点是距离坐标圆点的距离小于等于1，这样通过计算判断x 2 ^\{2\} 2\+y 2 ^\{2\} 2 ≤ 1来实现。

实例代码如下：

public class MonteCarloDemo { 
    
        public static double monteCarlPI(int n) { 
            double PI;
            double x, y;
            int i, sum = 0;
    
            for (i = 0; i < n; i++) { 
                x = Math.random();        // 产生一个0~1之间的随机数
                y = Math.random();
    
                if ((Math.pow(x, 2) + Math.pow(y, 2)) <= 1) { 
                    sum++;      // 计数
                }
            }
            PI = 4.0 * sum / n;
            return PI;
        }
    
        public static void main(String[] args) { 
            int n = 10000 + new Random().nextInt(10000);
            double pi = monteCarlPI(n);
            System.out.println("撒点次数：" + n + "\nPI：" + pi);
        }
    }

[20210618004711767.png_pic_center]: /images/20221005/c2904f949ce74f3e9613a83c348c7674.png
[20210618004540820.png_pic_center]: /images/20221005/89e3757a01834848b1d92a46ce767ecb.png
[20210618004624928.png_pic_center]: /images/20221005/f3f81e70c71e47b899962b4933ac44d5.png
[20210618004737134.png_pic_center]: /images/20221005/bb653f880df94d278c02678832c00aab.png
[20210618004801101.png_pic_center]: /images/20221005/0bd9c657be4541ac99cd89acbb46cd8b.png