一道算法问题，求解

Question

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-10的任意数  分解
貌似只有2分，就不给分了

Answer 1

1 1 1 1 1 1
问题转化为找到序列 分割上列数组，比如：
111 | 1 1 | 1
分割序列为 {3,4}
要砍枝避免重复： a(i)-a(i-1) >= a(i+1)-a(i)

Answer 2

package CSDN;import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;public class MathTest
{
private int n; private int[] a; public MathTest(int x)
{
n = x; a = new int[100];
} public void print(int m)
{
for (int i = 0; i < m; i++)
{
if (a[i] == n - 1)
{
System.out.print(a[i]);
}
else if (i == m - 1)
{
System.out.print(a[i] + "=" + (n - 1));
}
else
{
System.out.print(a[i] + "+");
} } System.out.println();
} public void resolve(int n, int m)
{

if (n == 1)
{
print(m);
}

else
{
for (int i = n - 1; i >= 1; i--)
{
if (m == 0 || i <= a[m - 1])
{
a[m] = i;

resolve(n - i, m + 1);
}
}

}

} public static void main(String[] args) throws Exception
{
Scanner s = new Scanner(System.in);

System.out.println("请输入一个整数："); int num = Integer.parseInt(s.nextLine());

MathTest i = new MathTest(num + 1);

i.resolve(num + 1, 0);
}
}

Answer 3

public static void main(String[] args) {
do_BT_problem(6);
}private static void do_BT_problem(int n) {
if(n<2 || n>10) {
System.out.println("错误，参数的范围应该是[2, 10]!");
} else {
int[] list = new int[n+1];
list[n] = n;
go(n, 1, list);
}
}private static void go(int n, int level, int[] list) {
for(int i=n; i>0; i--) {
if(level==1) {
if(i!=n) {
list[level-1] = i;
go(n-i, level+1, list);
}
}else if(i<=list[level-2]){ //如果把“if(if(i<=list[level-2]))”去掉，就会出现重复的组合
list[level-1] = i;
if(i==n) {
printList(list[list.length-1], list, level);
}else {
go(n-i, level+1, list);
}
}
}
}private static void printList(int n, int[] list, int length) {
System.out.print(String.format("%1$d = %2$d", n, list[0]));
for(int i=1; i<length; i++) {
System.out.print(String.format(" + %1$d", list[i]));
}
System.out.println();
}

Answer 4

简化了一下
private static void do_BT_problem(int n) {
    if(n<2 || n>10) {
        System.out.println("错误，参数的范围应该是[2, 10]!");
    } else {
        int[] list = new int[n+1];
        list[0] = n;
        resolve(n, 1, list);
    }
}private static void resolve(int n, int level, int[] list) {
    for(int i=(level==1 ? n-1 : n); i>0; i--) {
     list[level] = i;
     if(i<=list[level-1]){  //如果把“if(i<=list[level-2])”去掉，就会出现重复的组合
            if(i==n) {
                printList(list, level+1);
            }else {
             resolve(n-i, level+1, list);
            }
        }
    }
}private static void printList(int[] list, int length) {
    System.out.print(String.format("%1$d = %2$d", list[0], list[1]));
    for(int i=2; i<length; i++) {
        System.out.print(String.format(" + %1$d", list[i]));
    }
    System.out.println();
}

Answer 5

没安装JDK
给个C#的楼主自己改        public static void solve(int i)
        {
            innerSolve(i, i, 1, "");
        }
        private static void innerSolve(int tatol, int n, int min, String result)
        {
            if (n == 0)
            {
                Console.WriteLine(tatol + " = " + result.Substring(1));
            }
            else if (n >= min)
            {
                innerSolve(tatol, n - min, min, result + "+" + min);
                innerSolve(tatol, n, min + 1, result);
            }
        }

Answer 6

import java.util.Arrays;
import java.util.TreeMap;
public class Test0111 {

static TreeMap<String, Integer> resultTreeMap = new TreeMap<String, Integer>();
static String resultString = new String();

public static void main(String[] args) {
fun(0,6);
System.out.println(resultTreeMap);
} static void fun(int sum,int total){
for(int i = 1;i <= total;i++){
sum += i;
if(sum == total){
resultTreeMap.put(sort(resultString + i + " "), total);
return;
}
else if (sum > total) {
return;
}
resultString += i + " ";
fun(sum, total);
sum -= i;
resultString = resultString.substring(0,resultString.length() - 2);
}
}

static String sort(String string){
String[] array = string.split(" ");
Arrays.sort(array);
String result = new String();
for(String str : array){
result += str + "+";
}
return result.substring(0,result.length() - 1);
}
}
{1+1+1+1+1+1=6, 1+1+1+1+2=6, 1+1+1+3=6, 1+1+2+2=6, 1+1+4=6, 1+2+3=6, 1+5=6, 2+2+2=6, 2+4=6, 3+3=6, 6=6}