【算法】开篇
前言
最近出一系列算法的博客，以供復習。今天先列出一個綱，明天開始寫！
什么叫算法
算法（algorithm），在數學（算學）和計算機科學之中，為任何一系列良定義的具體計算步驟，常用于計算、數據處理和自動推理。作為一個有效方法，算法被用于計算函數，它包含了一系列定義清晰的指令，并可于有限的時間及空間內清楚的表述出來。
算法中的指令描述的是一個計算，當其運行時能從一個初始狀態(tài)和初始輸入（可能為空）開始，經過一系列有限而清晰定義的狀態(tài)最終產生輸出并停止于一個終態(tài)。一個狀態(tài)到另一個狀態(tài)的轉移不一定是確定的。包括隨機化算法在內的一些算法，都包含了一些隨機輸入。[來源：維基百科]
算法描述
算法設計過程
算法設計工具
循環(huán)設計
設計思維
自底向上的設計——核心合并
自頂向下的設計——核心分解
挖掘內在規(guī)律構建計算模型
挖掘問題的內在規(guī)律，并且挖掘其計算模型。
衡量算法的標準
主要是針對時間復雜度和空間復雜度的分析，由于是前言，所以這些放在后篇了。
常用算法
迭代法
- 簡單的迭代運算
- 楊輝三角形
- 穿越沙漠問題
- 內存移動問題
- 當 N<= 100 時 ，求N 階乘的準確值
- 求解方程近似算法
- 非線性方程
- 線性方程
- 線性規(guī)劃
- 線性規(guī)劃最值求解
蠻力法
-
枚舉法
-
輸入 n 個數字 ( 在 0 與 9 之間 ) ，然后統(tǒng)計出這組數中相鄰兩個數字組成的鏈環(huán)數字對出現(xiàn)的次數。
-
解數字迷
-
輸出玫瑰矩陣
- 窮舉查找
- 旅行商問題
- 背包問題
- 圖的搜索
- 迷宮問題
分治法
- 二分查找算法
- 設有 n 個元素的集合 a[0]~a[n-1] 是有序的，設計算法從這 n 個元素中找出值為 x 的特定元素。
- 大整數乘法和 Strassen 矩陣乘法
- 設 X, Y 是兩個 n 位的十進制數，求 X*Y 。
- 對于任意給定的 n 階方陣 A 和 B ，求 A × B 的積 C 。
- 棋盤覆蓋問題
- 殘缺棋盤
- 選擇性問題
- 選第 k 小值
回溯與分支限界
- 回溯法
- 四皇后問題
- 裝載問題
- n 皇后問題
- 0-1 背包問題
- 旅行商問題
- 分支限界法
- 裝載問題
- 非 0-1 背包問題
- 旅行商問題
貪心法
- 用貪心法求問題的解
- 活動安排問題
- 數列極差
- 最優(yōu)裝載
- 鍵盤輸入一個高精度的正整數N，去掉其中任意S個數字后剩下的數字按原左右次序將組成一個新的正整數。對給于定的N和S，尋找一種方案使得剩下的數字組成的新數最小。
- 近似貪心
- 找零問題
動態(tài)規(guī)劃
- 投資分配問題
- 背包問題
- 矩陣邊乘問題
- 最長公共子序問題
- 最大子段和問題
概率算法
- 隨機數
- 用線性同余法生成一個隨機序列
- 蒙特卡羅算法
- 利用隨機函數計算圓周率π\(zhòng)piπ
- 素數測試
- 舍伍德算法
- 設 A 是含有 n 個元素的集合，從 A 中選出第 k 小的元素，其中 1≤k≤n 。
- 拉斯維加斯算法
- n 皇后問題
注：點擊題目可以跳轉到對應文章，歡迎留言點贊！
（本來想寫全部的題目的，但是時間有限…）
累了
2020.07.22 ------- 李某人留
【參考】張小東老師ppt、維基百科（其余近期算法類的文章均有參考張老師的ppt）
總結
- 上一篇： aria2c: command not
- 下一篇： 联想E480升级硬盘到固态 加内存条