ACM程序设计2014new.ppt

ACM程序设计课程预备知识 1。程序设计语言；（C,C++,JAVA,PASCAL） 2。数据结构与算法； 3。组合数学、高等数学； 4。英语阅读； 课程内容 第一章 经典数据结构与算法 第二章 动态规划（Dynamic Programming） 第三章 贪心算法（Greedy） 第四章 穷举搜索（Complete Search） 第五章 最短路径（Shortest Path） 第六章 背包问题（Knapsack） 第七章 计算几何学(Computational Geometry) 第八章 网络流与二部图匹配（Network Flow） 第九章 凸包问题（Two-Dimensional Convex Hull） 第十章 数论与大数问题（BigNums） 第十一章????????? 线性规划与整数规划 第十二章????????? 着色问题与排队论 第十三章????????? 最小生成树（Minimum Spanning Tree） 第十四章????????? DFS与BFS以及剪枝问题 第十五章????????? 组合数学与概率论 第十六章????????? 启发式搜索（Heuristic Search） 第十七章????????? 近似搜索（Approximate Search） 第十八章????????? 泛滥填充（Flood Fill） 第十九章????????? 欧拉回路（Eulerian Path） 第二十章????????? 回溯搜索技术（Recursive Search Techniques） 最大公约数 Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB Problem description ??输入两个整数a,b(1=a,b=100000000)，请编写程序求出他们的最大公约数。Input?? 第一个数n表示测试数据的个数，接下来的n行每行有两个整数a b，用空格隔开Output ??输出n行，每行输出对应a,b的最大公约数Sample Input 3 12 8 25 10 21 63 Sample Output 4 5 21 解答 #include?stdio.h int?gcd(int?a,int?b) {int?c; if(!b)return?a; while(c=a%b){a=b;b=c;} return?b;} int?main() {int?a,b,t; scanf(%d,t); while(t--) {scanf(%d%d,a,b); printf(%d\n,gcd(a,b));} return?0; } 结果 Problem 10178 Solution 13069 User Jt030135 Judge Result Accepted Language GNU C Memory 640KB Used Time 0ms Used Code Length 212B 教 材 湖南大学ACM程序设计竞赛教练组的自编教材。 《ACM程序设计培训教程》 中国铁道出版社出版 *ACM程序设计 教练组 吴 昊 本次内容 1.绪论 2.2014湖南大学在全球总决赛 3.怎么样成为一个优秀的ACM选手 4.练习、练习，where，how 5.举一个例 6.教材与参考资料 绪言 什么是ACM程序设计竞赛？ ACM国际大学生程序设计竞赛（ACM/ICPC ：ACM International Collegiate Programming Contest）是由国际计算机界历史悠久、颇具权威性的组织ACM学会（Association for Computing Machinery，美国计算机协会）主办，是世界上公认的规模最大、水平最高的国际大学生程序设计竞赛，其目的旨在使大学生运用计算机来充分展示自已分析问题和解决问题的能力。 ACM程序设计竞赛介绍(之一) 该项竞赛从1970年举办至今已历39届，因历届竞赛都荟萃了世界各大洲的精英，云集了计算机界的“希望之星”，而受到国际各知名大学的重视，并受到全世界各著名计算机公司的高度关注，成为世界各国大学生最具影响力的国际级计算机类的赛事。此项赛事的主办目的不单是培养参赛选手的创造力