算法中分治法实验总结

在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。

AM1ng’s Algorithm Blog！

实验题目：maximum number in a unimodal array（单峰数组中的最大数目）

算法描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

int biosearch( int a[],int left,int right)
{
    while(left<=right)//满足二分法的条件，同时可以用于判断二分法何时停止
    {
        int max=(left+right)/2; //二分法循环后缩小范围
        if(a[max]>a[max-1]&&a[max]>a[max+1])//max大于左右，即为峰值，符合目的
        {
            return max;

        }
        if(a[max]>a[max+1]&&a[max]<a[max-1])//max大于右边小于左边 最大值在right左边 从右往左缩小范围 更新右指针
        {
        right=max-1;
        }
    else{
        left = max+1;//同上理 最大值在left右边 从左往右缩小范围 更新左指针
        }
        
    }
    
}

More info: 二分法

分治法的个人体会和思考

分治法解释：面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

基本步骤：分解、求解子问题、合并。

思考：分治法很直观明了的让我们作为计算机系的学生去体会到了算法的意义和目的，联想到数据结构课上学的快排，二分法，堆排等算法，不难理解分治法其实早已穿插在以前的学习中。但是总的目的都是要对算法进行优化，寻找最优解，过程中要进行复杂度分析，不一定所有情况都必须用分治法或者分治法里是否还需要考虑最优解。

More info: 分治法

See U next time！