学习笔记 - 整数划分问题（详解 n ＞ m 情况） - V2CE

整数划分问题

整数划分问题是算法中的一个经典命题之一

整数划分，是指把一个正整数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)
1. 划分中包含 n 的情况，即只有一个 {n}
2. 划分中不包含 n 的情况，即 n 的所有 (n-1) 划分

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

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

process 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");
}

process_time: 1

请按任意键继续. . .

学习笔记 – 整数划分问题（详解 n ＞ m 情况）

整数划分问题