將一個正整數n拆分成若干個正整數的和（至少兩個數,n<=100），
輸入格式:
一個正整數n
輸出格式:
若干行，每行一個等式（數與數之間要求非降序排列），最后一行給出解的總個數
輸入樣例:
在這里給出一組輸入，例如：
4輸出樣例:
4=1+1+1+1
4=1+1+2
4=1+3
4=2+2
4最后一行的4表示總共有4個解，
主要思路： 使用深度優先搜索演算法，從n開始，每次列舉所有可能的加數，如果加數滿足要求，則將其加入到組成部分中，繼續遞回處理剩余部分，直到剩余部分被成功分解或者不滿足要求，然后回溯，撤銷當前加數的選擇，嘗試下一個加數，這樣就能夠窮舉所有可能的分解方案， 使用遞回函式dfs()實作深度優先搜索，dfs()函式有三個引數：cur表示當前需要分解的數，sum表示已經分解的數之和，last表示上一個加數，當cur為0且sum為n時，找到了一個分解方案，將其輸出；否則，列舉所有可能的加數，并對剩余部分進行遞回處理， 在dfs()函式中使用陣列nums[]存盤每個組成部分的數值，使用變數size記錄當前組成部分的數量，在遞回處理剩余部分時，需要將當前加數加入組成部分，并遞回處理剩余部分，成功分解后回溯，撤銷當前加數的選擇，這里使用回溯法可以避免重復計算，
// 原作者箱庭，請勿轉載
#include <stdio.h> int n; // 待分解的數 int nums[100]; // 存盤每個組成部分的數值 int size; // 當前組成部分的數量 int cnt; // 分解方案的數量 // 深度優先搜索函式，cur為當前需要分解的數，sum為已分解的數之和，last為上一個加數 void dfs(int cur, int sum, int last) { // 如果已經成功分解出所有數且總和為n，則找到了一個分解方案 if (cur == 0 && sum == n) { cnt++; // 記錄分解方案的數量 // 輸出分解方案 printf("%d=%d", n, nums[0]); for (int i = 1; i < size; i++) { printf("+%d", nums[i]); } printf("\n"); } else { // 列舉所有可能的加數 for (int i = 1; i <= cur; i++) { // 確保加數不小于上一個加數，總和不超過n，并且不能僅剩一個數未加入 if (i >= last && sum + i <= n && i<n ) { nums[size] = i; // 將當前加數存入組成部分 size++; // 組成部分數量加1 dfs(cur - i, sum + i, i); // 繼續分解剩余部分 size--; // 回溯，撤銷當前加數的選擇 } } } }
//原作者箱庭，請勿轉載
int main() { scanf("%d", &n); // 輸入待分解的數 nums[0] = 0; // 初始化組成部分，第一個數為0 size = 0; // 初始化組成部分數量 dfs(n , 0, 1); // 開始分解 printf("%d", cnt); // 輸出分解方案數量 return 0; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/546312.html
標籤：其他
上一篇：03-RabbitMQ的作業模式