㈠ 10個常用演算法
原理：
二分法查找，也稱為折半法，是一種在有序數組中查找特定元素的搜索演算法。
一般步驟：
（1）確定該區間的中間位置K；
（2）將查找的值T與array[k]比較。
若相等，查找成功返回此位置；否則確定新的查找區域，繼續二分查找。每一次查找與中間值比較，可以確定是否查找成功，不成功當前查找區間將縮小一半，遞歸查找即可。
原理：
一種通過重復將問題分解為同類的子問題而解決問題的方法
典型例子：
斐波那契數列
描述： 斐波那契數列 指的是這樣一個數列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368.....自然中的斐波那契數列") 自然中的斐波那契數列，這個數列從第3項開始，每一項都等於前兩項之和。
解決方式：
原理：
在搜索嘗試過程中尋找問題的解，當發現已不滿足求解條件時，就「回溯」返回，嘗試別的路徑。
回溯法是一種選優搜索法，按選優條件向前搜索，以達到目標。
但當探索到某一步時，發現原先選擇並不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態的點稱為「回溯點」。
解決問題一般步驟：
1、 針對所給問題，定義問題的解空間，它至少包含問題的一個（最優）解。
2 、確定易於搜索的解空間結構,使得能用回溯法方便地搜索整個解空間 。
3 、以深度優先的方式搜索解空間，並且在搜索過程中用剪枝函數避免無效搜索。
典型例子：
八皇後問題
描述：在8×8格的國際象棋上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處於同一行、同一列或同一斜線上，問有多少種擺法。
解決方式： https://blog.csdn.net/weixin_41865447/article/details/80034433
概念：
將雜亂無章的數據元素，通過一定的方法按關鍵字順序排列的過程叫做排序。
分類：
非穩定排序演算法：快速排序、希爾排序、堆排序、直接選擇排序
穩定的排序演算法：基數排序、冒泡排序、直接插入排序、折半插入排序、歸並排序
十個常用排序演算法
利用計算機的高性能來有目的的窮舉一個問題解空間的部分或所有的可能情況，從而求出問題的解的一種方法。
分類：
枚舉演算法、深度優先搜索、廣度優先搜索、A*演算法、回溯演算法、蒙特卡洛樹搜索、散列函數等演算法。
將一個數據轉換為一個標志，這個標志和源數據的每一個位元組都有十分緊密的關系。
很難找到逆向規律
只要符合散列思想的演算法都可以被稱為是Hash演算法
對不同的關鍵字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，這種現象稱為 碰撞 。
原理
在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的是在 某種意義上的局部最優解 。
從問題的某一個初始解出發一步一步地進行，根據某個優化測度，每一步都要確保能獲得局部最優解。每一步只考慮一個數據，他的選取應該滿足局部優化的條件。若下一個數據和部分最優解連在一起不再是可行解時，就不把該數據添加到部分解中，直到把所有數據枚舉完，或者不能再添加演算法停止。
一種近似演算法
一般步驟：
1、建立數學模型來描述問題；
2、把求解的問題分成若干個子問題；
3、對每一子問題求解，得到子問題的局部最優解；
4、把子問題的解局部最優解合成原來解問題的一個解。
典型例子：
0/1背包問題
馬踏棋盤
均分紙牌
例題： https://www.cnblogs.com/hust-chen/p/8646009.html
概念：
分治演算法的基本思想是將一個規模為N的問題分解為K個規模較小的子問題，這些子問題相互獨立且與原問題性質相同。求出子問題的解，就可得到原問題的解。即一種分目標完成程序演算法，簡單問題可用二分法完成。
一般步驟：
（1）分解，將要解決的問題劃分成若干規模較小的同類問題；
（2）求解，當子問題劃分得足夠小時，用較簡單的方法解決；
（3）合並，按原問題的要求，將子問題的解逐層合並構成原問題的解。
典型例子：
排序中：歸並排序、堆排序、快速排序；
實例：找偽幣、求最值、棋盤覆蓋
https://ke..com/item/%E5%88%86%E6%B2%BB%E7%AE%97%E6%B3%95/3263297
概念：
用於求解具有某種最優性質的問題。在這類問題中，可能會有許多可行解。每一個解都對應於一個值，我們希望找到具有最優值的解。
動態規劃一般可分為線性動規，區域動規，樹形動規，背包動規四類。
舉例：
線性動規：攔截導彈，合唱隊形，挖地雷，建學校，劍客決斗等；
區域動規：石子合並， 加分二叉樹，統計單詞個數，炮兵布陣等；
樹形動規：貪吃的九頭龍，二分查找樹，聚會的歡樂，數字三角形等；
背包問題：01背包問題，完全背包問題，分組背包問題，二維背包，裝箱問題，擠牛奶（同濟）等；
應用實例：
最短路徑問題 ，項目管理，網路流優化等；
https://ke..com/item/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/529408?fromtitle=%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%AE%97%E6%B3%95&fromid=15742703&fr=aladdin
概念：
在一個給定的字元文本內搜尋出自己想要找的一個字元串，平常所用的各種文本編輯器里的ctrl+F大多就是使用的這些字元匹配演算法。
分類：
KMP、BM、Sunday、Horspool、RK
參考：
https://cloud.tencent.com/developer/news/282694
https://blog.csdn.net/paincupid/article/details/81159320
㈡ 數學建模建模分為幾種類型，分別用什麼法求解
數學建模應當掌握的十類演算法
1、蒙特卡羅演算法（該演算法又稱隨機性模擬演算法，是通過計算機模擬來解決問題的算
法，同時可以通過模擬可以來檢驗自己模型的正確性，是比賽時必用的方法）
2、數據擬合、參數估計、插值等數據處理演算法（比賽中通常會遇到大量的數據需要
處理，而處理數據的關鍵就在於這些演算法，通常使用Matlab作為工具）
3、線性規劃、整數規劃、多元規劃、二次規劃等規劃類問題（建模競賽大多數問題
屬於最優化問題，很多時候這些問題可以用數學規劃演算法來描述，通常使用Lindo、
Lingo軟體實現）
4、圖論演算法（這類演算法可以分為很多種，包括最短路、網路流、二分圖等演算法，涉
及到圖論的問題可以用這些方法解決，需要認真准備）
5、動態規劃、回溯搜索、分治演算法、分支定界等計算機演算法（這些演算法是演算法設計
中比較常用的方法，很多場合可以用到競賽中）
6、最優化理論的三大非經典演算法：模擬退火法、神經網路、遺傳演算法（這些問題是
用來解決一些較困難的最優化問題的演算法，對於有些問題非常有幫助，但是演算法的實
現比較困難，需慎重使用）
7、網格演算法和窮舉法（網格演算法和窮舉法都是暴力搜索最優點的演算法，在很多競賽
題中有應用，當重點討論模型本身而輕視演算法的時候，可以使用這種暴力方案，最好
使用一些高級語言作為編程工具）
8、一些連續離散化方法（很多問題都是實際來的，數據可以是連續的，而計算機只
認的是離散的數據，因此將其離散化後進行差分代替微分、求和代替積分等思想是非
常重要的）
9、數值分析演算法（如果在比賽中採用高級語言進行編程的話，那一些數值分析中常
用的演算法比如方程組求解、矩陣運算、函數積分等演算法就需要額外編寫庫函數進行調
用）
10、圖象處理演算法（賽題中有一類問題與圖形有關，即使與圖形無關，論文中也應該
要不乏圖片的，這些圖形如何展示以及如何處理就是需要解決的問題，通常使用Matlab
進行處理）
㈢ 數學建模建模分為幾種類型，分別用什麼法求解
數學建模應當掌握的十類演算法
1、蒙特卡羅演算法（該演算法又稱隨機性模擬演算法，是通過計算機模擬來解決問題的算 法，同時可以通過模擬可以來檢驗自己模型的正確性，是比賽時必用的方法） 2、數據擬合、參數估計、插值等數據處理演算法（比賽中通常會遇到大量的數據需要 處理，而處理數據的關鍵就在於這些演算法，通常使用Matlab作為工具） 3、線性規劃、整數規劃、多元規劃、二次規劃等規劃類問題（建模競賽大多數問題 屬於最優化問題，很多時候這些問題可以用數學規劃演算法來描述，通常使用Lindo、 Lingo軟體實現） 4、圖論演算法（這類演算法可以分為很多種，包括最短路、網路流、二分圖等演算法，涉 及到圖論的問題可以用這些方法解決，需要認真准備） 5、動態規劃、回溯搜索、分治演算法、分支定界等計算機演算法（這些演算法是演算法設計 中比較常用的方法，很多場合可以用到競賽中） 6、最優化理論的三大非經典演算法：模擬退火法、神經網路、遺傳演算法（這些問題是 用來解決一些較困難的最優化問題的演算法，對於有些問題非常有幫助，但是演算法的實 現比較困難，需慎重使用） 7、網格演算法和窮舉法（網格演算法和窮舉法都是暴力搜索最優點的演算法，在很多競賽 題中有應用，當重點討論模型本身而輕視演算法的時候，可以使用這種暴力方案，最好 使用一些高級語言作為編程工具） 8、一些連續離散化方法（很多問題都是實際來的，數據可以是連續的，而計算機只 認的是離散的數據，因此將其離散化後進行差分代替微分、求和代替積分等思想是非 常重要的） 9、數值分析演算法（如果在比賽中採用高級語言進行編程的話，那一些數值分析中常 用的演算法比如方程組求解、矩陣運算、函數積分等演算法就需要額外編寫庫函數進行調 用） 10、圖象處理演算法（賽題中有一類問題與圖形有關，即使與圖形無關，論文中也應該 要不乏圖片的，這些圖形如何展示以及如何處理就是需要解決的問題，通常使用Matlab 進行處理）
㈣ 皇後問題為什麼能同時求出多個解
N皇後問題是一個經典的問題，在一個N*N的棋盤上放置N個皇後，每行一個並使其不能互相攻擊（同一行、同一列、同一斜線上的皇後都會自動攻擊）。
一、 求解N皇後問題是演算法中回溯法應用的一個經典案例
回溯演算法也叫試探法，它是一種系統地搜索問題的解的方法。回溯演算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。
在現實中，有很多問題往往需要我們把其所有可能窮舉出來，然後從中顫前宏找出滿足某種要求的可能或最優的情況，從而得到整個問題的解。回溯演算法就是解決這種問題的「通用演算法」，有「萬能演算法」之稱。N皇後問題在N增大時就是這樣一個解空間很大的問題，所以比較適合用這種方法求解。這也是N皇後問題的傳統解法，很經典。
下面是演算法的高級偽碼描述，這里用一個N*N的矩陣來存儲棋盤：
1) 演算法開始, 清空棋盤，當前行設為第一行，當前列設為第一列
2) 在當前行，當前列的位置上判斷是否滿足條件(即保證經過這一點的行,列與斜線上都沒有兩個皇後)，若不滿足，跳到第4步
3) 在當前位置上滿足條件的情形：
在當前位置放一個皇後，若當前行是最後一行，記錄一個解；
若當前行不是最後一行，當前行設為下一行, 當前列設為當前行的第一個待測位置；
若當前行是最後一行，當前列不是最後一列，當前列設為下一列；
若當前行是最後一行，當前列是最後茄冊一列，回溯，即清空當前行及以下各行的棋盤，然後，當前行設為上一行，當前列設為當前行的下一個待測位置；
以上返回到第2步
4) 在當前位置上不滿足條件的情形：
若當前列不是最後一列，當前列設為下一列，返回到第2步;
若當前列是最後一列了，回溯，即，若當前行已經是第一行了，演算法退出，否則，清空當前行及以下各行的棋盤，然後，當前行設為上一行，當前列設為當前行的下一個待測位置，返回到第2步;
演算法的基本原理是上面這個樣子，但不同的是用的數據結構不同，檢查某個位置是否滿足條件的方法也不同。為了提高效率，有各種優化策略，如多線程，多分配內存表示棋盤等。
在具體解決該問題時，可以將其拆分為幾個小問題。首先就是在棋盤上如何判斷兩個皇後是否能夠相互攻擊，在最初接觸這個問題時，首先想到的方法就是把棋盤存儲為一個二維數組，然後在需要在第i行第j列放置皇後時，根據問題的描述，首先判斷是在第i行是否有皇後，由於每行只有一個皇後，這個判斷也可以省略，然後判斷第j列是否有皇後，這個也很簡單，最後需要判斷在同一斜線上是否有皇後，按照該方法需要判斷兩次，正對角線方向和負對角線方向，總體來說也不難。但是寫完之後，總感覺很笨，因為在N皇後問題中這個函數的使用次數太多了，而這樣做效率較差，個人感覺很不爽。上網查看了別人的實現之後大吃一驚，大牛們都是使用一個一維數組來存儲棋盤，在某個位置上是否有皇後可以相互攻擊的判斷也很簡單。具體細節如下：
把棋盤存儲為一個N維數組a[N]，數組中第i個元素的值代表第i行的皇後位置，這樣便可以把問題的空間規模壓縮為一維O(N)，在判斷是否沖突時也很簡單，首先每行只有一個皇後，且在數組中只佔據一個元素的位置，行沖突就不存在了，其次是列沖突，判斷一下是否有a[i]與當前要放置皇後的列j相等即可。至於斜線沖突，通過觀察可以發現所有在斜線上沖突的皇後的位置都有悔或規律即它們所在的行列互減的絕對值相等，即| row – i | = | col – a[i] | 。這樣某個位置是否可以放置皇後的問題已經解決。
㈤ 回溯演算法與貪心演算法
回溯是遞歸的副產品，只要有遞歸就會有回溯 ，所以回溯法也經常和二叉樹遍歷，深度優先搜索混在一起，因為這兩種方式都是用了遞歸。
回溯法就是暴力搜索，並不是什麼高效的演算法，最多再剪枝一下。
回溯演算法能解決如下問題：
組合問題：N個數裡面按一定規則找出k個數的集合
排列問題：N個數按一定規則全排列，有幾種排列方式
切割問題：一個字元串按一定規則有幾種切割方式
子集問題：一個N個數的集合里有多少符合條件的子集
棋盤問題：N皇後，解數獨等等
回溯演算法的本質是縱向遍歷
回溯演算法模板為
貪心的本質是選擇每一階段的局部最優，從而達到全局最優
貪心演算法一般分為如下四步：
將問題分解為若干個子問題
找出適合的貪心策略
求解每一個子問題的最優解
將局部最優解堆疊成全局最優解
eg：擺動序列
如果連續數字之間的差嚴格地在正數和負數之間交替，則數字序列稱為擺動序列。第一個差（如果存在的話）可能是正數或負數。少於兩個元素的序列也是擺動序列。
例如， [1,7,4,9,2,5] 是一個擺動序列，因為差值 (6,-3,5,-7,3) 是正負交替出現的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是擺動序列，第一個序列是因為它的前兩個差值都是正數，第二個序列是因為它的最後一個差值為零。
給定一個整數序列，返回作為擺動序列的最長子序列的長度。 通過從原始序列中刪除一些（也可以不刪除）元素來獲得子序列，剩下的元素保持其原始順序。
示例 2:
輸入: [1,17,5,10,13,15,10,5,16,8]
輸出: 7
解釋: 這個序列包含幾個長度為 7 擺動序列，其中一個可為[1,17,10,13,10,16,8]。
㈥ 應用問題求解，加油站有效加油位問題！
1.已知有
3
個物品：(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容積
M=20，根據
0-1
背
包動態規劃的遞推式求出最優解。
2.按要求完成以下關於排序和查找的問題。
①對數組
A={15，29，135，18，32，1，27，25，5}，用快速排序方法將其排成遞減序。
②請描述遞減數組進行二分搜索的基本思想，並給出非遞歸演算法。
③給出上述演算法的遞歸演算法。
④使用上述演算法對①所得到的結果搜索如下元素，並給出搜索過程：18，31，135。
3.已知
1
(
)
*
(
)
i
i
k
k
ij
r
r
A
a
+
=
，
k
=1，2，3，4，5，6，
r
1
=5，
r
2
=10，
r
3
=3，
r
4
=12，
r
5
=5，
r
6
=50，
r
7
=6，
求矩陣鏈積
A
1
×A
2
×A
3
×A
4
×A
5
×A
6
的最佳求積順序（要求給出計算步驟）
。
4.
根
據
分
枝
限
界
算
法
基
本
過
程
,
求
解
0-1
背
包
問
題
。
已
知
n=3,M=20
，
(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。
5.試用貪心演算法求解汽車加油問題：
已知一輛汽車加滿油後可行駛
n
公里，
而旅途中有若干個加油站。
試設計一個有效演算法，指出應在哪些加油站停靠加油，使加油次數最少，請寫出該演算法。
6.試用動態規劃演算法實現下列問題：設
A
和
B
是兩個字元串。我們要用最少的字元操作，將字元串
A
轉換為字元串
B，這里所說的字元操作包括：
①刪除一個字元。
②插入一個字元。
③將一個字元改為另一個字元。
請寫出該演算法。
7.對於下圖使用
Dijkstra
演算法求由頂點
a
到頂點
h
的最短路徑。
8.試寫出用分治法對數組
A[n]實現快速排序的演算法。
9.有
n
個活動爭用一個活動室。
已知活動
i
佔用的時間區域為[s
i
，
f
i
]，
活動
i,j
相容的條件是：
sj≥f
i
，問題的解表示為(x
i
|
x
i
=1，2…，n,)，x
i
表示順序為
i
的活動編號活動，求一個相容的活動子
集，且安排的活動數目最多。
10.設
x
1
、
x
2
、
x
3
是一個三角形的三條邊，而且
x
1
+x
2
+x
3
=14。請問有多少種不同的三角形？給出解答過
程。
11.設數組
A
有
n
個元素，需要找出其中的最大最小值。
①請給出一個解決方法，並分析其復雜性。
②把
n
個元素等分為兩組
A1
和
A2，分別求這兩組的最大值和最小值，然後分別將這兩組的最大值
和最小值相比較，求出全部元素的最大值和最小值。如果
A1
和
A2
中的元素多於兩個，則再用上述
方法各分為兩個子集。直至子集中元素至多兩個元素為止。這是什麼方法的思想？請給出該方法的
演算法描述，並分析其復雜性。
12.有
n
個程序和長度為
L
的磁帶，
程序
i
的長度為
a
i
，
已知
L
a
n
i
i
≻
∑
=
1
，
求最優解(x
i
，
x
2
，
...，
x
i
，
…，
x
n
)，x
i
=0，1,
x
i
=1，表示程序
i
存入磁帶，x
i
=0，表示程序
i
不存入磁帶，滿足
L
a
x
n
i
i
i
≤
∑
=
1
，
且存放的程序數目最多。
13.試用分治法實現有重復元素的排列問題：設
)
,...,
,
{
2
1
n
r
r
r
R
=
是要進行排列的
n
個元素，其中元素
n
r
r
r
,...,
,
2
1
可能相同，試設計計算
R
的所有不同排列的演算法。
14.試用動態規劃演算法實現
0-1
閉包問題，請寫出該演算法。
15.試用貪心演算法求解下列問題：將正整數
n
分解為若干個互不相同的自然數之和，使這些自然數的乘
積最大，請寫出該演算法。
16.試寫出用分治法對一個有序表實現二分搜索的演算法。
17.試用動態規劃演算法實現最長公共子序列問題，請寫出該演算法。
18.假設有
7
個物品，它們的重量和價值如下表所示。若這些物品均不能被分割，且背包容量
M＝150，
使用回溯方法求解此背包問題，請寫出狀態空間搜索樹。
物品
A
B
C
D
E
F
G
重量
35
30
60
50
40
10
25
價值
10
40
30
50
35
40
30
19.求解子集和問題：對於集合
S={1，2
，6，8}，求子集，要求該子集的元素之和
d=9。
①畫出子集和問題的解空間樹；
②該樹運用回溯演算法，寫出依回溯演算法遍歷節點的順序；
③如果
S
中有
n
個元素，指定
d，用偽代碼描述求解子集和問題的回溯演算法。
20.求解填字游戲問題：在
3×3
個方格的方陣中要填入數字
1
到
N（N≥10）內的某
9
個數字，每個方
格填一個整數，似的所有相鄰兩個方格內的兩個整數之和為質數。試採用回溯法寫出滿足這個要求
的一種數字填法的演算法和滿足這個要求的全部數字填法的演算法。
21.試用動態規劃演算法實現最大子矩陣和問題：
求
n
m
×
矩陣
A
的一個子矩陣，
使其各元素之和為最大。
22.試用回溯法解決下列整數變換問題：關於整數
i
的變換
f
和
g
定義如下：
⎣
⎦
2
/
)
(
;
3
)
(
i
i
g
i
i
f
=
=
。
對於給定的兩個整數
n
和
m
，要求用最少的變換
f
和
g
變換次數將
n
變為
m
。
23.關於
15
謎問題。在一個
4×4
的方格的棋盤上，將數字
1
到
15
代表的
15
個棋子以任意的順序置入
各方格中，空出一格。要求通過有限次的移動，把一個給定的初始狀態變成目標狀態。移動的規則
是：每次只能把空格周圍的四格數字（棋子）中的任意一個移入空格，從而形成一個新的狀態。為
了有效的移動，設計了估值函數
C
1
(x)，表示在結點
x
的狀態下，沒有到達目標狀態下的正確位置
的棋子的個數。