片頭
嗨~小伙伴們，大家好！現在我們來到實訓篇啦~本篇章涉及算法知識，比基礎篇稍微難一點，我會盡量把習題講的通俗易懂。準備好了嗎？咱們開始咯！
第1題? 遞歸實現指數型枚舉
??我們先畫個圖~
從圖中，我們看到，每個位置都有2種選擇，選或者不選。如果不選，那么該位置記為×；如果要選，該位置記為?，?整個結構是一層一層遞歸的，是一個遞歸搜索樹。
題目告訴我們，輸入的整數n的范圍：1<=n<=15，因此，我們可以定義一個長度為N的數組st[N]，N為16，多開一個空間，記錄每個位置的狀態：0表示還沒考慮，1表示選它，2表示不選它。
剛開始的時候，每個位置默認都是“不選”狀態，一直遞歸到最后一層，最后恢復現場；回到調用的地方，繼續往下執行；再一次選擇的時候，是“被選”狀態，一種遞歸到最后一層，最后恢復現場。
代碼如下：
//遞歸實現指數型枚舉
//從 1~n 這n個整數中隨機選取任意多個，輸出所有可能的選擇方案。
//輸入一個整數n。
//輸出每行輸出一種方案。
//同一行內的數必須升序排列，相鄰兩個數用恰好1個空格隔開。
//對于沒有選任何數的方案，輸出空行。
//數據范圍 1 < n < 15const int N = 16;
int n;
int st[N];//表示這個位置的狀態,//0表示還沒考慮,1表示選它,2表示不選它void Func(int k) {//越界if (k > n) {for (int i = 1; i <= n; i++) {if (st[i] == 1)printf("%d ", i);}cout << endl;return;}//第一次都是不選st[k] = 2;Func(k + 1); //遞歸到下一層st[k] = 0; //恢復現場//第二次選st[k] = 1;Func(k + 1);//遞歸到下一層st[k] = 0; //恢復現場
}int main() {cin >> n;Func(1); //k初始值為1,表示從第1個位置開始return 0;
}運行結果如下：
第2題? 遞歸實現排列型枚舉
?emmm，咱們先來畫一個圖~
我們可以采用：依次枚舉每個位置放哪個數。
題目已知，輸入的整數 1<=n<=9，定義長度為N的數組st[N]，N為10，多開一個空間，記錄每個位置的狀態：0 表示還沒放數，1~n 表示放了哪個數。
對于每一個位置，有1~n種選擇，如果前面的數被用了，那么后面就不能再使用這個數字。因此，我們可以定義一個bool型的數組used[N]，用來記錄這個數是否被用過。
我們還要保證按照從小到大的順序，因此，先排較小的數，再排較大的數，保證后一個數比前一個數大。定義一個for循環，依次循環遍歷。
代碼如下：
//遞歸實現排列型枚舉
//把 1~n 這 n 個整數排成一行后隨機打亂順序，輸出所有可能的次序。
//輸入格式一個整數n。
//輸出按照從小到大的順序輸出所有方案，每行1個。
//首先，同一行相鄰兩個數用一個空格隔開。
//其次，對于兩個不同的行，對應下標的數--比較，字典序較小的排在前面。
//數據范圍 1≤n < 9
//輸入樣例:
// 3
//輸出樣例 :
// 1 2 3
// 1 3 2
// 2 1 3
// 2 3 1
// 3 1 2
// 3 2 1const int N = 10;
int n;
int st[N]; //當前位置的狀態//0 表示還沒放數，1~n表示放了哪個數bool used[N]; //true表示用過，false表示還沒用過void Func(int k) {//邊界if (k > n) {for (int i = 1; i <= n; i++) {printf("%d ", st[i]);}cout << endl;return;}//依次枚舉每個分支，即當前位置可以填哪些數for (int i = 1; i <= n; i++) {if (!used[i]) { //如果這個數字沒有被用過st[k] = i; //當前這個位置填入數字used[i] = true; //標記這個數字被用過了Func(k + 1); //遞歸到下一層st[k] = 0; //恢復現場used[i] = false; //恢復現場}}
}int main() {cin >> n;Func(1);return 0;
}運行結果如下：
第3題? 遞歸實現組合型枚舉
這道題，仍然需要畫圖~
代碼如下：
//遞歸實現組合型枚舉
//從 1~n 這 n個整數中隨機選出 m 個，輸出所有可能的選擇方案。
//輸入兩個整數 n, m, 在同一行用空格隔開。
//輸出按照從小到大的順序輸出所有方案，每行1個。
//首先，同一行內的數升序排列，相鄰兩個數用一個空格隔開!
//其次，對于兩個不同的行，對應下標的數一一比較，字典序較小的排在前面(例如1357排在1368前面)
//數據范圍 n > 0 ， 0 < m < n ， n + (n - m)≤25
//輸入樣例 :
//5 3
//輸出樣例 :
// 1 2 3
// 1 2 4
// 1 2 5
// 1 3 4
// 1 3 5
// 1 4 5
// 2 3 4
// 2 3 5
// 2 4 5
// 3 4 5const int N = 30;
int ways[N];
int n, m;void dfs(int k, int start) {if (k > m) //如果k>m,那么剛好選了m個數,打印輸出{ for (int i = 1; i <= m; i++) {printf("%d ", ways[i]);}puts("");return;}for (int i = start; i <= n; i++) {ways[k] = i; //填入數dfs(k + 1, i + 1); //遞歸到下一層ways[k] = 0; //恢復現場}
}int main() {cin >> n >> m;dfs(1, 1);//最開始從第1個位置開始,start的初始值為1return 0;
}我們還可以對代碼進一步優化：當選中的前 k-1個數?+ 剩余的 n-start+1 之和小于 m 的時候，直接退出。
if (k - 1 + n - start + 1 < m) return;//剪枝: 如果把后面的數都選上，都不夠m個，當前的分支就一定無解第4題? 簡單斐波那契
這道題，我們在基礎篇已經講過。可以先定義一個數組，把斐波那契數列存進去，再遍歷。
代碼如下：
//簡單斐波那契
//以下數列0 1 1 2 3 5 8 13 21...被稱為裴波納契數列。
//這個數列從第3項開始，每一項都等于前兩項之和。
//輸入一個整數N，請你輸出這個序列的前N項。
//輸入一個整數N。
//輸出在一行中輸出斐波那契數列的前N項，數字之間用空格隔開。
//數據范圍 0 < N < 46
//輸入樣例: 5
//輸出樣例 : 0 1 1 2 3const int N = 50;int main() {int n;cin >> n;int a[N];a[0] = 0;a[1] = 1;a[2] = 1;for (int i = 3; i <= 46; i++) {a[i] = a[i - 1] + a[i - 2];}for (int i = 0; i < n; i++) {printf("%d ", a[i]);}cout << endl;return 0;
}?我們還可以將代碼優化：
int main() {int n;cin >> n;int a = 0;int b = 1;for (int i = 0; i <= n - 1; i++) //i的范圍: 0~n-1{cout << a << " ";//必須先打印a的值//如果先執行c=a+b,那么a原來的值會被覆蓋掉int c = a + b;a = b;b = c;}return 0;
}?我們畫個圖，理解一下優化代碼：
| i | a | b |
| 0 | f(0) = 0 | f(1) = 1 |
| 1 | f(1) = 1 | f(2) = 1 |
| 2 | f(2) = 1 | f(3) = 2 |
| 3 | f(3) = 2 | f(4) = 3 |
| 4 | f(4) = 3 | f(5) = 5 |
| 5 | f(5) = 5 | f(6) = 8 |
| ... | ... | ... |
| n-2 | f(n-2) | f(n-1) |
| n-1 | f(n-1) | f(n) |
| n | f(n) | f(n+1) |
觀察上表，我們發現
當 i?== 0?時，a的值為f(0)=0；
當 i == 1?時，a的值為f(1)=1；
當 i == 2?時，a的值為f(2)=1；
當 i == 3?時，a的值為f(3)=2；
當 i == 4?時，a的值為f(4)=3；
......
當 i == n-1 時，即可輸出a的值f(n-1)。
你可能會問：為啥不把打印a放在最后面？哈哈，如果把這行代碼放最后面，a原來的值會被覆蓋掉，所以必須把 cout<<a<<"? "; 這行代碼放最前面。
或者這樣寫也可以：
for (int i = 1; i <= n; i++) //i的范圍: 1~n{cout << a << " ";//必須先打印a的值//如果先執行c=a+b,那么a原來的值會被覆蓋掉int c = a + b;a = b;b = c;}第5題? 翻硬幣
?對于這道題，咱們先畫個圖~
因此，我們發現，每次都是翻轉相鄰2個硬幣，我們可以每相鄰2個硬幣共用1個開關。
我們可以定義2個數組，分別表示初始狀態和目標狀態，2個數組必須長度相同。定義計數器count，用來記錄總共操作步數。從初始數組的第一個元素開始比較，如果和目標數組對應位置的元素不一樣，那么改變當前元素的狀態，并且計數器+1。
代碼如下：
//翻硬市
//小明正在玩一個“翻硬幣”的游戲.
//桌上放著排成一排的若干硬幣。我們用"表示正面，用。表示反面(是小寫字母，不是零)
//比如，可能情形是: **oo***oooo
//如果同時翻轉左邊的兩個硬幣，則變為 : oooo***oooo
//現在小明的問題是 : 如果已知了初始狀態和要達到的目標狀態
//每次只能同時翻轉相鄰的兩個硬幣, 那么對特定的局面，最少要翻動多少次呢 ?
//我們約定 : 把翻動相鄰的兩個硬幣叫做一步操作。
//輸入格式
//兩行等長的字符串，分別表示初始狀態和要達到的目標狀態
//輸出格式
//1個整數，表示最小操作步數
//數據范圍
//輸入字符串的長度均不超過100.
//數據保證答案一定有解。const int N = 110;
char start[N];
char aim[N];void turn(int a) {if (start[a] == '*')start[a] = 'o';elsestart[a] = '*';
}int main() {cin >> start; //輸入初始狀態cin >> aim; //輸入目標狀態int len = strlen(start); //計算字符串長度int count = 0; //統計翻轉次數for (int i = 0; i < len; i++) {if (start[i] != aim[i]) //如果當前位置的值二者不相同,//那么將start位置的值改變{turn(i);turn(i + 1);count++; //次數+1}}cout << count << endl;return 0;
}第6題? 漢諾塔
咱們可以先畫個圖，理解一下什么是漢諾塔問題規則：
Hanoi塔問題規則
- 每次只能移動1個圓盤；
- 圓盤可以插在X、Y和Z中的任一塔座上；
- 任何時刻都不能將一個較大的圓盤壓在較小的圓盤之上。
?如圖所示是一個3階的Hanoi塔演示（從左往右依次為X、Y、Z塔）：
Hanoi塔分析
①當 n==1 階漢諾塔時，將唯一的圓盤從塔座X直接移動到塔座Z。
?②當 n>1 時（動圖展示為 n==3），需要利用Z作為輔助塔，總是設法將X塔的最后一個圓盤n移動到Z塔下，則必然要將 1~n-1 個圓盤移動到Y塔上
③此時Y塔作為最初的X塔的狀態，X塔作為Z塔的最初狀態，X塔是輔助塔，應該將當前Y塔下的最后1個圓盤 n-1 移動到Z塔上。
④若 n>3，則不斷在②和③循環執行，直到將所有的圓盤全部有移動到Z塔上
⑤當還剩最后1個圓盤時，則執行第1個步驟，直接將圓盤移動到Z塔。
如上步驟一般，當 n>1 總是在步驟②、③重復，且Z塔與X塔交換成為輔助塔。所以，我們可以使用遞歸來處理這種重復步驟。
//漢諾塔//定義漢諾塔遞歸函數
//n: 盤子的數量
//source: 起始柱
//target: 目標柱
//auxiliary: 輔助柱void hanota(int n, char source, char target, char auxiliary) {//基本情況: 如果只有1個盤子,直接移動到目標柱if (n == 1) {cout << "將盤子 1 從 " << source << " 移動到 " << target << endl;return; //遞歸終止}//遞歸步驟1: 將前 n-1 個盤子從起始柱移動到輔助柱(借助目標柱)hanota(n - 1, source, auxiliary, target);//將第n個盤子(最大的盤子)從起始柱移動到目標柱cout << "將盤子 " << n << " 從 " << source << " 移動到 " << target << endl;//遞歸步驟2: 將前 n-1 個盤子從輔助柱移動到目標柱(借助起始柱)hanota(n - 1, auxiliary, target, source);}int main() {int n = 3;cout << "解決 " << n << " 個盤子的漢諾塔問題: " << endl;//調用漢諾塔函數, A 是起始柱, C是目標柱, B是輔助柱hanota(n, 'A', 'C', 'B');return 0;
}
?第7題? 奇妙變換
?這道題，我們只需要按照題目要求，編寫代碼即可。注意：這里的元素類型為長整型long long，如果為int整型，容易溢出。
#include <iostream>
using namespace std;const int mod = 998244353;long long func(long long n){if(n<=10) return n*(n-1);else{long long ans = 2*n*func(n-6);ans %= mod;return ans;}
}int main()
{long long n;cin >> n;long long ret = func(n);cout << ret << endl;return 0;
}第8題? 全排列的價值
我們舉個例子，比如：“3”的全排列
假設有5個數，分別為“1”，“3”，“2”，“5”，“4”，全排列的價值為8?
做過逆序對問題的話，明顯可以看出對于任意一個排序，其價值等于逆序對的數量。考慮使用dp來進行遞推，我們定義f(n)為1~n的全排列中所有排列的價值之和，明顯可以得到f(1)=0，f(2)=1。
關鍵在于：如何從f(n-1)遞推得到f(n)的值？我們以n為4時進行舉例，仔細觀察3的全排列：
此時，我們在這些排列的基礎上插入”4“，無論在哪個排列中插入”4“，都有4個插入的位置，比如插入第1個排列（1，2，3）時可以得到下面4種情況：
我們每個排列只看元素4帶來的貢獻分別為 0+1+2+3 = 6，對于3的任何一個排列我們插入"4"帶來的價值都一樣，這是因為我們在n-1的全排列插入n時，排列中的元素都嚴格小于n，所以我們當n插入的位置之前有幾個元素，則帶來的價值就是幾。
根據該推導可知：當在n-1的任何一個排列插入n時，n帶來的貢獻則為，也就是從1累加到n-1，我們可以使用高斯求和計算。當然，這只是1個排列帶來的價值，對于n而言，它的全排列的數量為n！，我們設g(n)為n的全排列的數量，也就是n的階乘。
我們上述只考慮了n給我們帶來的價值，我們當然還必須考慮其他數，對于排列（1，2，3），在插入4后有四種情況，它自己也變成了4份，價值也相應變成了4倍，"3" 的任何一個排列的價值都是如此。由此我們可以得知，當從f(n-1)遞推到f(n)時，f(n-1)會變成n倍。根據上述的推導我們可以得到遞推轉移公式：
?答案很大，在推導過程中，需要進行取模
typedef long long ll;
const int MOD = 998244353; //定義模數vector<long long> f(1000010, 0);//f數組,存儲結果
vector<long long> g(1000010, 0);//g數組,存儲階乘//初始化g數組,計算階乘
void init(int n) {long long h = 1;for (int i = 1; i <= n; i++) {h = h * i % MOD; //計算階乘并取模g[i] = h;}
}//全排列的價值
int main() {int n;cin >> n; //輸入nf[1] = 0; //初始化f[1]init(n); //初始化g數組//動態規劃計算f[i]for (int i = 2; i <= n; i++) {f[i] = (f[i - 1] * i % MOD + (long long)i * (i - 1) / 2 % MOD * g[i - 1] % MOD) % MOD;}cout << f[n] << endl; //輸出結果return 0;
}第9題? 數正方形
對于本道題，咱們需要畫圖理解~
觀察上圖，我們可以發現，
①nn點陣，邊長(n-1)×(n-1)
②1×1的正方形，填 (n-1)^2個
③2×2的正方形中，有一個卡著中間的1個獨特正方形，加上本身，一共2個每個單元，能填(n-2)^2個
④同理，3×3的正方形中間可以卡2個獨特的正方形，加上本身，一共3個每個單元，能填(n-3)^2個
⑤一直到 (n-1)×(n-1)的正方形中間可以卡 n-2 個獨特的正方形，加上本身，一共 n-1 個每個單元，這就是第1個 i 的范圍，從1~n-1
⑥后面(n-1)^2就是總共的單元個數，乘以每個單元有多少個，即為for循環代碼含義。
我們看看當 n=6 時，也就是邊的個數 => n-1 = 5 情況：
?看到題給示例不同大小的畫法，一個思路是，把正方形劃分成不同維度的單元塊去找，有助于我們聚焦于更易于計算的子問題。
考慮一個 n×n 的點陣，其邊長為 (n-1)×(n-1)。
那我們先取 1×1 大小的單元，在這個 n×n 的點陣里，就像一塊小積木一樣，全圖四處劃動，顯然單元有 (n-1)×(n-1) 種存在的方式，而每個單元內部最多只能畫出1個正方形。因此，對于 1×1 這個維度在全圖中就有 1×(n-1)×(n-1) 種畫法。
?2×2 大小的單元，有 (n-2)×(n-2) 種取法，對于每個 2×2 單元的內部，能畫出一個 2×2 的邊框正方形，還能畫出一個斜著放的正方形，那么對于每個單元有2種畫法，對于 2×2 這個維度在全圖中就是 2×(n-2)×(n-2) 種畫法。
3×3 大小的單元，取法 (n-3)×(n-3) 種，對于每個?3×3?單元的內部，可以有3種畫法，全圖總共 3×(n-3)×(n-3) 種畫法。
..........
(n-1)×(n-1) 的單元，把整個圖框滿了，只能有1種取法，對于這個單元，內部易知有 n-1?種畫法，對于 (n-1)×(n-1) 這個維度在全圖就是 (n-1)×1×1?種畫法。
從 1 到 i 對每個 i × i 的單元遍歷求和：ans += i×(n-i)×(n-i)
每一步都取余一次就可以得到答案了。
#include <iostream>
using namespace std;typedef long long ll;
const int mod = 1e9 + 7;int main()
{ll n; // n*n 點陣cin >> n;ll ans = 0;for (int i = 1; i <= n - 1; i++) {ans += i * (n - i) * (n - i);ans %= mod;}cout << ans << endl;return 0;
}片尾
今天我們學習了遞歸以及相關的算法知識，希望看完這篇文章對友友們有所幫助！！！
求點贊收藏加關注！！！
謝謝大家！！！
?
