acmicpc编程基础_2

《acmicpc编程基础_2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ACM/ICPC编程基础第二节算法概述ACM/ICPC编程基础…•1、上机课上会有学长讲C语言。•2、要求下周上课前学会–1、变量–2、输入，输出–3、循环•3、校赛集训方案已经发在BBS上。上节课内容回顾•算法–正确性–高效性ACM/ICPC编程基础如何评价算法的效率•一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。ACM/ICPC编程基础例：

2、fibonacci•定义一个数列F(n)•F(0)=0•F(1)=1•当k>=2时，F(k)=F(k-1)+F(k-2)•求F(10亿)%10007ACM/ICPC编程基础例：fibonacci•方法一：递归–若想计算F(k)，需要计算F(k-1)和F(k-2)–若想计算F(k-1)，需要计算F(k-2)和F(k-3)–......–若想计算F(2)，需要计算F(1)和F(0)–共有k-1层，每层两个–共需要计算约2^(k-1)次–约2^(10亿-1)•约10^(3亿)次。需要时间10^(3亿)年。宇宙的年龄是1.37*10^(10)年。ACM/ICPC编程基础例：fi

3、bonacci•方法二：递推–根据F(0)和F(1)，计算出F(2)–根据F(1)和F(2)，计算出F(3)–......–根据F(k-2)和F(k-1)，计算出F(k)–计算F(k)共需要计算(k-1)次。–10亿-1次–一分钟左右。例：fibonacci•方法三：矩阵加速F(k+2)F(k+1)–设矩阵A(k)=F(k+1)F(k)–F(k+2)F(k+1)F(2)F(1)–则A(k)*A(0)=F(k+1)F(k)F(1)F(0)–F(k+2)F(k+1)11–=F(k+1)F(k)10–F(k+2)+F(k+1)F(k+2)–=F(k+1)+F(k)F(k+1)

4、–=A(k+1)–所以：A(k)=A(0)*A(0)^k=A(0)^(k+1)–计算次数：2*[log(10亿)]*8=500。时间：百万分之一秒时间复杂度•一般情况下，算法的基本操•问题规模为n作重复某一个非常简单的操–递归方法：2^(n-1)作。并且此操作的执行次数与问题的规模有关。–递推方法：n-1•首先，列出此操作的执行次–矩阵加速：数与问题规模的关系。2*[log(10亿)]*8•然后，忽略常数系数与低阶项。并加O()标志。•时间复杂度–递归方法:O(2^n)–递推方法:O(n)–矩阵加速:O(logn)不同的时间复杂度在1S的时间内能处理的问题规模•O(lo

5、g(n))10^(100000)•O(sqrt(n))10^16•O(n)10^8•O(n^2)10^4•O(n^3)10^2•O(2^n)30•O(N!)11时间复杂度•关于算法的时间复杂度的分析可以参考相关书籍。本课程的主要内容•特点–刚开始是枯燥的基础，中间是好玩的算法，最后是高深的数据结构。•我讲的是大家目前能听懂的，没讲的是以大家目前的水平听不懂的。•只讲一般问题，不讲具体解法。1、编程基础•1.1、多测试数据及基本输入输出•1.2、字符串–1.2.1、输入输出–1.2.2、编码，大小写转换–1.2.3、大整–1.2.4、操作•1.3、排序–1.3.1、插入排

6、序–1.3.2、冒泡排序–1.3.3、选择排序–1.3.4、归并排序2、高级编程方法•2.1、递归•2.2、DFS•2.3、队列与BFS3、基本算法•3.1、枚举•3.2、贪心•3.3、构造•3.4、模拟•3.5、二分查找•3.6、二进制分解4、基本图论•4.1、图的深度优先遍历和广度优先遍历.•4.2、最短路径算法•4.3、最小生成树算法•4.4、拓扑排序•4.5、二分图的最大匹配•4.6、最大流5、基本数据结构•5.1、并查集•堆：•5.2、哈希表–插入数据•5.3、堆–查找最小值–删除最小值•5.4、trie树6、基本动态规划•331627454325362219

7、31•只能向右走•12372029131630362226或者向下走•21181739322032133725•从左上角出•19123228391743262112发•39233149342748144520•23162130464332204611•到达右下角•35151417263516194327时路径上的•14253235241744141340数字之和最•17184628383413214449大是多少？•223046182922363624297、基本数论•7.1、排列组合•7.2、素数与整除，中国剩余定理•7.3、欧几里德8