整数分划Java

整数分划

正整数n的一个分划是指把n表示成若干个正整数的和。这里的分划与顺序无关，例如6=5+1 和 6=1+5即被认为是同一种分划。另外，这个整数本身也算一种分划。

例如，正整数n=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的分划可以看成一个递归的过程。把n分解成n-i和i两部分(1≤i≤n)，然后检查i或n-i是否可以继续被分解（只取其中较小 的那个进行继续分解，可以避免检查重复），直到最后分解完成。

输入：

待分解的正整数n

输出：

对应的排好序的分解，每行一个，中间用空格分开

样例输入：

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↵

 

 

import java.util.Scanner;
public class Main {
	public static void fun(int[] str,int n,int m){
		if(n==0)   
	        {      
	            for(int i=0;i<=m-1;i++)   
	            {      
	                if(i==(m-1))      
	                      System.out.println(str[i]);      
	                else     
	                	System.out.print(str[i]+" ");      
	            }       
	         }      
	         else  
	         {      
	            for(int i=n;i>=1;i--)   
	            {      
	               if(m==0||i<=str[m-1])   
	               {      
	                   str[m]=i;      
	                   fun(str,n-i,m+1);      
	               }      
	            }    
	         }
	}
			
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		fun(new int[n],n,0);
	}
}