第2章 递归与分治策略

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<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<queue>
#include<cmath>
#include<cstdlib>
#define MAX 100

using namespace std;

void permu(int *A, int k, int m)
{
    if(k == m)
    {
        for(int i=0; i<k; i++)
        {
            printf("%d,", A[i]);
        }
        printf("\n");
        return;
    }
    for(int i = k; i<m; i++)
    {
        swap(A[i], A[k]);
        permu(A, k+1, m);
        swap(A[i], A[k]);
    }
}

int main()
{
    int a[MAX];
    for(int i=0; i<MAX; i++)
    {
        a[i] = i;
    }
    permu(a, 0, 3);
    return 0;
}

2.整数划分

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<queue>
#include<cmath>
#include<cstdlib>
#define MAX 100

using namespace std;

int diviscount;  //division count


/**
* @name max m division of n
* 整数n的最大划分数为m
*/
void division(int *A, int len, int n, int m)
{
    if(n<0 || m<=0)return;
    if(n == 0)
    {
        diviscount++;
        for(int i=0; i<len; i++)
        {
            printf("%d,", A[i]);
        }
        printf("\n");
        return;
    }
    //n的m划分, m不会大于n
    if(m > n)
    {
        division(A, len, n, n);
    }
    else if(m == 1)
    {
        A[len] = 1;
        division(A, len+1, n-1, 1);
    }
    else
    {
        // n的m的划分包括最大划分数为m时, 以及 最大划分数小于m时.
        A[len] = m;
        division(A, len+1, n-m, m);
        division(A, len, n, m-1);
    }
}

int main()
{
    int a[MAX];
    diviscount = 0;
    division(a, 0, 5, 4);
    printf("division count = %d\n", diviscount);
    return 0;
}