第2章程序的设计与算法.pptVIP

思考并试做作业： 思考并练习本章书后习题，试着画出算法的流程图。 * * 算法和程序设计 （一）程序的基本组成: 输入、处理和输出 （二）算法和编程工具 科学技术的进步，社会生产力的发展，都是由于相关的问题得到不断的解决的结果。在当今社会中，由于信息化概念的提出，许多问题的解决都使用到了电子计算机。人们解决问题一般使用到以下两种方法： 1、人工解题 2、计算机解题 人工解题的步骤： 1.理解和分析所面临的问题 2.寻找解题的途径和方法 3.用笔、纸和计算器等工具进行计算 4.验证计算结果 计算机解题的步骤： 1、理解和分析所要求解决的问题 2、寻找解题的途径和方法 3、生成解题算法 4、选用一种编程语言根据算法编写程序 5、通过编辑、编译、连接产生计算机能够识别的指令序列 6、在计算机上执行该指令序列 相同点：无论何种解题方式，在解决某一实际问题时，都应该正确的理解问题的题意，从看似复杂的问题中整理出一个头绪，然后通过算法（即解决问题的一个一个步骤）描述出某一问题的解决过程，进行一定量的计算，最后都必须验证计算结果。 不同点：当计算量较大时，人工解题就有点力不从心了，而计算机上亿次的每秒计算速度却不在话下，并且只要算法正确，编程语句无误的话，使用计算机编写的解题程序可以反复使用。 例如：sum=1+2+3+4+………… + n 使用计算机解题前，需要将解题方法转换成一系列具体的在计算机上可执行的步骤，这些步骤能够清楚的反映解题方法一步步“怎么做”的过程，这个过程就是通常所说的算法。 算法及算法的表示 算法概述 什么是算法： 广义地讲：算法是为完成一项任务所应当遵循的一步一步的规则的、精确的、无歧义的描述，它的总步数是有限的。 狭义地讲：算法是解决一个问题采取的方法和步骤的描述。 下面通过两个简单的例子加以说明： 例1 输入三个数，然后输出其中最大的数。 将三个数依次输入到变量Ａ、B、C中，设变量MAX存放最大数。其算法如下： 例2 输入10个数，打印输出其中最大的数。 算法设计如下： （1）输入1个数,存入变量A中,将记录数据个数的变量N赋值为1，即N=1 （2）将A存入表示最大值的变量Max中，即Max=A （3）再输入一个值给A，如果AMax 则 Max=A, 否则Max不变 （4）让记录数据个数的变量增加1，即N=N+1 （5）判断N是否小于10，若成立则转到第（3）步执行，否则转到第（6）步。 （6）打印输出max 1) 输入A、B、C。 2) A与B中大的一个放入MAX中。 3) 把C与MAX中大的一个放入MAX中。 4) 输出MAX，MAX即为最大数。 有穷性（有限性） 确定性（唯一性） 能行性（可行性） 有0到多个输入 有1到多个输出 第一种：使用自然语言表示算法 第二种：使用流程图表示算法 第三种：使用伪代码表示算法 一、使用自然语言描述下列问题： Sum=1+2+3+4+………………+ n ① 确定一个n 的值； ② 假设等号右边的算式项中的初始值 i 为1； ③ 假设sum的初始值为0； ④ 如果 i ≤n 时，执行⑤，否则转出执行⑧； ⑥ 计算 i 加1，然后将值重新赋值给 i ； ⑤ 计算sum加上 i 的值后，重新赋值给sum； ⑦ 转去执行④； ⑧ 输出sum 的值，算法结束。 循环体语句 容易产生二义性 所用语句描述算法过于冗长 所用语句都是顺序排列，对算法中的构成的分支、循环结构描述不是很方便。 为了解决这些问题，我们引入了第二种表示算法的方法——流程图。 开始结束符 表示算法的开始和结束。 输入输出符 表示算法过程中，从外部获取的信息（输入），然后将处理过的信息输出。 处 理 框 表示算法过程中，需要处理的内容，只有一个入口和一个出口。 判 断 框 表示算法过程中的分支结构，菱形框的4个顶点中，通常用上面的顶点表示入口，根据需要用其余的顶点表示出口。 算法过程中的指向流程的方向。 二、使用流程图描述下列问题： Sum=1+2+3+4+………+ n 开 始 输入 n 的值 i ←1 ； sum ←0 i = n Yes sum ←sum + i i ← i + 1 No 输出sum 的值 结 束 流程图的缺点是在标准中没有规定流程线的用法，因为流程线能够指出流程控制方向，即算法步骤中的次序。在早期的程序设计中，曾经由于滥用流程线的转移而导致了可怕的“软件危机”，震动了整个软件业，并展开了关于“转移”用法的大讨论，从而产生了计算机科学的一个新的分支学科——程序设计方法。 无论是使用自然语言还是使用流程图描述算法，仅仅是表述