第02章_算法.pptVIP

第二章 程序的灵魂--算法 程序设计概述 一个程序应包括： 程序设计概述 2．对数据处理的描述，即计算机算法。算法是为解决一个问题而采取的方法和步骤，是灵魂，是解决“做什么”、“怎么做” 。 2.1 算法的概念 算法: 是指解决一个具体问题的意义明确的步骤的集合。是有限的. 概括地说，算法是指解题方案的准确而完整的描述。从程序来说，也可以说算法是一个有限条指令的集合，这些指令确定了解决某一特定类型问题的运算序列。 2.2 简单算法举例 算法： ⑴ a → t ⑵ b → a ⑶ t → b (1) max ← a1 (2) 如果a2max 则 max← a2, 否则max不变 如果a3max 则 max← a3, 否则max不变 ………………… 如果a10max 则 max← a10, 否则max不变 (3) 打印max （1）先求1×2，得到结果2； （2）将步骤1得到的结果再乘以3，得到结果6；（3）将6再乘以4，得到24； （4）将24再乘以5，得到120。 S1:设变量p，代表被乘数，p 1; s2:设变量i，代表乘数，i 2; s3:使p×i，乘积放在被乘数变量p中,可表示为:p×i p; s4:使i的值加1，即i+1 i; s5:如果i不大于5，返回重新执行步骤s3以及其后的s4、s5;否则，算法结束。最后得到的p就是5!的值。 例2: 求1×3×5×7×9 ×11 S1: 1→ i; S2: 如果gi=80,则打印ni和gi,否则不打印。 S3: i+1 → i ; S4: 如果i=50,返回s2,继续执行，否则算法结束。 例4: 求下列级数的值 1+1/2+1/3+1/4+...+1/100 2.3 算法的特性 1、有穷性：一个算法应当包含有限的步骤，而不能是无限的步骤；同时一个算法应当在执行一定数量的步骤后，算法结束，不能死循环。 事实上“有穷性”往往指“在合理的范围之内”的有限步骤。如果让计算机执行一个历时1000年才结束的算法，算法尽管有穷，但超过了合理的限度，人们也不认为此算法是有用的。 3、有0个或多个输入（即可以没有输入,也可以有输入） 所谓输入是指算法执行时从外界获取必要信息。（外界是相对算法本身的，输入可以是人工键盘输入的数据，也可以是程序其它部分传递给算法的数据） 例如：不需要输入任何信息，就可以计算出5！；（0个输入） 例如：如果要计算两个整数的最大公约数，则需要输入2个整数m，n。（2个输入） 2.4 怎样表示一个算法？ 常用的算法表示方法： 1、自然语言：带序号的自然语言描述（例 2.1-例2.5） 易懂却不直观，不严格 2、传统流程图：灵活、自由、形象、直观、可表示任何算法 3、N-S图（盒图）：特点：完全去掉了带箭头的流程线，算法的所有处理 步骤都写在一个大矩形框（表示简单、符合结构化思想） 4、伪代码：用介于自然语言与计算机语言之间的文字及符号来描述算 （方便、易懂、便于向计算机语言过渡） （ 重点：传统流程图、N-S流程图、伪代码 ） 2.5 结构化程序设计方法 一、结构化程序的三种基本结构  1966年提出三种基本结构，用这三中基本结构作为表示一种良好算法的基本单元：顺序、选择、循环 任何复杂的算法都是由这三种基本结构按一定规律组成 （1）顺序结构 按指令的顺序依次执行 （2）选择结构 根据判别条件有选择地改变执行流程 （3）循环结构 有条件的重复地执行某个程序块 (1) 顺序结构程序设计 依次顺序执行程序语句 (2) 选择结构程序设计 首先判别条件，若条件满足，程序执行A；否则，执行B； (3)循环结构程序设计 循环又分“当型循环”和“直到型循环” 0 S单元 1 n单元 S+n S n+1 n 判断n ≤ 100？是，转3；否则，转6 输出S的值 例： 计算5!，写出其算法。 例：给100个整数，打印输出其中的素数 * * 计算机学院 陈明霞 主要内容 2.1 算法的概念 2.2 简单算法举例 2.3 算法的特性 2.4 怎样表示一个算法 2.5 结构化程序设计方法 对数据的描述：数据结构(data structure)