学习算法的感想
算法是什么
很多人可能都听过算法，可能也实现过一些算法，如果问他什么是算法，可能也很难的准确的说出来。确实，给一个事物下定义是很难的，因为总会有没有覆盖的点。
当然了，百科已经有明确的说明了，想温习的可以自己去看。
不过我还是喜欢这个概念：解决问题的方法步骤，虽然不精准，但是容易理解。
比如让你求解1+2+3+4+...+99999999+100000000=?
最笨的方法从头加到尾，用我的破电脑计算，大概16秒后可以得出答案。
换个高效的数学方法：
（1+100000000）*100000000/2，一步到位，时间接近0。
这两个方法都能够计算出结果，都可以称为算法，因为它们都解决了问题。
那哪个算法更好呢？如果从计算时间来看，很明显第二种方法更好；如果从理解的角度来看，明显第一种更好理解。好坏的判断需要根据设定的维度来判断。
算法有什么用
初学编程是不是有这样一些想法，很多时候写的一些小程序，好像不需要用什么”高端“算法，程序也运行的很好。
首先是因为计算量小，再加上计算机的速度又非常快，所以基本上暴力循环算法可以搞定一切。
其次，很多底层核心的算法都已经被前人实现了，而我们只需要站在前人的基础上，根据需要，知道如何使用即可。
因此平常很少有对算法有比较强烈的需求。
算法的用处需根据应用场景来决定的，比如你做了一个游戏，要求结束后会立刻显示分数排名，这里就需要一个排序算法，从高到低排好序显示出来。如果你的暴力循环需要好几秒肯定不行，体验太差，这个时候你可能就需要一个排序非常快的算法了。
图书馆借书，图书馆很大，不知道自己要找的书在哪个位置，这个时候可以利用图书馆强大的检索系统，输入书名，就能够告诉你书在哪个具体位置了。
现在学习编程，相比之前已经简单很多了，因为绝大数人都是属于应用类型的。
游戏有创作者和玩家，机器有发明者和应用者。在玩游戏和使用机器的过程的时候，我们不需要知道它们是怎么来的，只需要按照它的说明就能够很好的玩起来，甚至比它的发明者玩的更好。
就好像你要做一个图像处理的程序，可能你并不知道怎么实现图片处理；如果你能够找到一个处理照片的方法，按照它的使用说明，对接到你的程序中，你只需要做一些基础的工作，提供照片，程序就会返回一个结果给你了。
所以学程序有时候就像拼积木一样，明确步骤，找到每一步的解决方法，最后拼到一起就是你想要的东西。
至于解决方法是你独自想出来的，还是参考其它人的，似乎并不是很重要，重要的是你已经解决了这个问题了。
因此未来很多人都将成为应用型人才，尽管如此，懂得事物背后的原理还是非常重要的。
应用型比较注重经验，步骤流程；而算法比较注重抽象，建模，找出问题和事物的本质。
怎么学习算法
先看几个策略问题：
渡河问题
一个农夫带着一头狼、一头羊、一颗白菜过河。他面前只有一条船，只能容纳他和一件物品，只有农夫会划船。如果农夫不在场，狼会吃羊、羊会吃白菜，农夫在场则不会。
求将所有物品运到对岸的方案。
传教士与吃人恶魔的问题
有三个传教士和三个吃人恶魔要渡过一条河，河中有一条船，只能装下两个人。在任何地方（无论是岸边还是船上），如果吃人恶魔数量多于传教士数量，吃人恶魔就会吃掉传教士。
问：怎么才能让这些都安全过河？
四人过桥问题
在一个漆黑的夜里，四位旅游者来到一座狭窄而没有护栏的桥边，如果不借助手电筒的话，大家是无论也不敢过去。不幸的是四个人中只有一只手电筒，而桥窄得只够两个人同时通过。如果各自单独过桥的话，四个人所需要的时间分别是1、2、5、10分钟，如果两个人同时过桥，所需要的时间是较慢的那个人单独行动时的时间。
问：如何设计一个方案，让四个人尽快过桥。
上面的问题，或多或少相信应该有见过一些，并且很多人应该很快的想出答案来了。
现在问题来了，能不能用计算机帮我们解决上面的问题呢？
通常情况下，我们比较擅长利用计算机解决纯数字类的计算问题，对于这种实际场景问题，好像不知道如何下手。
类似的还有汉诺塔问题
找零钱问题
N皇后问题
数独问题
迷宫问题
根据自己实践的经验，之所以会对这种问题束手无策，主要在于无法将场景数字化，其实也就是数学建模。
比如让你测量一座山的高度，不可能真的拿尺子去测量，可以站在山顶上扔一个石头，计算石头下落的时间。根据自由落体运动，计算高度：H = 1/2gt2；
这个公式就是一个数学模型。当然实践还需要对模型进行修正，还得考虑阻力，人的反应时间等等。
按照数学方法对模型分类，又可以分为很多种类，比如有几何模型，微分方程模型以及和图论模型等。（来源于数学建模书籍）
针对不同的问题，需要建立不同的数学模型。将实际问题用数字或者图形表示出来。
然后结合特定的算法与数据结构，解决特定的问题。除了常见的列表，字典，集合和排序和搜索算法外，还有队列，栈，树，图等数据结构，贪心算法，递归算法，递推算法，记忆化搜索，动态规划，回溯算法，广度，深度优先算法，它们各自有自己的应用场景。
太多了，写不完了，留到下次写吧。之后还是直接根据具体实例讲好理解。先放两个问题的效果和代码；
阶乘-递归算法过程图示
f(5) = 5*4*3*2*1
# 递归法
def f(n):
if n==1 or n ==2:
return 1
else:
return f(n-1)+f(n-2)
# 递推法
def f2(n):
a = list(range(n+1))
for i in range(n+1):
if i<2:
a[i]=i
else:
a[i]=a[i-1]+a[i-2]
# print(a[i])
return a[n]N 皇后问题过程图示
数据变化过程
--开始选择--
[1, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
--结束选择--
--开始选择--
[1, 0, 0, 0]
[0, 0, 1, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
--结束选择--
--开始回撤--
[1, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
--结束回撤--
--开始选择--
[1, 0, 0, 0]
[0, 0, 0, 1]
[0, 0, 0, 0]
[0, 0, 0, 0]
--结束选择--
--开始选择--
[1, 0, 0, 0]
[0, 0, 0, 1]
[0, 1, 0, 0]
[0, 0, 0, 0]
--结束选择--
--开始回撤--
[1, 0, 0, 0]
[0, 0, 0, 1]
[0, 0, 0, 0]
[0, 0, 0, 0]
--结束回撤--
--开始回撤--
[1, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
--结束回撤--
--开始回撤--
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
--结束回撤--
--开始选择--
[0, 1, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
--结束选择--
--开始选择--
[0, 1, 0, 0]
[0, 0, 0, 1]
[0, 0, 0, 0]
[0, 0, 0, 0]
--结束选择--
--开始选择--
[0, 1, 0, 0]
[0, 0, 0, 1]
[1, 0, 0, 0]
[0, 0, 0, 0]
--结束选择--
--开始选择--
[0, 1, 0, 0]
[0, 0, 0, 1]
[1, 0, 0, 0]
[0, 0, 1, 0]
--结束选择--
----方案----
[0, 1, 0, 0]
[0, 0, 0, 1]
[1, 0, 0, 0]
[0, 0, 1, 0]
------------
--开始回撤--
[0, 1, 0, 0]
[0, 0, 0, 1]
[1, 0, 0, 0]
[0, 0, 0, 0]
--结束回撤--
--开始回撤--
[0, 1, 0, 0]
[0, 0, 0, 1]
[0, 0, 0, 0]
[0, 0, 0, 0]
--结束回撤--
--开始回撤--
[0, 1, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
--结束回撤--
--开始回撤--
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
--结束回撤--
--开始选择--
[0, 0, 1, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
--结束选择--
--开始选择--
[0, 0, 1, 0]
[1, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
--结束选择--
--开始选择--
[0, 0, 1, 0]
[1, 0, 0, 0]
[0, 0, 0, 1]
[0, 0, 0, 0]
--结束选择--
--开始选择--
[0, 0, 1, 0]
[1, 0, 0, 0]
[0, 0, 0, 1]
[0, 1, 0, 0]
--结束选择--
----方案----
[0, 0, 1, 0]
[1, 0, 0, 0]
[0, 0, 0, 1]
[0, 1, 0, 0]
------------
--开始回撤--
[0, 0, 1, 0]
[1, 0, 0, 0]
[0, 0, 0, 1]
[0, 0, 0, 0]
--结束回撤--
--开始回撤--
[0, 0, 1, 0]
[1, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
--结束回撤--
--开始回撤--
[0, 0, 1, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
--结束回撤--
--开始回撤--
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
--结束回撤--
--开始选择--
[0, 0, 0, 1]
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
--结束选择--
--开始选择--
[0, 0, 0, 1]
[1, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
--结束选择--
--开始选择--
[0, 0, 0, 1]
[1, 0, 0, 0]
[0, 0, 1, 0]
[0, 0, 0, 0]
--结束选择--
--开始回撤--
[0, 0, 0, 1]
[1, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
--结束回撤--
--开始回撤--
[0, 0, 0, 1]
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
--结束回撤--
--开始选择--
[0, 0, 0, 1]
[0, 1, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
--结束选择--
--开始回撤--
[0, 0, 0, 1]
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
--结束回撤--
--开始回撤--
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
--结束回撤--N皇后问题代码（4*4）
# 打印 board
def print_board(board):
for row in board:
print(row)
def is_valid(board, row, col):
# 检查正上方
for i in range(0, row):
if board[i][col] == 1:
return False
# 检查左斜上方
for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)):
if board[i][j] == 1:
return False
# 检查右斜上方
for i, j in zip(range(row-1, -1, -1), range(col,cols)):
if board[i][j] == 1:
return False
return True
def backtrack(board, row):
if row == rows:
print("----方案----")
print_board(board)
print("------------")
else:
for col in range(0, cols):
#判断该位置是否有效
if not is_valid(board, row, col):
continue
# 选择
board[row][col] = 1
print("--开始选择--")
print_board(board)
print("--结束选择--")
backtrack(board, row+1)
# 回撤
board[row][col] = 0
print("--开始回撤--")
print_board(board)
print("--结束回撤--")
row = 0
rows = 4
cols = 4
board = [[0 for i in range(rows)] for j in range(cols)]
backtrack(board, row)