整数的分划问题。
如,对于正整数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+1
现在的问题是,对于给定的正整数n,编写算法打印所有划分。
用户从键盘输入 n (范围1~10)
程序输出该整数的所有划分。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
public class MyTest {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int x = in.nextInt();
List expressions[] = new List[x];
for(int i=1;i<=x;i++){
if(i==1){
expressions[i-1] = new ArrayList();
expressions[i-1].add("1");
}else{
expressions[i-1] = new ArrayList();
expressions[i-1].add(String.valueOf(i));
//expressions[i-1].add(String.valueOf(i-1)+"+1");
for(int j=i-1;j>=i/2;j--){
for(int k=0;k
// 原来的表达式
String str1=(String)expressions[j-1].get(k);
// 排序后的表达式
String str2=process(str1+"+"+(i-j));
// 查找是否已经存在
boolean b=false;
for(int kk=0;kk
if(expressions[i-1].get(kk).toString().equals(str2)){
b = true;
break;
}
}
if(!b){
expressions[i-1].add(str2);
}
}
}
}
}
http://tcc55.com
http://70ky.com
Collections.sort(expressions[x-1]);
String temp=null;
for(int i=expressions[x-1].size()-1;i>=0;i--){
String value = expressions[x-1].get(i).toString();
if(temp==null){
System.out.print(value);
temp = value.substring(0,1);
}else{
if(value.startsWith(temp)){
System.out.print(",");
}else{
System.out.println();
temp = value.substring(0,1);
}
System.out.print(value);
}
}
}
/*
* 调整顺序,例如 3+1+2+1 调整后 3+2+1+1
*/
static String process(String exp){
exp = exp.replace("+"," ");
String str[] = exp.split(" ");
Arrays.sort(str);
StringBuffer sb = new StringBuffer();
for(int i=str.length-1;i>=0;i--){
sb.append(str[i]+"+");
}
sb.deleteCharAt(sb.length()-1);
return sb.toString();
}
}
转载于:https://www.cnblogs.com/geziwu/p/3564471.html