NOIP算法提纲Bymatrix.ppt

《NOIP算法提纲Bymatrix.ppt》由会员分享，可在线阅读，更多相关《NOIP算法提纲Bymatrix.ppt（20页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、经典算法经典算法语言与计算机语言与计算机递归调用递归调用向前引用向前引用随机化随机化指针类型指针类型按位运算按位运算排序（一）排序（一）冒泡排序（起泡排序）冒泡排序（起泡排序）选择排序选择排序插入排序插入排序快速排序快速排序排序（二）排序（二）线性时间排序线性时间排序查找第查找第k大元素大元素带第二关键字的排序带第二关键字的排序数论（一）数论（一）素性判断素性判断筛选建立素数表筛选建立素数表分解质因数分解质因数进制转换进制转换二分取幂二分取幂数论（二）数论（二）求最大公约数求最大公约数求最小公倍数求最小公倍数扩展的辗转相除扩展的辗转相除求解一元一次同余式求解一元一次同余式中国剩余定理中国剩余定

2、理高斯消元高斯消元四则运算四则运算表达式计算表达式计算高精度加法高精度加法高精度减法高精度减法高精度乘法高精度乘法高精度除法高精度除法图论：最小生成树图论：最小生成树Prim算法算法Kruskal算法算法次小生成树次小生成树图论：求最短路图论：求最短路Dijkstra算法算法Bellman-Ford算法算法Floyd-Warshall算法算法次短路次短路差分约束系统差分约束系统图论：图论：DFS遍历遍历深度优先搜索深度优先搜索欧拉回路欧拉回路求弱连通分量求弱连通分量图论：图论：BFS遍历遍历广度优先搜索（宽度优先搜索）广度优先搜索（宽度优先搜索）求不带权的最短路求不带权的最短路求图的直径求图的

3、直径AOV问题（拓扑排序）问题（拓扑排序）树树求树的最短链求树的最短链二叉树的四种遍历二叉树的四种遍历已知先序中序求后序已知先序中序求后序已知中序后序求先序已知中序后序求先序已知先序后序求中序已知先序后序求中序数据结构（一）数据结构（一）表和栈表和栈Hash表与开散列表与开散列并查集并查集堆堆二叉查找树二叉查找树排列与组合排列与组合生成所有排列生成所有排列生成所有组合生成所有组合生成下一个排列生成下一个排列生成下一个组合生成下一个组合0-1背包背包完全背包完全背包乘法问题乘法问题数塔问题数塔问题装箱问题装箱问题动态规划（一）动态规划（一）动态规划（二）动态规划（二）最长上升序列（最长上升序列（

4、LISLIS）最长公共子串（最长公共子串（LCMLCM）最小代价子母树最小代价子母树分治与递归分治与递归二分查找二分查找归并排序归并排序最近点对问题最近点对问题求最大子序列和的求最大子序列和的O(nlogn)算法算法Hanoi塔问题及其变种塔问题及其变种棋盘覆盖问题棋盘覆盖问题循环赛日程表问题循环赛日程表问题贪心贪心最优装载问题最优装载问题部分背包问题部分背包问题独立区间的选择独立区间的选择覆盖区间的选择覆盖区间的选择区间的最小点覆盖区间的最小点覆盖点的最小区间覆盖点的最小区间覆盖递推递推Fibonacci数的若干应用数的若干应用Catalan数的若干应用数的若干应用拆分数拆分数差分序列差分序列其它网络流网络流置换群置换群KMP算法算法