[C_GD16-中] 正整數分解(Java)

[C_GD16-中] 正整數分解

Time Limit: 2 seconds
問題描述 ：
算出一個正整數遞減分解的方式，所謂正整數遞減分解是將一個正整數寫成幾個遞減數列的和。例如若給正整數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
因此共有11種遞減分解的方式。
 輸入說明 ：
輸入會包含多筆測資，每列有一筆測資，每筆測資最多有一個正整數n(20>n>1)。
輸出說明 ：
    請計算每筆測資輸入數遞減分解的方式數。
範例 ：

輸入範例	輸出範例
6 5	11 7

1. import java.util.*;  
2. import java.lang.*;  
3. import java.io.*;  
4.   
5. class Main  
6. {  
7.     public static void main (String[] args)   
8.     {  
9.         // your code goes here  
10.         Scanner sc = new Scanner(System.in);  
11.         while(sc.hasNext())  
12.         {  
13.             int n = sc.nextInt();  
14.             System.out.println(f(n, 1));  
15.         }  
16.     }  
17.       
18.     private static int f(int n, int k)  
19.     {  
20.         if(n==k || n < 2*k)  
21.         {  
22.             return 1;  
23.         }  
24.         else  
25.         {  
26.             int num = 0;  
27.             for(int i = k;i < n;i++)  
28.             {  
29.                 if(n - i >= i)  
30.                 {  
31.                     num = num + f(n-i, i);  
32.                 }  
33.             }  
34.             return num + 1;  
35.         }  
36.     }  
37. }