<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # Brute Force - 暴力枚舉 -------- #### 問題 序列$$ s $$有$$ n $$個成員$$ [s_1,s_2, \dots ,s_n] $$，每個成員可以選取$$ [1,2, \dots ,m] $$這$$ m $$種值。 例如當$$ n = 5 $$，$$ m = 3 $$時，序列$$ s $$有如下排列組合： $$ [1,1,1,1,1], [1,1,1,1,2], [1,1,1,1,3], [1,1,1,2,1] \dots $$ 遍歷序列$$ s $$的可能排列組合的所有情況。 #### 原理 加法原理：完成一件事情有$$ n $$類方法，每類方法有若干子方法，完成這件事需要且只需要$$ n $$類方法中的一類方法中的一個子方法。第$$ 1 $$類方法有$$ m_1 $$種子方法，第$$ 2 $$類方法有$$ m_2 $$種子方法，$$ \dots $$，第$$ n $$類方法有$$ m_n $$種子方法。則完成這件事共有$$ m_1 + m_2 + \cdots + m_n $$種方法。 乘法原理：完成一件事情需要$$ n $$個步驟，每個步驟有若干子方法，完成這件事情需要$$ n $$個步驟都完成，每個步驟需要且只需要選擇一種方法。第$$ 1 $$步有$$ m_1 $$種子方法，第$$ 2 $$步有$$ m_2 $$種子方法，$$ \dots $$，第$$ n $$步有$$ m_n $$種子方法。則完成這件事共有$$ m_1 \times m_2 \times \cdots \times m_n $$種方法。 #### 解法 通過$$ for $$循環枚舉出序列$$ s $$中的所有可能。 例如對于序列$$ [s_1,s_2,s_3,s_4] $$，其中每個元素的取值范圍是$$ [0,m] $$。如果把該序列看作一個正整數，從$$ 0000 $$依次數到$$ 9999 $$即為全部的排列組合。 對于成員數量為$$ n $$，每個成員有$$ m $$種值的序列$$ s $$，遍歷所有排列組合的時間復雜度$$ O(n^m) $$。 -------- #### 源碼 [BruteForce.h](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Search/BruteForce.h) [BruteForce.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Search/BruteForce.cpp) #### 測試 [BruteForceTest.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Search/BruteForceTest.cpp)