分治算法案例二：整数划分

整数划分

实验内容：

1. 整数划分问题：将正整数n表示成一系列正整数之和： ，其中 ，k≥1。正整数n的这种表示称为正整数n的划分。请设计一个算法，求正整数n的不同划分个数或方案。例如正整数6有以下11种不同的划分个数或方案：
   {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}。

(1). 算法设计思路
当为q(n,m)且n=m时,有两种情况。
  ① 包含n，此时只有一种情况的划分，即{n}。
  ② 不包含n，此时最大值小于n，即n的n-1的划分。
  因此q(n,n) = 1+q(n,n-1)
当为q(n,m)时，此时1<m<n,可分为两种情况。
  ③ 包含m本身：对于{m,{…}}，只需计算{…}的大小，并对其总和进行划分，故为q(n-m,m)
  ④ 不包含m本身:只需对n的m-1进行划分，即q(n,m-1)
  因此q(n,m)=q(n-m,m)+q(n,m-1)
当n=1或m=1时，都是只有一种划分，分别为{1}或者{1,1…1,1}。作为递归的边界条件。
递归树

(2).算法实现伪代码
  算法functionB(input 1, input 2, …, input n)
  输入：对某个正整数n进行划分
  输出：正整数n的划分个数
  S1: function(n,m)
  S2: if n=1 | m=1 then return 1
  S3: if n < m return function(n,n)
  S4: if n=m return 1+function(n,m-1)
  S5: return function(n-m,m)+function(n,m-1)
（3）.实现代码

import java.util.Scanner;
public class Main {
	static int num;
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		num = n;
		System.out.println(q(n,n));
	}

	private static int q(int n, int m) {
		//当n=1或m=1时，能划分的只有一种情况 1 || 1+1+...+1
		if(n == 1||m == 1)
			return 1;
		//当m>n时，是无法划分的，故要将m改为n。
		if(n < m)
			return q(n,n);
		//当m=n时，当划分包含m时，就有一种情况 n,即为1  
		//当划分不包含m时，就要从m-1开始划分故为q(n,m-1)
		if(n == m) 
			return 1+q(n,m-1);
		//当n>m>1时，1.包含m本身，即{m, {…}}，{…}中元素的和为n-m，可能再次出现m，故为n-m的m划分
		//			2.不包含m本身，即为n的m-1划分
		return q(n-m,m)+q(n,m-1);
		
	}
}