IntroductiontoACM/ICPCProgrammingContestChenBinYangzhouUniversityE-mail:chb@yzu.edu.cn精选
ppt
关于艾滋病ppt课件精益管理ppt下载地图下载ppt可编辑假如ppt教学课件下载triz基础知识ppt
ACM(AssociationforComputingMachinery)成立于计算机诞生次年，是目前计算机学界中历史最悠久、最具权威性的组织，是推进信息技术专业人员和学生提高技巧的主要力量。ACM通过提供前沿技术信息和从理论到实践的转化，为其全球7.5万名成员服务，并已经成为信息科技领域的一个基本信息来源。WhatisACM?ACM/ICPC：ACM主办的国际大学生程序设计竞赛(InternationalCollegiateProgrammingContest)，简称ACM/ICPC，自从1977年开始至今已经连续举办30届。其宗旨是提供一个让大学生向IT界展示自己分析问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
和解决问题的能力的绝好机会，并成为一个有效的途径，让下一代IT天才可以接触到其日后工作中将要用到的各种软件。现在，ACM/ICPC已成为世界各国大学生中最具影响力的国际计算机赛事。精选PPTACM/ICPCinChina中国大陆高校从1996年开始参加ACM国际大学生程序设计竞赛亚洲预赛。前五届中国赛区设在上海，由上海大学承办；2002年由清华大学和西安交通大学承办；2003年由清华大学和中山大学承办。2004年由北京大学和上海交通大学承办。2005年由四川大学、北大和浙大承办。2006年由上海大学、清华和西电承办。2007年由吉林大学、北大和西华大学以及南京航空航天大学承办。2008年由哈尔滨
工程
路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理
大学、北京交通大学、中国科学技术大学、杭州电子科技大学、西南民族大学承办精选PPT如何比赛？3人组队可以携带诸如书、手册、程序清单等参考资料；不能携带任何可用计算机处理的软件或数据、不能携带任何类型的通讯工具；可能收到的反馈信息包括：CompileError--程序不能通过编译。RunTimeError--程序运行过程中出现非正常中断。TimeLimitExceeded--运行超过时限还没有得到输出结果。WrongAnswer--答案错误。PresentationError--输出格式不对，可检查空格、回车等等细节。Accepted--恭喜恭喜！精选PPT首先根据解题数目进行排名。如果多支队伍解题数量相同，则根据总用时加上惩罚时间进行排名。总用时和惩罚时间由每道解答正确的试题的用时加上惩罚时间而成。每道试题用时将从竞赛开始到试题解答被判定为正确为止，其间每一次错误的运行将被加罚20分钟时间，未正确解答的试题不记时。如何排名？精选PPT比赛形式1支队伍1台机器（提供打印服务）上机编程解决问题（可带纸质资料）实时测试，动态排名试题6-10题全英文（可以带字典）时间：持续5个小时精选PPTLanguage精选PPTCourseObjectProvideaconvenientsummary/referenceofimportanttopicsinmathematicsandalgorithms,alongwithappropriatechallengestohelpyoumasterthematerial.PreparingforthecontestImprovetheprogrammingability精选PPTCourseOutlineAlgorithmbasicsDataStructuresAlgorithmdesignGreedyBranchandBoundDynamicProgrammingMathematicalBasicsNumbertheoryArithmeticandalgerbraCombinatoricsComputationalGeometry精选PPT第一讲 算法基础扬州大学信息工程学院计算机系陈斌二○○九年三月精选PPT参考书目算法艺术和信息学竞赛 刘汝佳 算法与数据结构 傅清祥现代计算机常用数据结构与算法 潘金贵等IntroductiontoAlgorithmsComputerAlgorithmsIntroductiontoDesignandAnalysisSaraBaase&AllenVanGelder计算机程序设计艺术DonaldKnuthArtofProgrammingContest—CProgramming,DataStructures,Algorithms2ndEditionProgrammingChallenges……精选PPT1.1算法什么是算法？平时所说的算法 算法就是解决问题的方法或过程。计算机科学中的算法 算法是指由有限指令集合中的一系列指令所组成的过程。精选PPT算法的基本特征有穷性 算法必须是可终止的。确切性 算法的每一步都应确切地、无歧义地定义。可行性 算法原则上能够精确地运行。输入 一个算法必须有零个或多个输入。输出 一个算法有一个或多个输出精选PPT1.2时间复杂度和空间复杂度时间复杂度 对于一个规模为n的输入数据，我们希望知道算法要运行多长时间得到结果，也希望知道随着n的增长，算法所需时间的增长速度如何？空间复杂度 对于一定规模输入数据，算法运行所需空间的度量 精选PPT1.2.1基本渐进记号定义1.1设f和g是两个函数，如果存在c1，c2，N>0,使得当n>N时，此时用表示函数集合，其运行时间用 来度量。如果存在正常数N和c使得当n>N时，f(n)
N时，f(n)>cg(n)记为。精选PPT渐进记号的图例精选PPT1.2.2代码分析简单实例复杂实例算法比较精选PPT代码分析的例子(1)fact:=1;fori:=1tondofact:=fact*i;一次乘法为一个基本操作忽略i改变的时间共f(n)=n次基本操作时间复杂度为n精选PPT代码分析的例子(2)sum:=0;fori:=1tondoforj:=1tondosum:=sum+a[i,j];基本操作：加法忽略循环变量i和j的改变时间共n2次基本操作时间复杂度为n2精选PPT一个更为复杂的例子sum:=0;fori:=1tondobeginfact:=1;forj:=1toidofact:=fact*i;sum:=sum+fact;end第i次循环执行了i个操作总时间复杂度为1+2+3+…+n=n(n+1)/2精选PPT比较两个算法算法一执行了f(n)=n2次基本操作算法二执行了g(n)=n2/2次基本操作那个算法好呢？算法二好，因为g(n)a[i+1]thendo_it;假设do_it操作为一次基本操作，忽略其他如果输入是从小大到排序好的，则操作数为0如果输入是从大到小排序好的，则操作数为n-1即使规模(n)相同，不同的输入导致不同的运行时间！精选PPT一道题目给一串整数a[1…n]，求出它和最大的子序列，即找出1<=i<=j<=n，使a[i]+a[i+1]+…+a[j]最大介绍四个算法并分析时间复杂度枚举：O(n3)优化的枚举：O(n2)分治：O(nlogn)贪心：O(n)精选PPT算法一思想：枚举所有的i和j，计算a[i]+…+a[j]，选择最大的程序如下：max:=a[1];fori:=1tondoforj:=itondobeginsum:=0;fork:=itojdosum:=sum+a[k];ifsum>maxthenmax:=sum;end;End;时间复杂度如何分析？精选PPT算法一分析当i和j一定的时候，内层循环执行j-i+1次总次数为应该如何计算？方法一：直接计算先计算里层求和号，得再加起来？好复杂…自己做一做吧，得利用公式12+…+n2=O(n3)一般地，有1k+…+nk=O(nk+1)精选PPT算法一分析（续）总次数为：完全的计算太麻烦能不能不动笔就知道渐进时间复杂度呢？何必非要计算出详细的公式再化简呢？里层求和计算出的结果是O((n-i)2)12+22+…+n2=O(n3)每步都化简！但是要保留外层需要的变量结论：算法一时间复杂度为O(n3)经验：一般只能支持n<=200精选PPT算法二思路枚举i和j后，能否快速算出a[i]+…+a[j]呢？预处理！记s[i]=a[1]+a[2]+…+a[i],规定s[0]=0则可以在O(n)的时间内计算出s[1],…,s[n]s[0]:=0;fori:=1tondos[i]:=s[i–1]+a[i];精选PPT算法二（续）有了s[i]，怎么快速求a[i]+…+a[j]呢？a[i]+…+a[j]=(a[1]+…+a[j])–(a[1]+…+a[i-1])=s[j]–s[i-1]而s[i]经过预处理以后可以直接读出！程序如下：max:=a[1];fori:=1tondoforj:=itondoifs[j]–s[i-1]>maxthenmax:=s[j]–s[i-1];end;end;时间复杂度：预处理+主程序=O(n+n2)=O(n2).n<=3000精选PPT算法三用一种完全不同的思路最大子序列的位置有三种可能完全处于序列的左半，即j<=n/2完全处于序列的右半，即i>=n/2跨越序列中间，即imaxthenmax:=s[j]–min_s;ifs[j]
本文档为【《算法基础》PPT课件】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483