by 等流星的牧羊人
写完这个这学期大概不用写了。。。。
考点
主要考到前四章,贪心证明为止(两种,数学归纳与。。。。) 看一下课后题


一些例题

迭代法求解
迭代法求解递推方程
• 直接迭代,代入初值,然后求和
• 对递推方程和初值进行换元,然后求和,求和后进行相反换元,得到原始递推方程的解
• 验证方法—— 数学归纳法


换元


差消法化简高阶递推方程
对于高阶递推方程先要用差消法化简为一阶方程,然后再迭代求解

递归树
递归树是迭代的图形表述

主定理


分治策略

动态规划


贪心
数学归纳法证明活动选择正确性

最优装载问题正确性证明

交换论证证明最优调度正确性
贪心法正确性证明方法:交换论证
- 分析算法解与一般最优解的区别,找到把一般解改造成算法解的一系列操作( 替换成份、交换次序)
- 证明操作步数有限
- 证明每步操作后的得到解仍旧保持最优

回溯

线性规划

最大流
Ford-Fulkerson 方法


网友评论