Boil's Blog HomeArchivesTagsCategories
递归第二讲
Word count: 1.6k|Reading time: 6 min

分治法的基本步骤

递归地求解问题，在每层递归中应用三个步骤：

  1. 分解(Divide)：将问题划分为一些子问题。子问题的形式与原问题一样，只是规模更小；

  2. 解决(Conquer)：递归地求解子问题。若子问题规模较小而容易被解决则直接求解，否则递归地解各个子问题；

  3. 合并(Combine)：将子问题的解合并成原问题的解。

分治法的适用条件

分治法所能解决的问题一般具有以下几个特征：

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

  2. 该问题可以分解为若干个规模较小的相同问题；

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

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

分治法的设计模式

divide-and-conquer(P)

{

if ( | P | <= n0) adhoc(P); //解决小规模的问题，递归出口

divide P into smaller subinstances P1,P2,…,Pk；//分

for (i=1; i<=k; i++)

​ yi=divide-and-conquer(Pi); //递归的解各子问题，治

return merge(y1,…,yk); //将各子问题的解合并为原问题的解，合

}

分治法与减治法

​ 有些作者考虑“分治法”这个名称应只用于最少有两个子问题的算法。而只有一个子问题的曾被建议使用减治法这个名称。

​ 减治法：它利用了一个问题给定实例的解和同样问题较小实例的解之间的关系。

减一个常量

（通常减1）

减一个常因子

（减去因子2，折半查找）

减可变规模

（欧基几得算法，gcd(m,n)=gcd(n,m mod n)）

二分搜索技术

1
2
3
4
5
6
7
8
9
10
11
template<class Type> 
int BinarySearch(Type a[], const Type& x, int n)
{      int left=0; int right=n-1;
        while (left<= right){ 
             int middle = (left+right)/2;
             if (x == a[middle]) return middle;
             if (x > a[middle]) left = middle+1; 
             else right = middle-1;
             }
    return -1;    //未找到x
}

分治法的复杂性分析（主定理）及其应用

参考网址：https://www.cnblogs.com/oier/p/9454539.html

网站已在本地备份

算法分析题2-2

题目见教材，这里不再给出

题1

这里错误的地方在于左右断游标left,right调整不正确，应该是mid-1和mid+1，否则会出现死循环，如只有两个数时，第一个数不是要找的，但每次mid始终是第一个数并在下一次中还是端点，导致死循环

题2

这里和上面一样左右端不正确，并且无法比较到a[n-1]这个元素

题3

和上题问题一样

题4

和题1一样的错误

题5

算法正确，并且当数组中有重复元素时，返回满足条件的最右元素

题6

与题2一样的错误

题7

左右调整不正确，并且当x=a[0]时陷入死循环

有重复元素的排列问题(homework)

题目大意

当元素有重复时的全排列问题，输出个数以及每一种方案

实现思路

首先说全排列的思路，这边其实和dfs先放再收的操作有点像，我们每次都假定前几个是确定的，后几个是不确定的，带排列的，如果前几个确定，那么我们在前几个这样的条件下排列总数就是后几个的排列数。我们每次定好未确定区的左边界（显然开始所有都是未确定的），那么第一个元素就与包括本身在内的所有元素进行交换，那么交换完之后这个地方就是确定了，接着左边界就要向右挪一位，以此往复。先放再收在哪？每次交换完，向下延展完之后再换回来，以便于下一次递归穷举。再说说去重，这里的策略是，如果这个数与除本身外的从不定区左端到这个数的这些数存在重复，那么左端点就不再与他交换（这里的原因通俗讲就是对于即将变为确定区的这个左端点来说，两个重复的对他来说一样，虽然不同的位置交换过来会导致后面不一样，但是由于后面是不定区，既然还不确定就不会产生影响）

实现细节

记得在判断重复时要把自己去掉

实现代码

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//
//  Second homework of Algorithm Designing and Analyzing in spring semester, 2020
//
//  Author:
//      Yihang Bao
//      2018011890
//  Created by Yihang Bao on 2020/3/11.
//
//
#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));
int sum;
template<class Type>
void permut_repeat(Type a[], int head, int tail)
{
    if (head == tail)
    {
        sum++;
        for (int i=0;i<=tail;i++)
            cout << a[i];
        cout << endl;
        return;
    }
    for (int i=head;i<=tail;i++)
    {
        bool flag = false;
        for (int j=head;j<i;j++)
            if (a[i]==a[j])
            {
                flag = true;
                break;
            }
        if (head==i)
            flag = false;
        if (flag)
            continue;
        swap(a[head], a[i]);
        permut_repeat(a, head+1, tail);
        swap(a[head], a[i]);
    }
    return;
}
int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    // if need file I/O, activate this
    int n;
    cin >> n;
    char a[10000];
    for (int i=0;i<n;i++)
        cin >> a[i];
    sum=0;
    permut_repeat(a, 0, n-1);
    cout << sum << endl;
}

input:
4
AACC
  
output:
AACC
ACAC
ACCA
CAAC
CACA
CCAA
6

整数因子分解问题 (programming)

题目大意

问我们的是整数可以拆分成多少种大于1整数相乘的式子

实现思路

非常无脑，此处略过

实现细节

要明白他是不需要去重的

实现代码

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
#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));

int sum;

void fac(int number)
{
    if (number==1)
    {
        sum++;
        return;
    }
    for (int i=number;i>=2;i--)
    {
        if (number %i!=0)
            continue;
        fac(number/i);
    }
    return;
}

int main()
{
    int n;
    cin >> n;
    sum=0;
    fac(n);
    cout << sum << endl;
}

input:
12
output:
8
Author: YihangBao
Link: https://roarboil.github.io/2020/03/28/cha2-2/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.