整数划分问题（详解 n ＞ m 情况）

关注

发布于: 2021 年 06 月 07 日

整数划分问题

整数划分问题是算法中的一个经典命题之一整数划分，是指把一个正整数 n 如下如下形式：n = n1 + n2 + ... + nk (其中 n1 >= n2 ... >= nk > 0, k >= 1)

依旧是以 6 来举例，有如下划分：

5+1;

4+2,4+1+1;

3+3,3+2+1,3+1+1+1;

2+2+2,2+2+1+1,2+1+1+1+1;

1+1+1+1+1+1;

正整数 n 的所有不同划分中，将最大加数 x 不大于 m 的情况记为 q(n,m)，这个称作 n 的 m 划分

算法的 4 种情况（前三种都很容易理解）

n = m = 1 时，显然 q(n, m) = 1
n < m 时，如 q(4, 5), 显然 q(4, 5) = q(4, 4), 即 q(n, m) = q(n, n) (while n < m)
n = m 时，q(n, m) = 1 + q(n, n-1)
划分中包含 n 的情况，即只有一个 {n}
划分中不包含 n 的情况，即 n 的所有 (n-1) 划分

所以，q(n, m) = 1 + q(n, n-1)

n > m > 1 时，比较难理解
第一种情况：加数中包含 m，如果加数中包含 m，对于 n 来说，就是拆分剩下的 n - m 这些大小的数字，所以此时情况就是 q(n-m, m)
此处划分前提是包含 m，我们将 m 提出来，即可保证划分中一定会有 m，那么，剩下数字划分的和为 (n - m), 因为我们已经提出了一个 m，所以划分的最大数就是 m，这也就解释了 f 的第二个数为什么是 m
第二种情况：不包含 m，这时，使 m-1，m 就不存在了，所以这时候就是 q(n, m-1)

所以，q(n, m) = q(n, m-1) + q(n-m,m)

Java 代码实现

package EquationCount;
public class EquatinCount {
  public static void main(String[] args) {        /*     * 以 ms 计算: System.currentTimeMillis();     * 以 ns 计算: System.nanoTime();     */        long startTime = System.nanoTime(); // 获取开始时间    int n = 6;    System.out.println(equationCount(n, n));    long endTime = System.nanoTime(); // 获取结束时间        System.out.println("process time: "+(endTime-startTime)+"ns");  }      public static int equationCount(int n, int m) {    if (n == 1 || m == 1)      return 1;    else if (n > m)      return equationCount(n-m, m) + equationCount(n, m-1);    else if (n < m)      return equationCount(n, n);    else       return 1+equationCount(n, n-1);  }}

复制代码

11process time: 157800ns

复制代码

c++代码实现

#include <iostream>#include <ctime>using namespace std;
int equationCount(int n, int m){    if (n == 1 || m == 1)        return 1;    else if (n > m)        return equationCount(n-m, m) + equationCount(n, m-1);    else if (n < m)        return equationCount(n, n);    else         return 1+equationCount(n ,n-1);}
int main(){    double start, stop, dur;    start = clock();
    int n = 6;    cout << equationCount(n, n) << endl;
    stop = clock();    dur = stop - start;    cout << "process_time: " << dur << endl;    system("pause");}

复制代码

11process_time: 1请按任意键继续. . .

复制代码

发布于: 2021 年 06 月 07 日阅读数: 9

原文链接:【http://xie.infoq.cn/article/651e6d19dac5006d8f4a793b1】。文章转载请联系作者。

若尘

关注

还未添加个人签名 2021.01.11 加入

还未添加个人简介

发布

暂无评论

创作场景

整数划分问题（详解 n ＞ m 情况）

整数划分问题

若尘

评论