簡單的整數劃分問題

總時間限制: 100ms 記憶體限制: 65536kB

描述

将正整數n 表示成一系列正整數之和，n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ，k>=1 。

正整數n 的這種表示稱為正整數n 的劃分。正整數n 的不同的劃分個數稱為正整數n 的劃分數。

輸入

标準的輸入包含若幹組測試資料。每組測試資料是一個整數N(0 < N <= 50)。

輸出

對于每組測試資料，輸出N的劃分數。

樣例輸入

樣例輸出

提示

5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1

解題思路：

該問題是求出n的所有劃分個數，即f(n, n)。下面我們考慮求f(n,k)的方法;

根據n和k的關系，考慮以下幾種情況：

（1）當 n = 1 時，不論k的值為多少（k > 0 )，隻有一種劃分即 { 1 };

( 2 ) 當 k = 1 時，不論n的值為多少，隻有一種劃分即 n 個 1，{ 1, 1, 1, …, 1 };

(3) 當 n = k 時，根據劃分中是否包含 n，可以分為兩種情況：

(a). 劃分中包含n的情況，隻有一個即 { n }；

(b). 劃分中不包含n的情況，這時劃分中最大的數字也一定比 n 小，即 n 的所有 ( n - 1 ) 劃分。是以 f(n, n) = 1 + f(n, n-1);

(4) 當 n < k 時，由于劃分中不可能出現負數，是以就相當于 f(n, n);

(5) 但 n > k 時，根據劃分中是否包含最大值 k，可以分為兩種情況：

(a). 劃分中包含 k 的情況，即 { k, { x1, x2, …, xi } }, 其中 { x1, x2, …, xi } 的和為 n - k，可能再次出現 k，是以是（n - k）的 k 劃分，是以這種劃分

個數為 f(n-k, k);

(b). 劃分中不包含 k 的情況，則劃分中所有值都比 k 小，即 n 的 ( k - 1 ) 劃分，個數為 f(n, k - 1);

是以 f(n, k) = f(n - k, k) + f(n, k - 1);

Java代碼如下：

import java.util.Scanner;

public class Main {

    public static int Function(int n,int k){
        if (n == 1 || k == 1){
            return 1;
        }
        if (n < k){
            return Function(n, n);
        }
        if ( n == k){
            return Function(n, k-1)+1;
        }
        return Function(n-k, k)+Function(n, k-1);
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        System.out.println(Function(n, n));

        in.close();
    }

}

複制