分治算法的基本思想：先将整个问题拆分成多个相互独立且数据量更少的小问题，通过逐一解决这些简单的小问题，最终找到解决整个问题的方案。

所谓问题间相互独立，简单理解就是每个问题都可以单独处理，不存在“谁先处理，谁后处理”的次序问题。

分治算法

如上图所示，分治算法解决问题的过程分为三个阶段：

  1. 分：将整个问题划分成多个相对独立、涉及数据量更少的小问题，有些小问题还可以划分成很多更小的问题，直至每个问题都不可再分；
  2. 治：逐个解决所有的小问题；
  3. 合并：将所有小问题的解决方案合并到一起，找到解决整个问题的方案。

分治算法的经典应用

汉诺塔问题

  • 每次只能移动柱子最顶端的一个圆盘；

  • 每个柱子上，小圆盘永远要位于大圆盘之上；

汉诺塔问题

分治算法解决汉诺塔问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
internal class Program
{
    private static int i = 1; // 统计移动次数

    private static void Main(string[] args)
    {
        // Hanoi(圆盘个数，起始柱子，目标柱子，辅助柱子)
        Hanoi(3, 'A', 'B', 'C');
    }

    private static void Hanoi(int n, char sou, char tar, char aux)
    {
        if (n == 1) // 只有一个圆盘，直接从起始柱移动到目标柱
        {
            Console.WriteLine("第{0}次，从{1}移动到{2}", i, sou, tar);
            i++;
        }
        else
        {
            // 递归调用 Hanoi 方法，将 num-1 个圆盘从起始移动到辅助柱上
            Hanoi(n - 1, sou, aux, tar);
            Console.WriteLine("第{0}次，从{1}移动到{2}", i, sou, tar);
            i++;
            // 将辅助柱上的num-1圆盘移动到目标柱上
            Hanoi(n - 1, aux, tar, sou);
        }
    }
}

输出结果：

第1次，从A移动到B
第2次，从A移动到B
第3次，从C移动到B
第4次，从A移动到B
第5次，从C移动到B
第6次，从C移动到B
第7次，从A移动到B

寻找数组中最大最小值问题

查找数组（序列）中最大值或最小值的算法有很多

普通的迭代算法法求最大最小值

最大最小值问题_普通算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
internal class Program
{
    private static void Main(string[] args)
    {
        int n;
        n = Convert.ToInt32(Console.ReadLine());
        int[] a = new int[n];
        string? input = Console.ReadLine();
        // 通过空格分割输入的字符串
        string[] inputs = input?.Split(' ') ?? new string[0];
        for (int i = 0; i < inputs.Length; i++)
        {
            a[i] = int.Parse(inputs[i]);
        }
        GetMaxMin(a);
    }

    private static void GetMaxMin(int[] a)
    {
        int max = a[0], min = a[0];
        // 迭代对比，选出其中最大值和最小值存储起来
        for (int i = 1; i < a.Length; i++)
        {
            if (a[i] > max)
            {
                max = a[i];
            }
            if (a[i] < min)
            {
                min = a[i];
            }
        }
        Console.WriteLine("最大值为：" + max + "\n最小值为：" + min);
    }
}

输入：

4

3 7 2 1

输入结果：

最大值为：7
最小值为：1

分治算法求解

最大最小值问题_分治算法.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
internal class Program
{
    private static void Main(string[] args)
    {
        int n;
        n = Convert.ToInt32(Console.ReadLine());
        int[] a = new int[n];
        string? input = Console.ReadLine();
        // 通过空格分割输入的字符串
        string[] inputs = input?.Split(' ') ?? new string[0];
        for (int i = 0; i < inputs.Length; i++)
        {
            a[i] = int.Parse(inputs[i]);
        }
        Console.WriteLine("最大值为："GetMax(a, 0, n - 1));
    }

    private static int GetMax(int[] a, int left, int right)
    {
        int maxLeft = 0, maxRight = 0, middle = 0;
        // 如果数据为空
        if (a == null)
        {
            return -1;
        }
        // 如果比较的数据只剩下一个数
        if (right - left == 0)
        {
            return a[left];
        }
        // 如果比较的数据只剩下两个数
        // 则返回大的那个数
        if (right - left <= 1)
        {
            if (a[left] >= a[right])
            {
                return a[left];
            }
            return a[right];
        }
        // 取数组中间索引值
        middle = (right - left) / 2 + left;
        // 递归调用 GetMax 找到数组左边数据中的最大值
        maxLeft = GetMax(a, left, middle);
        // 递归调用 GetMax 找到数组右边数据中的最大值
        maxRight = GetMax(a, middle + 1, right);
        // 判断得到的左右两边最后返回的值的大小
        if (maxLeft >= maxRight)
        {
            return maxLeft;
        }
        else
        {
            return maxRight;
        }
    }
}

输入：

4

3 7 2 1

输入结果：

最大值为： 7