《算法基础》PPT课件

《《算法基础》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、IntroductiontoACM/ICPCProgrammingContestChenBinYangzhouUniversityE-mail:chb@yzu.edu.cn1ACM(AssociationforComputingMachinery)成立于计算机诞生次年，是目前计算机学界中历史最悠久、最具权威性的组织，是推进信息技术专业人员和学生提高技巧的主要力量。ACM通过提供前沿技术信息和从理论到实践的转化，为其全球7.5万名成员服务，并已经成为信息科技领域的一个基本信息来源。WhatisACM?7/17/

2、20212ACM/ICPC：ACM主办的国际大学生程序设计竞赛(InternationalCollegiateProgrammingContest)，简称ACM/ICPC，自从1977年开始至今已经连续举办30届。其宗旨是提供一个让大学生向IT界展示自己分析问题和解决问题的能力的绝好机会，并成为一个有效的途径，让下一代IT天才可以接触到其日后工作中将要用到的各种软件。现在，ACM/ICPC已成为世界各国大学生中最具影响力的国际计算机赛事。3ACM/ICPCinChina中国大陆高校从1996年开始参加ACM国际大

3、学生程序设计竞赛亚洲预赛。前五届中国赛区设在上海，由上海大学承办；2002年由清华大学和西安交通大学承办；2003年由清华大学和中山大学承办。2004年由北京大学和上海交通大学承办。2005年由四川大学、北大和浙大承办。2006年由上海大学、清华和西电承办。2007年由吉林大学、北大和西华大学以及南京航空航天大学承办。2008年由哈尔滨工程大学、北京交通大学、中国科学技术大学、杭州电子科技大学、西南民族大学承办4如何比赛？3人组队可以携带诸如书、手册、程序清单等参考资料；不能携带任何可用计算机处理的软件或数据

4、、不能携带任何类型的通讯工具；可能收到的反馈信息包括：CompileError--程序不能通过编译。RunTimeError--程序运行过程中出现非正常中断。TimeLimitExceeded--运行超过时限还没有得到输出结果。WrongAnswer--答案错误。PresentationError--输出格式不对，可检查空格、回车等等细节。Accepted--恭喜恭喜！5首先根据解题数目进行排名。如果多支队伍解题数量相同，则根据总用时加上惩罚时间进行排名。总用时和惩罚时间由每道解答正确的试题的用时加上惩罚时间而成

5、。每道试题用时将从竞赛开始到试题解答被判定为正确为止，其间每一次错误的运行将被加罚20分钟时间，未正确解答的试题不记时。如何排名？6比赛形式1支队伍1台机器（提供打印服务）上机编程解决问题（可带纸质资料）实时测试，动态排名试题6-10题全英文（可以带字典）时间：持续5个小时7Language8CourseObjectProvideaconvenientsummary/referenceofimportanttopicsinmathematicsandalgorithms,alongwithappropriatec

6、hallengestohelpyoumasterthematerial.PreparingforthecontestImprovetheprogrammingability9CourseOutlineAlgorithmbasicsDataStructuresAlgorithmdesignGreedyBranchandBoundDynamicProgrammingMathematicalBasicsNumbertheoryArithmeticandalgerbraCombinatoricsComputational

7、Geometry10第一讲　算法基础扬州大学信息工程学院计算机系陈斌二○○九年三月11参考书目算法艺术和信息学竞赛　刘汝佳算法与数据结构　　傅清祥现代计算机常用数据结构与算法　潘金贵等IntroductiontoAlgorithmsComputerAlgorithmsIntroductiontoDesignandAnalysisSaraBaase&AllenVanGelder计算机程序设计艺术DonaldKnuthArtofProgrammingContest—CProgramming,DataStructure

8、s,Algorithms2ndEditionProgrammingChallenges……121.1算法什么是算法？平时所说的算法算法就是解决问题的方法或过程。计算机科学中的算法算法是指由有限指令集合中的一系列指令所组成的过程。13算法的基本特征有穷性算法必须是可终止的。确切性算法的每一步都应确切地、无歧义地定义。可行性算法原则上能够精确地运行。输入　一个算法必须有零个或