KMP
· · · kmp演算法是一種字串匹配演算法，用于在一個文本串中查找模式串的位置，出現的次數等；其中求解next陣列是核心(只與模式串有關)，若記模式串為p，next[i] = j 表示p[i]之前的子串中，存在長度為j的相同前綴和后綴，即p[0]–p[j-1]與p[i-j]~p[i-1]相同；如果p[j] = p[i]，則有next[i+1] = j+1，否則子串的最長公共前后綴長度必定小于j+1；充分利用已經匹配的字符和模式串的特征來減少指標回退，對于p[i]前的子串的公共前后綴，再分別尋找這兩部分的公共前后綴，共四段，這四段相同，通過j = next[j]和next陣列本身的定義，回溯到第一段后面一個位置，再判斷此時p[j]是否等于p[i]，若不等，以此方式遞回查找，直到相等或j<0；然后根據求得的next陣列與next陣列本身的定義來完成與文本串的匹配
C++
void get_next(string str2, int next[]) {
int i = 0, j = -1; // i為模式串指標，j表示最長公共前后綴長度
next[0] = -1; // 表示一個通配符，可和任意字符匹配
while (i < str2.length()) {
if (j == -1 || str2[i] == str2[j]) {
next[++i] = ++j;
}
else {
j = next[j]; //回退
}
}
}
int kmp(string str1, string str2, int next[]) {
int len1 = str1.length(), len2 = str2.length();
int i = 0, j = 0; // i,j分別表示文本串和模式串下標指標
while (i < len1 && j < len2) {
if (j == -1 || str1[i] == str2[j]) {
i++, j++;
}
else {
j = next[j];
}
}
if (j == len2) //匹配成功，回傳模式串第一次出現的首字符位置
return i - j + 1;
else //失敗
return -1;
}
Java
public static void get_next(String s2, int[] next) {
int i = 0, j = -1;
next[0] = -1;
while(i < s2.length()) {
if(j == -1 || s2.charAt(i) == s2.charAt(j)) {
next[++i] = ++j;
}
else {
j = next[j];
}
}
}
public static int kmp(String s1, String s2, int[] next) {
int len1 = s1.length(), len2 = s2.length();
int i = 0, j = 0;
while(i < len1 && j < len2) {
if(j == -1 || s1.charAt(i) == s2.charAt(j)) {
i++; j++;
}
else {
j = next[j];
}
}
if(j == len2) {
return i-j+1;
}
else {
return -1;
}
}
Python
def get_next(s2, next):
i,j = 0,-1
next.append(-1)
while i < len(s2):
if j == -1 or s2[i] == s2[j]:
i,j = i+1,j+1
next.append(j)
else:
j = next[j]
def kmp(s1, s2, next):
i,j = 0,0
while i < len(s1) and j <len(s2):
if j == -1 or s1[i] == s2[j]:
i,j = i+1,j+1
else:
j = next[j]
if j == len(s2):
return i-j+1
else:
return -1
最長公共子序列
· · ·這是典型的利用動態規劃思想求解字串的問題，目標是求出兩個字串的最長公共子序列；字串的一個子序列是原始字串洗掉一些字符而不改變剩余字符相對位置形成的新字串；根據求解目標和線性dp的核心特點，制定dp狀態：dp[i][j]表示第一個串的前i個字符與第二個串的前j個字符的最長公共子序列長度；假定兩個字串分別為s1,s2；討論：如果s1[i]≠s2[j]，即s1[i]無法與s2[j]匹配，此時狀態轉移到dp[i-1][j]或dp[i][j-1]，即dp[i][j] = max(dp[i-1][j],dp[i][j-1])，如果s1[i]==s2[j]，此時根據前面記憶化的結果，有：dp[i][j] = dp[i-1][j-1]+1；另外注意考慮邊界：當i=0或j=0，dp[i][j]=0;該問題(LCS)作為雙串匹配的最基本dp問題，狀態轉移思想應用廣泛
C++
int LCS(string s1, string s2) {
int n = s1.length(), m = s2.length();
vector<vector<int> > dp(n + 1, vector<int>(m + 1, 0)); // 初始化置零,考慮到i=0或j=0的情況
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
if (s1[i - 1] == s2[j - 1]) { // 注意此處下標表示要-1
dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1); // 結合上一個轉移方程，三個取最大
}
}
}
return dp[n][m]; // 回傳最長公共長度
}
Java
public static int LCS(String s1, String s2) {
int n = s1.length(), m = s2.length();
int[][] dp = new int[n+1][m+1]; // 默認初始化為0
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
if(s1.charAt(i-1) == s2.charAt(j-1)) {
dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1]+1);
}
}
}
return dp[n][m];
}
Python
def LCS(s1, s2):
n,m = len(s1),len(s2)
dp = [[0 for i in range(m+1)] for j in range(n+1)]
for i in range(1,n+1):
for j in range(1,m+1):
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
if s1[i-1] == s2[j-1]:
dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1)
return dp[n][m]
單調堆疊
· · · 單調堆疊，單調佇列，優先佇列都是十分優秀的資料結構，在很多實際問題中有著廣泛的應用；單調堆疊：堆疊內元素保持一定單調性的堆疊，包括單調遞增堆疊和單調遞減堆疊；單調堆疊有很多的應用場景，靈活變動性很大；一個最基礎的應用就是對于一個陣列中所有元素，每個元素只訪問一次，找到每個元素右邊比它大的元素下標之差，若不存在，則為0；下面就以解決此問題為例
C++
vector<int> Increase_Stack(vector<int>& array) {
stack<int> s;
vector<int> result(array.size()); // 存盤元素索引，并非元素
for (int i = array.size() - 1; i >= 0; i--) {
// 單調遞增堆疊，若當前元素大于堆疊頂元素，出堆疊
while (!s.empty() && array[s.top()] <= array[i]) {
s.pop();
}
/* 堆疊空則表示該元素右邊不存在比它大的元素，否則，堆疊頂元素即是
當前元素右邊最近的比它大的元素（根據入堆疊的順序可知）*/
result[i] = s.empty() ? 0 : (s.top() - i);
s.push(i);
}
return result;
}
Java
public static int[] Increase_Stack(int[] array){
Stack<Integer> s = new Stack<Integer>();
int[] result = new int[array.length];
for(int i = array.length -1 ; i >= 0; i--) {
while(!s.isEmpty() && array[s.peek()] <= array[i]) {
s.pop();
}
result[i] = s.isEmpty() ? 0 : (s.peek() - i);
s.push(i);
}
return result;
}
Python
def Increase_Stack(array):
stack,result = [],{} # 用串列實作堆疊，字典存盤元素索引
for i in range(len(array)-1, -1, -1):
while stack and array[stack[-1]] <= array[i]:
stack.pop()
if stack:
result[i] = stack[-1] - i
else:
result[i] = 0
stack.append(i)
return result
并查集
· · · 這是一種極其優雅的資料結構，其有著十分廣泛的應用，比如：判斷一個圖是否存在環路，判斷一個圖是否為連通圖，求最少需要添加幾條線才能使一個圖成為連通圖（具體應用為城市道路問題）等，因在kruskal演算法中用到并查集，在此引入求解最小生成樹問題的兩種演算法，prim演算法：從某一點出發，貪心選擇與該點連通且未曾選入的邊權最小的頂點加入集合，對每次新選入的點可能造成的影響來修改侯選邊的邊權和前驅結點，直到選入n-1個點，kruskal演算法：也運用了貪心策略，它是一種按權值的遞增次序依次選擇合適的邊來構造最小生成樹的方法，其核心是判斷并入的邊會不會產生環；并查集的常見操作為查詢，合并，添加等，在查詢的時候完成路徑壓縮可降低在后面搜索的復雜度；下面給出并查集常見操作
C++
void init(int vset[], int n) {
for (int i = 0; i < n; i++) {
vset[i] = i; // 初始化將雙親結點指向自己，方便后面的查詢判斷
}
}
int find(int vset[], int x) { // 遞回查詢x的根結點，回溯時壓縮路徑
if (x == vset[x]) return x;
else return vset[x] = find(vset, vset[x]);
}
// 上面查詢部分也可轉成非遞回寫法
int find(int vset[], int x) {
int temp, root = x;
while (root != vset[root]) { // 查找根結點
root = vset[root];
}
while (x != root) { // 非遞回路徑壓縮
temp = vset[x];
vset[x] = root;
x = temp;
}
return root;
}
inline bool is_connect(int vset[], int a, int b) { // 判斷a,b兩點是否連通
return find(vset, a) == find(vset, b);
}
void node_union(int vset[], int a, int b) { // 連通a,b兩點
int x = find(vset, a), y = find(vset, b);
vset[x] = y;
}
Java
public class Union {
private int[] vset;
public Union(int n){
this.vset = new int[n];
}
public void init(int n) {
for(int i = 0; i < n; i++) {
vset[i] = i;
}
}
public int find(int x) { //查詢部分用非遞回寫法,防止堆疊溢位
int temp, root = x;
while (root != vset[root]) {
root = vset[root];
}
while (x != root) {
temp = vset[x];
vset[x] = root;
x = temp;
}
return root;
}
public boolean is_connect(int a, int b) { // 判斷a,b是否連通
return find(a) == find(b);
}
public void node_union(int a, int b) { // 連通a,b兩個結點
int x = find(a), y = find(b);
vset[x] = y;
}
}
Python
class Union(object):
'''并查集類（基本操作)'''
def __init__(self, n):
self.vset = [i for i in range(n)]
def find(self, x): # 尾遞回，回溯時壓縮路徑
if x == self.vset[x]:
return x
else:
self.vset[x]=self.find(self.vset[x])
return self.vset[x]
def is_connect(self, a, b):
return self.find(a) == self.find(b)
def node_union(self, a, b):
x,y = self.find(a),self.find(b)
self.vset[x] = y
Floyd
· · · 處理最短路問題時，常用這四種演算法進行求解：Dijkstra是基于貪心策略的求解一個結點到其它結點的最短路徑，其特點是應用廣搜的思想，核心是考慮新加入結點的影響而修改前驅和記錄的最短路長度；Floyd演算法是基于動態規劃思想的多源最短路徑演算法，用于求解任意兩點之間的最短路徑，利用滾動陣列從三維降成二維，合理定義狀態和根據關系尋找狀態轉移方程是關鍵；Dijkstra演算法局限性最大，不允許存在負權邊；而Floyd演算法允許有負權邊，不允許有負權環；要求解存在負權邊甚至負權環的圖時，就要用到Bellman-Ford演算法和SPFA演算法了，而后者SPFA演算法是在前者的基礎上進行了剪枝優化；下面給出Floyd演算法核心代碼
C++
// 維護路徑矩陣
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
/* 從i號頂點到j號頂點經不經過k號頂點取二者的最短路徑，
并利用滾動陣列降維 */
a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
}
}
}
Java
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
a[i][j] = Math.min(a[i][j], a[i][k] + a[k][j]);
}
}
}
Python
for k in range(n):
for i in range(n):
for j in range(n):
a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
記憶化搜索
· · · 該演算法是搜索和動態規劃的結合，通過記憶化已經搜索過的情況并直接利用該值從而避免大量的重復搜索，極大的提高了效率，這是一種很訓練思維的演算法，能夠巧妙的解決很多實際問題，該演算法綜合了搜索剪枝的特性和動態規劃記憶化的特性，具有很大的實用性，下面就以一個經典的滑雪問題為例，實作該演算法的應用，問題大致描述：給定一個二維矩陣，從其中某個點出發，可到達上下左右四個相鄰的點，當且僅當到達的點對應的數比前一個數小，求該矩陣中最長的一條此種路徑
C++
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e2+5;
int a[maxn][maxn], dp[maxn][maxn], n, m;
int dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 };
void init(){ // 初始化二維矩陣
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
}
int mem_dfs(int x, int y) {
// 若是已經訪問過的路徑，直接回傳記憶化存盤結果
if (dp[x][y]) return dp[x][y];
int ans = 0;
for (int i = 0; i < 4; i++) {
int xx = x + dx[i], yy = y + dy[i];
//如果該點滿足訪問條件（沒越界且數值比前一個點更小，訪問并更新從該點出發的最長路徑
if (xx > 0 && xx <= n && yy > 0 && yy <= m && a[xx][yy] < a[x][y]){
ans = max(mem_dfs(xx, yy), ans);
}
}
dp[x][y] = ans + 1; // 不滿足條件時，加上本身點長度1，即為從該點出發的最大值
return dp[x][y];
}
int solve(){
int res = 0;
// 計算從每個點出發所得的最大長度，并更新最大值
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
res = max(mem_dfs(i, j), res);
}
}
cout << res; // 輸出最優解
}
int main(){
init();
solve();
return 0;
}
Java
import java.util.Scanner;
public class Mem_Dfs {
private int n, m;
private int[][] a;
private int[][] dp;
private static int[] dx = {-1,1,0,0}, dy = {0,0,-1,1};
public Mem_Dfs(int n, int m) {
this.n = n;
this.m = m;
this.a = new int[n+1][m+1];
this.dp = new int[n+1][m+1];
}
public int me_dfs(int x, int y) {
if(dp[x][y] != 0) {
return dp[x][y];
}
int res = 0;
for(int i = 0; i < 4; i++) {
int xx = x + dx[i], yy = y + dy[i];
if(xx > 0 && xx <= n && yy > 0 && yy <= m && a[xx][yy] < a[x][y]) {
res = Math.max(me_dfs(xx, yy), res);
}
}
dp[x][y] = res + 1;
return dp[x][y];
}
public void solve() {
int ans = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
ans = Math.max(me_dfs(i, j), ans);
}
}
System.out.println(ans);
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
Mem_Dfs m_dfs = new Mem_Dfs(n, m);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
m_dfs.a[i][j] = in.nextInt();
}
}
m_dfs.solve();
}
}
Python
n,m = [int(num) for num in input().split()]
dp = [[0 for j in range(m)] for i in range(n)]
a = [[int(i) for i in input().split()] for j in range(n)]
dx,dy = [-1,1,0,0],[0,0,-1,1]
def mem_dfs(x, y):
if dp[x][y]:
return dp[x][y]
cnt = 0
for i in range(4):
xx,yy = dx[i] + x,dy[i] + y
if xx >= 0 and xx < n and yy >= 0 and yy < m:
if(a[xx][yy] < a[x][y]):
cnt = max(mem_dfs(xx, yy), cnt)
dp[x][y] = cnt + 1
return dp[x][y]
def solve():
ans = 0
for i in range(n):
for j in range(m):
ans = max(mem_dfs(i, j), ans)
print(ans)
def main():
solve()
if __name__ == '__main__':
main()
背包問題
該類問題是動態規劃的入門問題，決定性思想和求解思路廣泛應用于各個領域；
01背包特點：每種物品只有一件，即只存在該種物品放與不放的決策；
完全背包特點：每種物品無窮多件，相比01背包僅有狀態轉移方程發生改變；
多重背包特點：每種物品的數量是確定的，可以將其樸素拆分成01背包進行求解；
對以下程式做特別說明：n表示物品種數，m表示背包容量，w陣串列示物品容量，v陣串列示物品價值，dp陣列存盤每種狀態下的最優解；以下程式都利用滾動陣列做空間優化，二維變一維
C++
// 01背包
void beibao_1(int dp[], int w[], int v[], int n, int m) {
for (int i = 1; i <= n; i++) {
for (int j = m; j >= w[i]; j--) {
// 本次決策只與上一次的狀態有關，且由狀態轉移的結果可知，需要逆向列舉
dp[j] = max(dp[j - w[i]] + v[i], dp[j]);
}
}
}
// 完全背包
void beibao_2(int dp[], int w[], int v[], int m, int n) {
for (int i = 1; i <= n; i++) {
for (int j = w[i]; j <= m; j++) {
//正向列舉，確保能夠充分利用前面記憶化的最優解
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
}
// 多重背包(a[]存盤每種物品有多少件)
void beibao_3(int dp[], int w[], int v[], int a[], int m, int n) {
// 樸素拆分成01背包進行求解
for (int i = 1; i <= n; i++) {
for (int j = m; j >= 0; j--) {
for (int k = 0; k <= a[i]; k++) {
if (j >= w[i] * k) {
// 存盤放當前物品k件與不放的最優解
dp[j] = max(dp[j - w[i] * k] + v[i] * k, dp[j]);
}
}
}
}
}
Java
// 01背包
public static void beibao_1(int[] dp, int[] w, int[] v, int n, int m) {
for (int i = 1; i <= n; i++) {
// 逆向列舉
for (int j = m; j >= w[i]; j--) {
dp[j] = Math.max(dp[j - w[i]] + v[i], dp[j]);
}
}
}
// 完全背包
public static void beibao_2(int[] dp, int[] w, int[] v, int n, int m) {
for (int i = 1; i <= n; i++) {
// 正向列舉
for (int j = w[i]; j <= m; j++) {
dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
}
}
}
// 多重背包
public static void beibao_3(int[] dp, int[] w, int[] v, int[] a, int n, int m) {
for (int i = 1; i <= n; i++) {
for (int j = m; j >= 0; j--) {
// 樸素拆分成01
for (int k = 0; k <= a[i]; k++) {
if (j >= w[i] * k) {
dp[j] = Math.max(dp[j - w[i] * k] + v[i] * k, dp[j]);
}
}
}
}
}
Python
# 01背包
def beibao_1(dp, w, v, n, m):
for i in range(1, n+1):
'''此處w與v的索引都是從0開始的，故要-1'''
for j in range(m, w[i-1]-1, -1):
dp[j] = max(dp[j - w[i-1]] + v[i-1], dp[j]);
# 完全背包
def beibao_2(dp, w, v, n, m):
for i in range(1, n+1):
for j in range(w[i-1], m+1):
dp[j] = max(dp[j], dp[j - w[i-1]] + v[i-1]);
# 多重背包
def beibao_3(dp, w, v, a, n, m):
for i in range(1, n+1):
for j in range(m, -1, -1):
'''同理此處a索引也是從0開始'''
for k in range(a[i-1]+1):
if j >= w[i-1]*k:
dp[j] = max(dp[j - w[i-1] * k] + v[i-1] * k, dp[j]);
博弈論基礎
博弈問題特點：兩名選手交替操作，每次一步且在有限的合法集合中選取一種進行，合法操作只取決于情況本身，與選手無關；
幾種經典博弈問題：
巴士博弈：一堆n個物品，兩個人輪流從中取出1~m個，最后取光者勝；
分析：n與m的關系可以表示成：n=k*(m+1)+r 和 n=k*(m+1)，當為第一種情況，先者拿走r個，無論后者拿走多少了，先者都可以確保每輪拿走m+1個，從而最后獲得勝利，以同樣的方法來分析第二種情況，后者便變成了先者的第一種情況，此時后者會獲勝
威佐夫博弈：兩堆各若干物品，兩人輪流從任意一堆中至少取出一個或者從兩堆中取出相同多的物品，規定每次至少取一個，至多不限，最后取光者勝；
分析：利用數學歸納法，先統計出必輸局勢，可以看到每組的第一個是前面沒有出現的最小正整數，
兩堆可分別表示為a=[k*(1+sqrt(5)/2], b=a+k,k=0,1,2,3…，根據兩者差值*黃金分割比是否等于最小值來判斷是先手贏還是后手贏
斐波那契博弈：一堆n個物品，兩人輪流取，先取者第一次可以取任意多個，但不能取完，以后每次取的物品數不能超過上次取物品數的兩倍，取完者勝
分析：根據問題特點，可以判斷先手勝當且僅當n不是斐波那契數
尼姆博弈：有n堆物品，兩人輪流取，每次取某堆中不少于1個，最后取完者勝
分析：尼姆博弈是一個很重要的博弈問題，通過對可解狀態的統計分析，我們可以發現將n堆物品數量全部異或后結果為0先手必敗，否則必勝
很多博弈問題并非這幾種標準博弈問題，我們需要通過SG函式將其轉換成尼姆博弈進行求解
C++
// 巴士博弈
bool bashi(int n, int m) { // n個物品，每次每人最多取m個
if (n % (m + 1))
return true; //此時先手贏
else
return false; // 否則后手贏
}
// 威佐夫博弈
bool wezuofu(int a, int b) {// 兩堆物品的個數分別為a,b
double r = (sqrt(5) + 1) / 2;
int d = abs(a - b) * r;
if (d != min(a, b)) //
return true; // 此時先手贏
else
return false; // 后手贏
}
// 斐波那契博弈
bool fabonacci(int f[], int n) { // n個物品
f[0] = f[1] = 1;
for (int i = 2; f[i - 1] < n; i++) {
f[i] = f[i - 1] + f[i - 2];
if (f[i] == n)
return true; // 先手贏
}
return false; // 后手贏
}
// 尼姆博弈
bool nim(int a[], int n) { // a陣列存盤n堆物品的數量
int res = 0;
for (int i = 1; i <= n; i++) {
res ^= a[i]; // n堆物品數量異或
}
if (res)
return true; // 先手贏
else
return false; // 后手贏
}
Java
// 巴士博弈
public static boolean bashi(int n, int m) {
if (n % (m + 1) != 0)
return true;
else
return false;
}
// 威佐夫博弈
public static boolean wezuofu(int a, int b) {
double r = (Math.sqrt(5) + 1) / 2;
int d = (int)(Math.abs(a - b) * r);
if (d != Math.min(a, b))
return true;
else
return false;
}
// 斐波那契博弈
public static boolean fabonacci(int f[], int n) {
f[0] = f[1] = 1;
for (int i = 2; f[i - 1] < n; i++) {
f[i] = f[i - 1] + f[i - 2];
if (f[i] == n)
return true;
}
return false;
}
// 尼姆博弈
public static boolean nim(int a[], int n) {
int res = 0;
for (int i = 1; i <= n; i++) {
res ^= a[i];
}
if (res != 0)
return true;
else
return false;
}
Python
# 巴士博弈
def bashi(n, m):
if n%(m+1):
return True
else:
return False
# 威佐夫博弈
def wezuofu(a, b):
r = float((math.sqrt(5)+1)/2)
d = int(abs(a - b)*r)
if d != min(a, b):
return True
else:
return False
# 斐波那契博弈
def fabonacci(n):
f = [1,1]
i = 2
while f[i-1] < n:
f.append(f[i-1] + f[i-2])
if f[i] == n:
return True
i += 1
return False
# 尼姆博弈
def nim(a, n):
res = 0
for i in range(n):
res ^= a[i]
if res:
return True
else:
return False
排序
三種低效排序：
冒泡排序：相鄰元素比較，每一趟一個元素歸位；以升序為例：向下冒大泡（待排序列最大元素從后往前不斷歸位）；向上冒小泡（待排序列從前往后不斷歸位）
選擇排序：每次選擇目標數歸位（最大值/最小值），在待排序列中找到目標數下標，與待放位置的元素交換
插入排序：從第二個元素開始處理，每次將其插入在前面已排好序的相應位置
C++
// 冒泡排序
void bubble_sort(int a[], int length) {
for (int i = 0; i < length - 1; i++) { // n-1輪比較，可優化
for (int j = 0; j < length - i - 1; j++) { // 向下冒大泡，從后向前歸位
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]); //swap函式在<algorithm>頭檔案中
}
}
}
}
// 選擇排序
void select_sort(int a[], int length) {
for (int i = 0; i < length - 1; i++) { // n-1個元素歸位，第n個元素自動歸位
int index = i;
for (int j = i + 1; j < length; j++) { // 每輪比較找到最小值下標
if (a[j] < a[index]) {
index = j;
}
}
swap(a[i], a[index]);
}
}
// 插入排序
void insert_sort(int a[], int length) {
for (int i = 1; i < length; i++) { // 從第二個元素開始插入
int temp = a[i], j;
// 在前面已排好序的序列中找到待插入位置
for (j = i - 1; j >= 0 && temp < a[j]; j--) {
a[j + 1] = a[j];
}
a[j + 1] = temp;
}
}
Java
// 冒泡排序
public static void bubble_sort(int[] a) {
for(int i = 0; i < a.length-1; i++) {
for(int j = 0; j < a.length-i-1; j++) {
if(a[j] > a[j+1]) {
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
// 選擇排序
public static void select_sort(int[] a) {
for(int i = 0; i < a.length-1; i++) {
int index = i;
for(int j = i+1; j < a.length; j++) {
if(a[j] < a[index]) {
index = j;
}
}
int temp = a[index];
a[index] = a[i];
a[i] = temp;
}
}
// 插入排序
public static void insert_sort(int[] a) {
for(int i = 1; i < a.length; i++) {
int temp = a[i], j;
for(j = i-1; j >= 0 && temp < a[j]; j--) {
a[j+1] = a[j];
}
a[j+1] = temp;
}
}
Python
# 冒泡排序
def bubble_sort(a):
for i in range(0,len(a)):
for j in range(0,len(a)-i-1):
if a[j] > a[j+1]:
a[j],a[j+1] = a[j+1],a[j]
# 選擇排序
def select_sort(a):
for i in range(0,len(a)-1):
index = i
for j in range(i+1,len(a)):
if a[j] < a[index]:
index = j
a[i],a[index] = a[index],a[i]
# 插入排序
def insert_sort(a):
for i in range(1,len(a)):
temp = a[i]
j = i-1
while j >= 0 and temp < a[j]:
a[j+1] = a[j]
j -= 1
a[j+1] = temp
快速排序：以首元素為基準點，通過首尾指標將序列不斷劃分成大小兩個部分，分別對劃分后的序列做同樣處理，遞回至該子序列有序
C++
void quick_sort(int a[], int left, int right) {
int temp = a[left]; // 以首元素為基準點
int i = left, j = right;
if (i >= j) { // 序列長度為0或1必為有序序列，不用再處理
return;
}
while (i < j) { // 找到首元素待放位置，左小，右大
while (i < j && a[j] >= temp) {
j--;
}
a[i] = a[j];
while (i < j && a[i] <= temp) {
i++;
}
a[j] = a[i];
}
a[i] = temp; // 首元素歸位
quick_sort(a, left, i - 1);
quick_sort(a, i + 1, right);
}
Java
public static void quick_sort(int[] a, int left, int right) {
int temp = a[left];
int i = left, j = right;
if(i >= j) {
return ;
}
while(i < j) {
while(i < j && a[j] >= temp) {
j--;
}
a[i] = a[j];
while(i < j && a[i] <= temp) {
i++;
}
a[j] = a[i];
}
a[i] = temp;
quick_sort(a, left, i-1);
quick_sort(a, i+1, right);
}
Python
def quick_sort(a, left, right):
temp,i,j = a[left],left,right
if i >= j:
return
while i < j:
while i < j and a[j] >= temp:
j -= 1
a[i] = a[j]
while i < j and a[i] <= temp:
i += 1
a[j] = a[i]
a[i] = temp
quick_sort(a, left, i-1)
quick_sort(a, i+1, right)
歸并排序：利用二分思想，將待排序列遞回分割，直到序列長度為1(有序)，然后有序子序列兩兩合并
C++
void merge(int a[], int left, int mid, int right) {
int* temp = new int[right - left + 1]; // 合并成新序列輔助空間
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) { // 先處理完長度較小的序列
if (a[i] <= a[j]) {
temp[k++] = a[i++];
}
else {
temp[k++] = a[j++];
}
}
// 剩下序列為有序序列，直接歸位
while (i <= mid) {
temp[k++] = a[i++];
}
while (j <= right) {
temp[k++] = a[j++];
}
for (i = 0, j = left; i < k; i++, j++) {
a[j] = temp[i];
}
}
void merge_sort(int a[], int left, int right) {
if (left >= right) {
return;
}
int mid = (left + right) / 2;
merge_sort(a, left, mid);
merge_sort(a, mid + 1, right);
merge(a, left, mid, right);
}
Java
public static void merge_sort(int[] a, int left, int right) {
if(left >= right) {
return ;
}
int mid = (left+right)/2;
merge_sort(a, left, mid);
merge_sort(a, mid+1, right);
merge(a, left, mid, right);
}
public static void merge(int[] a, int left, int mid, int right) {
int[] temp = new int[right-left+1];
int i = left, j = mid+1, k = 0;
while(i <= mid && j <= right) {
if(a[i] <= a[j]) {
temp[k++] = a[i++];
}
else {
temp[k++] = a[j++];
}
}
while(i <= mid) {
temp[k++] = a[i++];
}
while(j <= right) {
temp[k++] = a[j++];
}
for(i = 0, j = left; i < k; i++, j++) {
a[j] = temp[i];
}
}
Python
def merge_sort(a, left, right):
if left >= right:
return
mid = int((left+right)/2)
merge_sort(a, left, mid)
merge_sort(a, mid+1, right)
merge(a, left, mid, right)
def merge(a, left, mid, right):
temp = []
i,j = left,mid+1
while i <= mid and j <= right:
if a[i] <= a[j]:
temp.append(a[i])
i += 1
else:
temp.append(a[j])
j += 1
temp += a[i:mid+1]+a[j:right+1]
a[left:right+1] = temp
希爾排序：按下標的希爾增量對序列進行分組，對每組使用直接插入排序演算法排序，隨著增量減少，每組序列元素增多，增量為1時，恰為有序一組
C++
void shell_sort(int a[], int length) {
for (int h = length / 2; h > 0; h /= 2) { // 逐步縮小增量h
// 從第h個元素逐個對其所在組進行直接插入排序操作
for (int i = h; i < length; i++) {
int j = i;
while (j >= h && a[j] < a[j - h]) {
swap(a[j], a[j - h]);
j -= h;
}
}
}
}
Java
public static void shell_sort(int[] a) {
for(int h = a.length/2; h > 0; h /= 2) {
for(int i = h; i < a.length; i++) {
int j = i;
while(j >= h && a[j] < a[j-h]) {
int temp = a[j];
a[j] = a[j-h];
a[j-h] = temp;
j -= h;
}
}
}
}
Python
def shell_sort(a):
h = int(len(a)/2)
while h > 0:
for i in range(h,len(a)):
j = i
while j >= h and a[j] < a[j-h]:
a[j],a[j-h] = a[j-h],a[j]
j -= h
h = int(h/2)
二分查找（加強版）
· · · 二分查找常應用在一個有序序列中進行資料查找，在該序列中待查找數可能不存在，可能存在多個，要求查找該資料第一次出現的位置或者再加上最后一次出現的位置，對于此類問題，要在logn的時間內完成查找，就需要用到二分查找，下面就以尋找某給定資料在序列中第一次出現的位置為例
C++
// 在a陣列中尋找x第一次出現的位置，并回傳其下標
int find(int a[], int len, int x) {
int left = 0, right = len - 1;
// 非遞回求解
while (left < right) {
int mid = (left + right) / 2;
if (a[mid] >= x) // 此處等號是關鍵，通過修改等號的位置，可以找到該數所在區間
right = mid; // 注意右端點的修改位置
else
left = mid + 1;
}
if (a[left] == x)
return left;
else
return -1; //表示該序列不存在待查找資料
}
Java
public static int find(int[] a, int x) {
int left = 0, right = a.length;
while(left < right) {
int mid = (left+right)/2;
if(a[mid] >= x)
right = mid;
else
left = mid + 1;
}
if(a[left] == x)
return left;
else
return -1;
}
Python
def find(a, x):
left,right = 0,len(a)-1
while left < right:
mid = int((left + right)/2)
if a[mid] >= x:
right = mid
else:
left = mid + 1
if a[left] == x:
return left
else:
return -1
埃氏篩
· · · 埃氏篩和歐拉篩是兩種常見的素數篩法，埃氏篩原理：如果某數是合數，那么它的倍數也一定是合數，根據這個原理可以避免很多不必要的檢測；歐拉篩原理：在埃氏篩的基礎上，讓每個合數只被它的最小質因子篩選一次，以達到不重復篩除的目的，效率為線性，故又稱線性篩
C++
void count_prime(int is_prime[], int n) { // 求出n以內的所有素數，初始化都為素數，默認為0
is_prime[0] = is_prime[1] = 1; // 0和1都不是素數
for (int i = 2; i <= n; i++) {
if (!is_prime[i]) { // 如果i是素數，那么i的倍數則不是素數
for (int j = i * i; j <= n; j += i) { // 注意從i*i開始篩是因為2到i-1的倍數已經篩過了
is_prime[j] = 1;
}
}
}
}
Java
public static void count_prime(boolean[] is_prime, int n) { // 初始化默認全是素數，表示成ture
is_prime[0] = is_prime[1] = false;
for(int i = 2; i <= n; i++) {
if(is_prime[i]) { // 如果i為素數
for(int j = i*i; j <= n; j += i) {
is_prime[j] = false;
}
}
}
}
Python
def count_prime(is_prime, n):
is_prime[0] = is_prime[1] = 1
for i in range(2,n+1):
if not is_prime[i]:
j = i*i
while j <= n:
is_prime[j] = 1
j += i
唯一分解定理
· · · 對于任何一個大于1的正整數，都存在一個標準的分解式：N=p1a1*p2a2…pn^an（其中pn為質數，an為指數）；此定理表明：任何一個大于1的正整數都可以表示為素數的積；該定理有著廣泛的應用，設X(n)代表n的正因子的數量，X(n)=(a1+1)(a2+1)…*(an+1)，下面就給出求解一個數正因子數量的代碼
C++
// 求解x正因子的數量
int get_count(int prime[],int cnt, int x) { // prime為素數陣列，cnt為素數個數
int ans = 1;
for (int i = 1; i <= cnt && prime[i] <= x; i++) {
int sum = 0; // 表示當前質因數的冪指數
while (x % prime[i] == 0) {
sum++;
x /= prime[i];
}
ans *= (sum + 1); // 直接利用定理計算
}
if (x > 1) // 此時最后結果肯定是素數，根據定理，故乘2
ans *= 2;
return ans;
}
Java
public static int get_count(int[] prime, int cnt, int x) {
int res = 0;
for(int i = 1; i <= cnt && prime[i] <= x; i++) {
int sum = 0;
while(x % prime[i] == 0) {
sum++;
x /= prime[i];
}
res *= (sum+1);
}
if(x > 1)
res *= 2;
return res;
}
Python
def get_count(prime, cnt, x):
ans,i = 0,1
while i <= cnt and prime[i] <= x:
sum = 0
while(x % prime[i] == 0):
sum += 1
x /= prime[i]
ans *= (sum+1)
if x > 1:
ans *= 2
return ans
總結：雖然只涉及了常用演算法的冰山一角，但這些思想在后面很多演算法的理解上有著很深刻的應用
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/261014.html
標籤：其他
上一篇：C語言基礎——讓我用短短幾分鐘就讓你了解資料是怎樣在記憶體中存盤的
下一篇：自動駕駛概述