ACM常用算法网站设计

ACM常用算法网站设计 摘要:本论文设计实现了对ACM常用算法的介绍及应用，网站以MacromediaDreamweaver8作为开发工具，用 html,javascript,css等语言开发。我通过调查发现本学院学生由于在学完C语言后没有适当的题目训练，导致 在学习数据结构或参加ACM的时候产生了许多困难，有些同学甚至失去了对编程的兴趣。为了让学生在学习数据 结构或参加ACM的过程中减少困难，让更多的同学了解ACM，参加ACM，特此开发了ACM常用算法设计网站。该 网站界面友好，操作简单，题型多样，代码真确，可转移性强，在叙述算法的过程中语言简洁，加入了大量的图 片解释，易于理解，在设计过程中最大限度满足用户的需求，具有较强的实用性和针对性。 关键词:html，javascript，css，ACM常用算法 Design of the ACM commonly used algorithms ABSTRACT:This paper designed and implemented the introduction of the ACM 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 learning data structures or to participate in ACM's 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 participate 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 as possible to meet the needs of users, has a strong practical and relevant. Keywords:html，javascript，css，ACMcommonlyusedalgorithm 1 ACM国际大学生程序设计竞赛(ACM-ICPC或ICPC)又称为计算机中的奥林匹克，是由美国计算机协会(ACM)主办的，一项旨在展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力的年度竞赛。经过近30多年的发展，ACM国际大学生程序设计竞赛已经发展成为最具影响力的大学生计算机竞赛。 要使计算机能完成人们预定的工作，首先必须为如何完成预定的工作设计一个算法，然后再根据算法编写程序。著名计算机科学家沃思(NikiklausWirth)提出一个公式: 数据结构+算法=程序 算法和数据结构是程序的两个重要方面。 1. 网站设计的现实需求和特点 1.1选题背景和意义 ACM和算法对于一个计算机程序员是十分重要的，而我们学校的ACM虽然成立已经三年，但在复习这方面有很多问题。我眼看了我们学院的ACM的发展，发现有以下几个问题: 1(学生对ACM的兴趣只是一时的。 2(对于参加训练的选手没有系统的复习资料，而是到各种网站或书馆去找书看，这样对于学习有很大的不方便。 对于以上这两个问题，我认为原因都在于在ACM的准备过程中，学生都是从会基本的C或C++语法中直接跳到对于算法学习并实践，这样造成了很多的困难，让很多同学都认为ACM特别难，因此很多同学退出ACM协会或减少了对ACM的热情。 我设计的ACM算法设计网站就是根据以上原因设计的，该网站可以轻松的帮你从最简单的C或C++语法中过度到对算法的了解并应用。 1.2网站简介 本网站界面友好，操作简单，可转移性强，在叙述算法的过程中语言简洁，题型多样加入了大量的图片解释，易于理解，各种算法都有具体实例(主要以北大ACM网站上的题目为主)的讲解，每种实例都给出了完整的程序代码，在设计过程中最大限度满足用户的需求，具有较强的 [1]实用性和针对性。 1.3本网站的主要特点为 1(友好的操作界面 菜单方式与直观方式，操作简单，界面友好，功能完备。完全采用人机对话方式，交互性强。显示题目和代码的背景都为白色，看起来一目了然。菜单也用IE收藏夹的形式显示信息准确， ,[25]信息量大，直观。 2(操作的简易性 2 多用鼠标操作。而且对各个ACM题都给出了网站的链接，方便能上网的读者浏览原题。 3(转移的方便 由于本网站全部用静态的方式，所以在没有网路的情况下也可以使用，各个读者之间可以相互拷贝。可以说只要有台电脑，就可以方便的进行学习。 4(题型的多样性 在两年的ACM比赛当中，我总结了大量的题型，读者可以通过一个网站了解各种题型。 5(代码的正确性 在训练的时候我们很多时候都要有正确的代码来调试，我在编译网站的时候所有代码都进行了调试，而且大部分实例都用北大ACM网站的题目，里面附的代码都是我提交后Accept的代码。 2. 网站分析 2.1网站开发目标 本网站旨在为读者创造操作方便、可靠、使用性高以及简单的页面使用环境。 2.2网站设计思想 [6]网站设计遵循以下几点: 1(该网站采用模块化结构，整个网站使用分层菜单。 2(提示通俗易懂。当读者使用该网站时，都有足够的提示信息。程序操作符合用户习惯，键盘工作量小，使用方便。 3(具有操作失误保护。无论管理者如何选取菜单，都不会导致网站中断。 4(查询资料简便。算法分为迭代、穷举搜索、递推、递归、回溯、贪婪、分治、动态规划、排序、数据结构、杂题等。读者可以根据自己的情况适当的选择阅读。 5(维护手段简单。该网站是静态网页，能够提供方便的文件移动、存储、清除和修改功能。 6(实用性。整个网站既要能存储大量资料，同时又要能进行快速响应。并采用多种有效的措施。 7(编制各分模块网站功能结构图，使管理一目了然，为管理者提供方便。 2.3网站可行性分析 1(技术可行性 现代计算机配置均较高，有足够的空间可以安装运行平台、数据库和各类编程工具，在编程环境上提供了可靠的支持。编程人员方面，可以运用所学的各种开发计算机软件知识和管理知识，为网站的开发提供必要的技术保障。根据实际情况该网站使用的开发工具为 [7]MacromediaDreamweaver8，开发语言主要以htmlcssJavaScript等。 2(经济可行性 3 本网站属于一个工具型网站，可以节省读者大量资料收集、录入、分类、整理、查询、修改等手工操作，而且迅速准确，能够极大地提高学习效率，同时促进读者主动学习，及时的了解ACM，参加ACM。该网站开发所需费用较低，可利用现有的设备和装置。 3(实践的可行性 本网站在开发的时候询问了大量的ACM队友，他们都认为我的开发有价值，而且现在已经有很多同学在使用这个网站 通过以上从技术、经济、实践三方面的分析，可以确定该网站是可行的。 2.4网站开发方法 本网站的开发采用了快速原型法(RPP---RapidPrototypePing)。即在总体设计思想的指导下，根据学习中会遇到得基本问题，选择一些关键的子网站作为基本原型，并加以实现，然后逐步扩 [8]大原型向整个网站的其它方面延伸，最终达到网站的开发目标，以得到整个网站。 具体开发过程如下: 1(确定网站的基本要求和功能。 2(建造初始快速原型框架。 3(运行、评价、修改快速原型框架。 4(建造各子网站的快速原型，并将其连接到总体原型网站。 5(补充完善原型，形成最终的管理信息网站。 这种方法的主要优点在于: 网站开发效益高。运用快速原型法可以使网站开发的周期短，速度快，费用低，获得较高的综合开发效益。 网站适用性强。由于快速原型法是以读者为中心的，网站的开发符合读者的实际需要，所以网站开发的成功率高，容易被读者接受。 网站的可扩展性。由于快速原型法开始并不考虑许多细节问题，网站是在原型应用中不断修改完善的。所以网站具有较强的可扩展性，功能的增减都比较灵活方便。 3. 网站设计 4 3(1网站功能结构设计 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简述 ACM-AssociationforComputingMachinery,即美国计算机协会。 ICPC-InternationalCollegiateProgrammingContest,即国际大学生程序设计竞赛。 ACM国际大学生程序设计竞赛(ACM-ICPC或ICPC)是由美国计算机协会(ACM)主办的，一项旨在展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力的年度竞赛。经过近30多年的发展，ACM国际大学生程序设计竞赛已经发展成为最具影响力的大学生计算机竞赛。 ACM-ICPC的历史 ACM-ICPC的历史可以上溯到1970年，首届比赛是在美国德克萨斯A&M大学举办的。当时比赛的主办方是theAlphaChapteroftheUPEComputerScienceHonorSociety。作为一种全新的发现和培养计算机科学顶尖学生的方式，竞赛很快得到美国和加拿大各大学的积极响应。1977年，在ACM计算机科学会议期间举办了首次总决赛，并演变成为目前的一年一届的国际性比赛，迄今为止已经成功地举办了33届。 5 ACM-ICPC最初几届的参赛队伍主要来自美国和加拿大，后来逐渐发展成为一项世界范围内的竞赛。自从ICPC等到了IBM等大型IT公司的赞助之后，规模开始增长迅速。1997年，总共有来自560所大学的840支队伍参加了比赛，而到了2004年，这一数字迅速增加到840所大学的4109支队伍，并正在以每年10-20%的速度持续增长。 从上世纪八十年代开始，ACM将ICPC的总部设在位于美国德克萨斯州的贝勒大学。 在大赛举办的早期，冠军多为美国或加拿大的大学获得。而进入上世纪九十年代后期以来，俄罗斯和其它一些东欧国家的大学连夺数次冠军。来自中国大陆的上海交通大学代队则在2002年美国夏威夷第26届和2005年上海举行的第29届全球总决赛上两夺冠军。这也是目前为止亚洲大学在该竞赛上取得的最好成绩。赛事的竞争格局已经由最初的北美大学一枝独秀演变成目前亚欧对抗的局面。 规则简介 ACM-ICPC以学校为单位的团体赛。每支学校的代表队可以由三名队员组成，每位队员必须是入校五年以内的在校学生，每人一生最多可以参加两次全球总决赛和四次分区预选赛。 比赛时，每支队伍只能使用一台电脑在五个小时内编写程序解决八到十个问题。程序完成之后将会提交给赛场的裁判运行，运行的结果将及时通知参赛队伍。有趣的是，当一支队伍在正确完成一道问题后，组委会将在其位置上升起一只代表该题颜色的气球。 最后的获胜者为正确解答题目最多且总用时最少的队伍。每道用时将从竞赛开始到试题解答被判定为正确为止，其间每一次提交运行结果被判错误的话将被加罚20分钟时间，未正确解答的试题不予算入记时。例如:A、B两队都完成了两道题目，其中A队提交解答的时间分别是 ，但B队有一题提交了2次。这样A队的总用时为比赛开始后1:00和2:45，B队为1:20和2:00 1:00+2:45=3:45而B队为1:20+2:00+0:20=3:40，所以B队总用时少而优于A队。 与其它计算机程序竞赛(例如国际信息学奥林匹克，IOI)相比，ACM-ICPC的特点在于题量大，另外，每支队伍有三名队员却只有一台电脑，使得上机时间更加紧张。因此除了扎实的专业水平，良好的团队协作和心理素质同样是获胜的关键。 分区预选赛和全球总决赛 每届ACM-ICPC由各大洲的分区预选赛和全球总决赛两个阶段组成。各分区预选赛的第一名自动获得参加全球总决赛的资格。总决赛一般安排在每年的三、四月份举行，而预选赛一般安排在前一年的九到十二月份举行。每个大学可以有多支队伍参加不同的预选赛，但最多只能有一支队伍代表这个学校参加总决赛。 全球总决赛的冠军将获得一座奖杯。此外，成绩靠前的参赛队伍也将分别获得金牌、银牌或铜牌。 6 历届冠军:列出自1977年以来，历年全球总决赛的冠军。 (2)ACM站点 ACM 中国?黑龙江省及东北地区组委会 国内部分高校ACM站点 (3)ACM常见错误 "SubmissionError"--提交使用了不正确的队名、题号等。 "NoSuchProblem"--检查题号有没有填错, "CompileError"--程序不能通过编译。 "RunTimeError"--程序运行过程中出现非正常中断，一般是数组比较小 "MemoryLimitExceeded"--内存使用量超过裁判规定的上限。 "OutputLimitExceeded"--输出数据量过大，多半死循环了„„ "TimeLimitExceeded"--运行超过时限还没有得到输出结果。 "WrongAnswer"--答案错误。 "PresentationError"--输出格式不对，可检查空格、回车等等细节。 "Accepted"--恭喜恭喜～ "OutOfContestTime"--比赛已经结束啦～ "ContestRuleViolation"--宣判极刑，参赛资格随即被yty取消。 2(“算法简历”模块 7 算法简历 简述 迭代 穷举搜索 递推 递归 回溯 贪婪 分治 动态规划 图3.3算法简历模块 如图3.3所示，本模块包括算法简述、迭代、穷举搜索、递推、递归、回溯、贪婪、分治、 动态规划。 3(“题集”模块 如图3.4所示，本模块包括迭代、穷举搜索、递推、递归、回溯、贪婪、分治、动态规划、 排序、数据结构、杂题、整数划分、高精度计算、参考书籍。 题集 迭代 穷举搜索 递推 递归 回溯 贪婪 分治 动态规划 排序 数据结构 杂题 整数划分 高精度计算 参考书籍 图3.4题集模块 4.“游戏“模块 游戏 俄罗斯方块 五子棋 推箱子 图3.5游戏模块 如图3.5所示，本模块包括俄罗斯方块、五子棋、推箱子，是为了让读者劳逸结合，在学习 的过程中可以娱乐所编。这三个游戏本身的生成就需要各种算法，有兴趣的读者可以查看网页的 源代码。 5.“日历”模块 由于微软的系统日历没有农历的显示，为了方便读者方便的了解到当天的农历特编写此模 8 块，此日历也是ACM中常出现的一种题型，在杂题里有相关类型的题目，读者可以自己编写相同类型的模块。 3.2“代码”设计 “代码”是用以代表网站中客观存在的事物名称、属性或状态的符号。由于现代管理生活中的数据量很大，所需的信息种类也很多，所以必须经过分类整理后才能更有效地利用。将网站中具有某些共同属性或特征的信息归并在一起，并通过一些便于计算机或人进行识别和处理的符号来表示各类信息，即是代码设计。 代码设计坚持的原则: 1(唯一性:每一个代码只能唯一的代表网站中的一个实体或实体属性，而一个实体或实体属性也只能唯一的由一个代码表示。 2(化与通用性:国家或有关部委颁布的编码标准，是代码设计的依据，网站内各子网站使用的代码应力求统一。例如，一个子网站的id号应该和主网页的id号都一致。 3(合理性:网站的代码与编码的对象的分类体系必须相适应，使得代码对编码对象具有表示作用。 4(可扩充性和稳定性:网站的代码应有足够的备用代码。当增加了新的实体或属性时，直接地使源代码体系扩充，而不需要变动代码网站。 5(适用性:代码设计尽量反映编码对象的特点，以便于记忆，使用户容易了解和掌握。 6(规范性:代码的结构、类型、编码格式必须严格统一，以便于计算机处理。 7(简单性:代码结构要简单，要尽量缩短的长度，以方便输入，提高处理效率，并且便于记忆，减少读写的差错。本网站的代码长度有一定的限制，这样便于输入。 4. 系统使用与维护 4.1运行环境 1(硬件环境 ?主机:推荐配置奔III以上机型，64MB以上内存，硬盘剩余空间45MB以上; ?显示器:VGA系列; ?鼠标:Windows支持的各类鼠标; ?UPS不间断电源一个。 2(软件环境 ?操作系统:Windows9X/2000/XP; ?应用软件:IE浏览器或支持JavaScript的各种浏览器一种; ?汉字系统:若Windows操作系统为西文，则需汉字系统的支持。 9 4.2网站的使用 启动应用程序时，直接用鼠标单击main.html页面即可打开界面如图4.1所示。 图4.1 网站界面 主网页分为三个子网页，分别为top.htmlleft.htmlright.html 本模块又分为ACM简介、算法简介、题集、游戏、日历 简单的介绍了一下ACM及常见的ACM网页和提交的过程中系统常见的错误 算法简介:简单的介绍了一下迭代、穷举搜索、递推、递归、回溯、贪婪、分治、动态规划等算法并讲解了一些简单的例子 题集:对各种题目进行了简单的归类，并有大量的ACM题目及源代码 10 5. 结论 ACM常用算法设计的设计网站包括ACM简介、算法简介、题集、游戏、日历。读者通过该网站的学习，可以顺利的从C语言的基本语法中迅速的适应ACM参加比赛的强度，进而可以选择算法书进行学习，是一个具有实际应用意义的典型网站。 在网站开发过程中以用户操作简洁、使用方便为宗旨，不断完善系统的功能，尽量做到功能完备，同时力求系统健壮性较强。通过不断地进行程序调整和测试，该系统证明可以在实际中得到应用。 通过本次毕业设计，把课本知识运用在软件的实际开发中，加深了对知识原理的理解，同时提高了专业实践了能力，感觉收获很大。由于时间较短，所以该系统还有许多不尽如人意的地方，比如用户界面不够美观、出错处理不够、功能及信息不够完善等多方面问题。这些都有待进一步改善。 11 参考文献 [1]谭浩强.C语言程序设计(第三版)，清华大学出版社:2006，14-36 [2]严蔚敏.吴伟民.数据结构(C语言版)，清华大学出版社:2007，122 [3]王晓东.算法设计与分析(第二版)，清华大学出版社:2008，165 [4]潘金贵等(译)ThomasH.Cormen..算法导论，机械工业出版社:2006，102 [5]丁丽娟.数值计算方法，北京理工大学出版社:1997，13 [6]MiltonAbramowitzandIreneA.Stegun,editors.HandbookofMathematicalFunctions.Dover,2005,342 [7]G..M.Adel’son-Vel’skiiandE.M.Landis.Analgorithmfortheorganizationofinformation.SovietMathematicsDoklady:2002,3:1259-1263 [8]LeonardM.Adleman,CarlPomerance,andRobertS.Rumely.Ondistinguishingprimenumbersfromcompositenumbers,AnnalsofMathematics:2003,117:173-206 12