C语言编程题（六）分治算法

怼烎@ 2022-10-28 13:25 178阅读 0赞

> ***敌人太多，我们要学会逐个瓦解***  
>                                                                                       – **沃兹基硕得**

在面对一些算法问题的时候，往往会觉得规模较大，直接从全局出发很难把握。这个时候如果能够将一个大问题划分成几个小问题，进行逐个击破，最后难题的解决也就水到渠成。

*  分治思想的第一步是**分**，如何将一个规模为n的问题拆分成有限个子问题。这里的子问题要满足的条件是，首先规模需要减小，第二子问题之间不能有重合的部分，即子问题之间不能够有纠缠。
 *  第二步，就是**治**，子问题拆分的最后结果就是能够直接解决，否则程序永远不会有出口。

下面的几道编程题有助于体会分治法的精髓

#### 计算n！ ####

分治算法的思想往往与递归有很大的联系，许多问题用递归的方法解决十分简洁。这是因为，递归函数通过调用自身，可以不断使得问题的规模减小，而递归出口往往就是分治算法中子问题能够直接解决的情况。

对于本题而言，计算n！可以拆成 （n - 1）! \* n,即只需要 (n - 1)!就能够得到n！，同理问题的规模还可以继续缩小，直到n = 0.  
我们可以写出递归式 F(n) = F(n - 1) \* n,该递归式表明可以将原问题拆解成规模为1的子问题。

long Fn(int n)
    { 
    	if(n == 0)
    	 	return 0;
    	 return Fn(n - 1) * n;
    }

阶乘的分治算法实际上通过每次递归将问题规模减小1，最后由规模为1的子问题倒推回规模为n的原问题。

#### 斐波那契数列 ####

F1 = 1,  
F2 = 2  
Fn = Fn -1 + Fn-2

这个数列的递归式天然就是一个分治算法，要想知道第n项的和，那么就必须知道两个子项的值，两个子项比原项规模减小，且Fn-1的值与Fn-2无关，只与n有关。

long Fibonacci(int n)
    { 
    	if(n == 1 || n == 2)
    		return 1;
    	return Fibonacci(n - 1) + Fibonacci(n - 2);
    }

#### 全排列算法问题 ####

正整数1 ~ n，求n个数的全排列，并且按照字典顺序从小到大输出。

这题如果没接触过分治算法可能脑子一团乱麻。  
现在想象桌子上摆了正整数1 ~ n的卡牌，我们要将可能的序列从小到大依次摆出来。毫无疑问，应该首先选择1对应的卡片放在第一个位置，然后从剩下的卡片中选出最小的。  
假设以1打头的序列都被摆完了，那么下一个序列第一张牌毫无疑问选择2，依次类推。

通过这个模拟可以发现，全排列必定包括n组不重复的序列，每组的开头从1到n，也就是说规模为n的全排列问题可以分成10个独立的子问题。每个子问题还可以分成9个独立的子问题，直到10张卡片都被分完。

下面我们尝试用伪代码来表达一下思路  
全排列（问题规模 n）：  
当n== 0时，卡片已经分完直接返回；  
当n != 0时，依次将当前剩下的n张牌放在首位，拆分成n个子问题，递归函数。

将上述思路用代码实现时会遇到一个很重要的问题，当n不等于0时，如何直到当前问题中哪些牌已经被用过了，即剩下的牌堆还有什么牌？  
现实生活中我们可以直接看到哪些牌用掉了，哪些还需要继续排列，而在计算机中这种信息就需要被保留下来。可以使用一个bool类型的数组，下标对应各个正整数。当某个正整数被使用掉了，就将对应数组中的值置为true，下次就不应当挑选了。  
此外为了查看全排列结果，声明一个数组，在每次确定一张卡片的位置时将它存到数组里。

#include <stdbool.h>
    #include <stdio.h>
    #define N 3
    bool flag[N + 1] = { false};
    int result[N + 1];
    int count = 1;
    void full_sort(int);
    int main()
    { 
    
        full_sort(N);
        return 0;
    }
    void full_sort(int n)
    { 
        if(n == 0)
        { 
            for(int i = 1;i <= N;i++)
                printf("%d ",result[i]);
            putchar('\n');
            return;
        }
        for(int i = 1;i <= N;i++)
        { 
            if(!flag[i])
            { 
                result[count++] = i;
                flag[i] = true;
                full_sort(n - 1);
                flag[i] = false;
                count--;
            }
        }
    }

下面详细分析下这个程序

*  定义的明示变量N表示 这次求的全排列是正整数 1 ~ N
 *  flag数组用来表示每个下标对应的正整数有没有在排列中被用掉，因为下标0不用，所以长度是N + 1
 *  result数组用来存取当前全排列序列，用于打印
 *  count是下标，标识当前全排列数组存取到哪一位了
 *  当n = 0的时候，此时没有数字待排列，将数组中的值全部打印出来
 *  当n != 0时，从小到大检测1到N中的整数，只要没被用过，就加入到全排列中，并将标记数组中对应的数字标记为已用过，执行子问题。子问题执行完以后，将标记位释放，下次全排列这个数字又可以用了。这里可以把flag看成一把锁，递归层次每增加一层就将一位数字锁住，当函数返回时，就将这位数字解锁。

#### n皇后问题 ####

在一个n \* n的国际象棋棋盘上放置n个皇后，使得这n个皇后，不在同一列，同一行，同一对角线，求方案的合法数。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70]  
a)是合法方案，b)不是合法方案

考虑第一种暴力求解的算法。试遍棋盘上每一个点（可以用对称性来简化），扫描棋盘上每一个点，直至找到可以落子的点，再找下一个点，如果最终找到的棋子数为n，就是合法方案。  
首先试遍棋盘上每一个点就是n2的规模，每次落子扫描棋盘又是n2的规模，每次还要落n次子，算法复杂度为n5,几乎没有任何使用价值。

初学者可能会有这个问题，现在每种方案是要找n个落子的位置，那可不可以向阶乘算法那样拆分成规模为1的子问题呢，求第n个落子的位置，先求第n - 1落子的位置。。。先求第一个落子的位置，然后通过递归算法的回退来推导呢？  
一开始看似乎有些道理，但是其实这种算法并不符合分治的条件。因为拆分的子问题并不是相互独立的，第n - 1次落子是要影响第n次落子的，函数在回退的时候该怎么统一处理呢？阶乘算法对于每次回退的处理都是一致的，即子问题之间互相独立。

让我们换一种思路，在设计一个算法之前要充分利用一些背景信息，这些信息往往可以节省大量的算法步骤。

*  每一行，每一列都有一个棋子，当我们从第一列看到最后一列，可以得到行号的一个排列序列。
 *  可以先求所有行号的全排列序列，一一代回去验证是否每一个棋子在对角线上没有另一个棋子
 *  棋子只要列号的差值和行号的差值不等，那么就不在一条对角线上。

#include <stdio.h>
    #include <stdbool.h>
    #include <math.h>
    #define N 8
    bool flag[N + 1] = { false};
    int result[N + 1];
    int count = 0,pointer = 1;
    bool is_ok();
    void full_sort(int n)
    { 
        if(n == 0)
        { 
          if(is_ok())
              count++;
          return;
        }
        for(int i = 1; i<= N;i++)
        { 
            if(!flag[i])
            { 
                result[pointer++] = i;
                flag[i] = true;
                full_sort(n - 1);
                flag[i] = false;
                pointer--;
            }
        }
    }
    int main()
    { 
        full_sort(N);
        printf("count:%d\n",count);
        return 0;
    }
    bool is_ok()
    { 
        for(int i = 1;i < N;i++)
        { 
            for(int j = i+1;j <= N;j++)
            { 
                if(abs(j - i) == abs(result[i] - result[j]))
                    return false;
            }
        }
        return true;
    }

实际上只是在将打印全排列序列换成了判断是否有棋子在同一对角线上。

#### 神奇的口袋 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 1]  
本题有多种解法，接下来介绍两种递归版的和一种非递归版的。

##### 解法一 #####

介绍解法一之前需要先给出一个引例  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 2]  
假设最后一天吃了N块巧克力的最后一块，对应的是前段时间吃了N - 1块巧克力的情况，假设最后一天吃了N块巧克力的最后两块，对应的是前段时间吃了N - 2 块巧克力的情况。  
由上分析可得，设吃N块巧克力的方案数是An,则An = An-1 \+ An-2  
这是经典的斐波那契数列，当n = 1时，只有一种方案即A1 = 1,当n = 2时，A2 = 2。

引例给出以后再看下神奇的口袋这道题目。  
假设一种由n种物品给我们挑选，在选择第n种物品时，我们有两种选择，一种是选了第n种物品的方案数，另一种是不选第n种物品的方案数。

#include<stdio.h>
    #define N 40
    int a[N];
    int bag(int,int);
    int main()
    { 
    	int n,count;
    	scanf("%d",&n);
    	for(int i = 0;i < n;i++)
    		scanf("%d",&a[i]);
    	count = bag(40,n);
    	printf("count:%d\n",count);
    	return 0;
    }
    int bag(int weight,int n)
    { 
    	if(weight == 0)
    		return 1;
    	else if(n < 1 || weight < 0)
    		return 0;
    	return bag(weight,n - 1) + bag(weight - a[n - 1],n - 1);
    }

选择了第n个物体，则把其重量在总重量上减去即可。

##### 解法二 #####

解法二与全排列问题的思想类似，全排列是要找出全部的排列方案，而这道题目是组合问题，先看代码。

#include <stdio.h>
    #include <stdbool.h>
    #define N 40
    bool flag[N] = { false};
    int a[N];
    int sum = 0;
    int count = 0;
    void bag(int,int);
    int main()
    { 
        int n;
        scanf("%d",&n);
        for(int i = 0;i < n;i++)
            scanf("%d",&a[i]);
        bag(0,n);
        printf("count:%d",count);
        return 0;
    }
    void bag(int index,int n)
    { 
        if(sum >= 40)
        { 
            if(sum == 40)
                count++;
            return;
        }
        for(int i = index;i < n;i++)
        { 
            if(!flag[i])
            { 
                sum += a[i];
                flag[i] = true;
                bag(i + 1,n);
                flag[i] = false;
                sum -= a[i];
            }
        }
    }

与全排列算法最大的不同是，bag函数多了一个index参数。因为对于若干个数字的组合而言顺序是无所谓的，123，213在全排列中是两个满足条件的结果，而在组合中就是一样的了。所以利用index来调整首个数字，让其在子序列中不再出现。

##### 解法三（非递归版本） #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 3]  
按顺序从口袋中拿出物品，如果拿出的物品加上现有的重量小于40kg，则添加到已选队列中。如果大于40kg则跳过该物品。当选到最后一个物品不满足条件，则需要把现有队列中的最后一个去掉，如上图的例子，到达最后15的时候也不满足，则需要退回到20，并将20从已选物品中去除，从它的下一个物品30开始判断。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 4]  
恰好等于40，则方案数加一，对下一个物品进行判断。最终已选队列为空的时候，进入下一次循环，这次从第二个物体加入队列，第一个物体不再进行判断。因为有第一种物体的所有满足情况的方案都已经被找到。  
这其实就是分治算法的思想，第一次划分子问题，是包含第一个物体的可能情况和不包含第一个物体的可能情况。

现在不能借助递归来实现回溯，就需要借助栈的先进后出。

#include <stdio.h>
    #define N 40
    typedef struct Item
    { 
        int weight;
        int pos;
    }Item;
    int a[N];
    Item items[N];
    int main()
    { 
        int n,i,j;
        int count = 0;
        int top = -1;
        int sum;
        scanf("%d",&n);
        for(i = 0;i < n;i++)
            scanf("%d",&a[i]);
        for(i = 0; i < n;i++)
        { 
            if(a[i] == 40) { 
                count++;
                continue;
            }
            if(n == 1 || i == n -1)
                break;
            j = i + 1;
            items[++top].weight = a[i];
            items[top].pos = i;
            sum = a[i];
            while(top != -1)
            { 
                if(a[j] + sum == 40){ 
                    count++;
                }else if(a[j] + sum < 40 && j <n -1)
                { 
                    sum += a[j];
                    items[++top].weight = a[j];
                    items[top].pos = j;
                }
                j++;
                if(j >= n -1)
                { 
                    sum -= items[top].weight;
                    j = items[top].pos + 1;
                    top--;
                }
            }
        }
        printf("count:%d\n",count);
        return 0;
    }

结构体item中保存了元素的下标，在回溯的时候可以用到。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70]: /images/20221024/dfa98119e7fe4b90984d9f85b3d94f56.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 1]: /images/20221024/abfdf368897448f4937c1ccb897e3b21.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 2]: /images/20221024/e36bfa421db54ef4b9c4ad4b38339e31.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 3]: /images/20221024/ef1bdeb4af974071b417e4b78b579eb5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 4]: /images/20221024/2d2b4cba231f4b3f93fe0369d80bb3f3.png