当前位置:文库下载 > c程序设计 谭浩强 第02章课件
免费下载此文档

c程序设计 谭浩强 第02章课件

第2章 2.1 2.3 2.4 2.5 程序的灵魂——算法 算法的概念 算法的特性 怎样表示一个算法 结构化程序设计方法 一个程序应包括以下两方面内容: (1) 对数据的描述。在程序中要指定数据的类型和 数据的组织形式,即数据结构(data structure)。 (2) 对操作的描述。即操作步骤, 也就是算法 (algorithm)。 数据是操作的对象,操作的目的是对数据进行加工 处理,以得到期望的结果。作为程序设计人员,必 须认真考虑和设计数据结构和操作步骤(即算法)。 因此,Pascal之父沃思(Nikiklaus Wirth)提出一 个公式: 数据结构 + 算法 = 程序 实际上,一个程序除了以上两个主要要素之外,还应当采 用结构化程序设计方法进行程序设计,并且用某一种计算机 语言表示。因此,可以这样表示: 程序 = 算法 + 数据结构 + 程序设计方法 + 语言工具和环 境 也就是说,以上4个方面是一个程序设计人员所应具备的知 识。在设计一个程序时要综合运用这几方面的知识。 ? 在这4个方面中,算法是灵魂,数据结构是加工对象,语言 是工具,编程需要采用合适的方法。算法是解决“做什么” 和“怎么做”的问题。程序中的操作语句,实际上就是算法 的体现。显然,不了解算法就谈不上程序设计。 ? 2.1 算 法 的 概 念 问题一:有两个杯子A和B,分别放有酒精和纯净水,试着 将两个杯子中的液体进行互换。 ? 问题二:有三个牧师和三个野人过河,只有一条能装下两 个人的船,在河的任何一方或者船上,如果野人的人数大于 牧师的人数,那么牧师就会有被吃掉的危险。请找出一种安 全的渡河方案。 ①两个野人先过河,一个野人回来; ②再两个野人过河,一个野人回来; ③两个牧师过河,一个野人和一个牧师回来; ④两个牧师过河,一个野人回来; ⑤两个野人过河,一个野人回来; ⑥两个野人过河。 ? 算法是指为解决一个问题而采取的方法和步骤。算法并不 是问题的结果,而是解题的过程和策略。 ? ? ? ? ? 又例:对有序表关键字序

列{5,10,19,21,31,37, 42,48,50,52},查找k为50的记录。 解一:顺序查找,从第1个元素到最后1个元素,逐个进 行比较,直至找到为止。共比较9次 解二:折半查找,算法步骤: step1 首先确定整个查找区间的中间位置,mid = ( left + right )/ 2; step2 用待查关键字值与中间位置的关键字值进行比较: 若相等,则查找成功;若大于,则在后半区域继续进行 二分查找;若小于,则在前半区域继续进行二分查找。 Step3 对确定的缩小区域再按二分公式,重复上述步骤; 最后 得到结果:要么,查找成功,要么,查找失败。 上例共比较3次 对

第1页下一页

免费下载Word文档免费下载:c程序设计 谭浩强 第02章课件

(下载1-37页,共37页)

我要评论

返回顶部