Java一道经典算法题！！！求解！

整数的分划问题。 
如，对于正整数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 （范围1~10）
程序输出该整数的所有划分。

19 个解决方案

#1

public class t11 {
	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) {
		fun(new int[6], 6, 0);
	}
}

#2

引用 1 楼 yewuqing007 的回复:

Java code
public class t11 {
    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))
            ……

感谢你的解答，能说一下你的思想，或加一些注释吗？

#3

该回复于2011-04-27 09:00:03被版主删除

#4

        public static void divideNumber(int n)
        {
            int[] arr = new int[n];
            divideNumber(arr, 0, 6, 6);
        }

//往数组中填充数字， index为待添位， maxNum 为能填入的最大值， remnant 为剩余数字
        public static void divideNumber(int[] arr, int index, int maxNum, int remnant)
        {
            if (index <= arr.Length && remnant == 0)
            {
                for (int i = 0; i < index - 1; i++)
                {
                    System.out.print(arr[i] + " + ");
                }
                System.out.println(arr[index - 1]);
            }
            else
            {
                for (int i = 1; i <= remnant && i <= maxNum; i++)
                {
                    arr[index] = i;
                    divideNumber(arr, index + 1, i, remnant - i);
                }
            }
        }

#5

引用 4 楼 keeya0416 的回复:

Java code


        public static void divideNumber(int n)
        {
            int[] arr = new int[n];
            divideNumber(arr, 0, 6, 6);
        }

//往数组中填充数字， index为待添位， maxNum 为能填入的……

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  
这里可以看出填充数组的话，填入的数字是递减的
我在 4 楼写的就是这个思路

#6

引用 5 楼 keeya0416 的回复:

引用 4 楼 keeya0416 的回复:
Java code


public static void divideNumber(int n)
{
int[] arr = new int[n];
divideNumber(arr, 0, 6, 6);
}

//往数组中填充数字， index为待添位， maxNum 为能填入的……

6  
5+1  
4+2, 4……

非常感谢你的解答，但是思路 我还是不能理解，呵呵

#7

引用 5 楼 keeya0416 的回复:

引用 4 楼 keeya0416 的回复:
Java code


public static void divideNumber(int n)
{
int[] arr = new int[n];
divideNumber(arr, 0, 6, 6);
}

//往数组中填充数字， index为待添位， maxNum 为能填入的……

6  
5+1  
4+2, 4……

哥们  有QQ吗？想向你再讨教一下！

#8

该回复于2011-04-27 09:04:33被版主删除

#9

分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。
对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。
将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。
分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

#10

正在思考中

#11

引用 9 楼 afgasdg 的回复:

分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。
对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。
将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。
分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的……

谢谢！看来递归这块 还得再花时间研究研究！

#12

这个思路应该是挺清晰的

#13

我在4楼的代码不是分治
思路是 n 最大能填充够一个长度为 n 、值均为 1 的数组
考虑到重复
所以在填充的时候让数组递减

            if (index <= arr.Length && remnant == 0)
            {
                for (int i = 0; i < index - 1; i++)
                {
                    System.out.print(arr[i] + " + ");
                }
                System.out.println(arr[index - 1]);
            }

这段代码路判断，当需要填充的数字为 0 时，即为填充完毕，开始输出。其实index <= arr.Length 这个条件可以不要，因为 n 最大能填充够一个长度为 n 、值均为 1 的数组，所以这个总是成立的。

                for (int i = 1; i <= remnant && i <= maxNum; i++)
                {
                    arr[index] = i;
                    divideNumber(arr, index + 1, i, remnant - i);
                }

这段代码的意思是，当剩余的数字大于0，将可以添入的合法数字枚举填入，分别进入数组下一个序号的填充步骤，因为填充数字的规则是不变的，所以用了递归，并没有分治。合法的数字是满足 小于等于 剩余数字 和 下于等于上一数字填充时的值以满足数组递减的性质（那个值是当前数组中的非0最小值）。
下边这个是用分治做的，楼主也可以看下

        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){
                System.out.println(tatol + " = " + result.substring(1));
            }
            else if (n >= min){
                innerSolve(tatol, n - min, min, result + "+" + min);
                innerSolve(tatol, n, min + 1, result);
            }
        }

#14

引用 13 楼 keeya0416 的回复:

我在4楼的代码不是分治
思路是 n 最大能填充够一个长度为 n 、值均为 1 的数组
考虑到重复
所以在填充的时候让数组递减
Java code

            if (index <= arr.Length &amp;&amp; remnant == 0)
            {
                for (int i = 0; i < index - 1……

Thank you very much!

#15

LZ偷懒哥

#16

我是打酱油的！

#17

厉害，看半天没看懂

#18

该回复于2011-05-09 17:07:18被版主删除

#19

这个算法好精巧。。