第1讲算法引论.ppt
《第1讲算法引论.ppt》由会员分享,可在线阅读,更多相关《第1讲算法引论.ppt(25页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第一章第一章第一章第一章 算法引论算法引论算法引论算法引论例子例子:给定两个正整数给定两个正整数a a和和b,b,求它们的最大公因子求它们的最大公因子算法算法:欧几里德算法欧几里德算法输入输入:正整数正整数a a、b b输出:输出:a a和和b b的最大公因子的最大公因子第一章第一章 算法引论算法引论1.1 1.1 算法的基本概念算法的基本概念一、什么是算法及其与程序的区别一、什么是算法及其与程序的区别第一章第一章第一章第一章 算法引论算法引论算法引论算法引论求解的数学模型为:gcd(a,b)=gcd(b,a)/gcd为求(a,b)的最大公因子的函数,其中abgcd(a,b)=gcd(b,a%
2、b)/%为取模运算,求a除b的余数 =gcd(b,0)/当a%b=0时,b为(a,b)的最大公因子第一章第一章第一章第一章 算法引论算法引论算法引论算法引论什么是算法?什么是算法?它是一组它是一组有穷规则有穷规则的集合,它规定了解决某一的集合,它规定了解决某一 特定类特定类型问题的一系列运算。型问题的一系列运算。Gcd(int a,int b)/a,bN+1 if a b2 then swap(a,b);/交换a和b,保证a比b大3 n a%b;/a和b取余4 while n05 do a b;6 b n;7 n a%b;8 return b;第一章第一章第一章第一章 算法引论算法引论算法引论
3、算法引论二、算法的特征二、算法的特征 1 1、确定性、确定性 2 2、能行性、能行性 3 3、输入、输入 4 4、输出、输出 5 5、有穷性、有穷性:一个算法总是在有限步之后结束,且每一步一个算法总是在有限步之后结束,且每一步都可在有穷时间内完成都可在有穷时间内完成.算法与程序的区别:算法与程序的区别:程序:与某种语言有关,能直接在机器上运行。程序:与某种语言有关,能直接在机器上运行。算法:与特定的语言无关,可用任何语言实现算法:与特定的语言无关,可用任何语言实现 ,甚至,甚至可以用自然语言实现,但是一般为了避免二义性,本书可以用自然语言实现,但是一般为了避免二义性,本书采用类采用类C C语言
4、描述。语言描述。第一章第一章第一章第一章 算法引论算法引论算法引论算法引论 一个算法总是在执行了有穷步骤的运算后终止,否则就一个算法总是在执行了有穷步骤的运算后终止,否则就一个算法总是在执行了有穷步骤的运算后终止,否则就一个算法总是在执行了有穷步骤的运算后终止,否则就是一个计算过程。是一个计算过程。是一个计算过程。是一个计算过程。有穷性与有效性的关系有穷性与有效性的关系:三、评价算法的标准三、评价算法的标准 有穷性是对算法的基本要求,如果一个算法要能使用,有穷性是对算法的基本要求,如果一个算法要能使用,必须具有有效性。有效性是指算法在有效的时间里终止。必须具有有效性。有效性是指算法在有效的时间
5、里终止。时间复杂性和空间复杂性时间复杂性和空间复杂性第一章第一章第一章第一章 算法引论算法引论算法引论算法引论四、本书介绍的内容四、本书介绍的内容 1、如何设计算法:、如何设计算法:2、如何表示算法:类、如何表示算法:类C语言语言(自学自学page 2-5)3、如何确定(或称证明)算法:、如何确定(或称证明)算法:4、如何分析算法:、如何分析算法:5、如何测试算法:作时空分布图、如何测试算法:作时空分布图第一章第一章第一章第一章 算法引论算法引论算法引论算法引论1.2 1.2 算法设计的步骤算法设计的步骤一、问题的描述一、问题的描述例例:货郎担问题货郎担问题 设售货员在一天内要到设售货员在一天
6、内要到5 5个城市去推销货物,已知从一个个城市去推销货物,已知从一个城市到其他城市的费用,求总费用最少的路线。给出的城市到其他城市的费用,求总费用最少的路线。给出的信息主要有五个城市的关系图及相应的费用矩阵。信息主要有五个城市的关系图及相应的费用矩阵。二、模型的拟制二、模型的拟制 建模阶段至少要考虑以下两个基本问题:建模阶段至少要考虑以下两个基本问题:1 1)最适合于这个问题的数学结构是什么?)最适合于这个问题的数学结构是什么?2 2)有没有已经解决了的类似问题可供借鉴?)有没有已经解决了的类似问题可供借鉴?第一章第一章第一章第一章 算法引论算法引论算法引论算法引论 在模型建立好了以后,应该依
7、据所选定的模型对在模型建立好了以后,应该依据所选定的模型对问题重新陈述问题重新陈述,并考虑下列问题并考虑下列问题:(1)(1)模型是否清楚地表达了与问题有关的所有重要模型是否清楚地表达了与问题有关的所有重要的信息的信息?(2)(2)模型中是否存在与要求的结果相关的数学量模型中是否存在与要求的结果相关的数学量?(3)(3)模型是否正确反映了输入、输出的关系模型是否正确反映了输入、输出的关系?(4)(4)对这个模型处理起来困难吗?对这个模型处理起来困难吗?第一章第一章第一章第一章 算法引论算法引论算法引论算法引论152434724335211 对于货郎担问题,其数学模型是带权图,与此图相关的对于货
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 引论
限制150内