整数划分问题

整数划分问题是算法中的一个经典命题之一,有关这个问题的讲述在讲解到递归时基本都将涉及。
所谓整数划分,是指把一个正整数n写成如下形式:
n=m1+m2+…+mi; (其中mi为正整数,并且1 <= mi <= n),则{m1,m2,…,mi}为n的一个划分。
如果{m1,m2,…,mi}中的最大值不超过m,即max(m1,m2,…,mi)<=m,则称它属于n的一个m划分。这里我们记n的m划分的个数为f(n,m);
例如但n=4时,他有5个划分,{4},{3,1},{2,2},{2,1,1},{1,1,1,1};
注意4=1+3 和 4=3+1被认为是同一个划分。
该问题是求出n的所有划分个数,即f(n, n)。下面我们考虑求f(n,m)的方法;

根据n和m的关系,考虑以下几种情况:

  1. 当n=1时,不论m的值为多少(m>0),只有一种划分即{1};

  2. 当m=1时,不论n的值为多少,只有一种划分即n个1,{1,1,1,…,1};

  3. 当n=m时,根据划分中是否包含n,可以分为两种情况:
    (1) 划分中包含n的情况,只有一个即{n};
    (2) 划分中不包含n的情况,这时划分中最大的数字也一定比n小,即n的所有(n-1)划分。
    因此 f(n,n) =1 + f(n,n-1);

  4. 当n<m时,由于划分中不可能出现负数,因此就相当于f(n,n);

  5. 但n>m时,根据划分中是否包含最大值m,可以分为两种情况:
    (1) 划分中包含m的情况,即{m, {x1,x2,…xi}}, 其中{x1,x2,… xi} 的和为n-m,可能再次出现m,因此是(n-m)的m划分,因此这种划分
    个数为f(n-m, m);
    (2) 划分中不包含m的情况,则划分中所有值都比m小,即n的(m-1)划分,个数为f(n,m-1);
    因此 f(n, m) = f(n-m, m)+f(n,m-1);

综合以上情况,我们可以看出,上面的结论具有递归定义特征,其中(1)和(2)属于回归条件,(3)和(4)属于特殊情况,将会转换为情况(5)。而情况(5)为通用情况,属于递推的方法,其本质主要是通过减小m以达到回归条件,从而解决问题。其递推表达式如下:

f(n, m)= 1; (n=1 or m=1)
f(n, n); (n<m)
1+ f(n, m-1); (n=m)
f(n-m,m)+f(n,m-1); (n>m)

递归代码

import java.util.Scanner;

/**
 * Created by EthanWalker on 2017/11/19.
 */
public class IntPartition {

    public static int digui(int n, int m) {
        if(n==0||m==0) return 0;
        if (n == 1 || m == 1) return 1;
        if (n == m) return 1 + digui(n, n - 1);
        if (n < m) return digui(n, n);
        // n>m 时
        return digui(n - m, m) + digui(n, m - 1);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (true) {
            int i = scanner.nextInt();
            if (i == -1) {
                break;
            }
            long begin = System.currentTimeMillis();
            int digui = digui(i, i);   //递归超时
            long end = System.currentTimeMillis();

            System.out.println("递归的结果: " + digui);
            System.out.println("花费的时间: "+(end-begin)+" 毫秒");
        }
    }


}

非递归(二维数组)

import java.util.Scanner;

/**
 * Created by EthanWalker on 2017/11/19.
 */
public class IntPartitionArray {


    public static int array(int n) {
        int[][] a = new int[n + 1][n + 1];

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



    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int[][] a = new int[121][121];

        for (int i = 0; i <= 120; i++) {
            for (int j = 0; j <= 120; j++) {
                a[i][j] = 0;
            }
        }
        for (int i = 1; i <= 120; i++) {
            a[i][1] = 1;
            a[1][i] = 1;
        }
        for (int i = 1; i <= 120; i++) {
            for (int j = 1; j <= 120; j++) {
                if (j == 1 || i == 1) a[i][j] = 1;
                else if (i == j) {
                    a[i][j] = 1 + a[i][i - 1];
                } else if (i < j) {
                    a[i][j] = a[i][i];
                } else if (i > j) {
                    a[i][j] = a[i - j][j] + a[i][j - 1];
                }
            }
        }
        while (scanner.hasNext()) {
            int i = scanner.nextInt();
//            long begin = System.currentTimeMillis();
            int array =a[i][i];
//            long end = System.currentTimeMillis();
            System.out.println(array);
//            System.out.println("数组计算的结果: " + array);
//            System.out.println("花费的时间: " + (end - begin) + " 毫秒");
        }
    }
}

推荐阅读更多精彩内容