- 算法需要符合的条件
- input
- output
- definiteness 明确性
- effectiveness 有效性
- finiteness 有限性
-
分治法 - Divide and Conquer
把大规模问题 依照相同的概念 分解成多个小规模子问题，各个击破，最后在将各子问题的解合并得到原问题的解。
快速排序、递归算法（recursion）、大整数乘法 -
递归法 - Recursion
一个可以反复执行的递归过程
一个可以离开递归执行过程的出口- 尾归递归 - Tail Recursion
函数或子程序的最后一条语句为递归调用，因为每次调用后，再回到前一次调用的第一条语句，就是 return 语句，所以不需要再进行任何运算工作。 - 堆栈 - Stack
一组相同数据类型的集合，所有的操作均在这个结构的顶端进行，LIFO。
- 尾归递归 - Tail Recursion
# 阶乘
def factorial(i):
if i == 0:
return 1
else:
ans = i * factorial(i - 1)
return ans
-
贪心法 - Greed Method
采取在当前状态下最有利或最优化的选择，不断地改进该解答，持续在每一步骤中选择最佳地方法，并且逐步逼近给定地目标，当达到某一步骤不能再继续前进时，算法就停止。
虽然是把求解的问题分成若干个子问题，但是，并不能保证最后解是最佳的。
常用于 找出图的最小生成树MST、最短路径、哈夫曼编码等。 -
动态规划法 - Dynamic Programming Algorithm
如果一个问题的答案与子问题相关的话，就可能将大问题拆解成各个小问题。
与分治法最大的不同点是：可以让每一个子问题的答案被存储起来，一共下次求解时直接取用。故而可解决重复计算的问题。def Fibonacci(n): result = output[n] if result == None: return 0 elif n == 1: return 1 else: return Fibonacci(n - 1) + Fibonacci(n - 2) output[n] = result return result -
迭代法 - Iterative Method
无法使用公式一次求解，而需要使用迭代。
变量初始值、循环条件判别式、调整变量增减值# 阶乘 sum = 1 n = 6 for j in range(n, 0, -1): sum *= j print("%d!=%3d" % (n, sum)) sum = 1 -
枚举法
列举所有的可能。 -
回溯法 - Backtracking
枚举法的一种。对某些问题而言，回溯法是可以找出所有（或一部分）解的一般性算法，同时避免枚举不正确的值。一旦发现不正确的值，就不再递归到下一层，而是回溯到上一层，以节省时间。是一种走不通就退回再走的方式。- 老鼠走迷宫
(1) 一次只能走一格
(2) 遇到墙无法再走时，则退回一步找找看是否有其他的路可以走
(3) 走过的路不再走第二次 - 如何在计算机中模拟迷宫？
二维数组MAZE[ i ][ j ] = 1 表示有墙，无法通过； 0 表示无墙，可以通过。
MAZE[ 1 ][ 1 ]是入口，MAZE[ m ][ n ] 是出口。
可以使用链表来记录走过的位置，并将走过的位置对应数组元素内容标记为 2，然后将这个位置放入堆栈再进行下一次选择。如果进入死胡同并且没有达到终点，就退出上一个位置，并退回到上一个岔路口选择其他的路。堆栈顶端的指针所指的方格编号便是老鼠当前所在的位置。
if 上一格可走: 把方格编号加入到堆栈 往上走 判断是否为出口 elif 下一个可走: 把方格编号加入到堆栈 往下走 判断是否为出口 elif 左一格可走: 把方格编号加入到堆栈 往左走 判断是否为出口 elif 右一格可走: 把放个编号加入到堆栈 往右走 判断是否为出口 else: 从堆栈删除一个方格编号 从堆栈中弹出一个方格编号 往回走 - 老鼠走迷宫