算法及基础知识.ppt

该【算法及基础知识 】是由【wxq362】上传分享，文档一共【46】页，该文档可以免费在线阅读，需要了解更多关于【算法及基础知识 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。算法分析
张阳
信息工程学院
第1页,共46页。
教师简介
张阳
信息工程学院109
教学资源:作业管理系统-张阳
第2页,共46页。
课程简介
课时:理论课36+实验课12=48
成绩:平时30+考试70=100
平时:作业+实验+实验考核+考勤
教材:
《算法设计与分析》王秋芬、吕聪颖等编著清华大学出版社2011年8月
参考
算法设计与分析王晓东第二版清华大学出版社(JAVA)
算法设计与分析王晓东第二版清华大学出版社(C/C++)
第3页,共46页。
课程简介
学****算法的理由:
一个人接受科技教育得到的最大收获,是那些能够受用一生的一般性智能工具。
——GeorgeForsythe《计算机科学家到来以前我们做什么》1968
算法是计算机科学的基石。没有算法,计算机程序将不复存在,另外学****算法可以提高人们的分析能力。
算法可以看作是解决问题的一类特殊方法——它虽非问题的答案,但它是经过准确定义的,用来获得答案的过程。
无论是否涉及计算机,特定的算法设计技术都能看作是问题求解的有效策略。
第4页,共46页。
课程简介
算法的魅力:思考
程序=算法+数据结构
算法让我们上一个更高的台阶
要求:思考+预****复****实践
上课:不旷课、不迟到
第5页,共46页。
课程简介
第1章 算法及基础知识
第2章 贪心法
第3章 分治法
第4章 动态规划
第5章 搜索法
第6章 随机化算法
第9章NP完全理论
第6页,共46页。
第1章算法概述
学****要点:
理解算法的概念。
理解什么是程序,程序与算法的区别和内在联系。
掌握算法的计算复杂性概念。
掌握用C++/JAVA语言描述算法的方法。
第7页,共46页。
第1章算法概述
算法:
对于计算机科学来说,算法指的是对特定问题求解步骤的一种描述,是若干条指令的有穷序列。
算法的特性
输入(0个或多个)、输出(至少1个)、确定性(无歧义)、有限性、可行性
描述方式
自然语言、图形、程序设计语言、伪代码
本书采用了面向对象程序设计语言C++
思考:算法与程序的区别?
第8页,共46页。
第1章算法概述
程序(Program)
程序是算法用某种程序设计语言的具体实现。
程序可以不满足算法的性质(4)。
操作系统:是一个在无限循环中执行的程序,因而不是一个算法。
操作系统的各种任务:可看成是单独的问题,每一个问题由操作系统中的一个子程序通过特定的算法来实现。
第9页,共46页。
最大共约数
求:非负整数M和N的最大公约数,
记为:Gcd(m,n)
方法一:欧几里得算法
Gcd(m,n)=Gcd(n,mmodn)
Gcd(60,24)=Gcd(24,12)=Gcd(12,0)=12
方法二:连续整数检测算法
(1)将min(m,n)的值赋给t。
(2)m除以t,如果余数为0,进入第3步,否则,进入第4步。
(3)n除以t,如果余数为0,返回t值,结束,否则,进入第4步。
(4)t=t-1,返回第2步。
方法三:中学里计算Gcd(m,n)的过程(用数学定义的方法)
(1)找到m的所有质因数。
(2)找到n的所有质因数。
(3)找到(1),(2)中的公因数。
(4)求公因数的积,该乘积为m、n的最大公约数。
第10页,共46页。