Lesson 2(c语言算法).ppt

第 二 章 程序的灵魂---算法 算法的表示 一、算法在程序中的地位 一个程序应包括的两个方面： （1）对数据的描述 在程序中要指定数据的类型和数据的组织形式，即数据结构。 （2）对操作的描述 即操作方法与步骤，也即算法。 数据和操作的关系： 数据是操作的对象，操作的目的是对数据进行加工，以得到期望的结果。 数据结构 + 算法 = 程序 程序与算法的联系： 程序中按一定顺序列出的操作语句，就是算法的体现。 二、算法的定义 算法的概念：用计算机解决问题的方法和步骤 算法的5个特性： 有穷性(有限的操作步骤) 确定性(每一步骤是确定的，不应产生“歧义性”) 有零个或多个输入 有一个或多个输出 有效性 三、算法的表示 用自然语言表示 用流程图表示（传统流程图和N-S结构图） 用计算机语言表示 结构化程序的三种基本结构： 顺序、选择、循环结构 用流程图表示算法: 流程图采用一些图形框表示算法要表述的各种操作。 美国国家标准化协会ANSI规定了一些常用的流程图符号： 起止框 处理框 输入输出框 流程线 或 判断框 连接点 举例：算法用流程图来表示 举例：算法用c语言表示: #include stdio.h void main() { int p,i; p=1, i=1; while(i=11) { p=p*i; i=i+2; } } 结构化程序的三种基本结构（1） 顺序结构： 结构化程序的三种基本结构（2） 选择结构 结构化程序的三种基本结构（3） 循环结构（当型---while型） 结构化程序的三种基本结构（4） 循环结构（直到型do-while/until型） 四 、结构化程序设计方法 三种基本结构的共同点： 一个入口； 一个出口； 结构内每一部分都有机会被执行(即对每一个框而言，都应有一条从入口到出口的路径通过它)。 结构内不存在“死循环”。(如条件永远成立时，就成了“死循环”) 已经证明，用上述三种基本结构顺序组成的算法结构，可以解决任何复杂的问题。 由基本结构构成的算法属于结构化的算法 对前述算法的流程图的结构化分析 五、用N-S流程图表示算法 用基本结构的顺序组合可表示任何复杂的算法，因此结构之间的流程线是多余的(去掉流程线,避免随意的跳转)。 1973年两名美国学者提出了一种新的流程图形式，并用二人名字的第一个字母组合命名了该流程图。即N-S流程图，也称盒图。 三种基本结构的表示： 前面的算法用N-S流程图来表示 习题： 开始 结束 计算1 x 3 x 5 x…x11的值 步骤1：令p=1 步骤2：令i=1 步骤3：使p x i,并将乘积放入p中。通常表示为p x i →p 步骤4：使 i 的值加2，表示为 i+ 2 → i 步骤5：如果i 不大于11，返回到步骤3继续向下执行；否则算法结束。p中的值即最后结果。 开始 1→p 1→i p× i→p i+2→i i≤11 真 结束 假 输出p的值 B A 虚线框内是一个顺序结构。 AB两个框是顺序执行的： 按图中所画的框的顺序，先执行A操作，再执行B操作。 也称分支结构。 虚线框内是一个选择结构。 此结构包括一个选择框，框中写有一个条件，根据给定的条件是否成立，从而选择执行A框还是B框。 例如：条件可以是i≤101 条件P A B 成立 不成立 条件P A 成立 不成立 B操作为空时，画成直线 虚线框内是一个当型循环结构。 当给定的条件成立时，执行A框中的操作； 执行完A操作后，判条件P是否成立； 如果仍成立，继续执行A操作； 如此反复执行A框中的操作，直到条件P不成立为止。 条件P A 成立 不成立 条件P A 成立 不成立 虚线框内是一个直到型循环结构。 先执行A框中的操作； 执行完A操作后，判条件P是否成立；