[C程序设计]电子教案--CH02--算法.pptVIP

* 算法的概念 算法的表示 结构化程序设计方法 第二章 程序的灵魂—算法 2.1 算法的概念和特性 算法的概念 简单算法举例 算法的特性 算法，就是为解决一个问题而采取的方法和步骤。 算法的概念 一个程序应包括以下两方面的内容： ⑴ 对数据的描述。在程序中要指定数据的类型和数据的组织形式，即数据结构（data structure） ⑵ 对操作的描述。即操作步骤，也就是算法（algorithm）。 数据结构 ＋ 算法 ＝ 程序 对于同一个问题可能存在着不同的解决方法和步骤，也就是说有不同的算法。所以确定算法时，在保证正确有效的前提下，应该尽量提高算法的效率和质量。 计算机算法：数值算法（如解方程）、非数值算法（如排序） 算法１：直接写一个乘法表达式来计算 S1：prod=1×2 ×3×4×5 简单算法举例 例：求 1×2 ×3×4×5 这个算法的结果虽然是正确的，但是这样的解决方法和步骤显然不是有效合理的:如果是10000个数相乘怎么写？！ 算法２：利用编程语言中“变量”的概念，每次计算一个乘法并把结果保存在该变量中，下次再用这个变量去乘下一个数 S1：prod=1 S2：prod=prod×2 S3：prod=prod×3 S4：prod=prod×4 S5：prod=prod×5 简单算法举例 例：求 1×2 ×3×4×5 这个算法的结果也是正确的，比算法１进了一步，使用变量，把问题描述为对变量的基本相同的重复处理。但是仍然不是有效合理的，每一次处理都要一行程序，如果是10000个自然数相乘呢。关键在于没有把重复的基本相同的工作, 描述为重复的完全相同的工作，如果把1，2，3，4这些数字也用变量n来表示, prod=prod×n,每次处理作的工作就完全相同，处理还是10000次，处理工作可以用一行程序来描述 算法３：利用“变量”的概念的同时，再利用“循环”的解决方法，可以实现真正的计算机算法 S1：prod=1 S2：n=1 S3：prod=prod×n S4：n=n+1 S5：如果n≤5，则返回到S3；否则，结束 简单算法举例 例：求 1×2 ×3×4×5 这个算法具有通用性、灵活性。而且所有计算机语言都有实现“循环”的控制语句，因此这个算法是有效的正确的算法。 求班上学生(30人)一门课的总成绩 把30个成绩依次存储到”数组”A中,A[1]表示第1个学生的成绩, A[2]表示第2个学生成绩,….,下标变量A[n]表示第n个学生的成绩 S2:总分=总分+A[n] 实现了加入每个学生成绩时是作的重复的完全相同的处理 循环和数组,是程序的基础 S1: 总分=0, n=1 S2: 总分=总分+第n个学生的成绩 S3: n=n+1 S4: n=30 ?是,转S2;否,转S5 S5: 结束 与前例不同,参与运算的30个数(成绩)无规则可循.不可能表示成一个简单变量. 在求总分时如何实现 “重复的完全相同的”处理? 算法的特性 一个算法应具有以下特点： ⑴ 有穷性：一个算法的步骤必须是合理有限的 ⑵ 确定性：算法中的每一个步骤应当是确定的，而不应该是含糊的、模棱两可的 ⑶ 有零个或多个输入：执行算法是需从外界取得必要的信息 ⑷ 有一个或多个输出：执行一个算法后应该有必要的结果 ⑸ 有效性：算法中的每一个步骤都必须是能有效成立和有效执行，并得到确定结果的。 1.1.3 算法的五大特性 1 输入 接受n=0个外部输入 2 输出 至少有一个输出 3 有穷性 有结束 4 确定性 指令清晰 5 有效性 指令可执行 以累加10个1的算法为例 不正确的算法 (无结束) 第一步 开始 第二步 N=0 第三步 N=N+1 第四步 转第三步 第五步 结束 不正确的算法 (指令不清晰 ) 第一步 开始 第二步 N=0 第三步 N=N+1 第四步 根据N值 转第三步或第五步 第五步 结束 正确的算法 第一步 开始 第二步 N=0 第三步 N=N+1 第四步 N9 转第五步 否则转第三步 第五步 结束 2.2 算法的表示 自然语言 流程图 伪代码 计算机语言 用自然语言表示算法 自然语言就是人们日常使用的语言，可以是英语、汉语