0%

整数划分

发表于 更新于 分类于 ，

前言

说明一下问题，什么是整数划分？
n=m1+m2+…+mi; （其中mi为正整数，并且1 <= mi <= n），则{m1,m2,…,mi}为n的一个划分。
如果{m1,m2,…,mi}中的最大值不超过m，即max(m1,m2,…,mi)<=m，则称它属于n的一个m划分。这里我们记n的m划分的个数为f(n,m);
举个例子，当n=5时我们可以获得以下这几种划分（注意，例子中m>=5）
5 = 5
= 4 + 1
= 3 + 2
= 3 + 1 + 1
= 2 + 2 + 1
= 2 + 1 + 1 + 1
= 1 + 1 + 1 + 1 + 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
42
43
44
45
46
47
//
// Created by ZhiNian on 2019/3/27.
//
/*
题目：将一个整数划分为多个整数想加的形式，并输出有所划分方法。
例：6的划分：
6=5+1
6=4+2
6=4+1+1
6=3+3
6=3+2+1
6=3+1+1+1
6=2+2+2
6=2+2+1+1
6=2+1+1+1+1
6=1+1+1+1+1+1
 */

#include <stdio.h>

int d[100]; //用来存放分解结果
int ans = 0; //用来存放划分的次数
int N = 0; //定义全局N为了记录下需要划分的值

void divide(int m, int n, int k) { //m的n划分，k记录数组所处位置
    int i;
    if (m == 0) { //当m为0时，得到一个划分，将分解结果输出
        ans++; //得出一个划分即自增计数
        printf("%d=%d", N, d[0]); //输入格式为 N=第一个数 因为第一个数的前面不能是加号
        for (i = 1; i < k; i++) //循环输出
            printf("+%d", d[i]); //依次输出之后的数
        printf("\n"); //满足一组后换行
    }
    for (i = (m < n ? m : n); i > 0; i--) { //把最小值给i
        d[k] = (i < n ? i : n); //把最小的值给d[k]存入数组然后再划分
        divide(m - d[k], d[k], k + 1); //递归调用使分解继续下去，直到得到一个划分
    }
}

int main() {
    int n; //声明接收的值
    scanf("%d", &n); //接收需要划分的值
    N = n; //保留需要划分的值
    divide(n, n, 0); //传入划分
    printf("The number of \"Divide the number :%d \" is %d.\n", n, ans); //输出计数结果
    return 0;
}

实不相瞒，浏览了很多算法，还有不理解的，接下来会摘抄在下面，以上的算法，也是通过看别人的，然后去理解优化，自己敲，小的太low，能想出来的，只能去输出，到底有多少个，但是，按要求输出就懒了，懒得再重打，去输出，倒是这一次优化这个代码，熟练使用了一下，二目运算符，以上逻辑应该很清晰了，基本上就是，比如一个6，首先，分解出6和剩下的0，0去划分，然后5和1，1去划分，然后4和2，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
#include <stdio.h>

int mark[100];//记录分解情况
int n;
int ans = 0;

//now记录数组当前长度，k记录递归深度， pre记录前一个的值
void divide(int now, int k, int pre) {
    int i;
//数组长度大于n就返回
    if (now > n) return;
    if (now == n) {//输出一个情况
        ans++;
        printf("%d=", n);
        for (i = 0; i < k - 1; i++) {
            printf("%d+", mark[i]);
        }
        printf("%d\n", mark[i]);
    } else {//if (now < n)
        for (i = pre; i > 0; i--) { //从前一个数值一直到1
            if (i <= pre) {//当i小于等于前一个数值时，就是从最大的划分开始一直找到1为止，此时now==n 即可输出
                mark[k] = i;
                now = now + i;
                divide(now, k + 1, i);
                now = now - i;
            }
        }
    }
}

int main() {
    scanf("%d", &n);
    divide(0, 0, n - 1);
    printf("%d", ans);
    return 0;
}

这个算法没有特别能看懂，准确的说还是懵逼，留着以后请教大佬给我讲讲……

算法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>

using namespace std;

int equationCount(int n, int m) {
    if (n == 1 || m == 1)
        return 1;
    else if (n < m)
        return equationCount(n, n);
    else if (n == m)
        return 1 + equationCount(n, n - 1);
    else
        return equationCount(n, m - 1) + equationCount(n - m, m);
}

int main(void) {
    int n;
    while (scanf("%d", &n) != EOF && (n >= 1 && n <= 120)) {
        printf("%d\n", equationCount(n, n));
    }
    return 0;
}

这是一个通过判断四种情况去递归算次数的方法，但是输出我开始懵了，但是其实呢好像，每一次划分结束记录下来去输出就好了。