ACM常用算法设计.doc

1、1ACM常用算法网站设计（吉林师范大学计算机学院吉林四平 136000）指导教师:（讲师）摘要：本论文设计实现了对 ACM 常用算法的介绍及应用，网站以 MacromediaDreamweaver8 作为开发工具，用html,javascript,css 等语言开发。我通过调查发现本学院学生由于在学完 C 语言后没有适当的题目训练，导致在学习数据结构或参加 ACM 的时候产生了许多困难，有些同学甚至失去了对编程的兴趣。为了让学生在学习数据结构或参加 ACM 的过程中减少困难，让更多的同学了解 ACM，参加 ACM，特此开发了 ACM 常用算法设计网站。该网站界面友好，操作简单，题型多样，代码真

2、确，可转移性强，在叙述算法的过程中语言简洁，加入了大量的图片解释，易于理解，在设计过程中最大限度满足用户的需求，具有较强的实用性和针对性。关键词：html，javascript，css，ACM 常用算法Design of the ACM commonly used algorithms（Computer Collage Jilin Normal University , Siping Jilin 136000）Supervisor: （lecturer）ABSTRACT：This paper designed and implemented the introduction of the AC

3、M and applications commonly used algorithms, the site to Macromedia Dreamweaver 8 as a development tool, html, javascript, css and other language development. I passed the survey found that college students because of the completion of C language of the subject without proper training, resulting in

4、learning data structures or to participate in ACMs time to produce many difficulties, some students even lost the right programming of interest. To enable students to learn data structures or to participate in the process decreased ACM difficulties, so that more students understand the ACM, to parti

5、cipate in ACM, ACM hereby used algorithm developed site. The site interface is friendly, simple operation, Questions in diversity, code true portability strong, in the course of the algorithm described in simple language, adding a lot of pictures to explain, easy to understand, in the design process

6、 as possible to meet the needs of users, has a strong practical and relevant.Keywords:html， javascript，css， ACMcommonlyusedalgorithmACM 国际大学生程序设计竞赛（ACM-ICPC 或 ICPC）又称为计算机中的奥林匹克，是由美国计算机协会（ACM）主办的，一项旨在展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力的年度竞赛。经过近 30 多年的发展，ACM 国际大学生程序设计竞赛已经发展成为最具影响力的大学生计算机竞赛。2要使计算机能完成人们预定

7、的工作，首先必须为如何完成预定的工作设计一个算法，然后再根据算法编写程序。著名计算机科学家沃思（NikiklausWirth）提出一个公式：数据结构+算法= 程序算法和数据结构是程序的两个重要方面。1. 网站设计的现实需求和特点1.1 选题背景和意义ACM 和算法对于一个计算机程序员是十分重要的，而我们学校的 ACM 虽然成立已经三年，但在复习这方面有很多问题。我眼看了我们学院的 ACM 的发展，发现有以下几个问题：1学生对 ACM 的兴趣只是一时的。2对于参加训练的选手没有系统的复习资料，而是到各种网站或书馆去找书看，这样对于学习有很大的不方便。对于以上这两个问题，我认为原因都在于在 ACM

8、 的准备过程中，学生都是从会基本的 C或 C+语法中直接跳到对于算法学习并实践，这样造成了很多的困难，让很多同学都认为 ACM特别难，因此很多同学退出 ACM 协会或减少了对 ACM 的热情。我设计的 ACM 算法设计网站就是根据以上原因设计的，该网站可以轻松的帮你从最简单的C 或 C+语法中过度到对算法的了解并应用。1.2 网站简介本网站界面友好，操作简单，可转移性强，在叙述算法的过程中语言简洁，题型多样加入了大量的图片解释，易于理解，各种算法都有具体实例（主要以北大 ACM 网站上的题目为主）的讲解，每种实例都给出了完整的程序代码，在设计过程中最大限度满足用户的需求，具有较强的实用性和针对

9、性 1。1.3 本网站的主要特点为1友好的操作界面菜单方式与直观方式，操作简单，界面友好，功能完备。完全采用人机对话方式，交互性强。显示题目和代码的背景都为白色，看起来一目了然。菜单也用 IE 收藏夹的形式显示信息准确，信息量大，直观。 252操作的简易性多用鼠标操作。而且对各个 ACM 题都给出了网站的链接，方便能上网的读者浏览原题。3转移的方便由于本网站全部用静态的方式，所以在没有网路的情况下也可以使用，各个读者之间可以相互拷贝。可以说只要有台电脑，就可以方便的进行学习。34题型的多样性在两年的 ACM 比赛当中，我总结了大量的题型，读者可以通过一个网站了解各种题型。5代码的正确性在训练的

10、时候我们很多时候都要有正确的代码来调试，我在编译网站的时候所有代码都进行了调试，而且大部分实例都用北大 ACM 网站的题目，里面附的代码都是我提交后 Accept 的代码。2. 网站分析2.1 网站开发目标本网站旨在为读者创造操作方便、可靠、使用性高以及简单的页面使用环境。2.2 网站设计思想网站设计遵循以下几点 6：1该网站采用模块化结构，整个网站使用分层菜单。2提示通俗易懂。当读者使用该网站时，都有足够的提示信息。程序操作符合用户习惯，键盘工作量小，使用方便。3具有操作失误保护。无论管理者如何选取菜单，都不会导致网站中断。4查询资料简便。算法分为迭代、穷举搜索、递推、递归、回溯、贪婪、分治

11、、动态规划、排序、数据结构、杂题等。读者可以根据自己的情况适当的选择阅读。5维护手段简单。该网站是静态网页，能够提供方便的文件移动、存储、清除和修改功能。6实用性。整个网站既要能存储大量资料，同时又要能进行快速响应。并采用多种有效的措施。7编制各分模块网站功能结构图，使管理一目了然，为管理者提供方便。2.3 网站可行性分析1技术可行性现代计算机配置均较高，有足够的空间可以安装运行平台、数据库和各类编程工具，在编程环境上提供了可靠的支持。编程人员方面，可以运用所学的各种开发计算机软件知识和管理知识，为网站的开发提供必要的技术保障。根据实际情况该网站使用的开发工具为MacromediaDreamw

12、eaver8，开发语言主要以 htmlcssJavaScript 等 7。2经济可行性本网站属于一个工具型网站，可以节省读者大量资料收集、录入、分类、整理、查询、修改等手工操作，而且迅速准确，能够极大地提高学习效率，同时促进读者主动学习，及时的了4解 ACM，参加 ACM。该网站开发所需费用较低，可利用现有的设备和装置。3实践的可行性本网站在开发的时候询问了大量的 ACM 队友，他们都认为我的开发有价值，而且现在已经有很多同学在使用这个网站通过以上从技术、经济、实践三方面的分析，可以确定该网站是可行的。2.4 网站开发方法本网站的开发采用了快速原型法（RPP-RapidPrototypePin

13、g） 。即在总体设计思想的指导下，根据学习中会遇到得基本问题，选择一些关键的子网站作为基本原型，并加以实现，然后逐步扩大原型向整个网站的其它方面延伸，最终达到网站的开发目标，以得到整个网站 8。具体开发过程如下：1确定网站的基本要求和功能。2建造初始快速原型框架。3运行、评价、修改快速原型框架。4建造各子网站的快速原型，并将其连接到总体原型网站。5补充完善原型，形成最终的管理信息网站。这种方法的主要优点在于：网站开发效益高。运用快速原型法可以使网站开发的周期短，速度快，费用低，获得较高的综合开发效益。网站适用性强。由于快速原型法是以读者为中心的，网站的开发符合读者的实际需要，所以网站开发的成功

14、率高，容易被读者接受。网站的可扩展性。由于快速原型法开始并不考虑许多细节问题，网站是在原型应用中不断修改完善的。所以网站具有较强的可扩展性，功能的增减都比较灵活方便。3. 网站设计531 网站功能结构设计3.1.1 总体结构设计ACM 常用算法设计ACM 简介算法简介题集游戏日历图 3.1 网站功能图该网站总体结构如图 3.1 所示，包含 ACM 简介、算法简介、题集、游戏、日历五大模块。3.1.2 各功能模块设计1 “ACM 简介”模块ACM 简介ACM 简述ACM 站点ACM 常见错误图 3.2ACM 简历模块本模块包括 ACM 简述，ACM 站点，ACM 常见错误。（1）ACM 简述AC

15、M-AssociationforComputingMachinery,即 美 国 计 算 机 协 会 。ICPC-InternationalCollegiateProgrammingContest,即 国 际 大 学 生 程 序 设 计 竞 赛。ACM 国际大学生程序设计竞赛（ACM-ICPC 或 ICPC）是由美国计算机协会（ACM）主办的，一项旨在展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力的年度竞赛。经过近 30 多年的发展，ACM 国际大学生程序设计竞赛已经发展成为最具影响力的大学生计算机竞赛。ACM-ICPC 的历史ACM-ICPC 的历史可以上溯到 1970

16、年，首届比赛是在美国德克萨斯 A&M 大学举办的。当时比赛的主办方是 theAlphaChapteroftheUPEComputerScienceHonorSociety。作为一种全新的发现和培养计算机科学顶尖学生的方式，竞赛很快得到美国和加拿大各大学的积极响应。1977 年，在 ACM 计算机科学会议期间举办了首次总决赛，并演变成为目前的一年一届的国际性比赛，迄今为止已经成功地举办了 33 届。6ACM-ICPC 最初几届的参赛队伍主要来自美国和加拿大，后来逐渐发展成为一项世界范围内的竞赛。自从 ICPC 等到了 IBM 等大型 IT 公司的赞助之后，规模开始增长迅速。1997 年，总共有来

17、自 560 所大学的 840 支队伍参加了比赛，而到了 2004 年，这一数字迅速增加到 840 所大学的 4109 支队伍，并正在以每年 10-20%的速度持续增长。从上世纪八十年代开始，ACM 将 ICPC 的总部设在位于美国德克萨斯州的贝勒大学。在大赛举办的早期，冠军多为美国或加拿大的大学获得。而进入上世纪九十年代后期以来，俄罗斯和其它一些东欧国家的大学连夺数次冠军。来自中国大陆的上海交通大学代表队则在2002 年美国夏威夷第 26 届和 2005 年上海举行的第 29 届全球总决赛上两夺冠军。这也是目前为止亚洲大学在该竞赛上取得的最好成绩。赛事的竞争格局已经由最初的北美大学一枝独秀演变

18、成目前亚欧对抗的局面。规则简介ACM-ICPC 以学校为单位的团体赛。每支学校的代表队可以由三名队员组成，每位队员必须是入校五年以内的在校学生，每人一生最多可以参加两次全球总决赛和四次分区预选赛。比赛时，每支队伍只能使用一台电脑在五个小时内编写程序解决八到十个问题。程序完成之后将会提交给赛场的裁判运行，运行的结果将及时通知参赛队伍。有趣的是，当一支队伍在正确完成一道问题后，组委会将在其位置上升起一只代表该题颜色的气球。最后的获胜者为正确解答题目最多且总用时最少的队伍。每道试题用时将从竞赛开始到试题解答被判定为正确为止，其间每一次提交运行结果被判错误的话将被加罚 20 分钟时间，未正确解答的试题

19、不予算入记时。例如：A、B 两队都完成了两道题目，其中 A 队提交解答的时间分别是比赛开始后 1:00 和 2:45，B 队为 1:20 和 2:00，但 B 队有一题提交了 2 次。这样 A 队的总用时为 1:00+2:45=3:45 而 B 队为 1:20+2:00+0:20=3:40，所以 B 队总用时少而优于 A 队。与其它计算机程序竞赛（例如国际信息学奥林匹克，IOI）相比，ACM-ICPC 的特点在于题量大，另外，每支队伍有三名队员却只有一台电脑，使得上机时间更加紧张。因此除了扎实的专业水平，良好的团队协作和心理素质同样是获胜的关键。分区预选赛和全球总决赛每届 ACM-ICPC 由

20、各大洲的分区预选赛和全球总决赛两个阶段组成。各分区预选赛的第一名自动获得参加全球总决赛的资格。总决赛一般安排在每年的三、四月份举行，而预选赛一般安排在前一年的九到十二月份举行。每个大学可以有多支队伍参加不同的预选赛，但最多只能有一支队伍代表这个学校参加总决赛。全球总决赛的冠军将获得一座奖杯。此外，成绩靠前的参赛队伍也将分别获得金牌、银牌或铜牌。7历届冠军：列出自 1977 年以来，历年全球总决赛的冠军。（2）ACM 站点ACMhttp:/icpc.baylor.edu/icpc/ACM/ICPC 中国黑龙江省及东北地区组委会http:/necpc.acm- ACM 站点http:/http:/

21、http:/http:/http:/http:/http:/http:/（3）ACM 常见错误“SubmissionError“-提交使用了不正确的队名、题号等。“NoSuchProblem“-检查题号有没有填错？“CompileError“-程序不能通过编译。“RunTimeError“-程序运行过程中出现非正常中断，一般是数组比较小“MemoryLimitExceeded“-内存使用量超过裁判规定的上限。“OutputLimitExceeded“-输出数据量过大，多半死循环了“TimeLimitExceeded“-运行超过时限还没有得到输出结果。“WrongAnswer“-答案错误。“Pr

22、esentationError“-输出格式不对，可检查空格、回车等等细节。“Accepted“-恭喜恭喜！“OutOfContestTime“-比赛已经结束啦！“ContestRuleViolation“-宣判极刑，参赛资格随即被 yty 取消。2 “算法简历”模块8算法简历简述 迭代动态规划分治贪婪回溯递归递推穷举搜索图 3.3 算法简历模块如图 3.3 所示，本模块包括算法简述、迭代、穷举搜索、递推、递归、回溯、贪婪、分治、动态规划。3 “题集”模块如图 3.4 所示，本模块包括迭代、穷举搜索、递推、递归、回溯、贪婪、分治、动态规划、排序、数据结构、杂题、整数划分、高精度计算、参考书籍。题

23、集迭代 穷举搜索递推 递归回溯 贪婪分治 动态规划排序 数据结构杂题 整数划分高精度计算 参考书籍图 3.4 题集模块4.“游戏“模块游戏俄罗斯方块 五子棋 推箱子图 3.5 游戏模块如图 3.5 所示，本模块包括俄罗斯方块、五子棋、推箱子，是为了让读者劳逸结合，在学习的过程中可以娱乐所编。这三个游戏本身的生成就需要各种算法，有兴趣的读者可以查看网页的源代码。5.“日历”模块由于微软的系统日历没有农历的显示，为了方便读者方便的了解到当天的农历特编写此模9块，此日历也是 ACM 中常出现的一种题型，在杂题里有相关类型的题目，读者可以自己编写相同类型的模块。3.2“代码”设计“代码”是用以代表网站

24、中客观存在的事物名称、属性或状态的符号。由于现代管理生活中的数据量很大，所需的信息种类也很多，所以必须经过分类整理后才能更有效地利用。将网站中具有某些共同属性或特征的信息归并在一起，并通过一些便于计算机或人进行识别和处理的符号来表示各类信息，即是代码设计。代码设计坚持的原则：1唯一性：每一个代码只能唯一的代表网站中的一个实体或实体属性，而一个实体或实体属性也只能唯一的由一个代码表示。2标准化与通用性：国家或有关部委颁布的编码标准，是代码设计的依据，网站内各子网站使用的代码应力求统一。例如，一个子网站的 id 号应该和主网页的 id 号都一致。3合理性：网站的代码与编码的对象的分类体系必须相适应

25、，使得代码对编码对象具有表示作用。4可扩充性和稳定性：网站的代码应有足够的备用代码。当增加了新的实体或属性时，直接地使源代码体系扩充，而不需要变动代码网站。5适用性：代码设计尽量反映编码对象的特点，以便于记忆，使用户容易了解和掌握。6规范性：代码的结构、类型、编码格式必须严格统一，以便于计算机处理。7简单性：代码结构要简单，要尽量缩短的长度，以方便输入，提高处理效率，并且便于记忆，减少读写的差错。本网站的代码长度有一定的限制，这样便于输入。4. 系统使用与维护4.1 运行环境1硬件环境主机：推荐配置奔 III 以上机型， 64MB 以上内存，硬盘剩余空间 45MB 以上；显示器：VGA 系列；

26、鼠标：Windows 支持的各类鼠标；UPS 不间断电源一个。2软件环境操作系统：Windows9X/2000/XP；应用软件：IE 浏览器或支持 JavaScript 的各种浏览器一种；汉字系统：若 Windows 操作系统为西文，则需汉字系统的支持。104.2 网站的使用启动应用程序时，直接用鼠标单击 main.html 页面即可打开界面如图 4.1 所示。图 4.1 网站界面主网页分为三个子网页，分别为 top.htmlleft.htmlright.html本模块又分为 ACM 简介、算法简介、题集、游戏、日历简单的介绍了一下 ACM 及常见的 ACM 网页和提交的过程中系统常见的错误算

27、法简介：简单的介绍了一下迭代、穷举搜索、递推、递归、回溯、贪婪、分治、动态规划等算法并讲解了一些简单的例子题集：对各种题目进行了简单的归类，并有大量的 ACM 题目及源代码5. 结论ACM 常用算法设计的设计网站包括 ACM 简介、算法简介、题集、游戏、日历。读者通过该网站的学习，可以顺利的从 C 语言的基本语法中迅速的适应 ACM 参加比赛的强度，进而可以选择算法书进行学习，是一个具有实际应用意义的典型网站。在网站开发过程中以用户操作简洁、使用方便为宗旨，不断完善系统的功能，尽量做到功能完备，同时力求系统健壮性较强。通过不断地进行程序调整和测试，该系统证明可以在实际中得到应用。通过本次毕业设计，把课本知识运用在软件的实际开发中，加深了对知识原理的理解，同时提高了专业实践了能力，感觉收获很大。由于时间较短，所以该系统还有许多不尽如人意的地方，比如用户界面不够美观、出错处理不够、功能及信息不够完善等多方面问题。这些都有待进一步改善。参考文献1谭浩强.C 语言程序设计(第三版)，清华大学出版社：2006，14-36