1.數的劃分
題目描述
將整數?nn?分成?kk?份，且每份不能為空，任意兩份不能相同(不考慮順序)。
例如：n=7，k=3n=7，k=3，下面三種分法被認為是相同的。
1，1，5;1，5，1;5，1，1;1，1，5;1，5，1;5，1，1;
問有多少種不同的分法。
輸入描述
輸入一行，22?個整數?n,k?(6≤n≤200，2≤k≤6)n,k?(6≤n≤200，2≤k≤6)。
輸出描述
輸出一個整數，即不同的分法。
輸入輸出樣例
示例 1
輸入
7 3
輸出
4遞歸解題思路
看到“整數分拆”問題，直接想到“遞歸”
遞歸的核心思想：將大問題分解為小問題，通過解決小問題來構建大問題的解。
遞歸的終止條件：
-
當
n或m為 0，或者n小于m時，分拆方式數量為 0。 -
當
m為 1 或n等于m時，分拆方式數量為 1。
遞歸的分解邏輯：
-
不選1的情況：將每個數字減去1，問題轉化為
f(n - m, m)。 -
選1的情況：其中一個數字是1，問題轉化為
f(n - 1, m - 1)。
最終結果是兩種情況的和：f(n - m, m) + f(n - 1, m - 1)。
解題步驟模板：
public static int f(int n, int m) {// 邊界條件if (n == 0 || m == 0 || n < m) {return 0;}if (m == 1 || n == m) {return 1;}// 遞歸邏輯else {return f(n - m, m) + f(n - 1, m - 1);}
}示例代碼模板：
import java.util.Scanner;public class Main {// 遞歸函數，用于計算將整數 n 分成 m 份的方式數public static int f(int n, int m) {// 邊界條件：當 n 或 m 為 0，或者 n 小于 m 時，分拆方式數量為 0if (n == 0 || m == 0 || n < m) {return 0;}// 當 m 為 1 或 n 等于 m 時，分拆方式數量為 1if (m == 1 || n == m) {return 1;}// 遞歸邏輯：// 1. 不選1的情況：將每個數字減去1，問題轉化為 f(n - m, m)// 2. 選1的情況：其中一個數字是1，問題轉化為 f(n - 1, m - 1)// 總分拆方式數量為兩者的和else {return f(n - m, m) + f(n - 1, m - 1);}}// 主函數，程序入口public static void main(String[] args) {// 創建 Scanner 對象，用于讀取用戶輸入Scanner sc = new Scanner(System.in);// 讀取用戶輸入的整數 nint n = sc.nextInt();// 讀取用戶輸入的整數 kint k = sc.nextInt();// 調用遞歸函數 f(n, k)，計算分拆方式數量// 輸出結果System.out.println(f(n, k));}
}思維導圖：
訓練方法：
-
理解遞歸思想：仔細閱讀代碼，確保理解遞歸的終止條件和遞歸邏輯。
-
手算小例子：選擇一個小的例子（如
n = 4，m = 2），手動計算遞歸調用的過程，然后用代碼驗證結果。 -
調試和優化：觀察遞歸調用的深度和次數，嘗試用記憶化技術優化代碼，避免重復計算。
-
擴展應用：將代碼邏輯應用到其他類似問題，如“將整數分成任意多份”的問題
2.數的計算
題目描述
輸入一個自然數?n?(n≤1000)n?(n≤1000)，我們對此自然數按照如下方法進行處理:
-
不作任何處理;
-
在它的左邊加上一個自然數,但該自然數不能超過原數的一半;
-
加上數后,繼續按此規則進行處理,直到不能再加自然數為止。
問總共可以產生多少個數。
輸入描述
輸入一個正整數?nn。
輸出描述
輸出一個整數，表示答案。
輸入輸出樣例
示例 1
輸入
6
輸出
6遞歸解題思路
看到“整數分拆”問題，直接想到“遞歸”
遞歸的核心思想：將大問題分解為小問題，通過解決小問題來構建大問題的解。
遞歸的終止條件：當 n == 1 時，分拆方式數量為 1。
遞歸的分解邏輯：通過遍歷從1到n/2的數i，每次將當前數i分拆，并遞歸計算i的分拆方式。
解題步驟模板：
public static void f(int n) {// 遞歸終止條件if (n == 1) {return;}// 遍歷 i 從 1 到 n/2，計算分拆方式for (int i = 1; i <= n / 2; i++) {// 每次分拆時，增加結果計數res++;// 遞歸計算更小的整數 i 的分拆方式f(i);}
}示例代碼模板：
import java.util.Scanner;public class Main {// 全局變量，用于存儲最終結果static int res = 1;// 遞歸函數，用于計算整數 n 的分拆方式數量public static void f(int n) {// 遞歸終止條件：當 n == 1 時，分拆方式數量為 1if (n == 1) {return;}// 遍歷 i 從 1 到 n/2，計算分拆方式for (int i = 1; i <= n / 2; i++) {// 每次分拆時，增加結果計數res++;// 遞歸計算更小的整數 i 的分拆方式f(i);}}// 主函數，程序入口public static void main(String[] args) {// 創建 Scanner 對象，用于讀取用戶輸入Scanner sc = new Scanner(System.in);// 讀取用戶輸入的整數 nint n = sc.nextInt();// 調用遞歸函數 f(n)，計算分拆方式數量f(n);// 輸出最終結果System.out.println(res);}
}思維導圖：
訓練方法：
-
理解遞歸思想：仔細閱讀代碼，確保理解遞歸的終止條件和遞歸邏輯。
-
手算小例子：選擇一個小的例子（如
n = 4），手動計算遞歸調用的過程，然后用代碼驗證結果。 -
調試和優化：觀察遞歸調用的深度和次數，嘗試用記憶化技術優化代碼，避免重復計算。
-
擴展應用：將代碼邏輯應用到其他類似問題，如“將整數分成特定數量的份”或“將整數分成不相等的份”的問題。
?
?自學藍橋杯筆記,希望我們可以一起學習!
