騰訊實習生筆試程式設計題--數的分解

原題如下：

如下示例：

1:共0種分解方法;

2:共0種分解方法;

3: 3 = 2 + 1 共1種分解方法;

4: 4 = 3 + 1 = 2 + 1 + 1 共2種分解方法;

5: 5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 共5種分解方法;

6: 6 = 5 + 1 = 4 + 2 = 4 + 1 = 3 + 2 + 1 = 3 + 1 + 1 + 1 = 2 + 2 + 1 + 1 = 2 + 1 + 1 +1 + 1 共7種分解方法

依此類推，求一任意整數num有幾種分解方法？

輸入一個數字（1到90），輸出該整數按如上示例的分解方法個數

如：

輸入：2

輸出：0

輸入：3

輸出：1

輸入：5

輸出：5

對于一個num>5，分解方法如下：

要求num的分解方法，可以把上表中的每一種情況（一列代表一種情況）的分解方法累加起來：

f( x ) 代表數x的分解方法數目，g( i )代表數i拆分成1或2的分解方法數目。

f( num ) = 1 + 1 + g( 1 ) + g( 2 ) + … + g( num-3 );

g( 1 ) = 1 : 1;

g( 2 ) = 2 : 2; 1,1;

g( 3 ) = 2 : 2,1; 1,1,1;

g( 4 ) = 3 : 2,2; 2,1,1; 1,1,1,1;

g( 5 ) = 3 : 2,2,1; 2,1,1,1; 1,1,1,1,1;

g( 6 ) = 4: 2,2,2; 2,2,1,1; 2,1,1,1,1; 1,1,1,1,1,1;

總結規律為把 i 拆盡可能多的2，然後把每一個2拆成兩個1；是以對于 i 可以拆出 i/2（向下取整） 個2，故依次把每一個2拆成兩個1可以得到 i/2 中分解方法，加上拆成2最多的情況（全2或者隻有1個1），即得 g( i ) = i/2 +1

故：f( num ) = 2 + g( 1 ) + g( 2 ) + … + g( num-3 )

= 2 + ( 1/2 + 1 ) + ( 2/2 + 1 ) + .. + ( (num-3)/2 + 1 )

= 2 + (num-3) + ( 1 + 2 + … + (num-3) )/2

= num-1 + ( 1 + 2 + … + (num-3) )/2 (注意此處是的除法是向下取整)

即對于num的解法: f( 1 ) = f( 2 ) =0; f( 3 ) = 1; f( 4 ) = 2;

f ( num ) = num-1 + ( 1 + 2 + … + (num-3) )/2 (num >= 5, 注意此處是的除法是向下取整)

import java.util.Scanner;
public class SplitNum1 {
    private static int[] f = new int[];
    private static void calcu(){
        f[] = ;
        f[] = ;
        f[] = ;
        f[] = ;
        f[] = ;
        for(int i = ; i < f.length; ++i){
            f[i] = i - ;
            for(int j = ; j <= i-; ++j)
                f[i] += j/;
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num;
        calcu();
        while( sc.hasNextInt() ){
            num = sc.nextInt();
            System.out.println( f[num] );
        }
    }
}
           

這種解法的時間複雜度為O(n2),空間複雜度為O(n)。

計算每一個結果都要從1開始計算，是以時間複雜度比較大，考慮動态規劃是否可以降低時間複雜度。

f( n+1 ) = (n+1) -1 + ( 1 + 2 + .. + (n+1 -4) + (n+1 -3))/2

= n-1 +1 +(1+2+…+n-3)/2 + (n+1-3)/2

= f( n ) + 1 + (n+1 -3)/2

= f( n ) + (n+1 -1)/2

是以f(num) 可以通過前一項的結果計算得出，進而可以将每一項的計算複雜度降至O(1),使總時間複雜度降至O(n)。

import java.util.Scanner;
public class SplitNum1 {
    private static int[] f = new int[];
    private static void calcu2(){
        f[] = ;
        f[] = ;
        f[] = ;
        f[] = ;
        f[] = ;
        f[] = ;
        for(int i = ; i < f.length; ++i){
            f[i] = f[i-] + ( i- )/;
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num;
        calcu2();
        while( sc.hasNextInt() ){
            num = sc.nextInt();
            System.out.println( f[num] );
        }
    }
}
           

另外一種思路：

當num>=6時，其分解方法f( num )是 ：

(num-1, 1), (num-2, 2),計p1 = 2;

在(num-1)的每一種分解方法後面加1，計p2 = f( num-1 );

在(num-2)的分解方法中有且僅有1個1且有2的分解方法後面加2，計p3;

即可得到num的所有分解方法:

f( num ) = p1 + p2 + p3 = 2 + f( num - 1) + p3

計算p3：p3 = (num-1)/2 -2

f(num) = 2 + f(num-1) + (num-1)/2-2

= f(num-1) + (num-1)/2