罗兵
探索云世界
罗兵
数学专业。擅数据分析，涉stock、lotto。了解随机过程分析、神经网络。涉web前端、后端。了解vba、js，稍擅python
我的博客即将入驻“云栖社区”，诚邀技术同仁一同入驻。
这是我的vue.js 2.0的学习笔记，采取了将官方文档中的代码集中到一个文件的形式。目的是保存下来，方便自己查阅。 !官方文档：https://cn.vuejs.org/v2/guide/ 01. vue 介绍 <html> <head> <meta charset="utf-8"/> <title>vue 介绍</title> <!-- <script src="js/vue.min.js"></script> --> <script src="https://unpkg.com/vue"></script> </head> <body> <!-- 官方文档：https://cn.vuejs.org/v2/guide/ --> <!-- 绑定 --> <div id="app"> <!-- ①声明式渲染 --> <p>{{ info }}</p> <p v-text="info"></p> <p v-html="info"></p> <p v-once>{{ info }}</p> <p>{{ info }}</p> <p>{{ info.concat("!!!") }}</p> <p>{{ info ? "has info" : "no info" }}</p> <!-- <p>{{ var info2 = "info2" }}</p> --> <!-- <p>{{ if (info) {return "info2"} }}</p> --> <!-- ②绑定元素特性 --> <span v-bind:title="message">鼠标悬停几秒钟查看此处动态绑定的提示信息！</span> <!-- ③条件：控制切换一个元素是否显示 --> <p v-if="seen">现在你看到我了</p> <!-- ④循环：绑定数组的数据来渲染一个项目列表 --> <ol> <li v-for="todo in todos"> {{ todo.text }} </li> </ol> <!-- ⑤处理用户输入 --> <button v-on:click="reverseMessage">逆转消息</button> </br> <!-- ⑥表单输入和应用状态之间的双向绑定 --> <input v-model="info"> <!-- ⑦使用组件 --> <ol> <todo-item v-for="item in groceryList" v-bind:todo="item" v-bind:key="item.id"> </todo-item> </ol> <!-- ①②③④⑤⑥⑦⑧⑨⑩ --> </div> <!-- 数据 --> <script> var data = { info : "Hello world", // ①⑥ message: '页面加载于 ' + new Date().toLocaleString(), // ② seen: true, // ③ todos: [ // ④ { text: '学习 JavaScript' }, { text: '学习 Vue' }, { text: '整个牛项目' } ], groceryList: [ // ⑦ { id: 0, text: '蔬菜' }, { id: 1, text: '奶酪' }, { id: 2, text: '随便其它什么人吃的东西' } ] } // 注册组件（全局）// ⑦ Vue.component('todo-item', { props: ['todo'], template: '<li>{{ todo.text }}</li>' }) // 创建根实例 var vm = new Vue({ el: '#app', data: data, methods: { reverseMessage: function () { // ⑤ this.message = this.message.split('').reverse().join('') } } }) </script> </body> </html>
本文摘录自知乎的一个问题的答案，作为我的一篇笔记。感谢原作者。 作者：李乐丁 链接：https://www.zhihu.com/question/60577602/answer/178077799 来源：知乎 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 还差得远，js和python压根不是同一个目标，要说餐食，是大家一起蚕室php。 backend的场景比frontend复杂多了，除了最常见的拉起个server处理请求这种在线业务外，还有各种由时间、任务或数据触发的离线计算，各种资源分配、管理、采集和监控处理，以及无数的一次性程序，无论按代码量、数据量还是计算量来看，非在线业务才是backend的大战场。 对于非在线业务而言，主要强调的是吞吐量和研发效率，所以一个带有庞大标准库的、使用同步模型但易于并行、语法简单但规整、有多语言粘合性的语言，才是大家最爱。这是python真正的活跃地带，js的异步模型相比就太复杂了，async/await并不能cover全部，backend不喜爱不成熟的东西。 说回在线业务，无论什么总是可以分出三层来，交互层、业务层和数据层。交互层node是很适合的，但主要对手是php；业务层最看重质量和性能，目前还没有替代java和c/c++的方案；至于数据层都是各种成熟软件。 总的来说js和python不是敌人，各擅胜场而已。
版本一 版本二 版本三 版本四
本文地址：http://www.cnblogs.com/hhh5460/p/7397006.html 说明 以前的那个例子的思路是后端监控数据存入数据库；前端ajax定时查询数据库。 这几天在看websocket。前端有一个js库：socket.io.js，后端python也有很多库实现了websocket，flask就有一个好用的扩展：flask-socketio。 在参考了这里之后，将前面那个例子改写成后端后台线程一旦产生数据，即刻推送至前端。 好处是不需要前端ajax定时查询，节省服务器资源。 项目一共两个文件： app.py templates/index.htmll app.py 路由及后台线程 ''' 服务器cpu监控程序 思路：后端后台线程一旦产生数据，即刻推送至前端。 好处：不需要前端ajax定时查询，节省服务器资源。 作者：hhh5460 时间：2017.8.19 ''' import psutil import time from threading import Lock from flask import Flask, render_template, session, request from flask_socketio import SocketIO, emit # Set this variable to "threading", "eventlet" or "gevent" to test the # different async modes, or leave it set to None for the application to choose # the best option based on installed packages. async_mode = None app = Flask(__name__) app.config['SECRET_KEY'] = 'secret!' socketio = SocketIO(app, async_mode=async_mode) thread = None thread_lock = Lock() # 后台线程 产生数据，即刻推送至前端 def background_thread(): """Example of how to send server generated events to clients.""" count = 0 while True: socketio.sleep(5) count += 1 t = time.strftime('%M:%S', time.localtime()) # 获取系统时间（只取分:秒） cpus = psutil.cpu_percent(interval=None, percpu=True) # 获取系统cpu使用率 non-blocking socketio.emit('server_response', {'data': [t, *cpus], 'count': count}, namespace='/test') # 注意：这里不需要客户端连接的上下文，默认 broadcast = True ！！！！！！！ @app.route('/') def index(): return render_template('index.html', async_mode=socketio.async_mode) # 与前端建立 socket 连接后，启动后台线程 @socketio.on('connect', namespace='/test') def test_connect(): global thread with thread_lock: if thread is None: thread = socketio.start_background_task(target=background_thread) if __name__ == '__main__': socketio.run(app, debug=True) index.html 页面文件 <!DOCTYPE html> <html lang="en"> <head> <meta charset="utf-8"> <title>ECharts3 Ajax</title> <script type="text/javascript" src="//cdn.bootcss.com/jquery/3.1.1/jquery.min.js"></script> <script type="text/javascript" src="//cdn.bootcss.com/socket.io/1.5.1/socket.io.min.js"></script> <!-- ECharts 3 引入 --> <script src="http://echarts.baidu.com/dist/echarts.min.js"></script> </head> <body> <!--为ECharts准备一个具备大小（宽高）的Dom--> <div id="main" style="height:500px;border:1px solid #ccc;padding:10px;"></div> <script type="text/javascript"> // 作者：hhh5460 // 时间：2017.8.19 //--- 折柱 --- var myChart = echarts.init(document.getElementById('main')); myChart.setOption({ title: { text: '服务器系统监控' }, tooltip: {}, legend: { data:['cpu1','cpu2','cpu3','cpu4'] }, xAxis: { data: [] }, yAxis: {}, series: [{ name: 'cpu1', type: 'line', data: [] },{ name: 'cpu2', type: 'line', data: [] },{ name: 'cpu3', type: 'line', data: [] },{ name: 'cpu4', type: 'line', data: [] }] }); // 本人笔记本有四个cpu，读者朋友请根据自己的情况，相应修改！！ // 五个全局变量：time、cpu1、cpu2、cpu3、cpu4 var time = ["","","","","","","","","",""], cpu1 = [0,0,0,0,0,0,0,0,0,0], cpu2 = [0,0,0,0,0,0,0,0,0,0], cpu3 = [0,0,0,0,0,0,0,0,0,0], cpu4 = [0,0,0,0,0,0,0,0,0,0] //准备好统一的 callback 函数 var update_mychart = function (res) { //res是json格式的response对象 // 隐藏加载动画 myChart.hideLoading(); // 准备数据 time.push(res.data[0]); cpu1.push(parseFloat(res.data[1])); cpu2.push(parseFloat(res.data[2])); cpu3.push(parseFloat(res.data[3])); cpu4.push(parseFloat(res.data[4])); if (time.length >= 10){ time.shift(); cpu1.shift(); cpu2.shift(); cpu3.shift(); cpu4.shift(); } // 填入数据 myChart.setOption({ xAxis: { data: time }, series: [{ name: 'cpu1', // 根据名字对应到相应的系列 data: cpu1 },{ name: 'cpu2', data: cpu2 },{ name: 'cpu3', data: cpu3 },{ name: 'cpu4', data: cpu4 }] }); }; // 首次显示加载动画 myChart.showLoading(); // 建立socket连接，等待服务器“推送”数据，用回调函数更新图表 $(document).ready(function() { namespace = '/test'; var socket = io.connect(location.protocol + '//' + document.domain + ':' + location.port + namespace); socket.on('server_response', function(res) { update_mychart(res); }); }); </script> </body> </html> 效果图
说明 搞了一个最新版本的雷达图，比以前那个美观。 不多说，代码奉上： 完整代码 ''' matplotlib雷达图 ''' import numpy as np import matplotlib.pyplot as plt # 雷达图 def plot_radar(labels, data, score): ''' 用法： >>> labels = np.array(['艺术A','调研I','实际R','常规C','企业E','社会S']) #标签 >>> data = np.array([1,4,3,6,4,8]) # 数据 >>> score = 10 # 表明数据是“十分制”。其可选的选项有1分制、5分制、10分制、100分制 >>> plot_radar(labels, data, score) # 画雷达图 ''' n = len(labels) # 转化为十分制！！！ if score in [5, 10, 100]: data = data * 10/score elif score == 1: data = data * 10 angles = np.linspace(0 + np.pi/2, 2*np.pi + np.pi/2, n, endpoint=False) # 旋转90度，从正上方开始！ data = np.concatenate((data, [data[0]])) # 闭合 angles = np.concatenate((angles, [angles[0]])) # 闭合 fig = plt.figure() ax = fig.add_subplot(111, polar=True)# 参数polar，表示极坐标！！ # 自己画grid线（5条环形线） for i in [2,4,6,8,10]: ax.plot(angles, [i]*(n+1), 'b-',lw=0.5) # 之所以 n +1，是因为要闭合！ # 填充底色 ax.fill(angles, [10]*(n+1), facecolor='g', alpha=0.5) # 自己画grid线（6条半径线） for i in range(n): ax.plot([angles[i], angles[i]], [0, 10], 'b-',lw=0.5) # 画线 ax.plot(angles, data, 'bo-', linewidth=2) # 填充 #ax.fill(angles, data, facecolor='r', alpha=0.25) ax.fill(angles, data, facecolor='r') ax.set_thetagrids(angles * 180/np.pi, labels, fontproperties="SimHei") ax.set_title("matplotlib雷达图", va='bottom', fontproperties="SimHei") ax.set_rlim(0,10) # 下两行去掉所有默认的grid线 ax.spines['polar'].set_visible(False) # 去掉最外围的黑圈 ax.grid(False) # 去掉中间的黑圈 # 关闭数值刻度 ax.set_yticks([]) plt.show() # 测试 if __name__ == '__main__': labels = np.array(['艺术A','调研I','实际R','常规C','企业E','社会S']) #标签 data = np.array([1,4,3,6,4,8]) # 数据 score = 10 # 表明数据是“十分制”。其可选的选项有1分制、5分制、10分制、100分制 # 画雷达图 plot_radar(labels, data, score) 效果图
说明 本文参考了这里 由于数据是连续的，因此使用了高斯隐马尔科夫模型：gaussianHMM 一、stock代码 import tushare as ts import pandas as pd import numpy as np from hmmlearn.hmm import GaussianHMM from matplotlib import cm, pyplot as plt import seaborn as sns sns.set_style('white') ''' 假定隐藏状态数目为4，观测状态数目为2 ''' # 1.准备 X df = ts.get_hist_data('sh',start='2014-01-01',end='2017-07-27')[::-1] # 上证指数 close = np.log(df['close']) low, high = np.log(df['low']), np.log(df['high']) t = 5 X = pd.concat([close.diff(1), close.diff(t), high-low], axis=1)[t:] # 显状态时间序列（观测得到） # 2.拟合 HMM model = GaussianHMM(n_components=6, covariance_type="diag", n_iter=1000).fit(X) Z = model.predict(X) # 隐状态时间序列 # 3.画图看看 plt.figure(figsize=(12, 7)) for i in range(model.n_components): mask = (Z==i) # 注意这里的Z!!! plt.plot_date(df.index[t:][mask], df['close'][t:][mask],'.',label=f'{i}th hidden state',lw=1) plt.legend() plt.grid(1) plt.show() 效果图 解释 下面是对6种隐状态的一种可能的解释：【图文对不上，文字来自这里】 状态0————蓝色————震荡下跌 状态1————绿色————小幅的上涨 状态2————红色————牛市上涨 状态3————紫色————牛市下跌 状态4————黄色————震荡下跌 状态5————浅蓝色————牛市下跌 以上的意义归结是存在一定主观性的。因为HMM模型对输入的多维度观测变量进行处理后，只负责分出几个类别，而并不会定义出每种类别的实际含义。所以我们从图形中做出上述的判断。 所以，这种方法本质上是一种 Classification（分类） 或者 Clustering（聚类） 二、lotto 代码 import tushare as ts import pandas as pd import numpy as np from hmmlearn.hmm import GaussianHMM from matplotlib import cm, pyplot as plt from matplotlib.widgets import MultiCursor import seaborn as sns sns.set_style('white') import marksix_1 import talib as ta ''' 假定隐藏状态数目为6，观测状态数目为4 ''' # 1.准备 X lt = marksix_1.Marksix() lt.load_data(period=1000) #series = lt.adapter(loc='0000001', zb_name='ptsx', args=(1,), tf_n=0) m = 2 series = lt.adapter(loc='0000001', zb_name='mod', args=(m, lt.get_mod_list(m)), tf_n=0) # 实时线 close = np.cumsum(series).astype(float) # 低阶数据 t1, t2, t3 = 5, 10, 20 ma1 = ta.MA(close, timeperiod=t1, matype=0) std1 = ta.STDDEV(close, timeperiod=t1, nbdev=1) ma2 = ta.MA(close, timeperiod=t2, matype=0) std2 = ta.STDDEV(close, timeperiod=t2, nbdev=1) ma3 = ta.MA(close, timeperiod=t3, matype=0) std3 = ta.STDDEV(close, timeperiod=t3, nbdev=1) # 转换一 ''' t = t3 X = pd.DataFrame({'ma1':ma1,'ma2':ma2,'ma3':ma3,'std1':std1,'std2':std2,'std3':std3}, index=lt.df.index)[t:] ''' # 转换二 t = t2 X = pd.DataFrame({'ma1':ma1,'ma2':ma2,'std1':std1,'std2':std2}, index=lt.df.index)[t:] #close = np.log(df['close']) #low, high = np.log(df['low']), np.log(df['high']) #t = 5 #X = pd.concat([close.diff(1), close.diff(t), high-low], axis=1)[t:] # 显状态时间序列（观测得到） # 2.拟合 HMM model = GaussianHMM(n_components=6, covariance_type="diag", n_iter=1000).fit(X) Z = model.predict(X) # 隐状态时间序列 # 3.画图看看 fig, axes = plt.subplots(2, 1, sharex=True) ax1, ax2 = axes[0], axes[1] show_period = 300 # 布林线 upperband, middleband, lowerband = ta.BBANDS(close, timeperiod=5, nbdevup=2, nbdevdn=2, matype=0) axes[0].plot_date(lt.df.index[-show_period:], close[-show_period:], 'rd-', markersize = 3) axes[0].plot_date(lt.df.index[-show_period:], upperband[-show_period:], 'y-') axes[0].plot_date(lt.df.index[-show_period:], middleband[-show_period:], 'b-') axes[0].plot_date(lt.df.index[-show_period:], lowerband[-show_period:], 'y-') for i in range(model.n_components): mask = (Z[-show_period:]==i) # 注意这里的Z!!! axes[1].plot_date(lt.df.index[-show_period:][mask], close[-show_period:][mask],'d',markersize=3,label=f'{i}th hidden state',lw=1) axes[1].legend() axes[1].grid(1) multi = MultiCursor(fig.canvas, (axes[0], axes[1]), color='b', lw=2) plt.show() 效果图
说明 本文受知乎陈小米启发而写。有兴趣的朋友可以移步这里。 本文的代码完全是本人所撸。 问题描述 假想一个游戏。赢的概率是60%，输的概率40%。入场费随意交。如果赢了获得2倍的入场费金额（1赔1），输则输掉入场费。小米有1000元做本金，请问小米每次给多少入场费，理论上100次游戏后几何期望收益能最大？ 【本人的疑问】为何这里考虑几何期望，而不是数学期望？【已解决，见代码注释！】 凯利公式 \[f=p-\frac{q}{b}\] 不多说，上代码。 完整代码 import pandas as pd import numpy as np import random import matplotlib.pyplot as plt ''' 用蒙特卡罗方法，验证凯利公式的计算得到资金比例是不是最佳的 参考：https://zhuanlan.zhihu.com/p/20849995 ''' pwin = 0.6 # 胜率 b = 1 # 净赔率 # 凯利值 def kelly(pwin, b): ''' 参数 pwin 胜率 b 净赔率 返回 f 投注资金比例 ''' f = (b * pwin + pwin - 1) / b return f # 游戏 def play_game(f, cash=100, m=100): global pwin, b res = [cash] for i in range(m): if random.random() <= pwin: res.append(res[-1] + int(f*res[-1])*b) else: res.append(res[-1] - int(f*res[-1])) return res # 蒙特卡罗方法重复玩游戏 def montecarlo(n=1000, f=0.15, cash=1000, m=100): res = [] for i in range(n): res.append(play_game(f, cash, m)) #return pd.DataFrame(res).sum(axis=0) / n #【 数学期望】不平滑 return np.exp(np.log(pd.DataFrame(res)).sum(axis=0) / n) # 【几何期望】平滑 n = 1000 # 重复次数 cash = 1000 # 初始资金池 m = 100 # 期数 f = 0.1 # 资金比例 10% res1 = montecarlo(n, f, cash, m) fk = kelly(pwin, b) # 资金比例 凯利值 res2 = montecarlo(n, fk, cash, m) f = 0.5 # 资金比例 50% res3 = montecarlo(n, f, cash, m) f = 1.0 # 资金比例 100% res4 = montecarlo(n, f, cash, m) # 画个图看看 fig = plt.figure() axes = fig.add_subplot(111) axes.plot(res1,'r-',label='10%') axes.plot(res2,'g*',label='{:.1%}'.format(fk)) axes.plot(res3,'b-',label='50%') axes.plot(res4,'k-',label='100%') plt.legend(loc = 0) plt.show() 效果图 结论 由图显见，凯利值是最优的。
1. 不带参数的多重继承 # 作者：hhh5460 # 时间：2017.07.18 class A(object): def show_x(self): print('A') class B(object): def show_y(self): print('B') class C(object): def show_z(self): print('C') class D(A, B, C): pass # 测试 if __name__ == '__main__': d = D() d.show_x() # A d.show_y() # B d.show_z() # C 2. 带参数的多重继承 # 作者：hhh5460 # 时间：2017.07.18 class A(object): def __init__(self, x=0): self._x = x def show_x(self): print(self._x) def show_name(self): print('A') class B(object): def __init__(self, y=0): self._y = y def show_y(self): print(self._y) def show_name(self): print('B') class C(object): def __init__(self, z=0): self._z = z def show_z(self): print(self._z) def show_name(self): print('C') # 注意下面两类D、E，都是继承A、B、C，且A类的优先级最高。但是三条__init__语句的顺序是相反的 class D(A, B, C): def __init__(self, x=0, y=0, z=0): C.__init__(self, z) # init C B.__init__(self, y) # init B A.__init__(self, x) # init A （A最优先） class E(A, B, C): def __init__(self, x=0, y=0, z=0): super(E, self).__init__(x) # init A （A最优先） # 此句可简写成：super().__init__(x) super(A, self).__init__(y) # init B super(B, self).__init__(z) # init C # 测试 if __name__ == '__main__': d = D(1,2,3) d.show_x() # 1 d.show_y() # 2 d.show_z() # 3 d.show_name() # A e = E(1,2,3) e.show_x() # 1 e.show_y() # 2 e.show_z() # 3 e.show_name() # A
利用上一篇的框架，再写了个翻转棋的程序，为了调试minimax算法，花了两天的时间。 几点改进说明： 拆分成四个文件：board.py，player.py，ai.py，othello.py。使得整个结构更清晰，更通用，更易于维护。 AI 的水平跟 minimax 的递归深度，以及评价函数有关。基于此，我把 minimax 和评价函数都放到 AI 类里面 AIPlayer 使用了多重继承。继承了 Player 与 AI 两个类 Game 类中把原run函数里的生成两个玩家的部分提出来，写成一个函数make_two_players，使得 run函数结构更清晰 AI 玩家等级不要选择 0：beginer。会报错，还没调试好 board.py ''' 作者：hhh5460 时间：2017年7月1日 ''' class Board(object): def __init__(self): self.empty = '.' self._board = [[self.empty for _ in range(8)] for _ in range(8)] # 规格：8*8 self._board[3][4], self._board[4][3] = 'X', 'X' self._board[3][3], self._board[4][4] = 'O', 'O' # 增加 Board[][] 索引语法 def __getitem__(self, index): return self._board[index] # 打印棋盘 def print_b(self): board = self._board print(' ', ' '.join(list('ABCDEFGH'))) for i in range(8): print(str(i+1),' '.join(board[i])) # 棋局终止 def teminate(self): list1 = list(self.get_legal_actions('X')) list2 = list(self.get_legal_actions('O')) return [False, True][len(list1) == 0 and len(list2) == 0] # 判断赢家 def get_winner(self): s1, s2 = 0, 0 for i in range(8): for j in range(8): if self._board[i][j] == 'X': s1 += 1 if self._board[i][j] == 'O': s2 += 1 if s1 > s2: return 0 # 黑胜 elif s1 < s2: return 1 # 白胜 elif s1 == s2: return 2 # 平局 # 落子 def _move(self, action, color): x,y = action self._board[x][y] = color return self._flip(action, color) # 翻子（返回list） def _flip(self, action, color): flipped_pos = [] for line in self._get_lines(action): for i,p in enumerate(line): if self._board[p[0]][p[1]] == self.empty: break elif self._board[p[0]][p[1]] == color: flipped_pos.extend(line[:i]) break for p in flipped_pos: self._board[p[0]][p[1]] = color return flipped_pos # 撤销 def _unmove(self, action, flipped_pos, color): self._board[action[0]][action[1]] = self.empty uncolor = ['X', 'O'][color=='X'] for p in flipped_pos: self._board[p[0]][p[1]] = uncolor # 生成8个方向的下标数组，方便后续操作 def _get_lines(self, action): '''说明：刚开始我是用一维棋盘来考虑的，后来改为二维棋盘。偷懒，不想推倒重来，简单地修改了一下''' board_coord = [(i,j) for i in range(8) for j in range(8)] # 棋盘坐标 r,c = action ix = r*8 + c r, c = ix//8, ix%8 left = board_coord[r*8:ix] # 要反转 right = board_coord[ix+1:(r+1)*8] top = board_coord[c:ix:8] # 要反转 bottom = board_coord[ix+8:8*8:8] if r <= c: lefttop = board_coord[c-r:ix:9] # 要反转 rightbottom = board_coord[ix+9:(7-(c-r))*8+7+1:9] else: lefttop = board_coord[(r-c)*8:ix:9] # 要反转 rightbottom = board_coord[ix+9:7*8+(7-(c-r))+1:9] if r+c<=7: leftbottom = board_coord[ix+7:(r+c)*8:7] righttop = board_coord[r+c:ix:7] # 要反转 else: leftbottom = board_coord[ix+7:7*8+(r+c)-7+1:7] righttop = board_coord[((r+c)-7)*8+7:ix:7] # 要反转 # 有四个要反转，方便判断 left.reverse() top.reverse() lefttop.reverse() righttop.reverse() lines = [left, top, lefttop, righttop, right, bottom, leftbottom, rightbottom] return lines # 检测，位置是否有子可翻 def _can_fliped(self, action, color): flipped_pos = [] for line in self._get_lines(action): for i,p in enumerate(line): if self._board[p[0]][p[1]] == self.empty: break elif self._board[p[0]][p[1]] == color: flipped_pos.extend(line[:i]) break return [False, True][len(flipped_pos) > 0] # 合法走法 def get_legal_actions(self, color): uncolor = ['X', 'O'][color=='X'] uncolor_near_points = [] # 反色邻近的空位 board = self._board for i in range(8): for j in range(8): if board[i][j] == uncolor: for dx,dy in [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1)]: x, y = i+dx, j+dy if 0 <= x <=7 and 0 <= y <=7 and board[x][y] == self.empty and (x, y) not in uncolor_near_points: uncolor_near_points.append((x, y)) for p in uncolor_near_points: if self._can_fliped(p, color): yield p # 测试 if __name__ == '__main__': board = Board() board.print_b() print(list(board.get_legal_actions('X'))) player.py from ai import AI ''' 作者：hhh5460 时间：2017年7月1日 ''' # 玩家 class Player(object): def __init__(self, color): self.color = color # 思考 def think(self, board): pass # 落子 def move(self, board, action): flipped_pos = board._move(action, self.color) return flipped_pos # 悔子 def unmove(self, board, action, flipped_pos): board._unmove(action, flipped_pos, self.color) # 人类玩家 class HumanPlayer(Player): def __init__(self, color): super().__init__(color) def think(self, board): while True: action = input("Turn to '{}'. \nPlease input a point.(such as 'A1'): ".format(self.color)) # A1~H8 r, c = action[1], action[0].upper() if r in '12345678' and c in 'ABCDEFGH': # 合法性检查1 x, y = '12345678'.index(r), 'ABCDEFGH'.index(c) if (x,y) in board.get_legal_actions(self.color): # 合法性检查2 return x, y # 电脑玩家（多重继承） class AIPlayer(Player, AI): def __init__(self, color, level_ix=0): super().__init__(color) # init Player super(Player, self).__init__(level_ix) # init AI def think(self, board): print("Turn to '{}'. \nPlease wait a moment. AI is thinking...".format(self.color)) uncolor = ['X','O'][self.color=='X'] opfor = AIPlayer(uncolor) # 假想敌，陪练 action = self.brain(board, opfor, 4) return action ai.py import random ''' 作者：hhh5460 时间：2017年7月1日 ''' class AI(object): ''' 三个水平等级：初级（beginner）、中级（intermediate）、高级（advanced） ''' def __init__(self, level_ix =0): # 玩家等级 self.level = ['beginner','intermediate','advanced'][level_ix] # 棋盘位置权重，参考：https://github.com/k-time/ai-minimax-agent/blob/master/ksx2101.py self.board_weights = [ [120, -20, 20, 5, 5, 20, -20, 120], [-20, -40, -5, -5, -5, -5, -40, -20], [ 20, -5, 15, 3, 3, 15, -5, 20], [ 5, -5, 3, 3, 3, 3, -5, 5], [ 5, -5, 3, 3, 3, 3, -5, 5], [ 20, -5, 15, 3, 3, 15, -5, 20], [-20, -40, -5, -5, -5, -5, -40, -20], [120, -20, 20, 5, 5, 20, -20, 120] ] # 评估函数（仅根据棋盘位置权重） def evaluate(self, board, color): uncolor = ['X','O'][color=='X'] score = 0 for i in range(8): for j in range(8): if board[i][j] == color: score += self.board_weights[i][j] elif board[i][j] == uncolor: score -= self.board_weights[i][j] return score # AI的大脑 def brain(self, board, opponent, depth): if self.level == 'beginer': # 初级水平 _, action = self.randomchoice(board) elif self.level == 'intermediate': # 中级水平 _, action = self.minimax(board, opponent, depth) elif self.level == 'advanced': # 高级水平 _, action = self.minimax_alpha_beta(board, opponent, depth) assert action is not None, 'action is None' return action # 随机选（从合法走法列表中随机选） def randomchoice(self, board): color = self.color action_list = list(board.get_legal_actions(color)) return None, random.choice(action_list) # 极大极小算法，限制深度 def minimax(self, board, opfor, depth=4): # 其中 opfor 是假想敌、陪练 '''参考：https://github.com/k-time/ai-minimax-agent/blob/master/ksx2101.py''' color = self.color if depth == 0: return self.evaluate(board, color), None action_list = list(board.get_legal_actions(color)) if not action_list: return self.evaluate(board, color), None best_score = -100000 best_action = None for action in action_list: flipped_pos = self.move(board, action) # 落子 score, _ = opfor.minimax(board, self, depth-1) # 深度优先，轮到陪练 self.unmove(board, action, flipped_pos) # 回溯 score = -score if score > best_score: best_score = score best_action = action return best_score, best_action # 极大极小算法，带alpha-beta剪枝 def minimax_alpha_beta(self, board, opfor, depth=8, my_best=-float('inf'), opp_best=float('inf')): '''参考：https://github.com/k-time/ai-minimax-agent/blob/master/ksx2101.py''' color = self.color if depth == 0: return self.evaluate(board, color), None action_list = list(board.get_legal_actions(color)) if not action_list: return self.evaluate(board, color), None best_score = my_best best_action = None for action in action_list: flipped_pos = self.move(board, action) # 落子 score, _ = opfor.minimax_alpha_beta(board, self, depth-1, -opp_best, -best_score) # 深度优先，轮到陪练 self.unmove(board, action, flipped_pos) # 回溯 score = -score if score > best_score: best_score = score best_action = action if best_score > opp_best: break return best_score, best_action othello.py from board import Board from player import HumanPlayer, AIPlayer ''' 作者：hhh5460 时间：2017年7月1日 ''' # 游戏 class Game(object): def __init__(self): self.board = Board() self.current_player = None # 生成两个玩家 def make_two_players(self): ps = input("Please select two player's type:\n\t0.Human\n\t1.AI\nSuch as:0 0\n:") p1, p2 = [int(p) for p in ps.split(' ')] if p1 == 1 or p2 == 1: # 至少有一个AI玩家 level_ix = int(input("Please select the level of AI player.\n\t0: beginner\n\t1: intermediate\n\t2: advanced\n:")) if p1 == 0: player1 = HumanPlayer('X') player2 = AIPlayer('O', level_ix) elif p2 == 0: player1 = AIPlayer('X', level_ix) player2 = HumanPlayer('O') else: player1 = AIPlayer('X', level_ix) player2 = AIPlayer('O', level_ix) else: player1, player2 = HumanPlayer('X'), HumanPlayer('O') # 先手执X，后手执O return player1, player2 # 切换玩家（游戏过程中） def switch_player(self, player1, player2): if self.current_player is None: return player1 else: return [player1, player2][self.current_player == player1] # 打印赢家 def print_winner(self, winner): # winner in [0,1,2] print(['Winner is player1','Winner is player2','Draw'][winner]) # 运行游戏 def run(self): # 生成两个玩家 player1, player2 = self.make_two_players() # 游戏开始 print('\nGame start!\n') self.board.print_b() # 显示棋盘 while True: self.current_player = self.switch_player(player1, player2) # 切换当前玩家 action = self.current_player.think(self.board) # 当前玩家对棋盘进行思考后，得到招法 if action is not None: self.current_player.move(self.board, action) # 当前玩家执行招法，改变棋盘 self.board.print_b() # 显示当前棋盘 if self.board.teminate(): # 根据当前棋盘，判断棋局是否终止 winner = self.board.get_winner() # 得到赢家 0,1,2 break self.print_winner(winner) print('Game over!') self.board.print_history() if __name__ == '__main__': Game().run() 效果图
说明 用python实现了井字棋，整个框架是本人自己构思的，自认为比较满意。另外，90%+的代码也是本人逐字逐句敲的。 minimax算法还没完全理解，所以参考了这里的代码，并作了修改。 特点 可以选择人人、人机、机人、机机四种对战模式之一 电脑玩家的AI使用了minimax算法，带apha-beta剪枝 电脑玩家在思考时，时时刻刻都有一个“假想敌”。以便使得minimax算法运转起来 代码 作者：hhh5460 时间：2017年6月26日 # 棋盘 class Board(object): def __init__(self): #self._board = '-'*9 # 坑！！ self._board = ['-' for _ in range(9)] self._history = [] # 棋谱 # 按指定动作，放入棋子 def _move(self, action, take): if self._board[action] == '-': self._board[action] = take self._history.append((action, take)) # 加入棋谱 # 撤销动作，拿走棋子 def _unmove(self, action): self._board[action] = '-' self._history.pop() # 棋盘快照 def get_board_snapshot(self): return self._board[:] # 取棋盘上的合法走法 def get_legal_actions(self): actions = [] for i in range(9): if self._board[i] == '-': actions.append(i) return actions # 判断走法是否合法 def is_legal_action(self, action): return self._board[action] == '-' # 终止检测 def teminate(self): board = self._board lines = [board[0:3], board[3:6], board[6:9], board[0::3], board[1::3], board[2::3], board[0::4], board[2:7:2]] if ['X']*3 in lines or ['O']*3 in lines or '-' not in board: return True else: return False # 胜负检查 def get_winner(self): board = self._board lines = [board[0:3], board[3:6], board[6:9], board[0::3], board[1::3], board[2::3], board[0::4], board[2:7:2]] if ['X']*3 in lines: return 0 elif ['O']*3 in lines: return 1 else: return 2 # 打印棋盘 def print_b(self): board = self._board for i in range(len(board)): print(board[i], end='') if (i+1)%3 == 0: print() # 打印棋谱 def print_history(self): print(self._history) # 玩家 class Player(object): ''' 玩家只做两件事：思考、落子 1. 思考 --> 得到走法 2. 落子 --> 执行走法，改变棋盘 ''' def __init__(self, take='X'): # 默认执的棋子为 take = 'X' self.take=take def think(self, board): pass def move(self, board, action): board._move(action, self.take) # 人类玩家 class HumanPlayer(Player): def __init__(self, take): super().__init__(take) def think(self, board): while True: action = input('Please input a num in 0-8:') if len(action)==1 and action in '012345678' and board.is_legal_action(int(action)): return int(action) # 电脑玩家 class AIPlayer(Player): def __init__(self, take): super().__init__(take) def think(self, board): print('AI is thinking ...') take = ['X','O'][self.take=='X'] player = AIPlayer(take) # 假想敌！！！ _, action = self.minimax(board, player) #print('OK') return action # 极大极小法搜索，α-β剪枝 def minimax(self, board, player, depth=0) : '''参考：https://stackoverflow.com/questions/44089757/minimax-algorithm-for-tic-tac-toe-python''' if self.take == "O": bestVal = -10 else: bestVal = 10 if board.teminate() : if board.get_winner() == 0 : return -10 + depth, None elif board.get_winner() == 1 : return 10 - depth, None elif board.get_winner() == 2 : return 0, None for action in board.get_legal_actions() : # 遍历合法走法 board._move(action, self.take) val, _ = player.minimax(board, self, depth+1) # 切换到 假想敌！！！ board._unmove(action) # 撤销走法，回溯 if self.take == "O" : if val > bestVal: bestVal, bestAction = val, action else : if val < bestVal: bestVal, bestAction = val, action return bestVal, bestAction # 游戏 class Game(object): def __init__(self): self.board = Board() self.current_player = None # 生成玩家 def mk_player(self, p, take='X'): # p in [0,1] if p==0: return HumanPlayer(take) else: return AIPlayer(take) # 切换玩家 def switch_player(self, player1, player2): if self.current_player is None: return player1 else: return [player1, player2][self.current_player == player1] # 打印赢家 def print_winner(self, winner): # winner in [0,1,2] print(['Winner is player1','Winner is player2','Draw'][winner]) # 运行游戏 def run(self): ps = input("Please select two player's type:\n\t0.Human\n\t1.AI\nSuch as:0 0\n") p1, p2 = [int(p) for p in ps.split(' ')] player1, player2 = self.mk_player(p1, 'X'), self.mk_player(p2, 'O') # 先手执X，后手执O print('\nGame start!\n') self.board.print_b() # 显示棋盘 while True: self.current_player = self.switch_player(player1, player2) # 切换当前玩家 action = self.current_player.think(self.board) # 当前玩家对棋盘进行思考后，得到招法 self.current_player.move(self.board, action) # 当前玩家执行招法，改变棋盘 self.board.print_b() # 显示当前棋盘 if self.board.teminate(): # 根据当前棋盘，判断棋局是否终止 winner = self.board.get_winner() # 得到赢家 0,1,2 break self.print_winner(winner) print('Game over!') self.board.print_history() if __name__ == '__main__': Game().run() 效果图 下图是人人对战的结果
来源：https://xkcd.com/832/ 解读：http://www.guokr.com/article/4754/
问题 在河的左岸有N个传教士、N个野人和一条船，传教士们想用这条船把所有人都运过河去，但有以下条件限制： （1）修道士和野人都会划船，但船每次最多只能运M个人； （2）在任何岸边以及船上，野人数目都不能超过修道士，否则修道士会被野人吃掉。 假定野人会服从任何一种过河安排，请规划出一个确保修道士安全过河的计划。 分析 百度一下，网上全是用左岸的传教士和野人人数以及船的位置这样一个三元组作为状态，进行考虑，千篇一律。 我换了一种考虑，只考虑船的状态。 船的状态：(x, y) x表示船上x个传教士，y表示船上y个野人，其中 |x|∈[0, m], |y|∈[0, m], 0<|x|+|y|<=m, x*y>=0, |x|>=|y| 船从左到右时，x,y取非负数。船从右到左时，x,y取非正数 解的编码：[(x0,y0), (x1,y1), ..., (xp,yp)] 其中x0+x1+...+xp=N, y0+y1+...+yp=N 解的长度不固定，但一定为奇数 开始时左岸(N, N), 右岸(0, 0)。最终时左岸(0, 0), 右岸(N, N) 由于船的合法状态是动态的、二维的。因此，使用一个函数get_states()来专门生成其状态空间，使得主程序更加清晰。 代码 n = 3 # n个传教士、n个野人 m = 2 # 船能载m人 x = [] # 一个解，就是船的一系列状态 X = [] # 一组解 is_found = False # 全局终止标志 # 计算船的合法状态空间（二维） def get_states(k): # 船准备跑第k趟 global n, m, x if k%2==0: # 从左到右，只考虑原左岸人数 s1, s2 = n - sum(s[0] for s in x), n - sum(s[1] for s in x) else: # 从右到左，只考虑原右岸人数（将船的历史状态累加可得！！！） s1, s2 = sum(s[0] for s in x), sum(s[1] for s in x) for i in range(s1 + 1): for j in range(s2 + 1): if 0 < i+j <= m and (i*j == 0 or i >= j): yield [(-i,-j), (i,j)][k%2==0] # 生成船的合法状态 # 冲突检测 def conflict(k): # 船开始跑第k趟 global n, m, x # 若船上载的人与上一趟一样（会陷入死循环！！！！） if k > 0 and x[-1][0] == -x[-2][0] and x[-1][1] == -x[-2][1]: return True # 任何时候，船上传教士人数少于野人，或者无人，或者超载（计算船的合法状态空间时已经考虑到了。） #if 0 < abs(x[-1][0]) < abs(x[-1][1]) or x[-1] == (0, 0) or abs(sum(x[-1])) > m: # return True # 任何时候，左岸传教士人数少于野人 if 0 < n - sum(s[0] for s in x) < n - sum(s[1] for s in x): return True # 任何时候，右岸传教士人数少于野人 if 0 < sum(s[0] for s in x) < sum(s[1] for s in x): return True return False # 无冲突 # 回溯法 def backtrack(k): # 船准备跑第k趟 global n, m, x, is_found if is_found: return # 终止所有递归 if n - sum(s[0] for s in x) == 0 and n - sum(s[1] for s in x) == 0: # 左岸人数全为0 print(x) is_found = True else: for state in get_states(k): # 遍历船的合法状态空间 x.append(state) if not conflict(k): backtrack(k+1) # 深度优先 x.pop() # 回溯 # 测试 backtrack(0) 效果图 解的解释，从上往下看： 一个结论 貌似只有满足m = n-1，此问题才有解。
1. 准备数据 import pandas as pd from io import StringIO csv_txt = '''"date","player1","player2","score1","score2" "2017-06-05","张继科","林思远",3,2 "2017-06-06","丁宁","刘思文",3,0 "2017-06-07","马琳","樊振东",2,3 "2017-06-08","张燕","丁宁",0,3 "2017-06-09","张继科","马琳",3,2 "2017-06-10","刘思文","张燕",4,1 "2017-06-11","马琳","林思远",3,2 ''' #df = pd.read_csv(StringIO(csv_txt), header=0, index_col="date") # 以 date 作为 index df = pd.read_csv(StringIO(csv_txt), header=0) # 默认 index 2. 列 ——> 索引 df.set_index('date') df.set_index('date', inplace=True) # column 改为 index 3. 索引 ——> 列 df['index'] = df.index df.reset_index(level=0, inplace=True) df.reset_index(level=['tick', 'obs']) df['si_name'] = df.index.get_level_values('si_name') # where si_name is the name of the subindex. df.reset_index() # （all）index 改为 column #df.reset_index(level=0, inplace=True) # （the first）index 改为 column
上一篇笔记的pygame游戏对敌人和白云的移动速度使用了随机函数randint()，游戏体验不是太好。如果是按概率随机选取设置速度的话，游戏体验会好一些。 据我了解，random.choice(seq)是等概率选取一个，不是我想要的。而 numpy.random.choice(seq, p, k)是按概率随机重复选取多个，这正是我想要的。 但是，我不想为这么一个函数引入巨大的numpy库，所以打算自己实现一个按概率随机选取的函数。 特此将代码记录如下： # 作者：hhh5460 # 时间：2017年6月17日 import random # 根据概率随机选取 def random_choice(seq, prob, k=1): ''' 功能： 按给定概率prob，从seq中选取元素。可重复k次 注意 1. seq, prob长度要相等 2. prob的概率和要等于1 3. k 表示重复选取的次数，默认为1次 4. 结果返回list 5. 用到了random模块的random()函数 例子： >>> random_choice(['a','b','c','d'], [0.4, 0.15, 0.1, 0.35]) ['d'] >>> random_choice('abcd', [0.4, 0.15, 0.1, 0.35], k=5) ['d','d','b','a','d'] ''' res = [] for j in range(k): p = random.random() for i in range(len(seq)): if sum(prob[:i]) < p <= sum(prob[:i+1]): res.append(seq[i]) return res # 测试 def test(): print(random_choice(['a','b','c','d'], [0.4, 0.15, 0.1, 0.35], k=5)) test()
本文基于win7(64) + py3.5(64)环境。 本文是这里的一篇学习笔记。加入了自己的理解。 本文最终目的是实现一个飞机躲避导弹的游戏。 1、核心概念 pygame 的核心概念有： Surface 对象（一个容器，一个载体，可以是空白的矩形区域，亦可是图片） Surface 对象的矩形区域（用 Surface 实例的get_rect()方法获得） 屏幕对象的blit()方法用于放置 Surface 对象 display 模块的flip()方法用于重绘游戏界面 窗口主循环 import pygame, sys from pygame.locals import * # 全局常量 # 初始化 pygame.init() # 屏幕对象 screen = pygame.display.set_mode((400,270)) # 尺寸 # Surface对象 surf = pygame.Surface((50,50)) # 长、宽 surf.fill((255,255,255)) # 颜色 # Surface对象的矩形区域 rect = surf.get_rect() # 窗口主循环 while True: # 遍历事件队列 for event in pygame.event.get(): if event.type == QUIT: # 点击右上角的'X'，终止主循环 pygame.quit() sys.exit() elif event.type == KEYDOWN: if event.key == K_ESCAPE: # 按下'ESC'键，终止主循环 pygame.quit() sys.exit() # 放置Surface对象 screen.blit(surf, ((400-50)//2, (270-50)//2)) # 窗口正中 #screen.blit(surf, rect) # surf的左上角 # 重绘界面 pygame.display.flip() 效果图 2、引入精灵 上面的代码很能体现pygame的核心概念，但不利于规模比较大的游戏开发。 为此，就需要继承 Sprite 类，并且设置属性surf为Surface对象。同时设置rect属性。 调用屏幕对象的blit方法时，以精灵实例的surf属性和rect属性为参数。 import pygame, sys from pygame.locals import * import random '''玩家随着方向键运动''' # 玩家 class Player(pygame.sprite.Sprite): def __init__(self): super().__init__() self.surf = pygame.Surface((75,25)) self.surf.fill((255,255,255)) self.rect = self.surf.get_rect() def update(self, key): # 随着方向键运动 if key[K_UP]: self.rect.move_ip(0,-5) if key[K_DOWN]: self.rect.move_ip(0,5) if key[K_LEFT]: self.rect.move_ip(-5,0) if key[K_RIGHT]: self.rect.move_ip(5,0) # 限定player在屏幕中 if self.rect.left < 0: self.rect.left = 0 elif self.rect.right > 800: self.rect.right = 800 if self.rect.top <= 0: self.rect.top = 0 elif self.rect.bottom >= 600: self.rect.bottom = 600 # 初始化 pygame.init() # 屏幕对象 screen = pygame.display.set_mode((800,600)) # 尺寸 # 玩家精灵对象 player = Player() # 窗口主循环 while True: # 遍历事件队列 for event in pygame.event.get(): if event.type == QUIT: # 点击右上角的'X'，终止主循环 pygame.quit() sys.exit() elif event.type == KEYDOWN: if event.key == K_ESCAPE: # 按下'ESC'键，终止主循环 pygame.quit() sys.exit() # 更新屏幕 screen.fill((0,0,0)) # 获得按键 key = pygame.key.get_pressed() # 更新玩家 player.update(key) # 放置玩家 screen.blit(player.surf, player.rect) # 更新界面 pygame.display.flip() 效果图 3、引入敌人 由于敌人很多，最好的方式是用Group来管理那么多的精灵。 import pygame, sys from pygame.locals import * import random # 玩家 class Player(pygame.sprite.Sprite): def __init__(self): super().__init__() self.surf = pygame.Surface((75,25)) self.surf.fill((255,255,255)) self.rect = self.surf.get_rect() def update(self, key): if key[K_UP]: self.rect.move_ip(0,-5) if key[K_DOWN]: self.rect.move_ip(0,5) if key[K_LEFT]: self.rect.move_ip(-5,0) if key[K_RIGHT]: self.rect.move_ip(5,0) # 限定player在屏幕中 if self.rect.left < 0: self.rect.left = 0 elif self.rect.right > 800: self.rect.right = 800 if self.rect.top <= 0: self.rect.top = 0 elif self.rect.bottom >= 600: self.rect.bottom = 600 # 敌人 class Enemy(pygame.sprite.Sprite): def __init__(self): super().__init__() self.surf = pygame.Surface((20, 10)) self.surf.fill((255, 255, 255)) self.rect = self.surf.get_rect(center=(820, random.randint(0, 600))) self.speed = random.randint(5, 20) def update(self): self.rect.move_ip(-self.speed, 0) # 从右向左 if self.rect.right < 0: self.kill() # Sprite 的内建方法 # 初始化 pygame.init() # 屏幕对象 screen = pygame.display.set_mode((800,600)) # 尺寸 # 自定义事件 ADDENEMY = pygame.USEREVENT + 1 # 事件本质上就是整数常量。比 USEREVENT 小的数值已经对应内置事件，因此任何自定义事件都要比 USEREVENT 大 pygame.time.set_timer(ADDENEMY, 250) # 每隔 250 毫秒(四分之一秒) 触发 # 玩家 player = Player() # 两个精灵组 enemies = pygame.sprite.Group() all_sprites = pygame.sprite.Group() all_sprites.add(player) # 窗口主循环 while True: # 遍历事件队列 for event in pygame.event.get(): if event.type == QUIT: pygame.quit() sys.exit() elif event.type == KEYDOWN: if event.key == K_ESCAPE: pygame.quit() sys.exit() elif event.type == ADDENEMY: # 自定义事件 new_enemy = Enemy() enemies.add(new_enemy) all_sprites.add(new_enemy) # 更新屏幕 screen.fill((0,0,0)) # 更新玩家 key = pygame.key.get_pressed() player.update(key) screen.blit(player.surf, player.rect) # 更新敌人 for enemy in enemies: enemy.update() screen.blit(enemy.surf, enemy.rect) # 碰撞检测（灵魂所在） if pygame.sprite.spritecollideany(player, enemies): player.kill() print('发生碰撞！') # 重绘界面 pygame.display.flip() 效果图 4、使用图片 上面的例子是丑陋的黑白界面，需要进行美化。好的方式是使用图片来代替。可以去网上找素材，也可以自己画。 为了让游戏更好看，增添了云朵精灵。 注意：下面的surf属性用image来代替了。 为方便朋友们测试，下面给出代码中用到的三张图片素材： import pygame, sys from pygame.locals import * import random '''飞机躲避导弹''' # 玩家 class Player(pygame.sprite.Sprite): def __init__(self): super().__init__() self.image = pygame.image.load('jet.png').convert() # load函数，返回一个 Surface 对象 self.image.set_colorkey((255,255,255), RLEACCEL) self.rect = self.image.get_rect() def update(self, key): if key[K_UP]: self.rect.move_ip(0,-5) if key[K_DOWN]: self.rect.move_ip(0,5) if key[K_LEFT]: self.rect.move_ip(-5,0) if key[K_RIGHT]: self.rect.move_ip(5,0) # 限定player在屏幕中 if self.rect.left < 0: self.rect.left = 0 elif self.rect.right > 800: self.rect.right = 800 if self.rect.top <= 0: self.rect.top = 0 elif self.rect.bottom >= 600: self.rect.bottom = 600 # 敌人 class Enemy(pygame.sprite.Sprite): def __init__(self): super().__init__() self.image = pygame.image.load('missile.png').convert() self.image.set_colorkey((255, 255, 255), RLEACCEL) self.rect = self.image.get_rect(center=(820, random.randint(0, 600))) self.speed = random.randint(5, 20) def update(self): self.rect.move_ip(-self.speed, 0) # 从右向左 if self.rect.right < 0: self.kill() # Sprite 的内建方法 # 白云 class Cloud(pygame.sprite.Sprite): def __init__(self): super().__init__() self.image = pygame.image.load('cloud.png').convert() self.image.set_colorkey((0,0,0),RLEACCEL) self.rect = self.image.get_rect( center = (random.randint(820,900),random.randint(0,600)) ) def update(self): self.rect.move_ip(-5,0) if self.rect.right < 0: self.kill() # 游戏初始化 pygame.init() # 屏幕对象 screen = pygame.display.set_mode((800,600)) # 尺寸 # 背景Surface background = pygame.Surface(screen.get_size()) background.fill((135, 206, 250)) # 浅蓝色 # 两个自定义事件 ADDENEMY = pygame.USEREVENT + 1 # 事件本质上就是整数常量。比 USEREVENT 小的数值已经对应内置事件，因此任何自定义事件都必须比 USEREVENT 大） pygame.time.set_timer(ADDENEMY, 250) # 每隔 250 毫秒(四分之一秒) 触发 ADDCLOUD = pygame.USEREVENT + 2 pygame.time.set_timer(ADDCLOUD, 1000) # 玩家精灵对象 player = Player() # 三个精灵组 enemies = pygame.sprite.Group() clouds = pygame.sprite.Group() all_sprites = pygame.sprite.Group() all_sprites.add(player) # 窗口主循环 while True: # 遍历事件队列 for event in pygame.event.get(): if event.type == QUIT: pygame.quit() sys.exit() elif event.type == KEYDOWN: if event.key == K_ESCAPE: pygame.quit() sys.exit() elif event.type == ADDENEMY: # 自定义事件 new_enemy = Enemy() enemies.add(new_enemy) all_sprites.add(new_enemy) elif event.type == ADDCLOUD: # 自定义事件 new_cloud = Cloud() clouds.add(new_cloud) all_sprites.add(new_cloud) # 背景 screen.blit(background, (0, 0)) # 获取按键 key = pygame.key.get_pressed() # 更新精灵（组） player.update(key) enemies.update() clouds.update() # 放置精灵 for sprite in all_sprites: screen.blit(sprite.image, sprite.rect) # 碰撞检测（灵魂所在） if pygame.sprite.spritecollideany(player, enemies): player.kill() #print('发生碰撞！') # 重绘界面 pygame.display.flip() 效果图 全都是类 所有的东西都放到类里面！难道这就是传说中的面向对象编程？？？ import pygame, sys from pygame.locals import * import random '''飞机躲避导弹''' # 根据概率随机选取 def choice(seq, prob): p = random.random() for i in range(len(seq)): if sum(prob[:i]) < p < sum(prob[:i+1]): return seq[i] # 玩家 class PlayerSprite(pygame.sprite.Sprite): speed = 5 def __init__(self): super().__init__() self.image = pygame.image.load('jet.png').convert() # load函数，返回一个 Surface 对象 self.image.set_colorkey((255,255,255), RLEACCEL) self.rect = self.image.get_rect() def update(self, key): if key[K_UP]: self.rect.move_ip(0, -self.speed) if key[K_DOWN]: self.rect.move_ip(0, self.speed) if key[K_LEFT]: self.rect.move_ip(-self.speed, 0) if key[K_RIGHT]: self.rect.move_ip(self.speed, 0) # 限定player在屏幕中 if self.rect.left < 0: self.rect.left = 0 elif self.rect.right > 800: self.rect.right = 800 if self.rect.top <= 0: self.rect.top = 0 elif self.rect.bottom >= 600: self.rect.bottom = 600 # 敌人 class EnemySprite(pygame.sprite.Sprite): speed = choice([1,3,5], [0.5, 0.4, 0.1]) def __init__(self): super().__init__() self.image = pygame.image.load('missile.png').convert() self.image.set_colorkey((255, 255, 255), RLEACCEL) self.rect = self.image.get_rect(center=(820, random.randint(0, 600))) #self.speed = random.randint(5, 20) def update(self): self.rect.move_ip(-self.speed, 0) # 从右向左 if self.rect.right < 0: self.kill() # Sprite 的内建方法 # 白云 class CloudSprite(pygame.sprite.Sprite): speed = choice([1,2], [0.8, 0.2]) def __init__(self): super().__init__() self.image = pygame.image.load('cloud.png').convert() self.image.set_colorkey((0,0,0),RLEACCEL) self.rect = self.image.get_rect( center = (random.randint(820,900),random.randint(0,600)) ) def update(self): self.rect.move_ip(-self.speed,0) if self.rect.right < 0: self.kill() # 背景 class BackgroundSprite(pygame.sprite.Sprite): def __init__(self, size): super().__init__() self.image = pygame.Surface(size) # 实际上是surf，为了统一写成image self.image.fill((135, 206, 250)) # 浅蓝色 self.rect = pygame.Rect(0, 0, *size) def update(self): pass class Game(): def __init__(self): # 游戏初始化 pygame.init() # 屏幕大小及屏幕对象 self.size = self.width, self.height = 800, 600 self.screen = pygame.display.set_mode(self.size) pygame.display.set_caption("Pygame 2D RPG !") # 两个自定义事件 self.ADDENEMY = pygame.USEREVENT + 1 # 事件本质上就是整数常量。比 USEREVENT 小的数值已经对应内置事件，因此任何自定义事件都必须比 USEREVENT 大） pygame.time.set_timer(self.ADDENEMY, 250) # 每隔 250 毫秒(四分之一秒) 触发 self.ADDCLOUD = pygame.USEREVENT + 2 pygame.time.set_timer(self.ADDCLOUD, 1000) # 两个精灵对象 self.background = BackgroundSprite(self.size) self.player = PlayerSprite() # 三个精灵组 self.enemies = pygame.sprite.Group() self.clouds = pygame.sprite.Group() self.all_sprites = pygame.sprite.Group() self.all_sprites.add(self.player) def run(self): # 窗口主循环 while True: # 遍历事件队列 for event in pygame.event.get(): if event.type == QUIT: pygame.quit() sys.exit() elif event.type == KEYDOWN: if event.key == K_ESCAPE: pygame.quit() sys.exit() elif event.type == self.ADDENEMY: # 自定义事件 new_enemy = EnemySprite() self.enemies.add(new_enemy) self.all_sprites.add(new_enemy) elif event.type == self.ADDCLOUD: # 自定义事件 new_cloud = CloudSprite() self.clouds.add(new_cloud) self.all_sprites.add(new_cloud) # 背景 self.screen.blit(self.background.image, self.background.rect) # 获取按键 key = pygame.key.get_pressed() # 更新精灵（组） self.player.update(key) self.enemies.update() self.clouds.update() # 放置精灵 for sprite in self.all_sprites: self.screen.blit(sprite.image, sprite.rect) # 碰撞检测（灵魂所在） if pygame.sprite.spritecollideany(self.player, self.enemies): self.player.kill() print('发生碰撞！') # 重绘界面 pygame.display.flip() if __name__ == '__main__': Game().run()
问题 将马放到国际象棋的8*8棋盘board上的某个方格中，马按走棋规则进行移动，走遍棋盘上的64个方格，要求每个方格进入且只进入一次，找出一种可行的方案。 分析 说明：这个图是5*5的棋盘。 图片来源：这里 类似于迷宫问题，只不过此问题的解长度固定为64 每到一格，就有[(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1)]顺时针8个方向可以选择。 走到一格称为走了一步，把每一步看作元素，8个方向看作这一步的状态空间。 套用回溯法子集树模板。 代码 '''马踏棋盘''' n = 5 # 8太慢了，改为5 p = [(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1)] # 状态空间，8个方向 entry = (2,2) # 出发地 x = [None]*(n*n) # 一个解，长度固定64，形如[(2,2),(4,3),...] X = [] # 一组解 # 冲突检测 def conflict(k): global n,p, x, X # 步子 x[k] 超出边界 if x[k][0] < 0 or x[k][0] >= n or x[k][1] < 0 or x[k][1] >= n: return True # 步子 x[k] 已经走过 if x[k] in x[:k]: return True return False # 无冲突 # 回溯法（递归版本） def subsets(k): # 到达第k个元素 global n, p, x, X if k == n*n: # 超出最尾的元素 print(x) #X.append(x[:]) # 保存（一个解） else: for i in p: # 遍历元素 x[k-1] 的状态空间: 8个方向 x[k] = (x[k-1][0] + i[0], x[k-1][1] + i[1]) if not conflict(k): # 剪枝 subsets(k+1) # 测试 x[0] = entry # 入口 subsets(1) # 开始走第k=1步 效果图
问题 有面额10元、5元、2元、1元的硬币，数量分别为3个、5个、7个、12个。现在需要给顾客找零16元，要求硬币的个数最少，应该如何找零？或者指出该问题无解。 分析 元素——状态空间分析大法：四种面额的硬币看作4个元素，对应的数目看作各自的状态空间，遍历状态空间，其它的事情交给剪枝函数。 解的长度固定：4 解的编码：(x1,x2,x3,x4) 其中x1∈[0,1,2,3], x2∈[0,1,2,3,4,5], x3∈[0,1,2,...,7], x4∈[0,1,2,...,12] 求最优解，增添全局变量：best_x, best_num 套用回溯法子集树模板。 代码 '''找零问题''' n = 4 a = [10, 5, 2, 1] # 四种面额 b = [3, 5, 7, 12] # 对应的硬币数目（状态空间） m = 53 # 给定的金额 x = [0]*n # 一个解（n元0-b[k]数组） X = [] # 一组解 best_x = [] # 最佳解 best_num = 0 # 最少硬币数目 # 冲突检测 def conflict(k): global n,m, x, X, a, b, best_num # 部分解的金额已超 if sum([p*q for p,q in zip(a[:k+1], x[:k+1])]) > m: return True # 部分解的金额加上剩下的所有金额不够 if sum([p*q for p,q in zip(a[:k+1], x[:k+1])]) + sum([p*q for p,q in zip(a[k+1:], b[k+1:])]) < m: return True # 部分解的硬币个数超best_num num = sum(x[:k+1]) if 0 < best_num < num: return True return False # 无冲突 # 回溯法（递归版本） def subsets(k): # 到达第k个元素 global n, a, b, x, X, best_x, best_num if k == n: # 超出最尾的元素 #print(x) X.append(x[:]) # 保存（一个解） # 计算硬币数目，若最佳，则保存 num = sum(x) if best_num == 0 or best_num > num: best_num = num best_x = x[:] else: for i in range(b[k]+1): # 遍历元素 a[k] 的可供选择状态: 0, 1, 2, ..., b[k] 个硬币 x[k] = i if not conflict(k): # 剪枝 subsets(k+1) # 测试 subsets(0) print(best_x) 效果图
问题 某楼梯有n层台阶，每步只能走1级台阶，或2级台阶。从下向上爬楼梯，有多少种爬法？ 分析 这个问题之前用分治法解决过。但是，这里我要用回溯法子集树模板解决它。 祭出元素-状态空间分析大法：每一步是一个元素，可走的步数[1,2]就是其状态空间。不难看出，元素不固定，状态空间固定。 直接上代码。 代码 '''爬楼梯''' n = 7 # 楼梯阶数 x = [] # 一个解（长度不固定，1-2数组，表示该步走的台阶数） X = [] # 一组解 # 冲突检测 def conflict(k): global n, x, X # 部分解步的步数之和超过总台阶数 if sum(x[:k+1]) > n: return True return False # 无冲突 # 回溯法（递归版本） def climb_stairs(k): # 走第k步 global n, x, X if sum(x) == n: # 已走的所有步数之和等于楼梯总台阶数 print(x) #X.append(x[:]) # 保存（一个解） else: for i in [1, 2]: # 第k步这个元素的状态空间为[1,2] x.append(i) if not conflict(k): # 剪枝 climb_stairs(k+1) x.pop() # 回溯 # 测试 climb_stairs(0) # 走第0步 效果图
作者：hhh5460 时间：2017年6月3日 用回溯法子集树模板解决了这么多问题，这里总结一下使用回溯法子集树模板的步骤： 1、确定元素及其状态空间（精髓） 对每一个元素，遍历它的状态空间，其它的事情交给剪枝函数！！！（正是这一点，使得它无愧于“通用解题法”这个称号！） 2、确定解的编码及解的长度是否固定 若解的长度固定，那么x[k] = i 若解的长度不固定，那么x.append(i) ... x.pop(i) 3、确定是求最优解，任一解，还是全部解 如果是求最优解，额外增加两个全局变量：best_x, best_value 4、问题是否有其特殊性 是的话，想法解决之 最后强调一下： 精髓 —— 元素-状态空间分析大法 对每一个元素，遍历它的状态空间，其它的事情交给剪枝函数！
问题 输入 第1行：字符串A 第2行：字符串B (A,B的长度 <= 1000) 输出 输出最长的子序列，如果有多个，随意输出1个。 输入示例 belong cnblogs 输出示例 blog 分析 既然打算套用回溯法子集树模板，那就要祭出元素-状态空间分析大法。 以长度较小的字符串中的字符作为元素，以长度较大的字符串中的字符作为状态空间，对每一个元素，遍历它的状态空间，其它的事情交给剪枝函数！！！ 解x的长度不固定，xi表示字符串b中的序号。 在处理每一个元素时，如果没有一个状态被选择（cnblogs中没一个字符被选取），那么程序无法去往下一个元素。 这确实是个不小的麻烦！！！思考了一天，终于想出办法了：扩充状态空间，增加一个状态q！如果元素选取了状态q，它是合法的。但是，状态q不加入解x内！！！ 看一个直观的图： 至此，enjoy it! 代码 '''最长公共子序列''' # 作者：hhh5460 # 时间：2017年6月3日 a = 'belong' b = 'cnblogs' x = [] # 一个解（长度不固定）xi是b中字符的序号 X = [] # 一组解 best_x = [] # 最佳解 best_len = 0 # 最大子序列长度 # 冲突检测 def conflict(k): global n, x, X, a,b,best_len # 如果两个字符不相等 if x[-1] < len(b) and a[k] != b[x[-1]]: return True # 如果两个字符相等，但是相对于前一个在b中的位置靠前 if a[k] == b[x[-1]] and (len(x) >= 2 and x[-1] <= x[-2]): return True # 如果部分解的长度加上后面a剩下的长度，小于等于best_len if len(x) + (len(a)-k) < best_len: return True return False # 无冲突 # 回溯法（递归版本） def LCS(k): # 到达a中的第k个元素 global x, X,a,b,best_len,best_x #print(k, x) if k == len(a): # 超出最尾的元素 if len(x) > best_len: best_len = len(x) best_x = x[:] else: for i in range(len(b)+1): # 遍历 状态空间：0~len(b)-1，技巧：人为增加一种状态len(b)，表示改行没有元素选取 if i==len(b): # 此状态不放入解x内 LCS(k+1) else: x.append(i) if not conflict(k): # 剪枝 LCS(k+1) x.pop() # 回溯 # 根据一个解x，构造最长子序列lcs def get_lcs(x): global b return ''.join([b[i] for i in x]) # 测试 LCS(0) print(b) print(best_x) print(get_lcs(best_x)) 效果图
问题 给定 n 个作业，每一个作业都有两项子任务需要分别在两台机器上完成。每一个作业必须先由机器1 处理，然后由机器2处理。 试设计一个算法找出完成这n个任务的最佳调度，使其机器2完成各作业时间之和达到最小。 分析： 看一个具体的例子： tji 机器1 机器2 作业1 2 1 作业2 3 1 作业3 2 3 最优调度顺序：1 3 2 处理时间：18 这3个作业的6种可能的调度方案是1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1； 它们所相应的完成时间和分别是19，18，20，21，19，19。易见，最佳调度方案是1,3,2，其完成时间和为18。 以1,2,3为例: 作业1在机器1上完成的时间为2,在机器2上完成的时间为3 作业2在机器1上完成的时间为5,在机器2上完成的时间为6 作业3在机器1上完成的时间为7,在机器2上完成的时间为10 3+6+10 = 19 1，3，2 作业1在机器1上完成的时间为2, 在机器2上完成的时间为3 作业3在机器1上完成的时间为4,在机器2上完成的时间为7 作业2在机器1上完成的时间为7,在机器2上完成的时间为8 3+7+8 = 18 解编码：（X1,X2,...,Xn），Xi表示顺序i执行的任务编号。所以，一个解就是任务编号的一个排列。 解空间：{（X1,X2,...,Xn）| Xi属于S，i=1,2,...,n}，S={1,2,...,n}。所以，解空间就是任务编号的全排列。 讲道理，要套用回溯法的全排列模板。 不过，有了前面两个例子做铺垫，这里套用回溯法的子集树模板。 代码 ''' 最佳作业调度问题 tji 机器1 机器2 作业1 2 1 作业2 3 1 作业3 2 3 ''' n = 3 # 作业数 # n个作业分别在两台机器需要的时间 t = [[2,1], [3,1], [2,3]] x = [0]*n # 一个解（n元数组，xi∈J） X = [] # 一组解 best_x = [] # 最佳解（一个调度） best_t = 0 # 机器2最小时间和 # 冲突检测 def conflict(k): global n, x, X, t, best_t # 部分解内的作业编号x[k]不能超过1 if x[:k+1].count(x[k]) > 1: return True # 部分解的机器2执行各作业完成时间之和未有超过 best_t #total_t = sum([sum([y[0] for y in t][:i+1]) + t[i][1] for i in range(k+1)]) j2_t = [] s = 0 for i in range(k+1): s += t[x[i]][0] j2_t.append(s + t[x[i]][1]) total_t = sum(j2_t) if total_t > best_t > 0: return True return False # 无冲突 # 最佳作业调度问题 def dispatch(k): # 到达第k个元素 global n, x, X, t, best_t, best_x if k == n: # 超出最尾的元素 #print(x) #X.append(x[:]) # 保存（一个解） # 根据解x计算机器2执行各作业完成时间之和 j2_t = [] s = 0 for i in range(n): s += t[x[i]][0] j2_t.append(s + t[x[i]][1]) total_t = sum(j2_t) if best_t == 0 or total_t < best_t: best_t = total_t best_x = x[:] else: for i in range(n): # 遍历第k个元素的状态空间，机器编号0~n-1，其它的事情交给剪枝函数 x[k] = i if not conflict(k): # 剪枝 dispatch(k+1) # 测试 dispatch(0) print(best_x) # [0, 2, 1] print(best_t) # 18 效果图
问题 从n个元素中挑选m个元素进行排列，每个元素最多可重复r次。其中m∈[2,n]，r∈[1,m]。 如：从4个元素中挑选3个元素进行排列，每个元素最多可重复r次。 分析 解x的长度是固定的，为m。 对于解x，先排第0个位置的元素x[0]，再排第1个位置的元素x[1]。我们把后者看作是前者的一种状态，即x[1]是x[0]的一种状态！！ 一般地，把x[k]看作x[k-1]的状态空间a中的一种状态，我们要做的就是遍历a[k-1]的所有状态。 那么，套用子集树模板即可。 代码 ''' 选排问题 从n个元素中挑选m个元素进行排列，每个元素最多可重复r次。其中m∈[2,n]，r∈[1,m]。 作者：hhh5460 时间：2017年6月2日 09时05分 声明：此算法版权归hhh5460所有 ''' n = 4 a = ['a','b','c','d'] m = 3 # 从4个中挑3个 r = 2 # 每个元素最多可重复2 x = [0]*m # 一个解（m元0-1数组） X = [] # 一组解 # 冲突检测 def conflict(k): global n, r, x, X, a # 部分解内的元素x[k]不能超过r if x[:k+1].count(x[k]) > r: return True return False # 无冲突 # 用子集树模板实现选排问题 def perm(k): # 到达第k个元素 global n,m, a, x, X if k == m: # 超出最尾的元素 print(x) #X.append(x[:]) # 保存（一个解） else: for i in a: # 遍历x[k-1]的状态空间a，其它的事情交给剪枝函数！ x[k] = i if not conflict(k): # 剪枝 perm(k+1) # 测试 perm(0) # 从x[0]开始排列 效果图
问题 实现 'a', 'b', 'c', 'd' 四个元素的全排列。 分析 这个问题可以直接套用排列树模板。 不过本文使用子集树模板。分析如下： 一个解x就是n个元素的一种排列，显然，解x的长度是固定的，n。 我们这样考虑：对于解x，先排第0个元素x[0]，再排第1个元素x[1]，...，当来到第k-1个元素x[k-1]时，就将剩下的未排的所有元素看作元素x[k-1]的状态空间，遍历之。 至此，套用子集树模板即可。 代码 '''用子集树实现全排列''' n = 4 a = ['a','b','c','d'] x = [0]*n # 一个解（n元0-1数组） X = [] # 一组解 # 冲突检测：无 def conflict(k): global n, x, X, a return False # 无冲突 # 用子集树模板实现全排列 def perm(k): # 到达第k个元素 global n, a, x, X if k >= n: # 超出最尾的元素 print(x) #X.append(x[:]) # 保存（一个解） else: for i in set(a)-set(x[:k]): # 遍历，剩下的未排的所有元素看作元素x[k-1]的状态空间 x[k] = i if not conflict(k): # 剪枝 perm(k+1) # 测试 perm(0) # 从x[0]开始 效果图
问题 图的m-着色判定问题 给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色，是否有一种着色法使G中任意相邻的2个顶点着不同颜色? 图的m-着色优化问题 若一个图最少需要m种颜色才能使图中任意相邻的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的最小色数m的问题称为m-着色优化问题。 分析 解的长度是固定的，n。若x为本问题的一个解，则x[i]表示第i个节点的涂色编号。 可以将m种颜色看作每个节点的状态空间。每到一个节点，遍历所有颜色，剪枝，回溯。 不难看出，可以套用回溯法子集树模板。 代码 '''图的m着色问题''' # 用邻接表表示图 n = 5 # 节点数 a,b,c,d,e = range(n) # 节点名称 graph = [ {b,c,d}, {a,c,d,e}, {a,b,d}, {a,b,c,e}, {b,d} ] m = 4 # m种颜色 x = [0]*n # 一个解（n元数组，长度固定）注意：解x的下标就是a,b,c,d,e!!! X = [] # 一组解 # 冲突检测 def conflict(k): global n,graph,x # 找出第k个节点前面已经涂色的邻接节点 nodes = [node for node in range(k) if node in graph[k]] if x[k] in [x[node] for node in nodes]: # 已经有相邻节点涂了这种颜色 return True return False # 无冲突 # 图的m着色（全部解） def dfs(k): # 到达（解x的）第k个节点 global n,m,graph,x,X if k == n: # 解的长度超出 print(x) #X.append(x[:]) else: for color in range(m): # 遍历节点k的可涂颜色编号（状态空间），全都一样 x[k] = color if not conflict(k): # 剪枝 dfs(k+1) # 测试 dfs(a) # 从节点a开始 效果图
问题 旅行商问题（Traveling Salesman Problem,TSP）是旅行商要到若干个城市旅行，各城市之间的费用是已知的，为了节省费用，旅行商决定从所在城市出发，到每个城市旅行一次后返回初始城市，问他应选择什么样的路线才能使所走的总费用最短？ 分析 此问题可描述如下：G=(V,E)是带权的有向图，找到包含V中每个结点一个有向环，亦即一条周游路线，使得这个有向环上所有边成本之和最小。 这个问题与前一篇文章的区别就是，本题是带权的图。只要一点小小的修改即可。 解的长度是固定的n+1。 对图中的每一个节点，都有自己的邻接节点。对某个节点而言，其所有的邻接节点构成这个节点的状态空间。当路径到达这个节点时，遍历其状态空间。 最终，一定可以找到最优解! 显然，继续套用回溯法子集树模板！！！ 代码 '''旅行商问题（Traveling Salesman Problem,TSP）''' # 用邻接表表示带权图 n = 5 # 节点数 a,b,c,d,e = range(n) # 节点名称 graph = [ {b:7, c:6, d:1, e:3}, {a:7, c:3, d:7, e:8}, {a:6, b:3, d:12, e:11}, {a:1, b:7, c:12, e:2}, {a:3, b:8, c:11, d:2} ] x = [0]*(n+1) # 一个解（n+1元数组，长度固定） X = [] # 一组解 best_x = [0]*(n+1) # 已找到的最佳解（路径） min_cost = 0 # 最小旅费 # 冲突检测 def conflict(k): global n,graph,x,best_x,min_cost # 第k个节点，是否前面已经走过 if k < n and x[k] in x[:k]: return True # 回到出发节点 if k == n and x[k] != x[0]: return True # 前面部分解的旅费之和超出已经找到的最小总旅费 cost = sum([graph[node1][node2] for node1,node2 in zip(x[:k], x[1:k+1])]) if 0 < min_cost < cost: return True return False # 无冲突 # 旅行商问题（TSP） def tsp(k): # 到达（解x的）第k个节点 global n,a,b,c,d,e,graph,x,X,min_cost,best_x if k > n: # 解的长度超出，已走遍n+1个节点 （若不回到出发节点，则 k==n） cost = sum([graph[node1][node2] for node1,node2 in zip(x[:-1], x[1:])]) # 计算总旅费 if min_cost == 0 or cost < min_cost: best_x = x[:] min_cost = cost #print(x) else: for node in graph[x[k-1]]: # 遍历节点x[k-1]的邻接节点（状态空间） x[k] = node if not conflict(k): # 剪枝 tsp(k+1) # 测试 x[0] = c # 出发节点：路径x的第一个节点（随便哪个） tsp(1) # 开始处理解x中的第2个节点 print(best_x) print(min_cost) 效果图
问题 一个图： A --> B A --> C B --> C B --> D B --> E C --> A C --> D D --> C E --> F F --> C F --> D 从图中的一个节点E出发，不重复地经过所有其它节点后，回到出发节点E，称为一条路径。请找出所有可能的路径。 分析 将这个图可视化如下： 本问题涉及到图，那首先要考虑图用那种存储结构表示。邻接矩阵、邻接表、...都不太熟。 百度一下，在这里发现了一个最爱。这是网上找到一种最简洁的邻接表表示方式。 接下来对问题本身进行分析： 显然，问题的解的长度是固定的，亦即所有的路径长度都是固定的：n（不回到出发节点） 或 n+1（回到出发节点） 每个节点，都有各自的邻接节点。 对某个节点来说，它的所有邻接节点，可以看作这个节点的状态空间。遍历其状态空间，剪枝，深度优先递归到下一个节点。搞定！ 至此，很明显套用回溯法子集树模板。 代码 ''' 图的遍历 从一个节点出发，不重复地经过所有其它节点后，回到出发节点。找出所有的路径 ''' # 用邻接表表示图 n = 6 # 节点数 a,b,c,d,e,f = range(n) # 节点名称 graph = [ {b,c}, {c,d,e}, {a,d}, {c}, {f}, {c,d} ] x = [0]*(n+1) # 一个解（n+1元数组，长度固定） X = [] # 一组解 # 冲突检测 def conflict(k): global n,graph,x # 第k个节点，是否前面已经走过 if k < n and x[k] in x[:k]: return True # 回到出发节点 if k == n and x[k] != x[0]: return True return False # 无冲突 # 图的遍历 def dfs(k): # 到达（解x的）第k个节点 global n,a,b,c,d,e,f,graph,x,X if k > n: # 解的长度超出，已走遍n+1个节点 （若不回到出发节点，则 k==n） print(x) #X.append(x[:]) else: for node in graph[x[k-1]]: # 遍历节点x[k]的邻接节点（x[k]的所有状态） x[k] = node if not conflict(k): # 剪枝 dfs(k+1) # 测试 x[0] = e # 出发节点 dfs(1) # 开始处理解x中的第2个节点 效果图
本来想用回溯法实现 算24点。题目都拟好了，就是《python 回溯法 子集树模板 系列 —— 7、24点》。无奈想了一天，没有头绪。只好改用暴力穷举法。 思路说明 根据四个数，三个运算符，构造三种中缀表达式，遍历，计算每一种可能 显然可能的形式不止三种。但是，其它的形式要么得不到24点，要么在加、乘意义下可以转化为这三种形式的表达式！ 使用内置的eval函数计算中缀表达式，使得代码变得非常简洁！ 完整代码 # 作者：hhh5460 # 时间：2017年6月3日 import itertools def twentyfour(cards): '''史上最短计算24点代码''' for nums in itertools.permutations(cards): # 四个数 for ops in itertools.product('+-*/', repeat=3): # 三个运算符（可重复！） # 构造三种中缀表达式 (bsd) bds1 = '({0}{4}{1}){5}({2}{6}{3})'.format(*nums, *ops) # (a+b)*(c-d) bds2 = '(({0}{4}{1}){5}{2}){6}{3}'.format(*nums, *ops) # (a+b)*c-d bds3 = '{0}{4}({1}{5}({2}{6}{3}))'.format(*nums, *ops) # a/(b-(c/d)) for bds in [bds1, bds2, bds3]: # 遍历 try: if abs(eval(bds) - 24.0) < 1e-10: # eval函数 return bds except ZeroDivisionError: # 零除错误！ continue return 'Not found!' # 测试 # 数据来源：http://www.cnblogs.com/grenet/archive/2013/02/28/2936965.html cards =[[1,1,1,8], [1,1,2,6], [1,1,2,7], [1,1,2,8], [1,1,2,9], [1,1,2,10], [1,1,3,4], [1,1,3,5], [1,1,3,6], [1,1,3,7], [1,1,3,8], [1,1,3,9], [1,1,3,10], [1,1,4,4], [1,1,4,5], [1,1,4,6], [1,1,4,7], [1,1,4,8], [1,1,4,9], [1,1,4,10], [1,1,5,5], [1,1,5,6], [1,1,5,7], [1,1,5,8], [1,1,6,6], [1,1,6,8], [1,1,6,9], [1,1,7,10], [1,1,8,8], [1,2,2,4], [1,2,2,5], [1,2,2,6], [1,2,2,7], [1,2,2,8], [1,2,2,9], [1,2,2,10], [1,2,3,3], [1,2,3,4], [1,2,3,5], [1,2,3,6], [1,2,3,7], [1,2,3,8], [1,2,3,9], [1,2,3,10], [1,2,4,4], [1,2,4,5], [1,2,4,6], [1,2,4,7], [1,2,4,8], [1,2,4,9], [1,2,4,10], [1,2,5,5], [1,2,5,6], [1,2,5,7], [1,2,5,8], [1,2,5,9], [1,2,5,10], [1,2,6,6], [1,2,6,7], [1,2,6,8], [1,2,6,9], [1,2,6,10], [1,2,7,7], [1,2,7,8], [1,2,7,9], [1,2,7,10], [1,2,8,8], [1,2,8,9], [1,2,8,10], [1,3,3,3], [1,3,3,4], [1,3,3,5], [1,3,3,6], [1,3,3,7], [1,3,3,8], [1,3,3,9], [1,3,3,10], [1,3,4,4], [1,3,4,5], [1,3,4,6], [1,3,4,7], [1,3,4,8], [1,3,4,9], [1,3,4,10], [1,3,5,6], [1,3,5,7], [1,3,5,8], [1,3,5,9], [1,3,5,10], [1,3,6,6], [1,3,6,7], [1,3,6,8], [1,3,6,9], [1,3,6,10], [1,3,7,7], [1,3,7,8], [1,3,7,9], [1,3,7,10], [1,3,8,8], [1,3,8,9], [1,3,8,10], [1,3,9,9], [1,3,9,10], [1,3,10,10], [1,4,4,4], [1,4,4,5], [1,4,4,6], [1,4,4,7], [1,4,4,8], [1,4,4,9], [1,4,4,10], [1,4,5,5], [1,4,5,6], [1,4,5,7], [1,4,5,8], [1,4,5,9], [1,4,5,10], [1,4,6,6], [1,4,6,7], [1,4,6,8], [1,4,6,9], [1,4,6,10], [1,4,7,7], [1,4,7,8], [1,4,7,9], [1,4,8,8], [1,4,8,9], [1,4,9,10], [1,4,10,10], [1,5,5,5], [1,5,5,6], [1,5,5,9], [1,5,5,10], [1,5,6,6], [1,5,6,7], [1,5,6,8], [1,5,6,9], [1,5,6,10], [1,5,7,8], [1,5,7,9], [1,5,7,10], [1,5,8,8], [1,5,8,9], [1,5,8,10], [1,5,9,9], [1,5,9,10], [1,5,10,10], [1,6,6,6], [1,6,6,8], [1,6,6,9], [1,6,6,10], [1,6,7,9], [1,6,7,10], [1,6,8,8], [1,6,8,9], [1,6,8,10], [1,6,9,9], [1,6,9,10], [1,7,7,9], [1,7,7,10], [1,7,8,8], [1,7,8,9], [1,7,8,10], [1,7,9,9], [1,7,9,10], [1,8,8,8], [1,8,8,9], [1,8,8,10], [2,2,2,3], [2,2,2,4], [2,2,2,5], [2,2,2,7], [2,2,2,8], [2,2,2,9], [2,2,2,10], [2,2,3,3], [2,2,3,4], [2,2,3,5], [2,2,3,6], [2,2,3,7], [2,2,3,8], [2,2,3,9], [2,2,3,10], [2,2,4,4], [2,2,4,5], [2,2,4,6], [2,2,4,7], [2,2,4,8], [2,2,4,9], [2,2,4,10], [2,2,5,5], [2,2,5,6], [2,2,5,7], [2,2,5,8], [2,2,5,9], [2,2,5,10], [2,2,6,6], [2,2,6,7], [2,2,6,8], [2,2,6,9], [2,2,6,10], [2,2,7,7], [2,2,7,8], [2,2,7,10], [2,2,8,8], [2,2,8,9], [2,2,8,10], [2,2,9,10], [2,2,10,10], [2,3,3,3], [2,3,3,5], [2,3,3,6], [2,3,3,7], [2,3,3,8], [2,3,3,9], [2,3,3,10], [2,3,4,4], [2,3,4,5], [2,3,4,6], [2,3,4,7], [2,3,4,8], [2,3,4,9], [2,3,4,10], [2,3,5,5], [2,3,5,6], [2,3,5,7], [2,3,5,8], [2,3,5,9], [2,3,5,10], [2,3,6,6], [2,3,6,7], [2,3,6,8], [2,3,6,9], [2,3,6,10], [2,3,7,7], [2,3,7,8], [2,3,7,9], [2,3,7,10], [2,3,8,8], [2,3,8,9], [2,3,8,10], [2,3,9,9], [2,3,9,10], [2,3,10,10], [2,4,4,4], [2,4,4,5], [2,4,4,6], [2,4,4,7], [2,4,4,8], [2,4,4,9], [2,4,4,10], [2,4,5,5], [2,4,5,6], [2,4,5,7], [2,4,5,8], [2,4,5,9], [2,4,5,10], [2,4,6,6], [2,4,6,7], [2,4,6,8], [2,4,6,9], [2,4,6,10], [2,4,7,7], [2,4,7,8], [2,4,7,9], [2,4,7,10], [2,4,8,8], [2,4,8,9], [2,4,8,10], [2,4,9,9], [2,4,9,10], [2,4,10,10], [2,5,5,7], [2,5,5,8], [2,5,5,9], [2,5,5,10], [2,5,6,6], [2,5,6,7], [2,5,6,8], [2,5,6,9], [2,5,6,10], [2,5,7,7], [2,5,7,8], [2,5,7,9], [2,5,7,10], [2,5,8,8], [2,5,8,9], [2,5,8,10], [2,5,9,10], [2,5,10,10], [2,6,6,6], [2,6,6,7], [2,6,6,8], [2,6,6,9], [2,6,6,10], [2,6,7,8], [2,6,7,9], [2,6,7,10], [2,6,8,8], [2,6,8,9], [2,6,8,10], [2,6,9,9], [2,6,9,10], [2,6,10,10], [2,7,7,8], [2,7,7,10], [2,7,8,8], [2,7,8,9], [2,7,9,10], [2,7,10,10], [2,8,8,8], [2,8,8,9], [2,8,8,10], [2,8,9,9], [2,8,9,10], [2,8,10,10], [2,9,10,10], [3,3,3,3], [3,3,3,4], [3,3,3,5], [3,3,3,6], [3,3,3,7], [3,3,3,8], [3,3,3,9], [3,3,3,10], [3,3,4,4], [3,3,4,5], [3,3,4,6], [3,3,4,7], [3,3,4,8], [3,3,4,9], [3,3,5,5], [3,3,5,6], [3,3,5,7], [3,3,5,9], [3,3,5,10], [3,3,6,6], [3,3,6,7], [3,3,6,8], [3,3,6,9], [3,3,6,10], [3,3,7,7], [3,3,7,8], [3,3,7,9], [3,3,8,8], [3,3,8,9], [3,3,8,10], [3,3,9,9], [3,3,9,10], [3,4,4,4], [3,4,4,5], [3,4,4,6], [3,4,4,7], [3,4,4,8], [3,4,4,9], [3,4,4,10], [3,4,5,5], [3,4,5,6], [3,4,5,7], [3,4,5,8], [3,4,5,9], [3,4,5,10], [3,4,6,6], [3,4,6,8], [3,4,6,9], [3,4,6,10], [3,4,7,7], [3,4,7,8], [3,4,7,9], [3,4,7,10], [3,4,8,9], [3,4,8,10], [3,4,9,9], [3,4,10,10], [3,5,5,6], [3,5,5,7], [3,5,5,8], [3,5,5,9], [3,5,6,6], [3,5,6,7], [3,5,6,8], [3,5,6,9], [3,5,6,10], [3,5,7,8], [3,5,7,9], [3,5,7,10], [3,5,8,8], [3,5,8,9], [3,5,9,9], [3,5,9,10], [3,5,10,10], [3,6,6,6], [3,6,6,7], [3,6,6,8], [3,6,6,9], [3,6,6,10], [3,6,7,7], [3,6,7,8], [3,6,7,9], [3,6,7,10], [3,6,8,8], [3,6,8,9], [3,6,8,10], [3,6,9,9], [3,6,9,10], [3,6,10,10], [3,7,7,7], [3,7,7,8], [3,7,7,9], [3,7,7,10], [3,7,8,8], [3,7,8,9], [3,7,9,9], [3,7,9,10], [3,7,10,10], [3,8,8,8], [3,8,8,9], [3,8,8,10], [3,8,9,9], [3,8,9,10], [3,8,10,10], [3,9,9,9], [3,9,9,10], [3,9,10,10], [4,4,4,4], [4,4,4,5], [4,4,4,6], [4,4,4,7], [4,4,4,8], [4,4,4,9], [4,4,4,10], [4,4,5,5], [4,4,5,6], [4,4,5,7], [4,4,5,8], [4,4,5,10], [4,4,6,8], [4,4,6,9], [4,4,6,10], [4,4,7,7], [4,4,7,8], [4,4,7,9], [4,4,7,10], [4,4,8,8], [4,4,8,9], [4,4,8,10], [4,4,10,10], [4,5,5,5], [4,5,5,6], [4,5,5,7], [4,5,5,8], [4,5,5,9], [4,5,5,10], [4,5,6,6], [4,5,6,7], [4,5,6,8], [4,5,6,9], [4,5,6,10], [4,5,7,7], [4,5,7,8], [4,5,7,9], [4,5,7,10], [4,5,8,8], [4,5,8,9], [4,5,8,10], [4,5,9,9], [4,5,9,10], [4,5,10,10], [4,6,6,6], [4,6,6,7], [4,6,6,8], [4,6,6,9], [4,6,6,10], [4,6,7,7], [4,6,7,8], [4,6,7,9], [4,6,7,10], [4,6,8,8], [4,6,8,9], [4,6,8,10], [4,6,9,9], [4,6,9,10], [4,6,10,10], [4,7,7,7], [4,7,7,8], [4,7,8,8], [4,7,8,9], [4,7,8,10], [4,7,9,9], [4,7,9,10], [4,7,10,10], [4,8,8,8], [4,8,8,9], [4,8,8,10], [4,8,9,9], [4,8,9,10], [4,8,10,10], [4,9,9,10], [5,5,5,5], [5,5,5,6], [5,5,5,9], [5,5,6,6], [5,5,6,7], [5,5,6,8], [5,5,7,7], [5,5,7,8], [5,5,7,10], [5,5,8,8], [5,5,8,9], [5,5,8,10], [5,5,9,9], [5,5,9,10], [5,5,10,10], [5,6,6,6], [5,6,6,7], [5,6,6,8], [5,6,6,9], [5,6,6,10], [5,6,7,7], [5,6,7,8], [5,6,7,9], [5,6,8,8], [5,6,8,9], [5,6,8,10], [5,6,9,9], [5,6,9,10], [5,6,10,10], [5,7,7,9], [5,7,7,10], [5,7,8,8], [5,7,8,9], [5,7,8,10], [5,7,9,10], [5,7,10,10], [5,8,8,8], [5,8,8,9], [5,8,8,10], [5,9,10,10], [6,6,6,6], [6,6,6,8], [6,6,6,9], [6,6,6,10], [6,6,7,9], [6,6,7,10], [6,6,8,8], [6,6,8,9], [6,6,8,10], [6,6,9,10], [6,7,7,10], [6,7,8,9], [6,7,8,10], [6,7,9,9], [6,7,10,10], [6,8,8,8], [6,8,8,9], [6,8,8,10], [6,8,9,9], [6,8,9,10], [6,9,9,10], [6,10,10,10], [7,7,9,10], [7,8,8,9], [7,8,8,10], [7,8,9,10], [7,8,10,10], [8,8,8,10]] for card in cards: print(twentyfour(card)) 以上数据全都pass，图我就不截了
问题 某乡村小学有六个年级，每个年级有一个班，共六个班。 周一到周五，每天上6节课，共计30节课。 开设的课程 一年级：语(9)数(9)书(2)体(2)美(2)音(2)德(2)班(1)安(1) 二年级：语(9)数(9)书(2)体(2)美(2)音(2)德(2)班(1)安(1) 三年级：语(8)数(8)英(4)体(2)美(2)音(2)德(2)班(1)安(1) 四年级：语(8)数(8)英(4)体(2)美(2)音(2)德(2)班(1)安(1) 五年级：语(8)数(8)英(4)体(2)美(2)音(2)德(2)班(1)安(1) 六年级：语(8)数(8)英(4)体(2)美(2)音(2)德(2)班(1)安(1) 要求 各门课课时必须相符 周一最后一节课班会，周五最后一节课安全教育是固定的。 上午只能排语、数、英 全校只有两位音乐老师 三年级的数学不能排在周五上午第三节（三年级数学潘老师家里有事） 分析 将每一个（时间，空间）点对，作为一个元素。这些元素都具有各自的[状态1，状态2，状态3，状态4，状态5，状态6，状态7，状态8，状态9]共9个状态。 （时间，空间） --> 状态 一种状态对应一个课程。 对每一个元素，遍历相应的9种状态。 解的长度是固定的，30 * 6 的二维数组 套用子集树模板即可。 本问题只需要解决存在性。也就是说，只要找到一个符合要求的解就ok了。 此问题的本质就是，各(时,空)点对的取各自状态搭配的问题。 代码 '''排课问题''' # 作者：hhh5460 # 写于：2017年5月30日22时33分 # 声明：此算法的版权归本人所有 m = 30 # 一周课时数（时间） n = 6 # 全校班级数（空间） o = 30 * 6 # 元素个数，即(时, 空)点对的个数 # 6个班开始的课程（状态空间） a = [['语','数','书','体','美','音','德','班','安'], # 一年级 ['语','数','书','体','美','音','德','班','安'], # 二年级 ['语','数','英','体','美','音','德','班','安'], # 三年级 ['语','数','英','体','美','音','德','班','安'], # 四年级 ['语','数','英','体','美','音','德','班','安'], # 五年级 ['语','数','英','体','美','音','德','班','安']] # 六年级 # 课时数 b = [[9,9,2,2,2,2,2,1,1], [9,9,2,2,2,2,2,1,1], [8,8,4,2,2,2,2,1,1], [8,8,4,2,2,2,2,1,1], [8,8,4,2,2,2,2,1,1], [8,8,4,2,2,2,2,1,1]] x = [[0 for _ in range(n)] for _ in range(m)] # 一个解，m*n 的二维数组 is_found = False # 结束所有递归标志!!!!! # 冲突检测 def conflict(t, s): '''只考虑刚刚排的x[t][s]''' global m,n,o,a,b,x # 一、各门课课时数必须相符（纵向看） # 1.前面已经排的课时不能超 if [r[s] for r in x[:t+1]].count(x[t][s]) > b[s][a[s].index(x[t][s])]: # 黑科技，不要眼花！ return True # 2.后面剩的课时不能不够 if [r[s] for r in x[:t+1]].count(x[t][s]) + (m-t-1) < b[s][a[s].index(x[t][s])]: return True # 二、周一最后一节课班会，周五最后一节课安全教育是固定的。 # 1.周一最后一节课班会 if x[t][s] == '班' and t != 5: return True # 2.周五最后一节课安全教育 if x[t][s] == '安' and t != 29: return True # 三、上午只能排语、数、英 if t % 6 in [0,1,2] and x[t][s] not in ['语','数','英']: return True # 四、只有两个音乐老师（横向看） # 前面已经排的班级不能有3个及以上的班级同时上音乐课 if x[t][s] == '音' and x[t][:s+1].count('音') >= 3: return True # 五、三年级的数学不能排在周五上午第三节（三年级数学潘老师家里有事） if x[t][s] == '数' and t==5*n+3-1: return True return False # 无冲突 # 套用子集树模板 def paike(t, s): # 到达(t,s)时空点对的位置 global m,n,o,a,b,x, is_found if is_found: return # 结束所有递归 if t == m: # 超出最尾的元素 #print(x) show(x) # 美化版 is_found = True # 只需找一个 else: for i in a[s]: # 遍历第s个班级的对应的所有状态，不同的班级状态不同 x[t][s] = i if not conflict(t, s): # 剪枝 ns = [s + 1, 0][s + 1 == n] # 行扫描方式 nt = [t, t + 1][s + 1 == n] paike(nt, ns) # 去往(nt, ns)时空点对 # 可视化一个解x def show(x): import pprint pprint.pprint(x[:6]) # 全校的周一课表 pprint.pprint(x[6:12]) # 全校的周二课表 pprint.pprint(x[12:18]) # 全校的周三课表 pprint.pprint(x[18:24]) # 全校的周四课表 pprint.pprint(x[24:]) # 全校的周五课表 # 测试 paike(0, 0) # 从时空点对(0,0)开始 效果图 正在运行中... ... 稍后奉上。 补：现在时间2017年6月1日7时40分，程序已运行34+时，还没有结果，囧！ 之所以这么慢，其原因可能是递归太多了！ 好吧，那只能等我以后将递归版本改为迭代版本，再运行看其结果如何了。
问题 有5件不同的上衣，3条不同的裤子，4顶不同的帽子，从中取出一顶帽子、一件上衣和一条裤子作为一种搭配，问有多少种不同的搭配？ 分析 换个角度看，现有头、身、腿三个元素，每个元素都有各自的几种状态。 头元素有['帽1', '帽2', '帽3', '帽4']共4种状态，身元素有['衣1', '衣2', '衣3', '衣4', '衣5']共5种状态，腿元素有['裤1', '裤2', '裤3']共3种状态 从头开始，自上而下，遍历每个元素的所有状态。 解的长度是固定的。 这里特别注意：每个元素的状态数目不同！！！ 套用子集树模板即可 代码 ```python '''取物排列问题''' n = 3 # 3个元素 头、身、腿3个元素各自的状态空间 a = [['帽1', '帽2', '帽3', '帽4'], ['衣1', '衣2', '衣3', '衣4', '衣5'], ['裤1', '裤2', '裤3']] x = [0]*n # 一个解，长度固定，3元数组 X = [] # 一组解 冲突检测 def conflict(k): return False # 无冲突 套用子集树模板 def match(k): # 到达第k个元素 global n, a, x, X if k >= n: # 超出最尾的元素 print(x) #X.append(x[:]) # 保存（一个解） else: for i in a[k]: # 直接a[k]，若间接则range(len(a[k]))。 遍历第k个元素的对应的所有选择状态，不同的元素状态数目不同 x[k] = i if not conflict(k): # 剪枝 match(k+1) 测试 match(0) # 从头（第0个元素）开始 ``` 效果图
问题 找出从自然数1、2、3、...、n中任取r个数的所有组合。 例如，n=5，r=3的所有组合为： 1,2,3 1,2,4 1,2,5 1,3,4 1,3,5 1,4,5 2,3,4 2,3,5 2,4,5 3,4,5 分析 换个角度，r=3的所有组合，相当于元素个数为3的所有子集。因此，在遍历子集树的时候，对元素个数不为3的子树剪枝即可。 注意，这里不妨使用固定长度的解。 直接套用子集树模板。 代码 '''数字组合问题''' n = 5 r = 3 a = [1,2,3,4,5] # 五个数字 x = [0]*n # 一个解（n元0,1数组） 固定长度 X = [] # 一组解 def conflict(k): global n, r, x if sum(x[:k+1]) > r: # 部分解的长度超出r return True if sum(x[:k+1]) + (n-k-1) < r: # 部分解的长度加上剩下长度不够r return True return False # 无冲突 # 套用子集树模板 def comb(k): # 到达第k个元素 global n, x, X if k >= n: # 超出最尾的元素 #print(x) X.append(x[:]) # 保存（一个解） else: for i in [1, 0]: # 遍历元素 a[k] 的两种选择状态:1-选择，0-不选 x[k] = i if not conflict(k): # 剪枝 comb(k+1) # 根据一个解x，构造对应的一个组合 def get_a_comb(x): global a return [y[0] for y in filter(lambda s:s[1]==1, zip(a, x))] # 根据一组解X，构造对应的一组组合 def get_all_combs(X): return [get_a_comb(x) for x in X] # 测试 comb(0) print(X) print(get_all_combs(X)) 效果图
问题 给定N个物品和一个背包。物品i的重量是Wi,其价值位Vi ，背包的容量为C。问应该如何选择装入背包的物品，使得放入背包的物品的总价值为最大？ 分析 显然，放入背包的物品，是N个物品的所有子集的其中之一。N个物品中每一个物品，都有选择、不选择两种状态。因此，只需要对每一个物品的这两种状态进行遍历。 解是一个长度固定的N元0,1数组。 套用回溯法子集树模板，做起来不要太爽！！！ 代码 '''0-1背包问题''' n = 3 # 物品数量 c = 30 # 包的载重量 w = [20, 15, 15] # 物品重量 v = [45, 25, 25] # 物品价值 maxw = 0 # 合条件的能装载的最大重量 maxv = 0 # 合条件的能装载的最大价值 bag = [0,0,0] # 一个解（n元0-1数组）长度固定为n bags = [] # 一组解 bestbag = None # 最佳解 # 冲突检测 def conflict(k): global bag, w, c # bag内的前k个物品已超重，则冲突 if sum([y[0] for y in filter(lambda x:x[1]==1, zip(w[:k+1], bag[:k+1]))]) > c: return True return False # 套用子集树模板 def backpack(k): # 到达第k个物品 global bag, maxv, maxw, bestbag if k==n: # 超出最后一个物品，判断结果是否最优 cv = get_a_pack_value(bag) cw = get_a_pack_weight(bag) if cv > maxv : # 价值大的优先 maxv = cv bestbag = bag[:] if cv == maxv and cw < maxw: # 价值相同，重量轻的优先 maxw = cw bestbag = bag[:] else: for i in [1,0]: # 遍历两种状态 [选取1, 不选取0] bag[k] = i # 因为解的长度是固定的 if not conflict(k): # 剪枝 backpack(k+1) # 根据一个解bag，计算重量 def get_a_pack_weight(bag): global w return sum([y[0] for y in filter(lambda x:x[1]==1, zip(w, bag))]) # 根据一个解bag，计算价值 def get_a_pack_value(bag): global v return sum([y[0] for y in filter(lambda x:x[1]==1, zip(v, bag))]) # 测试 backpack(0) print(bestbag, get_a_pack_value(bestbag)) 效果图
问题 给定一个迷宫，入口已知。问是否有路径从入口到出口，若有则输出一条这样的路径。注意移动可以从上、下、左、右、上左、上右、下左、下右八个方向进行。迷宫输入0表示可走，输入1表示墙。为方便起见，用1将迷宫围起来避免边界问题。 分析 考虑到左、右是相对的，因此修改为：北、东北、东、东南、南、西南、西、西北八个方向。在任意一格内，有8个方向可以选择，亦即8种状态可选。因此从入口格子开始，每进入一格都要遍历这8种状态。 显然，可以套用回溯法的子集树模板。 注意，解的长度是不固定的。 图片来源：点我 代码 # 迷宫（1是墙，0是通路） maze = [[1,1,1,1,1,1,1,1,1,1], [0,0,1,0,1,1,1,1,0,1], [1,1,0,1,0,1,1,0,1,1], [1,0,1,1,1,0,0,1,1,1], [1,1,1,0,0,1,1,0,1,1], [1,1,0,1,1,1,1,1,0,1], [1,0,1,0,0,1,1,1,1,0], [1,1,1,1,1,0,1,1,1,1]] m, n = 8, 10 # 8行，10列 entry = (1,0) # 迷宫入口 path = [entry] # 一个解（路径） paths = [] # 一组解 # 移动的方向（顺时针8个：N, EN, E, ES, S, WS, W, WN） directions = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)] # 冲突检测 def conflict(nx, ny): global m,n,maze # 是否在迷宫中，以及是否可通行 if 0 <= nx < m and 0 <= ny < n and maze[nx][ny]==0: return False return True # 套用子集树模板 def walk(x, y): # 到达(x,y)格子 global entry,m,n,maze,path,paths,directions if (x,y) != entry and (x % (m-1) ==0 or y % (n-1) == 0): # 出口 #print(path) paths.append(path[:]) # 直接保存，未做最优化 else: for d in directions: # 遍历8个方向(亦即8个状态) nx, ny = x+d[0], y+d[1] path.append((nx,ny)) # 保存，新坐标入栈 if not conflict(nx, ny): # 剪枝 maze[nx][ny] = 2 # 标记，已访问（奇怪，此两句只能放在if区块内！） walk(nx, ny) maze[nx][ny] = 0 # 回溯，恢复 path.pop() # 回溯，出栈 # 解的可视化（根据一个解x，复原迷宫路径，'2'表示通路） def show(path): global maze import pprint, copy maze2 = copy.deepcopy(maze) for p in path: maze2[p[0]][p[1]] = 2 # 通路 pprint.pprint(maze) # 原迷宫 print() pprint.pprint(maze2) # 带通路的迷宫 # 测试 walk(1,0) print(paths[-1], '\n') # 看看最后一条路径 show(paths[-1]) 效果图
问题 8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 分析 为了简化问题，考虑到8个皇后不同行，则每一行放置一个皇后，每一行的皇后可以放置于第0、1、2、...、7列，我们认为每一行的皇后有8种状态。那么，我们只要套用子集树模板，从第0行开始，自上而下，对每一行的皇后，遍历它的8个状态即可。 代码 ''' 8皇后问题 ''' n = 8 x = [] # 一个解（n元数组） X = [] # 一组解 # 冲突检测：判断 x[k] 是否与前 x[0~k-1] 冲突 def conflict(k): global x for i in range(k): # 遍历前 x[0~k-1] if x[i]==x[k] or abs(x[i]-x[k])==abs(i-k): # 判断是否与 x[k] 冲突 return True return False # 套用子集树模板 def queens(k): # 到达第k行 global n, x, X if k >= n: # 超出最底行 #print(x) X.append(x[:]) # 保存（一个解），注意x[:] else: for i in range(n): # 遍历第 0~n-1 列（即n个状态） x.append(i) # 皇后置于第i列，入栈 if not conflict(k): # 剪枝 queens(k+1) x.pop() # 回溯，出栈 # 解的可视化（根据一个解x，复原棋盘。'X'表示皇后） def show(x): global n for i in range(n): print('. ' * (x[i]) + 'X ' + '. '*(n-x[i]-1)) # 测试 queens(0) # 从第0行开始 print(X[-1], '\n') show(X[-1]) 效果图
一直不是太理解回溯法，这几天集中学习了一下，记录如下。 回溯法有“通用的解题法”之称。 1.定义： 也叫试探法，它是一种系统地搜索问题的解的方法。 2.基本思想： 从一条路往前走，能进则进，不能进则退回来，换一条路再试。 3.一般步骤： 定义一个解空间（子集树、排列树二选一） 利用适于搜索的方法组织解空间。 利用深度优先法搜索解空间。 利用剪枝函数避免移动到不可能产生解的子空间。 4.约束函数： 是否满足显约束（存在） 5.限界函数： 是否满足隐约束（最优） 6.子集树模板 遍历子集树，时间复杂度 O(2^n) 如果解的长度是不固定的，那么解和元素顺序无关，即可以从中选择0个或多个。例如：子集，迷宫，... 如果解的长度是固定的，那么解和元素顺序有关，即每个元素有一个对应的状态。例如：子集，8皇后，... 解空间的个数指数级别的，为2^n,可以用子集树来表示所有的解 适用于：幂集、子集和、0-1背包、装载、8皇后、迷宫、... a.子集树模板递归版 '''求集合{1, 2, 3, 4}的所有子集''' n = 4 #a = ['a','b','c','d'] a = [1, 2, 3, 4] x = [] # 一个解（n元0-1数组） X = [] # 一组解 # 冲突检测：无 def conflict(k): global n, x, X, a return False # 无冲突 # 一个例子 # 冲突检测：奇偶性相同，且和小于8的子集 def conflict2(k): global n, x, X, a if k==0: return False # 根据部分解，构造部分集 s = [y[0] for y in filter(lambda s:s[1]!=0, zip(a[:k+1],x[:k+1]))] if len(s)==0: return False if 0 < sum(map(lambda y:y%2, s)) < len(s) or sum(s) >= 8: # 只比较 x[k] 与 x[k-1] 奇偶是否相间 return True return False # 无冲突 # 子集树递归模板 def subsets(k): # 到达第k个元素 global n, x, X if k >= n: # 超出最尾的元素 #print(x) X.append(x[:]) # 保存（一个解） else: for i in [1, 0]: # 遍历元素 a[k] 的两种选择状态:1-选择，0-不选 x.append(i) if not conflict2(k): # 剪枝 subsets(k+1) x.pop() # 回溯 # 根据一个解x，构造一个子集 def get_a_subset(x): global a return [y[0] for y in filter(lambda s:s[1]!=0, zip(a,x))] # 根据一组解X, 构造一组子集 def get_all_subset(X): return [get_a_subset(x) for x in X] # 测试 subsets(0) # 查看第3个解，及对应的子集 #print(X[2]) #print(get_a_subset(X[2])) print(get_all_subset(X)) b.子集树模板非递归版 7.排列树模板 遍历排列树，时间复杂度O(n!) 解空间是由n个元素的排列形成，也就是说n个元素的每一个排列都是解空间中的一个元素，那么，最后解空间的组织形式是排列树 适用于：n个元素全排列、旅行商、... a.排列树模板递归版 '''求[1,2,3,4]的全排列''' n = 4 x = [1,2,3,4] # 一个解 X = [] # 一组解 # 冲突检测：无 def conflict(k): global n, x, X return False # 无冲突 # 一个例子 # 冲突检测：元素奇偶相间的排列 def conflict2(k): global n, x, X if k==0: # 第一个元素，肯定无冲突 return False if x[k-1] % 2 == x[k] % 2: # 只比较 x[k] 与 x[k-1] 奇偶是否相同 return True return False # 无冲突 # 排列树递归模板 def backkrak(k): # 到达第k个位置 global n, x, X if k >= n: # 超出最尾的位置 print(x) #X.append(x[:]) # 注意x[:] else: for i in range(k, n): # 遍历后面第 k~n-1 的位置 x[k], x[i] = x[i], x[k] if not conflict2(k): # 剪枝 backkrak(k+1) x[i], x[k] = x[k], x[i] # 回溯 # 测试 backkrak(0) b.排列树模板非递归版
分治法所能解决的问题一般具有以下几个特征： 1) 该问题的规模缩小到一定的程度就可以容易地解决 2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。 3) 利用该问题分解出的子问题的解可以合并为该问题的解； 4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。 第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加； 第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；、 第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。 第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。 题目1. 给定一个顺序表，编写一个求出其最大值的分治算法。 # 基本子算法（子问题规模小于等于 2 时） def get_max(max_list): return max(max_list) # 这里偷个懒！ # 分治法 版本一 def solve(init_list): n = len(init_list) if n <= 2: # 若问题规模小于等于 2，最终解决 return get_max(init_list) # 分解（子问题规模为 2，最后一个可能为 1） temp_list=(init_list[i:i+2] for i in range(0, n, 2)) # 分治，合并 max_list = list(map(get_max, temp_list)) # 递归（树） solve(max_list) # 分治法 版本二 def solve2(init_list): n = len(init_list) if n <= 2: # 若问题规模小于等于 2，解决 return get_max(init_list) # 分解（子问题规模为 n/2） left_list, right_list = init_list[:n//2], init_list[n//2:] # 递归（树），分治 left_max, right_max = solve2(left_list), solve2(right_list) # 合并 return get_max([left_max, right_max]) if __name__ == "__main__": # 测试数据 test_list = [12,2,23,45,67,3,2,4,45,63,24,23] # 求最大值 print(solve(test_list)) # 67 print(solve2(test_list)) # 67 题目2. 给定一个顺序表，判断某个元素是否在其中。 # 子问题算法（子问题规模为 1） def is_in_list(init_list, el): return [False, True][init_list[0] == el] # 分治法 def solve(init_list, el): n = len(init_list) if n == 1: # 若问题规模等于 1，直接解决 return is_in_list(init_list, el) # 分解（子问题规模为 n/2） left_list, right_list = init_list[:n//2], init_list[n//2:] # 递归（树），分治，合并 res = solve(left_list, el) or solve(right_list, el) return res if __name__ == "__main__": # 测试数据 test_list = [12,2,23,45,67,3,2,4,45,63,24,23] # 查找 print(solve2(test_list, 45)) # True print(solve2(test_list, 5)) # False 题目3. 找出一组序列中的第 k 小的元素，要求线性时间 # 划分（基于主元 pivot），注意：非就地划分 def partition(seq): pi = seq[0] # 挑选主元 lo = [x for x in seq[1:] if x <= pi] # 所有小的元素 hi = [x for x in seq[1:] if x > pi] # 所有大的元素 return lo, pi, hi # 查找第 k 小的元素 def select(seq, k): # 分解 lo, pi, hi = partition(seq) m = len(lo) if m == k: return pi # 解决！ elif m < k: return select(hi, k-m-1) # 递归（树），分治 else: return select(lo, k) # 递归（树），分治 if __name__ == '__main__': seq = [3, 4, 1, 6, 3, 7, 9, 13, 93, 0, 100, 1, 2, 2, 3, 3, 2] print(select(seq, 3)) #2 print(select(seq, 5)) #2 题目4. 快速排序 # 划分（基于主元 pivot），注意：非就地划分 def partition(seq): pi = seq[0] # 挑选主元 lo = [x for x in seq[1:] if x <= pi] # 所有小的元素 hi = [x for x in seq[1:] if x > pi] # 所有大的元素 return lo, pi, hi # 快速排序 def quicksort(seq): # 若问题规模小于等于1，解决 if len(seq) <= 1: return seq # 分解 lo, pi, hi = partition(seq) # 递归（树），分治，合并 return quicksort(lo) + [pi] + quicksort(hi) seq = [7, 5, 0, 6, 3, 4, 1, 9, 8, 2] print(quicksort(seq)) #[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 题目5. 合并排序（二分排序） # 合并排序 def mergesort(seq): # 分解（基于中点） mid = len(seq) // 2 left_seq, right_seq = seq[:mid], seq[mid:] # 递归（树），分治 if len(left_seq) > 1: left_seq = mergesort(left_seq) if len(right_seq) > 1: right_seq = mergesort(right_seq) # 合并 res = [] while left_seq and right_seq: # 只要两者皆非空 if left_seq[-1] >= right_seq[-1]: # 两者尾部较大者，弹出 res.append(left_seq.pop()) else: res.append(right_seq.pop()) res.reverse() # 倒序 return (left_seq or right_seq) + res # 前面加上剩下的非空的seq seq = [7, 5, 0, 6, 3, 4, 1, 9, 8, 2] print(mergesort(seq)) #[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 题目6. 汉诺塔 # 汉诺塔 def move(n, a, buffer, c): if n == 1: print(a,"->",c) #return else: # 递归（线性） move(n-1, a, c, buffer) move(1, a, buffer, c) # 或者：print(a,"->",c) move(n-1, buffer, a, c) move(3, "a", "b", "c") 问题7. 爬楼梯 假设你正在爬楼梯，需要n步你才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法爬到楼顶部？ # 爬楼梯 def climb(n=7): if n <= 2: return n return climb(n-1) + climb(n-2) # 等价于斐波那契数列！ print(climb(5)) # 8 print(climb(7)) # 21 问题8. 给定平面上n个点，找其中的一对点，使得在n个点的所有点对中，该点对的距离最小。（最近点对问题） from math import sqrt # 蛮力法 def solve(points): n = len(points) min_d = float("inf") # 最小距离：无穷大 min_ps = None # 最近点对 for i in range(n-1): for j in range(i+1, n): d = sqrt((points[i][0] - points[j][0])**2 + (points[i][1] - points[j][1])**2) # 两点距离 if d < min_d: min_d = d # 修改最小距离 min_ps = [points[i], points[j]] # 保存最近点对 return min_ps # 最接近点对（报错！） def nearest_dot(seq): # 注意：seq事先已对x坐标排序 n = len(seq) if n <= 2: return seq # 若问题规模等于 2，直接解决 # 分解（子问题规模n/2） left, right = seq[0:n//2], seq[n//2:] print(left, right) mid_x = (left[-1][0] + right[0][0])/2.0 # 递归，分治 lmin = (left, nearest_dot(left))[len(left) > 2] # 左侧最近点对 rmin = (right, nearest_dot(right))[len(right) > 2] # 右侧最近点对 # 合并 dis_l = (float("inf"), get_distance(lmin))[len(lmin) > 1] dis_r = (float("inf"), get_distance(rmin))[len(rmin) > 1] d = min(dis_l, dis_r) # 最近点对距离 # 处理中线附近的带状区域（近似蛮力） left = list(filter(lambda p:mid_x - p[0] <= d, left)) #中间线左侧的距离<=d的点 right = list(filter(lambda p:p[0] - mid_x <= d, right)) #中间线右侧的距离<=d的点 mid_min = [] for p in left: for q in right: if abs(p[0]-q[0])<=d and abs(p[1]-q[1]) <= d: #如果右侧部分点在p点的(d,2d)之间 td = get_distance((p,q)) if td <= d: mid_min = [p,q] # 记录p，q点对 d = td # 修改最小距离 if mid_min: return mid_min elif dis_l>dis_r: return rmin else: return lmin # 两点距离 def get_distance(min): return sqrt((min[0][0]-min[1][0])**2 + (min[0][1]-min[1][1])**2) def divide_conquer(seq): seq.sort(key=lambda x:x[0]) res = nearest_dot(seq) return res # 测试 seq=[(0,1),(3,2),(4,3),(5,1),(1,2),(2,1),(6,2),(7,2),(8,3),(4,5),(9,0),(6,4)] print(solve(seq)) # [(6, 2), (7, 2)] #print(divide_conquer(seq)) # [(6, 2), (7, 2)] 问题8. 从数组 seq 中找出和为 s 的数值组合，有多少种可能 ''' 求一个算法：N个数，用其中M个任意组合相加等于一个已知数X。得出这M个数是哪些数。 比如： seq = [1, 2, 3, 4, 5, 6, 7, 8, 9] s = 14 # 和 全部可能的数字组合有： 5+9, 6+8 1+4+9, 1+5+8, 1+6+7, 2+3+9, 2+4+8, 2+5+7, 3+4+7, 3+5+6 1+2+5+6, 1+3+4+6, 1+2+4+7, 1+2+3+8, 2+3+4+5 共计15种 http://club.excelhome.net/thread-443533-1-1.html ''' # 版本一（纯计数） def find(seq, s): n = len(seq) if n==1: return [0, 1][seq[0]==s] if seq[0]==s: return 1 + find(seq[1:], s) else: return find(seq[1:], s-seq[0]) + find(seq[1:], s) # 测试 seq = [1, 2, 3, 4, 5, 6, 7, 8, 9] s = 14 # 和 print(find(seq, s)) # 15 seq = [11,23,6,31,8,9,15,20,24,14] s = 40 # 和 print(find(seq, s)) #8 # 版本二 （打印） def find2(seq, s, tmp=''): if len(seq)==0: # 终止条件 return if seq[0] == s: # 找到一种，则 print(tmp + str(seq[0])) # 打印 find2(seq[1:], s, tmp) # 尾递归 ---不含 seq[0] 的情况 find2(seq[1:], s-seq[0], str(seq[0]) + '+' + tmp) # 尾递归 ---含 seq[0] 的情况 # 测试 seq = [1, 2, 3, 4, 5, 6, 7, 8, 9] s = 14 # 和 find2(seq, s) print() seq = [11,23,6,31,8,9,15,20,24,14] s = 40 # 和 find2(seq, s)
# 例1. 按照元素出现的次数来排序 seq = [2,4,3,1,2,2,3] # 按次数排序 seq2 = sorted(seq, key=lambda x:seq.count(x)) print(seq2) # [4, 1, 3, 3, 2, 2, 2] # 改进：第一优先按次数，第二优先按值 seq3 = sorted(seq, key=lambda x:(seq.count(x), x)) print(seq3) # [1, 4, 3, 3, 2, 2, 2] ''' 原理： 先比较元组的第一个值，值小的在前。（注意：False < True） 如果相等就比较元组的下一个值，以此类推。 ''' #例2.这是一个字符串排序，排序规则：小写<大写<奇数<偶数 s = 'asdf234GDSdsf23' s2 = "".join(sorted(s, key=lambda x: (x.isdigit(),x.isdigit() and int(x) % 2 == 0,x.isupper(),x))) print(s2) # addffssDGS33224 #例3. 一道面试题： list1 = [7, -8, 5, 4, 0, -2, -5] #要求1.正数在前负数在后 2.正数从小到大 3.负数从大到小 list2 = sorted(list1,key=lambda x:(x<0, abs(x))) print(list2) # [0,4,5,7,-2,-5,-8]
''' 两个乒乓球队进行比赛， 各出三人。 甲队为 a,b,c 三人， 乙队为 x,y,z 三人。 已 抽签决定比赛名单。 有人向队员打听比赛的名单。 a 说他不和 x 比， c 说他不和 x,z 比， 请 编程序找出三队赛手的名单。求教 会Python的大神 https://zhidao.baidu.com/question/1433668874819082859 ''' import itertools team1_order = 'abc' # 不妨定死甲队出场顺序 for team2_order in itertools.permutations('xyz'): # 乙队出场顺序有 6 种可能（全排列） game_order = list(zip(team1_order, team2_order)) # 捉对厮杀，得到比赛方案！ if game_order[0][1] != 'x' and game_order[2][1] not in 'xz': # 符合要求，则打印方案如下 for player1, player2 in game_order: print("{}----{}".format(player1, player2)) print() 效果图
频率 所属类型 模式名称 模式 简单定义 5 创建型 Singleton 单件 保证一个类只有一个实例，并提供一个访问它的全局访问点。 4 创建型 Abstract Factory 抽象工厂 提供一个创建一系列相关或相互依赖对象的接口，而无须指定它们的具体类。 4 创建型 Factory Method 工厂方法 定义一个用于创建对象的接口，让子类决定实例化哪一个类，Factory Method使一个类的实例化延迟到了子类。 3 创建型 Builder 生成器 将一个复杂对象的构建与他的表示相分离，使得同样的构建过程可以创建不同的表示。 2 创建型 Prototype 原型 用原型实例指定创建对象的种类，并且通过拷贝这些原型来创建新的对象。 5 结构型 Composite 组合 将对象组合成树形结构以表示部分整体的关系，Composite使得用户对单个对象和组合对象的使用具有一致性。 5 结构型 FAÇADE 外观 为子系统中的一组接口提供一致的界面，facade提供了一高层接口，这个接口使得子系统更容易使用。 5 结构型 Proxy 代理 为其他对象提供一种代理以控制对这个对象的访问 4 结构型 Adapter 适配器 将一类的接口转换成客户希望的另外一个接口，Adapter模式使得原本由于接口不兼容而不能一起工作那些类可以一起工作。 4 结构型 Decorator 装饰 动态地给一个对象增加一些额外的职责，就增加的功能来说，Decorator模式相比生成子类更加灵活。 3 结构型 Bridge 桥接 将抽象部分与它的实现部分相分离，使他们可以独立的变化。 2 结构型 Flyweight 享元 享元模式以共享的方式高效的支持大量的细粒度对象。享元模式能做到共享的关键是区分内蕴状态和外蕴状态。内蕴状态存储在享元内部，不会随环境的改变而有所不同。外蕴状态是随环境的改变而改变的。 5 行为型 Iterator 迭代器 提供一个方法顺序访问一个聚合对象的各个元素，而又不需要暴露该对象的内部表示。 5 行为型 Observer 观察者 定义对象间一对多的依赖关系，当一个对象的状态发生改变时，所有依赖于它的对象都得到通知自动更新。 5 行为型 Template Method 模板方法 定义一个操作中的算法的骨架，而将一些步骤延迟到子类中，Template Method使得子类可以不改变一个算法的结构即可以重定义该算法得某些特定步骤。 4 行为型 Command 命令 将一个请求封装为一个对象，从而使你可以用不同的请求对客户进行参数化，对请求排队和记录请求日志，以及支持可撤销的操作。 4 行为型 State 状态 允许对象在其内部状态改变时改变他的行为。对象看起来似乎改变了他的类。 4 行为型 Strategy 策略 义一系列的算法，把他们一个个封装起来，并使他们可以互相替换，本模式使得算法可以独立于使用它们的客户。 3 行为型 Chain of Responsibility 职责链 使多个对象都有机会处理请求，从而避免请求的送发者和接收者之间的耦合关系 2 行为型 Mediator 中介者 用一个中介对象封装一些列的对象交互。 2 行为型 Visitor 访问者 表示一个作用于某对象结构中的各元素的操作，它使你可以在不改变各元素类的前提下定义作用于这个元素的新操作。 1 行为型 Interpreter 解释器 给定一个语言，定义他的文法的一个表示，并定义一个解释器，这个解释器使用该表示来解释语言中的句子。 1 行为型 Memento 备忘录 在不破坏对象的前提下，捕获一个对象的内部状态，并在该对象之外保存这个状态。
python3 的 round 函数感觉很别扭，其运算结果与习惯不相符。特记录下来： 代码 ''' python 3的 round 函数 是“四舍六入五成双”的 https://www.zhihu.com/question/20128906 ''' print('python 3的 round 函数：四舍六入五成双') print('\nround(-3.5) = ', round(-3.5)) print('\nround(-2.5) = ', round(-2.5)) print('round(-1.5) = ', round(-1.5)) print('\nround(-0.5) = ', round(-0.5)) print('round(0.5) = ', round(0.5)) print('\nround(1.5) = ', round(1.5)) print('round(2.5) = ', round(2.5)) print('\nround(3.5) = ', round(3.5)) print('round(4.5) = ', round(4.5)) print('\nround(5.5) = ', round(5.5)) print('round(6.5) = ', round(6.5)) print('\nround(6.5000000000000001) = ', round(6.5000000000000001)) # 小数点后16位 print('round(6.500000000000001) = ', round(6.500000000000001)) # 小数点后15位 效果图
如果不考虑作图，这里的两个例子可以改写成下面的样子： 求圆周率 import random ''' 蒙特卡罗模拟 投点法计算圆周率 ''' # 投点游戏 def play_game(): # 圆 r = 1.0 # 半径 a, b = (0., 0.) # 圆心 # 正方形区域边界 x_min, x_max = a-r, a+r y_min, y_max = b-r, b+r # 在 正方形 区域内随机投点 x = random.uniform(x_min, x_max) # 均匀分布 y = random.uniform(y_min, y_max) # 计算点到圆心距离 d = (x-a)**2 + (y-b)**2 # 根据落在圆内与否，返回1,0（为方便计数） return [0, 1][d<r] # 游戏次数 n = 100000 # 蒙特卡罗方法，模拟 n 次游戏 pi = 4.0 * sum((play_game() for _ in range(n))) / n # 4 倍频率近似于圆周率 print('pi: ', pi) 求定积分 import random ''' 蒙特卡罗模拟 投点法计算函数 y=x^2在[0,1]内的定积分 ''' # 函数 y=x^2 def f(x): return x**2 # 投点游戏 def play_game(): # 矩形区域边界 x_min, x_max = 0, 1 y_min, y_max = 0, 1 # 在 矩形 区域内随机投点 x = random.uniform(x_min, x_max) # 均匀分布 y = random.uniform(y_min, y_max) # 根据点落在函数 y=x^2图像下方与否，返回1,0（为方便计数） return [0, 1][y<f(x)] # 游戏次数 n = 100000 # 蒙特卡罗方法，模拟 n 次游戏 integral = sum((play_game() for _ in range(n))) / n # 频率近似于定积分 print('integral: ', integral)
本文使用蒙特卡罗方法验证蒙提霍尔游戏的结论。 以下代码，本人原创！ 完整代码 import random # 蒙提霍尔游戏 def play_game(strategy='nonchange'): # 门牌编号 doors = [0,1,2] # 门后的奖品 gifts = ['goat', 'goat', 'car'] random.shuffle(gifts) # 观众挑选一扇门（编号） viewer_choice = random.choice(doors) # 主持人从剩下的两扇门中，打开门后是是山羊的某一扇门（编号） host_open = random.choice(list(filter(lambda x:gifts[x]=='goat' and x!=viewer_choice, doors))) # 顺便，也标记剩下的一扇门（编号） viewer_lift = list(filter(lambda x:x!=viewer_choice and x!=host_open, doors))[0] # 观众根据策略获得的奖品 viewer_gift = [gifts[viewer_choice], gifts[viewer_lift]][strategy=='change'] # 根据策略成功与否，返回 1、0 （为方便计数） return [0, 1][viewer_gift=='car'] # 游戏次数 n = 10000 # 蒙特卡罗方法，模拟 n 次游戏 # 策略一：不改变选择 p = sum((play_game('nonchange') for _ in range(n))) / n # 频率 ≈ 概率 print('nonchange:', p) # 蒙特卡罗方法，模拟 n 次游戏 # 策略二：改变选择 p = sum((play_game('change') for _ in range(n))) / n # 频率 ≈ 概率 print('change:', p) 效果图
蒙特卡罗（Monte Carlo）方法的精髓：用统计结果去计算频率，从而得到真实值的近似值。 一、求圆周率的近似值，采用 投点法 import numpy as np import matplotlib.pyplot as plt from matplotlib.patches import Circle # 投点次数 n = 10000 # 圆的信息 r = 1.0 # 半径 a, b = (0., 0.) # 圆心 # 正方形区域边界 x_min, x_max = a-r, a+r y_min, y_max = b-r, b+r # 在正方形区域内随机投点 x = np.random.uniform(x_min, x_max, n) # 均匀分布 y = np.random.uniform(y_min, y_max, n) # 计算 点到圆心的距离 d = np.sqrt((x-a)**2 + (y-b)**2) # 统计 落在圆内的点的数目 res = sum(np.where(d < r, 1, 0)) # 计算 pi 的近似值（Monte Carlo方法的精髓：用统计值去近似真实值） pi = 4 * res / n print('pi: ', pi) # 画个图看看 fig = plt.figure() axes = fig.add_subplot(111) axes.plot(x, y,'ro',markersize = 1) plt.axis('equal') # 防止图像变形 circle = Circle(xy=(a,b), radius=r, alpha=0.5) axes.add_patch(circle) plt.show() 效果图 二、求定积分（definite integral）的近似值，采用 投点法 import numpy as np import matplotlib.pyplot as plt '''蒙特卡罗方法求函数 y=x^2 在[0,1]内的定积分（值）''' def f(x): return x**2 # 投点次数 n = 10000 # 矩形区域边界 x_min, x_max = 0.0, 1.0 y_min, y_max = 0.0, 1.0 # 在矩形区域内随机投点 x = np.random.uniform(x_min, x_max, n) # 均匀分布 y = np.random.uniform(y_min, y_max, n) # 统计 落在函数 y=x^2图像下方的点的数目 res = sum(np.where(y < f(x), 1, 0)) # 计算 定积分的近似值（Monte Carlo方法的精髓：用统计值去近似真实值） integral = res / n print('integral: ', integral) # 画个图看看 fig = plt.figure() axes = fig.add_subplot(111) axes.plot(x, y,'ro',markersize = 1) plt.axis('equal') # 防止图像变形 axes.plot(np.linspace(x_min, x_max, 10), f(np.linspace(x_min, x_max, 10)), 'b-') # 函数图像 #plt.xlim(x_min, x_max) plt.show() 效果图
鼠标事件 <ButtonPress-n> <Button-n> <n> 鼠标按钮n被按下，n为1左键，2中键，3右键 <ButtonRelease-n> 鼠标按钮n被松开 <Double-Button-n> 鼠标按钮n被双击 <Triple-Button-n> 鼠标按钮n被三击 <Motion> 鼠标被按下，同时，鼠标发生移动 <Bn-Motion> 鼠标按钮n被按下，同时，鼠标发生移动 <Enter> 鼠标进入 <Leave> 鼠标离开 <MouseWheel> 鼠标滚轮滚动 键盘事件 <Any-KeyPress> <KeyPress> <Key> 任意键按下 <KeyRelease> 任意键松开 <KeyPress-key> <Key-key> <key> 特定键按下 <KeyRelease-key> 特定键松开 <Control-Shift-Alt-KeyPress-key> <Control-Shift-Alt-key> 组合键按下（Alt，Shift，Control任选一到三个） 对于大多数的单字符按键，你还可以忽略“<>”符号。但是空格键和尖括号键不能这样做（正确的表示分别为 特殊键的键名 <Return> <Escape> <space> <Tab> <Up> <Right> <Left> <Down> <Shitf_L> <Shift_R> <Control_L> <Control_R> <Alt_L> <Alt_R> <F1> ... <F12> 根据事件，查看按键 event.char 可见字符，甚至中文 event.keysym 用字符串命名了按键 event.keycode 用按键码命名了按键，但是它不能反映事件前缀：Alt、Control、Shift、Lock，并且它不区分大小写写按键，即输入a和A是相同的键码。 event.keysym_num 用数字代码命名了按键 event.Key 描述了键盘上的按键名，方便一一对应
我的理解： 假设有一个文件夹 app 若 app 下有app/__init__.py文件，则此 app 被视作一个 package，而 app 下的其他文件/文件夹被视作 module 我们知道，package 的意义是作为一个整体，提供某些功能。因此，package 内部的各个 module 之间使用相对路径导入。 比如：在 module1.py 内，这样相对导入：from .module2 import myClass2 注意，问题来了，此时不能之间运行 module.py 这个文件，否则会报错：SystemError: Parent module '' not loaded, cannot perform relative import 我们只能在package外，也就是文件夹 app 外的 run.py文件中导入：from app.module2 import myClass2
近日，决定用 python 实现插件架构，于是上 stackoverflow 逛了一下，在这里发现一段代码，非常喜欢。 提醒各位大侠注意，我对这段代码作了一点小小的改动：原 PLUGINS 是 list 对象，改动后 PLUGINS 是 dict 对象。 代码先贴出来，以飨观众： ''' 插件架构 ''' # 平台 class TextProcessor(object): PLUGINS = {} def process(self, text, plugins=()): if plugins is (): for plugin_name in self.PLUGINS.keys(): text = self.PLUGINS[plugin_name]().process(text) else: for plugin_name in plugins: text = self.PLUGINS[plugin_name]().process(text) return text @classmethod def plugin_register(cls, plugin_name): def wrapper(plugin): cls.PLUGINS.update({plugin_name:plugin}) return plugin return wrapper # 插件 @TextProcessor.plugin_register('plugin1') class CleanMarkdownBolds(object): def process(self, text): return text.replace('**', '') # 测试 processor = TextProcessor() print(processor.PLUGINS) # {’plugin1': <class '__main__.CleanMarkdownBolds'>} processed = processor.process(text="**foo bar**", plugins=('plugin1', )) processed = processor.process(text="**foo bar**") 这段代码运行良好！但是它是单文件，不适合实际使用。 在实际项目中，上面的三个注释下面的部分一定是拆开的，其中插件一般都约定俗成地放到 plugins 子目录下。 为了实现这个想法，走了很多弯路，花了两天时间！这期间查阅了__metaclass__原理, __subclass__()函数, package的组织方式等等。最后真的灵光一闪，成功实现！ 项目结构： ├─ myproject ├─ run.py ├─ app ├─ __init__.py ├─ main.py ├─ platform.py ├─ plugins ├─ __init__.py ├─ plugin1.py ├─ plugin2.py 完整代码 # mpyproject/app/platform.py class TextProcessor(object): PLUGINS = {} def process(self, text, plugins=()): if plugins is (): for plugin_name in self.PLUGINS.keys(): text = self.PLUGINS[plugin_name]().process(text) else: for plugin_name in plugins: text = self.PLUGINS[plugin_name]().process(text) return text @classmethod def plugin_register(cls, plugin_name): def wrapper(plugin): cls.PLUGINS.update({plugin_name:plugin}) return plugin return wrapper # mpyproject/app/plugins/plugin1.py from ..platform import TextProcessor @TextProcessor.plugin_register('plugin1') class CleanMarkdownBolds(object): def process(self, text): return text.replace('**', '') # mpyproject/app/plugins/plugin2.py # 第二个插件！ from ..platform import TextProcessor @TextProcessor.plugin_register('plugin2') class CleanMarkdownItalic(object): def process(self, text): return text.replace('--', '') # mpyproject/app/main.py from .platform import TextProcessor def test(): processor = TextProcessor() print(processor.PLUGINS) # {’plugin1': <class '__main__.CleanMarkdownBolds'>} processed = processor.process(text="**foo bar**", plugins=('plugin1', )) processed = processor.process(text="--foo bar--") # mpyproject/app/__init__.py from .plugins import * # mpyproject/app/plugins/__init__.py __all__ = ['plugin1', 'plugin2'] # mpyproject/run.py from app.main import test test() 说明： 优雅地实现插件架构，app/__init__.py 与 app/plugins/__init__.py 两个文件起了相互呼应的作用 在 app 目录下，除了 app/__init__.py，不需要在别的任何地方显式地导入插件：from .plugins import * 或 from .plugins import plugin1 若想添加插件 plugin3.py，可将其复制到 plugins 目录下，然后修改 app/plugins/__init__.py 文件为 __all__ = ['plugin1', 'plugin2', 'plugin3'] 插件是冷插拔的 插件不是懒加载 优化方向 热插拔 懒加载
有些时候，我们需要使用弹出窗口，对程序的运行参数进行设置。有两种选择 一、标准窗口 如果只对一个参数进行设置（或者说从弹出窗口取回一个值），那么可以使用simpledialog，导入方法： from tkinter.simpledialog import askstring, askinteger, askfloat 完整例子 import tkinter as tk from tkinter.simpledialog import askstring, askinteger, askfloat # 接收一个整数 def print_integer(): res = askinteger("Spam", "Egg count", initialvalue=12*12) print(res) # 接收一个浮点数 def print_float(): res = askfloat("Spam", "Egg weight\n(in tons)", minvalue=1, maxvalue=100) print(res) # 接收一个字符串 def print_string(): res = askstring("Spam", "Egg label") print(res) root = tk.Tk() tk.Button(root, text='取一个字符串', command=print_string).pack() tk.Button(root, text='取一个整数', command=print_integer).pack() tk.Button(root, text='取一个浮点数', command=print_float).pack() root.mainloop() 二、自定义窗口 如果要设置的参数个数超过两个，那么tkinter提供的标准窗口就处理不了了。 这就需要自定义一个窗口，那么问题来了：怎样将自定义窗口中的数据传回主窗口？ 百度查询，不外乎两种方法：全局变量（global）、对象变量（[]、{}等），都不是我想要的。 然后，去 stackoverflow 逛了一下，综合了个问题的答案，得到两个本人比较满意的方案。 一种是松耦合，另一种是紧耦合 1）松耦合 说明： 主窗类，继承了 tk.Tk 弹窗类，继承了 tk.Toplevel 要点： 弹窗，将多个数据，打包，放入一个名为 username 的私有 list 对象，销毁弹窗 主窗，待弹窗运行后，通过wait_window方法，取得弹窗的名为 username 私有变量 完整代码： import tkinter as tk '''松耦合''' # 弹窗 class MyDialog(tk.Toplevel): def __init__(self): super().__init__() self.title('设置用户信息') # 弹窗界面 self.setup_UI() def setup_UI(self): # 第一行（两列） row1 = tk.Frame(self) row1.pack(fill="x") tk.Label(row1, text='姓名：', width=8).pack(side=tk.LEFT) self.name = tk.StringVar() tk.Entry(row1, textvariable=self.name, width=20).pack(side=tk.LEFT) # 第二行 row2 = tk.Frame(self) row2.pack(fill="x", ipadx=1, ipady=1) tk.Label(row2, text='年龄：', width=8).pack(side=tk.LEFT) self.age = tk.IntVar() tk.Entry(row2, textvariable=self.age, width=20).pack(side=tk.LEFT) # 第三行 row3 = tk.Frame(self) row3.pack(fill="x") tk.Button(row3, text="取消", command=self.cancel).pack(side=tk.RIGHT) tk.Button(row3, text="确定", command=self.ok).pack(side=tk.RIGHT) def ok(self): self.userinfo = [self.name.get(), self.age.get()] # 设置数据 self.destroy() # 销毁窗口 def cancel(self): self.userinfo = None # 空！ self.destroy() # 主窗 class MyApp(tk.Tk): def __init__(self): super().__init__() #self.pack() # 若继承 tk.Frame ，此句必须有！ self.title('用户信息') # 程序参数/数据 self.name = '张三' self.age = 30 # 程序界面 self.setupUI() def setupUI(self): # 第一行（两列） row1 = tk.Frame(self) row1.pack(fill="x") tk.Label(row1, text='姓名：', width=8).pack(side=tk.LEFT) self.l1 = tk.Label(row1, text=self.name, width=20) self.l1.pack(side=tk.LEFT) # 第二行 row2 = tk.Frame(self) row2.pack(fill="x") tk.Label(row2, text='年龄：', width=8).pack(side=tk.LEFT) self.l2 = tk.Label(row2, text=self.age, width=20) self.l2.pack(side=tk.LEFT) # 第三行 row3 = tk.Frame(self) row3.pack(fill="x") tk.Button(row3, text="设置", command=self.setup_config).pack(side=tk.RIGHT) # 设置参数 def setup_config(self): # 接收弹窗的数据 res = self.ask_userinfo() #print(res) if res is None: return # 更改参数 self.name, self.age = res # 更新界面 self.l1.config(text=self.name) self.l2.config(text=self.age) # 弹窗 def ask_userinfo(self): inputDialog = MyDialog() self.wait_window(inputDialog) # 这一句很重要！！！ return inputDialog.userinfo if __name__ == '__main__': app = MyApp() app.mainloop() 2）紧耦合 说明： 主窗类，继承了 tk.Tk 弹窗类，继承了 tk.Toplevel 要点： 弹窗，显式地保存父窗口，显式地修改父窗口数据，显式地更新父窗口部件，最后销毁弹窗 主窗，待弹窗运行后，通过wait_window方法，返回 None 完整代码： import tkinter as tk '''紧耦合''' # 弹窗 class PopupDialog(tk.Toplevel): def __init__(self, parent): super().__init__() self.title('设置用户信息') self.parent = parent # 显式地保留父窗口 # 第一行（两列） row1 = tk.Frame(self) row1.pack(fill="x") tk.Label(row1, text='姓名：', width=8).pack(side=tk.LEFT) self.name = tk.StringVar() tk.Entry(row1, textvariable=self.name, width=20).pack(side=tk.LEFT) # 第二行 row2 = tk.Frame(self) row2.pack(fill="x", ipadx=1, ipady=1) tk.Label(row2, text='年龄：', width=8).pack(side=tk.LEFT) self.age = tk.IntVar() tk.Entry(row2, textvariable=self.age, width=20).pack(side=tk.LEFT) # 第三行 row3 = tk.Frame(self) row3.pack(fill="x") tk.Button(row3, text="取消", command=self.cancel).pack(side=tk.RIGHT) tk.Button(row3, text="确定", command=self.ok).pack(side=tk.RIGHT) def ok(self): # 显式地更改父窗口参数 self.parent.name = self.name.get() self.parent.age = self.age.get() # 显式地更新父窗口界面 self.parent.l1.config(text=self.parent.name) self.parent.l2.config(text=self.parent.age) self.destroy() # 销毁窗口 def cancel(self): self.destroy() # 主窗 class MyApp(tk.Tk): def __init__(self): super().__init__() # self.pack() # 若继承 tk.Frame，此句必须有！！！ self.title('用户信息') # 程序参数 self.name = '张三' self.age = 30 # 程序界面 self.setupUI() def setupUI(self): # 第一行（两列） row1 = tk.Frame(self) row1.pack(fill="x") tk.Label(row1, text='姓名：', width=8).pack(side=tk.LEFT) self.l1 = tk.Label(row1, text=self.name, width=20) self.l1.pack(side=tk.LEFT) # 第二行 row2 = tk.Frame(self) row2.pack(fill="x") tk.Label(row2, text='年龄：', width=8).pack(side=tk.LEFT) self.l2 = tk.Label(row2, text=self.age, width=20) self.l2.pack(side=tk.LEFT) # 第三行 row3 = tk.Frame(self) row3.pack(fill="x") tk.Button(row3, text="设置", command=self.setup_config).pack(side=tk.RIGHT) # 设置参数 def setup_config(self): pw = PopupDialog(self) self.wait_window(pw) # 这一句很重要！！！ return if __name__ == '__main__': app = MyApp() app.mainloop() 效果图
实现了后端与前端分离，后端提供 RESTful api。 后端 flask 与前端 vue 的数据传输都是 json。 本文使用 vue.js 2.0 对前一个例子：flask, SQLAlchemy, sqlite3 实现 RESTful API 的 todo list进行改写 两个文件 from flask import Flask, jsonify, render_template from flask_sqlalchemy import SQLAlchemy app = Flask(__name__) app.config['SQLALCHEMY_DATABASE_URI'] = 'sqlite://' app.config['SQLALCHEMY_TRACK_MODIFICATIONS'] = True db = SQLAlchemy(app) # 定义ORM class Todo(db.Model): id = db.Column(db.Integer, primary_key=True) title = db.Column(db.String(80), unique=True) description = db.Column(db.String(120), unique=True) done = db.Column(db.Boolean) def __init__(self, title, description, done): self.title = title self.description = description self.done = done def __repr__(self): return '<Todo %r>' % self.title # 创建表格、插入数据 @app.before_first_request def create_db(): # Recreate database each time for demo #db.drop_all() db.create_all() tasks = [Todo('Buy groceries', 'Milk, Cheese, Pizza, Fruit, Tylenol', False), Todo('Learn Python', 'Need to find a good Python tutorial on the web', False), Todo('Mow the lawn', 'Find out some tools', False)] db.session.add_all(tasks) db.session.commit() # ================================== # 下面是RESTful api # ================================== @app.route('/') def index(): return render_template('formdata_vue.html') # ================================== # 下面是RESTful api # ================================== # 辅助函数 from flask import url_for def replace_id_to_uri(task): return dict(uri = url_for('get_task', task_id=task.id, _external=True), title = task.title, description = task.description, done = task.done) # 查询全部 @app.route('/todo/api/v1.0/tasks/', methods=['GET']) def get_tasks(): tasks = Todo.query.all() return jsonify({'tasks': list(map(replace_id_to_uri, tasks))}) # 查询一个 from flask import abort @app.route('/todo/api/v1.0/tasks/<int:task_id>', methods=['GET']) def get_task(task_id): task = Todo.query.filter_by(id=task_id).first() if task is None: abort(404) return jsonify({'task': replace_id_to_uri(task)}) # 添加 from flask import request @app.route('/todo/api/v1.0/tasks/', methods=['POST']) def create_task(): # 没有数据，或者数据缺少 title 项，返回 400，表示请求无效 if not request.json or not 'title' in request.json: abort(400) task = Todo(request.json['title'], request.json.get('description', ""), False) db.session.add(task) db.session.commit() return jsonify({'task': replace_id_to_uri(task)}), 201 # 更新 @app.route('/todo/api/v1.0/tasks/<int:task_id>', methods=['PUT']) def update_task(task_id): task = Todo.query.filter_by(id=task_id).first() if task is None: abort(404) if not request.json: abort(400) if 'title' in request.json and type(request.json['title']) != unicode: abort(400) if 'description' in request.json and type(request.json['description']) is not unicode: abort(400) if 'done' in request.json and type(request.json['done']) is not bool: abort(400) task['title'] = request.json.get('title', task['title']) task['description'] = request.json.get('description', task['description']) task['done'] = request.json.get('done', task['done']) #db.session.update(task) db.session.commit() return jsonify({'task': replace_id_to_uri(task)}) # 删除 @app.route('/todo/api/v1.0/tasks/<int:task_id>', methods=['DELETE']) def delete_task(task_id): task = Todo.query.filter_by(id=task_id).first() if task is None: abort(404) db.session.delete(task) db.session.commit() return jsonify({'result': True}) # 定制404出错页面 @app.errorhandler(404) def not_found(error): return jsonify({'error': 'Not found'}), 404 if __name__ == '__main__': app.run(debug=True) 为了避免jinja2 与 vue 同时使用 “{{ }}”而发生冲突，vue 的数据绑定使用 v-text <meta charset="utf-8"/> <script src="{{ url_for('static', filename='js/vue.min.js') }}"></script> <!-- <script src="{{ url_for('static', filename='js/fetch.js') }}"></script> --> <div id="app"> <form v-on:submit="ajax"> <div class="form-group"> <input type="text" v-model="title" placeholder="任务标题" required="required"> </div> <div class="form-group"> <input type="texteara" v-model="description" placeholder="任务描述" required="required"> </div> <input type="submit" class="btn btn-default" value="添加任务"> </form> <!-- 任务列表 --> <ol> <li v-for="task in tasks"> <span v-text="task.title"></span> -- <span v-text="task.description"></span> -- <span v-text="task.done"></span> </li> </ol> </div> <script> var vm = new Vue({ el: '#app', data: { title: '', description: '', tasks: [ // { // uri: 'todo/api/v1.0/tasks/1', // title: 'waw the land', // description: 'do something best', // done: false // } ] }, // 事件钩子 beforeCreate: function () { // `this` 指向 vm 实例 var _this = this; //this只能到这一层 // 原生 js 实现 ajax var xhr = new XMLHttpRequest(); xhr.open('GET', '/todo/api/v1.0/tasks/'); xhr.send(); xhr.addEventListener('loadend', function() { if(xhr.status == 200){ var res = JSON.parse(xhr.responseText); console.log(res); res["tasks"].map(function(task){_this.tasks.push(task)}); } }, false); // fetch 库实现 ajax //fetch('/todo/api/v1.0/tasks/') //.then(r => r.json()) //.then(j => { // console.log(j); // this.tasks = j.tasks; //暴力替换 //}) }, methods: { ajax: function(event){ event.preventDefault(); var _this = this; //this只能到这一层 var payload = { title: _this.title, description: _this.description }; console.log(payload); // 原生 js 实现 ajax var xhr2 = new XMLHttpRequest(); xhr2.open('POST', '/todo/api/v1.0/tasks/'); xhr2.setRequestHeader('Content-Type', 'application/json'); xhr2.send(JSON.stringify(payload));// 发送json数据！ xhr2.addEventListener('loadend', function() { if(xhr2.status == 201){ // 注意，这里是201，与后台一致！！ var res2 = JSON.parse(xhr2.responseText); console.log(res2["task"]); //[res2["task"]].map(function(task){_this.tasks.push(task)}); // 这里也用map，没别的目的，只想与前面的形式一致 _this.tasks.push(res2["task"]); //动作温柔 } }, false); // fetch 库实现 ajax //fetch('/todo/api/v1.0/tasks/', { // method: 'POST', // headers: { // 'Content-Type': 'application/json' // }, // body: JSON.stringify(payload) //}) //.then(r => r.json()) //.then(j => { // console.log(j); //[j.task].map(function(task){_this.tasks.push(task)}); // _this.tasks.push(j.task); //动作温柔 //}) } } }); </script> 效果图 打开浏览器控制台
两种方法 <!-- 实例：将 FormData 转化为 json --> <meta charset="utf-8"/> <form enctype='application/json' method="post"> <label>用户：</label> <input type="text" name="user"></br> <label>密码：</label> <input type="texteara" name="password"></br> <input type="submit" value="提交"> </form> <script> // 版本二（箭头语法） var convert_FormData_to_json2 = function (formData) { var objData = {}; formData.forEach((value, key) => objData[key] = value); return JSON.stringify(objData); }; // 版本一 var convert_FormData_to_json = function (formData) { var objData = {}; for (var entry of formData.entries()){ objData[entry[0]] = entry[1]; } return JSON.stringify(objData); }; // 显示根据Form生成的json数据 var formobj = document.querySelector('form'); formobj.addEventListener('submit', function(event){ event.preventDefault(); console.log(convert_FormData_to_json(new FormData(formobj))); console.log(convert_FormData_to_json2(new FormData(formobj))); }, false); </script> 效果图 打开浏览器控制台
<!DOCTYPE html> <html> <head> <meta charset="UTF-8" /> <title>vue.js 2.0 实现的简单分页</title> <style> * { margin: 0; padding: 0; box-sizing: border-box } html { font-size: 12px; font-family: Ubuntu, simHei, sans-serif; font-weight: 400 } body { font-size: 1rem } .text-center{ text-align: center; } .pagination { display: inline-block; padding-left: 0; margin: 21px 0; border-radius: 3px; } .pagination > li { display: inline; } .pagination > li > a { position: relative; float: left; padding: 6px 12px; line-height: 1.5; text-decoration: none; color: #009a61; background-color: #fff; border: 1px solid #ddd; margin-left: -1px; list-style: none; } .pagination > li > a:hover { background-color: #eee; } .pagination .active { color: #fff; background-color: #009a61; border-left: none; border-right: none; } .pagination .active:hover { background: #009a61; cursor: default; } .pagination > li:first-child > a .p { border-bottom-left-radius: 3px; border-top-left-radius: 3px; } .pagination > li:last-child > a { border-bottom-right-radius: 3px; border-top-right-radius: 3px; } </style> </head> <body> <div id="app"> <ul class="pagination"> <li v-for="index in all"> <a v-bind:class="cur === index + 1 ? 'active' : ''" v-on:click="btnClick(index + 1)">{{ index + 1 }}</a> </li> </ul> </div> </body> <script src="js/vue.js"></script> <script> var vm = new Vue({ el: '#app', data: { cur: 1, //当前页码 all: 8 //总页数 }, watch: { cur: function(newVal, oldVal){ // 数值产生变化，触发回调 console.log(newVal, oldVal); } }, methods: { btnClick: function(i){ this.cur = i; // ajax 调取数据... } } }) </script> </html> 效果图
发表了文章
2015-01-18
发表了文章
2015-01-19
发表了文章
2015-01-19
发表了文章
2015-01-19
发表了文章
2015-01-19
发表了文章
2015-01-20
发表了文章
2015-01-21
发表了文章
2015-01-25
发表了文章
2015-01-26
发表了文章
2015-01-26
发表了文章
2015-02-02
发表了文章
2015-02-02
发表了文章
2015-02-02
发表了文章
2015-02-02
发表了文章
2015-02-02
发表了文章
2015-02-04
发表了文章
2015-02-05
发表了文章
2015-02-06
发表了文章
2015-02-06
发表了文章
2015-02-08
