2.3.1分治法（算法导论学习）

递归：为了解决一个给定的问题算法一次或多次递归的调用其自身以解决紧密相关的若干子问题

好吧还是没太理解清楚是啥百度百科给的解释

程序调用自身的编程技巧称为递归（ recursion）。递归做为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

嗯我觉得有道理的一句是递归是一种程序调用自身的编程技巧（一种技巧）在于用有限的语句来定义对象的无限集合。。。
呃好玄不过也是这样子递归是一种while for 之类的循环比较高级（抽象的）循环语句可以说 while for 都可以用递归来同等的代替但是有的递归不太好用while for 循环代替尤其是过程比较抽象的时候比如汉诺塔问题。。。
好了递归先扯到这毕竟我也没比较认真的学到来说今天看到的重点

分治法

将原问题分解为几个规模较小但类似于原问题的子问题递归地求解这些子问题然后合并这些子问题的解
三个步骤
分解：分解原问题为若干子问题
解决这些自问题复杂就递归简单就去直接求解
合并这些子问题

举个例子归并排序

MergeSort(A,p,r) if p<r  q=(p+r)/2 MergeSort（A,p,q） MergeSort（A,q,r) Merge（A,p,q,r) Merge(A,p,q,r) n1=q-p+1 n2=r-q let L[1,n1+1] and R[1,n2+1] be new arrays for i=1 to n1 L[i]=A[p+i-1] for j=1 to n2 R[j]=A[q+j] L[n1+1]=无穷大 R[n2+1]=无穷大 i=1 j=1 for k=p to r if L[i]<R[j] A[k]=L[i] i++ else A[k]=R[j] j++

普及一下英语 merge 中文融合很好理解 merge的过程初始化一下把小的放入A中（注意 L R 都已经按升序排好了）ok
划重点分治法的三步骤划分解决合并在本算法里

分解：分解待排序的n个元素的序列成个具有n/2的两个子序列
解决：使用递归即调用自己来解决两个子序列
合并：调用merge 算法来合并两个排好序的子序列
当待排序序列的长度为一时开始递归“开始回升”，因为一个即排好序了

哇好强的感觉对了为了帮助自己理解递归的过程可以去画一个二叉树每一层为一种递归状态即参数的值是一样的环境下的但递归一下时就进入了下一层即往下面长出了一个树枝
上图

好的就是这样子啦
至于递归算法时间的分析其实蛮简单的数学过程不细讲了后面有章再说
看一下思考题 2.3-5
二分查找算法
上一下我自己写的有点繁琐

int binary_search(int *A, int a, int begin, int end)
{
    int mid = (begin + end) / 2;
    if (begin < end)
    {
        if (a > A[(begin + end) / 2])
            binary_search(A, a, mid, end);
        else if (a < A[mid])
            binary_search(A, a, begin, end);
        else if (a == A[mid])
            return mid;
    }
    else
    {
        if (a == A[mid])
            return mid;
        else
            return -1;
    }
}

呃看看官方的答案递归写的是这样子的

int RecursiveBinarySearch(int *A, int v, int low, int high)
{
    if (low > high)
        return -1;
    int mid = (low + high) / 2;
    if (v == A[mid])
        return mid;
    else if (v > A[mid])
        return RecursiveBinarySearch(A, v, mid + 1, high);
    else
        return RecursiveBinarySearch(A, v, low, mid - 1);
}

哇简介美啊啊啊啊
学习一下了
第一部分
判断递归终止的条件
第二部分解决问题
简单的情况 return mid
复杂的情况return 自身来解决
好了好了看另一种用while 循环来解决的

两相对比一下可以稍稍理解一下递归和while 循环的关系啦
为了加深一下子理解
第一个例子汉诺塔问题
关于这个例子有很多很多的人说了
懒得说了不过是没有归并步骤的分治法
第二个是书上的一个题2-4（逆序对）

啊第一二三问想一想就ok了不是难题
问题是第四问啥子意思想了好久还是看了答案
感觉关键在于修改归并排序由第三问的提示可以感觉到一些东西就是举个列子还是
有两堆牌对于第二堆牌来说无论第一堆牌的顺序是如何的第二堆相对第一堆的逆序对的个数是不会有变化的（所以将第一堆的牌安照升序排列一下不就更加方便了）而且假设在之前的递归途中第一二堆的逆序对个数已经求出来了那么此时只有还有将两堆合在一起的逆序对个数没有计算那么算法就顺理成章的出来了神奇
附图

inversions 逆序对的意思 count 计算
递归第一段循环判断 if 。。。
第二段就是拆分为两个部分分别求逆序对的个数
重点在于mergeInversions

其他都好说初始化呗
这里注意一下 counted 这个变量英文意思为数过的（数的过去式）
看循环是从 p到r
分情况第一没有数过而且左边的牌堆比右边的牌堆大即满足逆序对的要求注意另一点左右的牌堆已经排好序了。。所以 inversions是inversions （原有的）加上n1-i+1 即因为是排序的那么如果L[i]大于R[j] 那么L[i+n]大于L[i]即大于R[j]即对于R[j]来说有这么多个逆序对并且为啥要设置counted呢先存一下疑问一会上代码跑一下试试再说然后R[j]就没有利用价值了排序到A里然后
进行下一个循环
总结一下就是比较 L 与 R 里较小的那个然后如果L 小于 R 就把L写入A中如果R 小于L即找到了一组计算一下然后再把R 写入到A中 ojbk了
写下代码试试

int mergeInversions(int *A, int p, int q, int r)
{
    int n1 = q - p+1;//q-p 为 q与p中间间隔几个 +1 是算上q 即求从p到q有几个
    int n2 = r - q;//之所以不用加一是因为 n1已经包含了q 求r q间隔几个就ok了
    int *L = new int[n1+1];
    int *R = new int[n2 + 1];
    for (int i = 0; i < n1; i++)
        L[i] = A[p + i];//因为i是从0 开始的所以不用减一
    for (int i = 0; i < n2; i++)
        R[i] = A[q + i+1];//还是因为i 是从0开始的 又因为q已经包含于L里了所以加一
    L[n1] = INT_MAX;
    R[n2] = INT_MAX;
    int i = 0;
    int j = 0;
    int inversions = 0;
    for(int k=p;k<=r;k++)
        if (R[j] < L[i])
        {
            inversions = inversions + n1 - i;
            A[k] = R[j];
            j++;
        }
        else
        {
            A[k] = L[i];
            i++;
        }
    return inversions;
}
int  countInversions(int *A, int p, int r)
{
    int inversions = 0;
    if (p < r)
    {
        int q = (p + r) / 2;
        inversions = inversions + countInversions(A, p, q);
        inversions = inversions + countInversions(A, q + 1, r);
        inversions = inversions + mergeInversions(A, p, q, r);
    }
    return inversions;
}