Python在AI领域是主流开发语言，学习入门不难，尤其是随着近几年人工智能深度学习快速发展，学习使用Python编程的程序员越来越多。同时Python涉及的领域很多，包括Web和Internet开发，科学计算和统计，人工智能，桌面界面开发，软件开发，后端开发，网络爬虫开发。每一项还涉及到背后的基础知识，如果没有基础知识支撑，那只会简单的程序操作也没有啥用。
所以，今天就给大家分享一些关于Python的编程小例子。
实例001：数字组合
题目 有四个数字：1、2、3、4，能组成多少个互不相同且无重复数字的三位数？各是多少？
程序分析 遍历全部可能，把有重复的剃掉。
total=0 for i in range(1,5): for j in range(1,5): for k in range(1,5): if ((i!=j)and(j!=k)and(k!=i)): print(i,j,k)
total+=1 print(total)
简便方法 用itertools中的permutations即可。
import itertools sum2=0 a=[1,2,3,4] for i in itertools.permutations(a,3): print(i) sum2+=1 print(sum2)
实例002：“个税计算”
题目
企业发放的奖金根据利润提成。利润(I)低于或等于10万元时，奖金可提10%；利润高于10万元，低于20万元时，低于10万元的部分按10%提成，高于10万元的部分，可提成7.5%；20万到40万之间时，高于20万元的部分，可提成5%；40万到60万之间时高于40万元的部分，可提成3%；60万到100万之间时，高于60万元的部分，可提成1.5%，高于100万元时，超过100万元的部分按1%提成，从键盘输入当月利润I，求应发放奖金总数？
程序分析 分区间计算即可。
profit=int(input('Show me the money: '))
bonus=0
thresholds=[100000,100000,200000,200000,400000]
rates=[0.1,0.075,0.05,0.03,0.015,0.01]
for i in range(len(thresholds)):
if profit<=thresholds[i]:
bonus+=profit*rates[i]
profit=0
break else: bonus+=thresholds[i]*rates[i]
profit-=thresholds[i]
bonus+=profit*rates[-1]
print(bonus)
实例003：完全平方数
题目 一个整数，它加上100后是一个完全平方数，再加上168又是一个完全平方数，请问该数是多少？
程序分析 因为168对于指数爆炸来说实在太小了，所以可以直接省略数学分析，用最朴素的方法来获取上限:
n=0 while (n+1)**2-n*n<=168:
n+=1 print(n+1)
思路是：最坏的结果是n的平方与(n+1)的平方刚好差168，由于是平方的关系，不可能存在比这更大的间隙。
至于判断是否是完全平方数，最简单的方法是：平方根的值小数为0即可。
结合起来：
n=0 while (n+1)**2-n*n<=168:
n+=1 for i in range((n+1)**2): if i**0.5==int(i**0.5) and (i+168)**0.5==int((i+168)**0.5):
print(i-100)
实例004：这天第几天
题目 输入某年某月某日，判断这一天是这一年的第几天？
程序分析 特殊情况，闰年时需考虑二月多加一天：
def isLeapYear(y): return (y%400==0 or (y%4==0 and y%100!=0))
DofM=[0,31,28,31,30,31,30,31,31,30,31,30]
res=0 year=int(input('Year:'))
month=int(input('Month:'))
day=int(input('day:')) if isLeapYear(year):
DofM[2]+=1 for i in range(month):
res+=DofM[i] print(res+day)
实例005：三数排序
题目 输入三个整数x,y,z，请把这三个数由小到大输出。
程序分析 练练手就随便找个排序算法实现一下，偷懒就直接调函数。
raw=[] for i in range(3):
x=int(input('int%d: '%(i)))
raw.append(x) for i in range(len(raw)): for j in range(i,len(raw)): if raw[i]>raw[j]:
raw[i],raw[j]=raw[j],raw[i] print(raw)
raw2=[] for i in range(3):
x=int(input('int%d: '%(i)))
raw2.append(x)
实例006：斐波那契数列
题目 斐波那契数列。
程序分析 斐波那契数列（Fibonacci sequence），从1,1开始，后面每一项等于前面两项之和。图方便就递归实现，图性能就用循环。
# 递归实现 def Fib(n): return 1 if n<=2 else Fib(n-1)+Fib(n-2)
print(Fib(int(input()))) # 朴素实现 target=int(input())
res=0 a,b=1,1 for i in range(target-1):
a,b=b,a+b
print(a)
实例007：copy
题目 将一个列表的数据复制到另一个列表中。
程序分析 使用列表[:]，拿不准可以调用copy模块。
import copy a = [1,2,3,4,['a','b']]
b = a # 赋值
c = a[:] # 浅拷贝
d = copy.copy(a) # 浅拷贝
e = copy.deepcopy(a) # 深拷贝
a.append(5)
a[4].append('c') print('a=',a) print('b=',b) print('c=',c) print('d=',d) print('e=',e)
============ RESTART: F:\PyWorkspace\Python100\100examples\007.py ============
a= [1, 2, 3, 4, ['a', 'b', 'c'], 5]
b= [1, 2, 3, 4, ['a', 'b', 'c'], 5]
c= [1, 2, 3, 4, ['a', 'b', 'c']]
d= [1, 2, 3, 4, ['a', 'b', 'c']]
e= [1, 2, 3, 4, ['a', 'b']]
实例008：九九乘法表
题目 输出 9*9 乘法口诀表。
程序分析 分行与列考虑，共9行9列，i控制行，j控制列。
for i in range(1,10): for j in range(1,i+1): print('%d*%d=%2ld '%(i,j,i*j),end='') print()
实例009：暂停一秒输出
题目 暂停一秒输出。
程序分析 使用 time 模块的 sleep() 函数。
import time for i in range(4): print(str(int(time.time()))[-2:]) time.sleep(1)
实例010：给人看的时间
题目 暂停一秒输出，并格式化当前时间。
程序分析 同009.
import time for i in range(4): print(time.strftime('%Y-%m-%d %H:%M:%S',time.localtime(time.time()))) time.sleep(1)
由于篇幅有限，就分享到这啦~如果想要了解更多关于Python编程小例子或者Python教程欢迎持续关注编程学习网

动态规划是一种解决问题的指导思想。
TriangleGiven a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.For example, given the following triangle[[2],[3,4],[6,5,7],[4,1,8,3]]The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).NOTE:Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
1. 根据题目，可采用深度优先搜索方法。
深度优先搜索中，类似于二叉树的递归算法，有两种策略： 遍历和分治。注意这两种策略都是递归算法。
1） 采用遍历 traverse, 把要变化的值（这里是sum）作为dfs递归函数的参数，在传递过程中使用。这里dfs的定义是，走到当前下（x，y）这个点的和为sum，这个sum随着点的下移在变化，因此把sum作为dfs的一个参数。
// traverse
void dfs(int x, int y, int sum) {
if (x == n) {
if (sum < best) {
best = sum;
}
return;
}
// 每次往下走有两个选择
dfs(x + 1, y, sum + a[x][y]);
// 向正下方走
dfs(x + 1, y + 1, sum + a[x][y]);
// 向右下方走
}
dfs(0,0);
// Java实现
class Solution {
private int minSum = Integer.MAX_VALUE;
public int minimumTotal(List<List<Integer>> triangle) {
dfs(triangle, 0, 0, 0);
return minSum;
}
private void dfs(List<List<Integer>> triangle, int x, int y, int sum) {
if (x == triangle.size()) {
minSum = Math.min(minSum, sum);
return;
}
sum += triangle.get(x).get(y);
dfs(triangle, x + 1, y, sum);
dfs(triangle, x + 1, y + 1, sum);
}
}
分析其复杂度：O(2^n)本题中的三角形本质上是一个二维数组，数据结构如下图所示。如果我们想要到达图中的节点 e ，经过的路径会有：a->b->e， a->c->e 两种。同理，如果想要到达节点 i ，经过的路径会有：abei, acei, acfi 三种可以看到，随着层的增加，到达每个节点的路径种类会逐渐增加，遍历的时间复杂度会随着层数增加迅速增加。具体而言，从顶点出发，每个节点往下走会有两个选择，根据数学的排列知识，到达最底层，一共有2 * 2 * ... * 2 * 2 种到达底端的路径，其中有 n 个2。因此，总的时间复杂度为O(n * 2^n) = O(2^n)，这样的时间复杂度基本上是不能用的。
2）采用Divide & Conquer 分治思想分治方法的核心要素： 一定要明确函数要做一件什么事情，返回什么结果，把函数的定义写在开头。分治法一个很重要的区分与traverse的方面是：traverse的返回值一般都是void，而分治法一般都有一个返回值，这个返回值就是在当前的参数下的最优解。
// Divide & Conquer
// dfs：从（x，y）出发走到最底层所能找到的最小路径之和
int dfs(int x, int y) {
if (x == n) {
return 0;
}
return min(dfs(x + 1, y), dfs(x + 1, y + 1)) + a[x][y];
}
dfs(0, 0);
// Java 实现代码
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
return dfs(triangle, 0, 0);
}
private int dfs(List<List<Integer>> triangle, int x, int y) {
if (x == triangle.size()) { return 0; }
return Math.min(dfs(triangle, x + 1, y), dfs(triangle, x + 1, y + 1)) +
triangle.get(x).get(y);
}
}
分析复杂度：复杂度和traverse一样，还是O(2n)，每次都有两个选择，一共n层，因此是O(2n)
根据上述的分析，dfs无法解决该问题，需要对dfs进行优化。
2. 优化
1） 分析分治算法的过程如下：计算dfs(0, 0) 依赖于dfs(1, 0) 和 dfs(1, 1)，依次往下，可以看到，分治算法中存在了大量的重复计算，例如dfs(2, 1) 2次，dfs(3, 1)和dfs(3, 2) 3次。因此，优化的思路就是避免重复计算。加入HashMap，每次求dfs结果之前，先看HashMap中是否已经有了对应的结果，如果有，直接拿来用，如果没有，计算dfs(x, y)，并将此时的键值对作为结果存放到HashMap。记忆化搜索这个题也可以使用一个二维数组存储计算过的dfs(x, y)值：NOTE： 下面这段伪代码看似使用了hashTable，但是实际上没有利用起来
// Divide & Conquer
int dfs(int x, int y) {
if (x == n) {
return 0;
}
// -1 表示还没有计算过
if (hashTable[x][y] != -1) {
// NOTE： 这个伪代码是错误的，实际上并没有利用上hashTable，因为dfs(x, y)采用递归最先计算出来的是靠近终点的值，因此，计算dfs(x, y)的时候，hashTable[x][y] 必然还没有结果。
return hashTable[x][y];
}
hashTable[x][y] = min(dfs(x + 1, y), dfs(x + 1, y + 1)) + a[x][y];
return hashTable[x][y];
}
正确的java实现如下：
// Java 实现：
// Divide & Conquer
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int[][] map = new int[triangle.size() + 1][triangle.size() + 1] ;
for (int i = 0; i <= triangle.size(); i++) {
for (int j = 0; j <= i; j++) {
map[i][j] = Integer.MIN_VALUE; // 初始化矩阵中每个没有计算过的值为Integer.MIN_VALUE
}
}
return dfs(triangle, 0, 0, map);
}
// 计算从 (x, y) 出发，到达最底端，最短路径和
private int dfs(List<List<Integer>> triangle, int x, int y, int[][] map) {
if (x == triangle.size()) { return 0; }
if (map[x + 1][y] == Integer.MIN_VALUE) {
// 靠近终点中的值才可能被map存起来
map[x + 1][y] = dfs(triangle, x + 1, y, map);
}
if (map[x + 1][y + 1] == Integer.MIN_VALUE) { // 靠近终点中的值才可能被map存起来
map[x + 1][y + 1] = dfs(triangle, x + 1, y + 1, map);
}
return Math.min(map[x + 1][y], map[x + 1][y + 1]) + triangle.get(x).get(y);
}
}
可以看到 这种记忆化搜索的策略和分治算法能很好的结合，而和traverse不太可。
记忆化搜索缺点：
有递归的开销，矩阵有多少层，递归就有多少层。
2）继续优化a、上述采用记忆化搜索，是一种自顶向下的策略，每次计算当前的dfs(x, y)时候，需要递归的计算出下一层的dfs(x + 1, y) 和 dfs(x + 1, y + 1)。该数组有多少层，递归深度就有多少层，因此递归开销很大。因此，我们可以把思路反过来，采用一种自底向上的方法。先计算最底层，让后逐渐上升。采用两层循环方式：
A[][]
// 状态定义
f[i][j] 表示从i，j出发到达最后一层的最小路径和
// 初始化，终点先有值
for(int i = 0; i < n; i++) {
f[n - 1][i] = A[n - 1][i];
}
// 循环递推求解
for (int i = n - 2; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
f[i][j] = Math.min(f[i + 1][j], f[i + 1][j + 1]) + A[i][j];
}
}
return f[0][0];
// 自底向上解法
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
// map[i][j] 存放从(i, j)出发到最后一行最小路径和
int[][] map = new int[triangle.size()][triangle.size()];
// 初始化最后一行，根据map[i][j]定义：最后一行的值为triangle最后一行值本身
for (int i = 0; i < triangle.size(); i++) {
map[triangle.size() - 1][i] = triangle.get(triangle.size() - 1).get(i);
}
// 两重循环，计算map矩阵
for (int x = triangle.size() - 2; x >= 0; x--) {
for (int y = 0; y <= x; y++) {
map[x][y] = Math.min(map[x + 1][y], map[x + 1][y + 1]) + triangle.get(x).get(y);
}
}
return map[0][0];
}
}
时间复杂度： O(n^2)
b、采用自顶向下的动态规划此时f[i][j]的含义变为：从起点到(i, j)这个点的最短路径。计算的方法为：f[i][j] = Math.min(f[i - 1][j - 1], f[i - 1][j]) + A[i][j];注意边界情况
// 自顶向下的动态规划
// f[i][j] 是从起点到(i, j)的最短路径
// 初始化
f[0][0] = A[0][0];
// 递推求解
for (int i = 1; i < n; i++) {
for (int j = 1; j <= i; j++) {
// to do
}
}
// 求结果：终点
Java实现：
// top-bottom
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
// map[i][j] 存放从 起点到(i, j) 的最小路径和
int[][] map = new int[triangle.size()][triangle.size()];
// 初始化map, 此时第一列和对角线为triangle对应的值本身只和
map[0][0] = triangle.get(0).get(0);
// 2-loop 计算矩阵剩余部分
for (int i = 1; i < triangle.size(); i++) {
for (int j = 0; j <= i; j++) {
if (j == 0) {
map[i][j] = map[i - 1][j] + triangle.get(i).get(j);
} else if (j == i) {
map[i][j] = map[i - 1][j - 1] + triangle.get(i).get(j);
} else {
map[i][j] = Math.min(map[i - 1][j - 1], map[i - 1][j]) + triangle.get(i).get(j);
}
}
}
// 从矩阵的最后一行中计算最后的结果
int result = map[triangle.size() - 1][0];
for (int i = 0; i < triangle.size(); i ++) {
result = Math.min(result, map[triangle.size() - 1][i]);
}
return result;
}
}
时间复杂度O(n^2)
记忆化搜索本质上就是一种动态规划。动态规划的本质就是解决重复计算的问题。
分治+记忆化搜索
自底向上的动态规划：先计算离终点最近的，一步一步向上计算，最后算出结果。
自顶向下的动态规划：顺着推
以下三种类型的问题，很大概率需要采用动态规划：a、问最大值/最小值：eg：上面的问题，问从上到下路径和的最小值b、问Yes/No eg：从上到下能否刚好找到一条和为target的路径c、问Count(*)：从(0, 0) 到 (n, 1) 一共有多少种出现以上三种类型的问题，90%用动态规划求解，考虑采用哪种形式的动态规划。
当题目参数 Can not sort / swap 90%可能是动态规划（反过来，能够排序/交换元素的 很可能不能用动态规划）
状态 State 「灵感+创造力」「总结了四类问题对应的固定的状态表示」eg：f[i][j]的意义 ， D&C + 记忆化搜索 dfs() 定义
方程 Function 「状态之间的联系，如何从一个小的状态去求一个大的状态」自顶向下中：离起点越近，状态越小eg: f[i][j]
初始化 Initialization最极限的小状态是什么，起点
答案 Answer最大的那个状态是什么，终点