整数划分问题（详解 n ＞ m 情况）
原创
整数划分问题
整数划分问题是算法中的一个经典命题之一
整数划分，是指把一个正整数n如下如下形式：
n = n<sub>1</sub> + n<sub>2</sub> + ... + n<sub>k</sub> (其中 n<sub>1</sub> >= n<sub>2</sub> ... >= n<sub>k</sub> > 0, k >= 1)
依旧是以6来举例，有如下划分：
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);
}
}11process time: 157800nsc++代码实现
#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请按任意键继续. . .原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
