文档介绍：第 第10 10章 章 程序设计基础 程序设计基础 ?程序设计的概念程序: 指计算机完成特定功能的指令的集合,是解 题方法和步骤的描述。 。主要描述两部分问题: 描述 问题的每个对象和对象之间的关系及对对象的处理 规则。 程序的核心:数据结构和算法。 程序设计( Programming):先对问题进行分析并建 立数学模型(对数值计算问题)或提出对数据处理 的需求( 对非数据计算问题),然后进行算法的设 计,并用某一种程序设计语言编写程序,最后调试 程序,使之运行后能产生预期的结果。程序设计的基本步骤: ?分析问题,确定数学模型或方法。明确要准备解 决的问题,确定好编程目标,定义好需要输入的 数据和想要得到的输出结果。 ?设计算法,画出流程图。 ?选择编程工具, 按算法编写程序。 ?调试程序,分析输出结果。程序设计的执行 ?编辑程序: 创建计算机源程序文件 ?编译程序: 对程序源代码进行语法分析,代码生 成,从而产生目标代码文件,其扩展名为 OBJ, 同时表明源程序无语法错误。 ?链接程序: 将目标文件和系统提供的函数链接起 来产生可执行文件,其扩展名为 EXE。 ?运行程序 法 ,是一组明确的可 以执行的步骤的有序集合。 算法举例: 例10-1:欧几里德(E uclid)算法求两个正整数m 和n 的最大公约数。例10-2输入1 0个数,要求找出其中最大的数。例10 -1算法(辗转相除法) 步骤如下: 1)比较 m和n的大小,把大数放在 m,把 小数放在 n中; 2)用 m除以n,余数存于 r;若r等于 0,则 n就是最大公约数,输出 n; 3)否则, 将n赋值给m,r赋值给 n,返回 到第 2步。例10 -2算法: 1)?输入一个数,放在存储单元 max 中。 2)?设置用来统计比较次数的单元 i,初始值为1。 3)?若i<=9,做第 4)步,否则做第 8)步。 4)?输入一个数,放在存储单元 x中。 5)?比较 max 和x中的数,若 x>m ax,则将x的值送给 max ,否则,max 值不变。 6)?i增加 1。 7)?返回到第 3)步。 8)?输出 max 中的数, 此时 max 中的数就是10个数中 最大的数 ?有穷性: 算法中执行的步骤总是有限次数的, 不能 无止境地执行下去。 ?确定性: 算法中的每一步操作必须具有确切的含 义,不能有二义性。 ?有效性: 算法中的每一步操作必须是可执行的。 ?输入:算法中操作的对象是数据, 因此应提供有关 数据。 ?输出:一个算法要有输出, 以反映输入数据加工后 的结果, 没有输出的算法是毫无意义的。 ?正确性运行结果正确 ?可读性指算法的简单性 ?通用性适用一类问题的求解 ?高效率时间与空间算法效率的度量 ?时间度量:执行一种简单操作所需的平均时间与 进行简单操作的次数的乘积。通常把算法中包含 简单操作的次数的多少称为算法的时间复杂度 。 ?空间度量:主要考虑在算法运行过程中临时占用 的存储空间,称为算法的空间复杂度。 算法的描述常用流程图、 N-S图、伪代码等 1.?用传统的流程图描述算法:通过流程线、几何图形、 文字说明来描述算法。 2.?用N-S图描述算法 ?程序的三种基本结构: 顺序结构、选择结构和循环 结构。 ?结构化流程图(N-S图) 3.?用伪代码描述算法: 伪代码是介于自然语言和高级语 言之间的一种文字和符号描述工具,它不涉及图形, 而是结合某种高级语言一行一行、自上而下描述算法。