必威体育精装版计算机第10章程序设计基础研究.ppt

第10章 程序设计基础 10.1 程序设计的概念 10.2 算法 10.3 程序设计语言 10.4 程序设计方法 10.1 程序设计的概念 程序：是解题方法和步骤的描述，是供计算机执行并能完成特定功能的指令序列。 程序的核心：数据结构和算法。 程序设计（Programming）：先对问题进行分析并建立数学模型，然后考虑数据的组织方式和算法，并用某一种程序设计语言编写程序，最后调试程序，使之运行后能产生预期的结果。 程序设计的基本步骤：(1)分析问题，确定数学模型或方法。(2)设计算法，画出流程图。(3)选择编程工具，按算法编写程序。(4)调试程序，分析输出结果。 10.2 算 法 10.2.1 算法的概念计算机解决问题的方法和步骤，就是计算机解题的算法(Algorithm)。算法举例：（1） 将两个变量的值互换 。 （2）欧几里德（Euclid）算法求两个正整数m和n的最大公约数。 （3）非数值计算算法：有9枚铜币，其中有1枚略轻的是假币，用一台没有砝码的天平将假币找出来，应怎样找称 。  　10.2.2 算法的特性(1) 有穷性。算法中执行的步骤总是有限次数的，不能无止境地执行下去。(2) 确定性。算法中的每一步操作必须具有确切的含义，不能有二义性。(3) 有效性。算法中的每一步操作必须是可执行的。(4) 要有数据输入。算法中操作的对象是数据，因此应提供有关数据。(5) 要有结果输出。 10.2.3 算法的评价1．算法评价标准 　（1）正确性。（2）可读性。（3）通用性。（4）高效率。2. 算法效率的度量（1）时间度量（2）空间度量 10.2.4 算法的描述 　1. 用传统的流程图描述算法 2. 用结构化流程图描述算法（1）程序的三种基本结构：顺序结构、选择结构和循环结构。（2）结构化流程图（N-S图） 10.2.5 算法示例 　1．迭代算法 迭代是一种建立在循环基础上的算法。在数学中，迭代经常被用来进行数值计算，例如求方程的解，不断用变量原来的值递推求新的值的过程。 讨论求若干个数之和或乘积的问题。 10.2.5 算法示例 　1．迭代算法 迭代是一种建立在循环基础上的算法。在数学中，迭代经常被用来进行数值计算，例如求方程的解，不断用变量原来的值递推求新的值的过程。 讨论求若干个数之和或乘积的问题。 　2．穷举算法 穷举法也叫枚举法，它的基本思路是对众多可能解，按某种顺序进行逐一枚举和检验，并从中找出那些符合要求的可能解，作为问题的解。穷举的计算量是相当大的，但对于计算机来说，做起来很容易。穷举算法是一种重要的算法设计策略，可以说是计算机解题的一大特点。 求方程x+2y+5z=100的整数解。 　3．排序算法所谓排序，就是将一组数据元素按照某个关键字递增或递减的次序排列起来。（1）选择排序(Selection Sort)选择排序法的实现过程是：首先找出表中关键字最小的元素，将其与第一个元素进行交换，然后，再在其余元素中找出关键字最小的元素，将其与第二个元素进行交换。依次类推，直到将表中所有关键字按由小到大的顺序排列好为止。 　 （2）冒泡排序(Bubble Sort) 　冒泡法排序法是每趟将相邻的两个数两两进行比较，若满足升序次序，则进行下一次比较，若不满足升序次序，则交换这两个数，直到最后。总的比较次数为n-1次，此时最后的元素为最大数，此为一趟排序。接着进行第二趟排序，方法同前，只是这次最后一个元素不再参与比较，比较次数为n-2次，依次类推。 　 4．查找算法 　查找是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素，若表中存在这样的数据元素，称此查找是成功的。若表中不存在关键字等于给定值的数据元素，称此查找是不成功的。（1）顺序查找顺序查找是最常用的查找方法，其查找过程为：从第一个元素起，逐个将给定值与数据元素的关键字进行比较，若某个元素的关键字与给定值相等，则认为查找是成功的，否则，查找失败。 （2）折半查找 　　作为折半查找的表必须是顺序存储的有序表，即表采用顺序结构存储，表中的元素按关键字值递增（或递减）排列。　　假设表中的关键字值递增排列，则折半查找的实现方法是：首先取整个有序表的中间元素Am的关键字同给定值x比较，若相等，则查找成功；否则，若Am的关键字小于x，则说明待查元素只可能落在表的后半部分中，接着只要在表的后半部分子表中查找即可；若 Am的关键字大于x，则说明待查元素只可能落在表的前半部分中，接着只要在表的前半部分子表中查找即可。这样，经过一次关键字的比较，就缩小一半的查找空间，重复进行下去，直到找到关键字为