目录

一、递归的概念

二、分治法的基本思想

三、分治策略范例

（1）二分搜索

（2）大整数乘法

（3）Strassen矩阵乘法

（4）棋盘覆盖

（5）合并排序和快速排序

（6）线性时间选择

（7）最接近点对问题

（8）循环赛日程表

一、递归的概念

递归算法：直接或间接地调用自身的算法

递归函数：用自身函数给出定义的函数

（边界条件、递归方程）

//例题1：阶乘函数
int factorial(int n)
{
  if(n==0)
    return 1;
  return n*factorial(n-1);
}

//例题2：Fibonacci数列
int fibonacci(int n)
{
   if(n<=1)
     return 1;
   return fibonacci(n-1)+fibonacci(n-2);
}

//例题3：排列问题
template<class Type>
void Perm(Type list[], int k, int m)
{
    if (k == m)
    {
        for (int i = 0; i <= m; i++)
        {
            cout << list[i];
        }
        cout << endl;
    }
    else
    {
        for (int i = k; i <= m; i++)
        {
            Swap(list[k], list[i]);
            Perm(list, k + 1, m);
            Swap(list[k], list[i]);
        }
    }
}
template<class Type>
inline void Swap(Type& a, Type& b)
{
    Type temp = a;
    a = b;
    b = temp;
}

//例题4：整数划分问题
int q(int n, int m)
{
    if ((n < 1) || (m < 1))
        return 0;
    if ((n==1) || (m==1))
        return 1;
    if (n < m)
        return q(n, n);
    if (n==m)
        return q(n, m-1)+1;
    return q(n, m - 1) + q(n - m, m);

}

//例题5：Hanoi问题
void hanoi(int n, int a, int b, int c)
{
    if (n > 0)
    {
        hanoi(n - 1, a, c, b);
        move(a, b);
        hanoi(n - 1, c, b, a);
    }
}

二、分治法的基本思想

设计思想：将一个难以直接解决的大问题分割成一些规模较小的相同问题，各个击破，分而治之。

适用条件:

1、该问题的规模缩小到一定的程度就可以容易地解决

2、该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

3、利用该问题分解出的子问题的解可以合并为该问题的解；

4、该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

递归式：

T(N) = a*T(N / b) + O (N^d)

条件	时间复杂度
log(b,a) < d	O(N ^ d)
log(b,a) > d	O(N ^ log(b,a))
log(b,a) = d	O((N^d) * logN)

三、分治策略范例

（1）二分搜索

（2）大整数乘法

（3）Strassen矩阵乘法

（4）棋盘覆盖

（5）合并排序和快速排序

（6）线性时间选择

（7）最接近点对问题

（8）循环赛日程表