$Date：2022?10?04$

$Everyone$ $has$ $to$ $grow$ $up,$ $but$ $not$ $everyone$ $understand$ $grew$ $up!$

文章目錄

• 🍕1. 紙牌三角形🍕
• • 🍔題目🍔
  • 🍔思路🍔
  • 🍔代碼🍔
  • 🍔總結🍔

🍕1. 紙牌三角形🍕

🍔題目🍔

A,2,3,4,5,6,7,8,9 共9張紙牌排成一個正三角形（A按1計算）。要求每個邊的和相等。如果考慮旋轉、鏡像后相同的算同一種，一共有多少種不同的排法呢？三角形如下

A 2 34 5 6 7 8 9

🍔思路🍔

本題是典型的全排列算法題目，通過對9個數字進行全排列，就可以計算出所有的三角形種類
什么是全排列？
全排列算法是一種經典的遞歸算法，如{1，2，3}的全排列為{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}，一共6鐘排列結果。全排列就是將全部可能出現的排序都列出來。而每一個數字能出現在任一個位置，如果不固定的話，那排序起來就會十分混亂，排序結果也不好記錄，所以遞歸求解的思路是每一次全排列都固定一個元素，然后求剩下元素的全排列，直到就剩一個元素的全排列時結束本次全排列，而且每一次全排列完成后，都應先將數字排序恢復到本次全排列開始前的狀態，以保證下一次的全排列都是基于初始狀態進行的。

舉個例子
對{1, 2, 3}進行全排列，下面按照上述全排列遞歸算法的思路實際模擬一遍
（每一次遞歸的第一步都是先判斷當前遍歷的是不是最后一個元素，如果是則說明全排列完成一次）

• 第1次遞歸調用，從頭開始遍歷，此時選擇當前第一個元素1為固定元素，并將固定元素1與當前遍歷的元素1進行換位，剩余元素為{2, 3}，此時排列為{1, 2, 3}；
• 第2次遞歸調用（基于第1次）：從剩余元素開始遍歷，此時選擇當前第一個元素2為固定元素，并將固定元素2與當前遍歷的元素2進行換位，剩余元素為{3}，此時排列為{1, 2, 3}；
• 第3次遞歸調用（基于第2次）：從剩余元素開始遍歷，此時選擇當前第一個元素3為固定元素，并將固定元素3與當前遍歷的元素3進行換位，剩余元素為空，此時排列為{1, 2, 3}；
• 第4次遞歸調用（基于第3次）：因為第4次遞歸調用時已經選擇到了最后一個元素，遍歷結束，取得第一個全排列結果{1, 2, 3}，第4次遞歸結束；
• 因為第3次遞歸調用已經遍歷結束，將本次遞歸調用開始前進行的換位元素返回原位置(3 <-> 3)，得到開始前的排列{1, 2, 3}；
• 第5次遞歸調用（基于第2次）：第2次遞歸往下遍歷，將固定元素2與遍歷元素3進行換位，剩余元素為空，此時排列為{1, 3, 2}；
• 第6次遞歸調用（基于第5次）：因為第6次遞歸調用時已經選擇到了最后一個元素，遍歷結束，取得第二個全排列結果{1, 3, 2}， 第6次遞歸結束；
• 因為第5次遞歸調用已經遍歷結束，將本次遞歸調用開始前進行的換位元素返回原位置(3 <-> 2)，得到開始前的排列{1, 2, 3}；
• 因為第2次遞歸調用已經遍歷結束，所以將本次遞歸調用開始前進行的換位元素返回原位置(2 <-> 2)，得到開始前的排列{1, 2, 3}；
• 第7次遞歸調用（基于第1次）：第1次遞歸往下遍歷，并將固定元素1與遍歷元素2進行換位，此時排列為{2, 1, 3}；
• 第8次遞歸調用（基于第7次）：此時選擇剩余元素的第一個元素3為固定元素，并將固定元素3與當前遍歷的元素3進行換位，剩余元素為空，此時排列為{2, 1, 3}；
• 第9次遞歸調用（基于第8次）：因為第9次遞歸調用時已經選擇到了最后一個元素，遍歷結束，取得第三個全排列結果{2, 1, 3}，第9次遞歸結束；
• 因為第8次遞歸調用已經遍歷結束，將本次遞歸調用開始前進行的換位元素返回原位置(3 <-> 3)，得到開始前的排列{2, 1, 3}；
• 第10次遞歸調用（基于第7次）：第7次遞歸往下遍歷，將固定元素1與遍歷元素3進行換位，剩余元素為空，此時排列為{2, 3, 1}；
• 第11次遞歸調用（基于第10次）：因為第11次遞歸調用時已經選擇到了最后一個元素，遍歷結束，取得遍歷結束，取得第四個全排列結果{2, 3, 1}， 第11次遞歸結束；
• 因為第10次遞歸調用已經遍歷結束，將本次遞歸調用開始前進行的換位元素返回原位置(1 <-> 3)，得到開始前的排列{2, 1, 3}；
• 因為第7次遞歸調用已經遍歷結束，將本次遞歸調用開始前進行的換位元素返回原位置(2 <-> 1)，得到開始前的排列{1, 2, 3}；
• 第12次遞歸調用（基于第1次）：第1次遞歸往下遍歷，并將固定元素1與遍歷元素3進行換位，剩余元素為{1}，此時排列為{3, 2, 1}；
• 第13次遞歸調用（基于第12次）：此時選擇剩余元素第一個元素1為固定元素，與遍歷元素1進行換位，剩余元素為空，此時排列為{3, 2, 1}；
• 第14次遞歸調用（基于第13次）：因為第14次遞歸調用時已經選擇到了最后一個元素，遍歷結束，取得遍歷結束，取得第五個全排列結果{3, 2, 1}， 第14次遞歸結束；
• 因為第13次遞歸調用已經遍歷結束，將本次遞歸調用開始前進行的換位元素返回原位置(1 <-> 1)，得到開始前的排列{3, 2, 1}；
• 第15次遞歸調用（基于第12次）：第12次遞歸往下遍歷，將固定元素1與遍歷元素2進行換位，此時排列為{3, 1, 2}；
• 第16次遞歸調用（基于第15次）：因為第16次遞歸調用時已經選擇到了最后一個元素，遍歷結束，取得遍歷結束，取得第六個全排列結果{3, 1, 2}， 第16次遞歸結束；
• 因為第12次遞歸調用已經遍歷結束，將本次遞歸調用開始前進行的換位元素返回原位置(1 <-> 3)，得到開始前的排列{1, 2, 3}；
• 因為第1次遞歸調用已經遍歷結束，將本次遞歸調用開始前進行的換位元素返回原位置(1 <-> 1)，得到開始前的排列{1, 2, 3}；

遞歸算法處理

確定遞歸函數的參數和返回值
參數：這里要求的是全排列的排列個數，所以參數一定有元素數組；要對整個數組進行遍歷，那么就少不了下標和范圍，所以這里的參數就是{數組、起始下標、數組長度}
返回值：這里不需要返回值，全排列個數通過全局變量進行累加計算，若放在函數中，則每次都會被重置

void func(vector<int>& arr, int start, int len);

確定終止條件
上面一開始就說到了終止條件：當遍歷到最后一個元素時，即說明完成一個全排列
所以終止條件就是當 下標值 >= 數組長度

if (start >= len)

確定單層遞歸的邏輯
由上面的模擬可以看到，每一次遞歸都是新的遍歷，所以有一個最外圍的循環遍歷邏輯，而每次遞歸前后都有換位操作，所以最終確定如下單層邏輯

for () {swap();func();swap(); }

🍔代碼🍔

void func(vector<int>& arr, int start, int len) {if (start >= len){count++;return;}for (i = start; i < len; i++){swap();func(arr, i + 1, len);swap();} }

以上是我對全排列算法的粗糙理解，但是本題還有一個關鍵點：考慮旋轉、鏡像后相同的算同一種
因為三角形有三個角，也就是說每個數字都能在三個角上出現一次，所以旋轉后相同算同一種的話，就需要將全排列總數 / 3；
鏡像對CV戰士來說好理解，就是2分一模一樣的數據，所以鏡像后算同一種的話，就需要將全排列總數 / 2；
最終計算結果就是 全排列總數 / 3 / 2，即總數 / 6；

🍔總結🍔

遞歸算法一般都很難理順，自己一開始自己按原理推理的時候也一直弄亂，記不清當前遞歸的條件。本題的關鍵就在于全排列算法和確定旋轉/鏡像的關系

總結

以上是生活随笔為你收集整理的【Code pratice】—— 纸牌三角形的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。