第6讲 算法与数据结构

《第6讲 算法与数据结构》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机软件技术基础TechnologyFundamentalsofComputerSoftware算法与数据结构（1）艾骏01082316413aijun@buaa.edu.cn十四系011教研室1本课内容•基本概念•算法与建模•算法的优劣•常用算法2算法与数据结构概述设计程序首先要研究要解决的问题，提出适当的计算模型并列出解决问题的方法和步骤。模型一旦建立起来，就要选择合适的算法，并将解题步骤表述出来；同时需要确定合适的数据结构本章着重讨论解决问题的核心--算法以及算法的处理对象--数据的结构3农夫过河–一个农夫带着一只狼、一只羊和一棵白菜，身处河南岸

2、，要把东西全部运到北岸。约束条件是只有一条能容下他和一件物品的小船，只有农夫能撑船。不能单独留下羊和白菜，也不能单独留下羊和狼，狼不爱吃白菜。4农夫过河算法•关键是要在渡河的任何一个步骤中，把羊和狼，羊和草分开，才能免受损失•带羊到对岸•带羊到对岸•空手回本岸空手回本岸•带狼到对岸带菜到对岸•带羊回本岸带羊回本岸•带菜到对岸带狼到对岸•空手回本岸空手回本岸带羊到对岸•带羊到对岸5由过河得出•引出对算法的一种定义。–所谓算法，是指在使用计算机解题前，需要将解题方法转换成一系列具体的在计算机上可执行的步骤，这些步骤能够清楚的反映解题方法一步步“怎么做”的过程

3、，这个过程就是通常所说的算法。•小知识：算法一词最早起源于公元9世纪的阿拉伯。有一位名叫花拉兹米的阿拉伯数学家，在他的一生中发现了很多求解算术问题的算法，并撰写了《合并与回代》一书，后被翻译成为拉丁文。合并与回代这两个词是指解方程时所用的两个主要过程，后被人简称为“代数学”。6算法解题过程的准确、完整的描述称作解该问题的算法程序就是用计算机语言表述的算法，流程图就是图形化了的算法著名计算机科学家、PASCAL语言发明者N·沃思(NiklausWirth)教授进一步提出如下的著名公式：程序＝算法＋数据结构——不能离开数据结构去抽象地分析程序的算法，也不能脱

4、离算法去孤立地研究程序的数据结构，而只能从算法与数据结构的统一上去认识程序7算法描述语言和编程语言有什么关系算算描法描述述的是程序的计算逻辑，编程语言表达的是程序本体(源代码)。算法描述是灵魂，编程语言包含有灵魂的肉体8算法的表示算法设计一般是由粗到细的过程，一般可以使用下面几种类型的工具描述算法:1.1.自然语言自然语言自然语言描述算法通俗易懂，但它有着难以克服的缺陷：(1)易产生歧义性武松打死老虎你输他赢(2)语句繁琐冗长，很难清楚地表达算法的逻辑流程(3)当今的计算机尚不能处理用自然语言表示的算法9自然语言描述•使用自然语言描述从1开始的连续n个自

5、然数求和的算法•①确定一个n的值；•②假设等号右边的算式项中的初始值i为1；•③假设sum的初始值为0；•④如果i≤n时，执行⑤，否则转出执行⑧；•⑤计算sum加上i的值后，重新赋值给sum；•⑥计算i加1，然后将值重新赋值给i；•⑦转去执行④；•⑧输出sum的值，算法结束。10流程图描述11伪代码描述•1)算法开始；•2)输入n的值；•3)i←1；/*为变量i赋初值*/•4)sum←0；/*为变量sum赋初值*/•5)dowhilei<=n/*当变量i<=n时，执行下面的循环体语句*/•6){sum←sum+i；•7)i←i+1+1；}•8)输出sum

6、的值；•9)算法结束；12算法两要素－1操作••算法的两要素算法的两要素算法由操作与控制结构两要素组成1.操作(1)逻辑运算：“与”“、或”“、非”；(2)算术运算：加、减、乘、除；(3)数据比较：大于、小于、等于、不等于；(4)数据传送：输入、输出、赋值。132.控制结构•算法的控制结构，决定了各操作的执行次序。用流程图可以形象地表示出算法的控制结构•任何复杂的算法都可以用顺序、选择、循环三种控制结构组合而成S1FBBSTS2SS1S2FBS3T(a)(b)(c)(d)14算法的定义算法的定义－－E.Knuth一个算法，就是一个有穷规则的集合，规则规定

7、了解决某类问题的运算序列。它是有穷的、确定的、能行的、并有0到多个输入和1到多个输出。算法的特征：1.算法是由一套计算规则组成的一个过程2.组成算法的规则是确定的、可执行的3.每种算法必须有确定的结果，产生一个或多个输出4.每个算法必须有0个（自动生成初始数）或多个输入5.解答必须在有限步内得到,不能出现“死循环”我们可以得出如下的结论：算法是一个过程，这个过程由一套明确的规则组成，这些规则指定了一个操作的顺序，以便用有限的步骤提供特定类型问题的解答15算法与建模16解题策略从何而来？人工解题步骤计算机解题步骤1、理解和分析所面临的问题1、理解和分析所要

8、解决的问题2、寻找解题的途径和方法2、寻找解题的途径和方法3、用笔、纸和算盘、计