想必大家經過三天的練習，已經對遞回有了深入的理解吧，那么今天的題解就不“保姆式教學了”，想必大家也都能理解的（也可以理解成題解人想要偷懶）
整數分解為若干項之和
將一個正整數N分解成幾個正整數相加，可以有多種分解方法，例如7=6+1，7=5+2，7=5+1+1，…，編程求出正整數N的所有整數分解式子，
輸入格式：
每個輸入包含一個測驗用例，即正整數N (0<N≤30)，
輸出格式：
按遞增順序輸出N的所有整數分解式子，遞增順序是指：對于兩個分解序列N1?? ={n?1?? ,n?2?? ,?}和N?2?? ={m?1?? ,m?2?? ,?}，若存在i使得n?1?? =m?1?? ,?,n?i?? =m?i?? ，但是i+1<m?i+1?? ,則N?1?? 序列必定在N?2?? 序列之前輸出，每個式子由小到大相加，式子間用分號隔開，且每輸出4個式子后換行，
輸入樣例：
7
輸出樣例：
7=1+1+1+1+1+1+1;7=1+1+1+1+1+2;7=1+1+1+1+3;7=1+1+1+2+2
7=1+1+1+4;7=1+1+2+3;7=1+1+5;7=1+2+2+2
7=1+2+4;7=1+3+3;7=1+6;7=2+2+3
7=2+5;7=3+4;7=7
代碼如下
#include<bits/stdc++.h>//萬能頭檔案
using namespace std;
int n;
int s[33];
int ans=0;//記錄滿足結果的個數
void dfs(int x,int cur,int sum){
/*
x為當前要加的數，cur為s陣列中要加
數的下標 ，sum為目前相加的數的總和
*/
if(sum>n)return ;//剪枝
if(sum==n){//如果當前的和等于n 輸出
ans++;//結果個數++，為了輸出要求的格式
cout<<n<<"="<<s[0];
for(int i=1;i<cur;i++){
cout<<"+"<<s[i];
}
if(ans%4!=0&&x!=n){
/*
除了行末都要輸出“; ”,注
意最后一行的最后一個不能有“; ”
*/
cout<<";";
}
if(ans%4==0){//每4個答案換一次行
cout<<endl;
}
}
for(int i=x;i<=n;i++){
s[cur]=i; //將i加入陣列
dfs(i,cur+1,sum+i);
/*
等待加入的陣列下標往后移一
位，此時的總和加上i;
*/
}
}
int main(){
cin>>n;
dfs(1,0,0);
return 0;
}
遞回實作指數型列舉
從 1～n 這 n 個整數中隨機選取任意多個，輸出所有可能的選擇方案，
輸入格式
輸入一個整數 n，
輸出格式
每行輸出一種方案，
同一行內的數必須升序排列，相鄰兩個數用恰好 1 個空格隔開，
對于沒有選任何數的方案，輸出空行，
本題有自定義校驗器（SPJ），各行（不同方案）之間的順序任意，
資料范圍
1≤n≤15
輸入樣例：
3
輸出樣例：
3
2
2 3
1
1 3
1 2
1 2 3
這里附上一張我嫖來的圖，覺得有了圖挺容易理解的
本題運用的是二叉樹遞回
每個數有三種狀態，0表示待考慮，1表示選擇，2表示不選
#include<iostream>
#include<cstring>
using namespace std;
int n;
int s[15];
/*
s陣列記錄每個數的狀態，0表示待考慮，
1表示選擇，2表示不選
*/
void f(int k) {
if (k > n) {
for (int i = 1; i <= n; i++) {
//如果是1，就輸出該數
if (s[i] == 1) {
cout << i << " ";
}
}
cout << endl;
return;
}
s[k] = 2;
f(k + 1);//第一個分支，不選
s[k] = 1;
f(k+1);//第二個分支，選擇
}
int main() {
cin >> n;
f(1);
return 0;
}
最后附上本題我借鑒的大佬題解的鏈接：https://blog.csdn.net/qq_41575507/article/details/108200053?utm_source=app&app_version=4.5.2
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/274481.html
標籤：其他