算法及其设计基础.pptVIP

第1章 算法及其设计基础 教学目的和要求 了解算法描述的基本要求和目的，掌握用自 然语言方式、流程图方式、盒图(N-S图)、 伪代 码方式、PAD图方式和计算机语言方式来描述一 个算法。 重点： 流程图方式、盒图(N-S图)、PAD图方式。 难点： 完整地用盒图(N-S图)来描述一个算法。 1.1 引言 程序设计方法首先强调的是设计，其次 才是实现（写出程序代码）。其核心是将程 序设计过程分为两部分。 第一部分集中于问题及其解法或算法，与 任何特定的计算机或计算机语言无关。 第二部分集中于选择某一种程序设计语言 ，把算法表达给特定的计算机。 1.2 算法的概念 广义地说，为解决一个问题而采取的方 法和步骤，就称为“算法”。 你想查看计算机CPU，首先必须将计算机断 电，拆除连线，打开机箱，然后按下夹子解 除夹口，最后取出CPU进行查看。 复制文件，首先要寻找所要复制的文件， 然后选中，再进行复制，最后移动到需要的 地方进行粘贴。 计算机算法的分类： 本书所讲述的算法只限于计算机算法，即计算机 能执行的算法。在设计一个计算机算法时，应当考 虑到计算机能否执行。 计算机算法可分为两大类别：数值运算算法和非 数值运算算法。 数值运算的目的是求数值解，例如求方程的根， 求一个函数的定积分等，都属于数值运算范围。 非数值运算包括的面十分广泛，最常见的是用于 事务管理领域，例如图书检索、人事管理等。目前 ，计算机在非数值运算方面的应用远远超过了在数 值运算方面的应用。 1.3 算法的特性 一个算法应该具有以下几个特性： 1)有穷性 n确定性 n输入 n输出 n有效性 1.3 算法的特性 1）有穷性 一个算法应包含有限的操作步骤，而不 能是无限的。 但是要注意，“有穷性”往往指“在合 理的范围之内”。如果让计算机执行一个历 时几百年才结束的算法，这虽然是有穷的， 但超过了合理的限度，人们也不把它视做有 效算法。究竟什么算“合理限度”，并无严 格标准，由人们的常识和需要而定。 n确定性 算法中的每一个步骤，必须是确切定义的，而 不应当含糊不清或模棱两可的。即算法的含义应当 是唯一的，而不应当产生“歧义性”。 例如，某人只说请您“复制文件”或查看计算 机的CPU，是不确定的，因为此人没有说明复制哪一 个文件或查看哪一台计算机的CPU。 1.3 算法的特性 n输入 所谓输入是指在执行算法时需要从外界取得必 要的信息。 例如，让计算机来完成“将N个正数按从小到 大的次序排列”时，就需要输入N个正整数。一个算 法可以有多个输入，也可以没有输入。 1.3 算法的特性 n输出 算法执行过程中往往会产生一些数据 ，它们在算法执行之后被保存下来或传递 给算法的调用者，这些数据被称为算法的 输出。 一个算法可以有多个输出，没有输 出的算法是没有意义的。 例如，计算机来完成“将N个整数按 从小到大的次序排列”的算法时，输出的 整数将是一组“从小到大的次序排列的N个 整数”。 1.3 算法的特性 n有效性 一个算法应该是具有现实意义的，如 果算法中含有不能实现的某一个步骤，则这 个所谓的“算法”无法解决问题，因此，不 能称为算法。 算法贯穿于程序设计的始终，希望读者 对算法给予很大的重视，在解决一个问题之 前应当首先构造出一个好的算法。在本书各 章中都贯穿这一原则。 1.3 算法的特性 1.4 算法的结构 1966年，计算机科学家Bohm和Jacopini 的研究表明，任何简单或复杂的算法都可以 由下述3种基本控制结构组成。 1）顺序结构 2) 选择结构 3) 循环结构 1）顺序结构 这是最简单的一种基本结构。顺序结构中的各个 部分是按书写顺序依次执行的。例如某个算法中可 能出现下列形式的一组操作： 操作 1 操作 2 操作 3 如果这样一组操作的执行顺序与操作出现的前后 顺序相同，即先进行“操作1”，然后进行“操作 2”，再后进行“操作3”，那么这段算法的结构就 是顺序结构。 2) 选择结构 这种结构也称为分支结构，它表示操作的处理步 骤出现了分支，它需要根据某一特定的条件选择其 中的一个分支执行。例如下述算法描述片段： 如果 成立 则执行 否则执行 和 之间构成了一种选择关系 ，两个操作中哪一个将被执行是通过对 的 判断来控制的。 3) 循环结构 循环结构是指被重复执行的一个操作集合 。例如下述算法描述片段： 重复执行 直到 不成立 这段描述指出 将被反复运行多 次，直到 不成立为止。 注意： 通过上述三种基本控制结构可以看到， 它们有一个共同的特点，即：只有一个入口 且只有一个出口，并且操作不会出现死循环 。 1.5 算法的描述 算法的描述具有重要意义，描述一个算法的目的 在于使其他人能够利用算法解决具体问题。 算法的描述方式没有统一规定，本书书将介绍绍常 用的自然语语言、流程图图、N-S图图、PAD图图、伪伪代码码以 及计计算机语语言等六种描述算法的方式。 注意： 不论是哪类方式，对它们的基本要求都是能提供 对算法的无歧义的描述，以便使我们能够将这种描 述很容易转换成计算机高级语言（程序）。 1.5.1 自然语言方式 自然语言就是人们日常使用的语言，可 以是汉语、英语或其他任何形式的语言。 算法可以表示如下： 第1步 使sign=1（sign代表数值的符号） 第2步 使sum1（sum代表累加和变量） 第3步 使deno=2（deno代表分母变量） 第4步 sign(-1)*sign（求级数中各项的符号，它的值为l或- 1） 第5步 termsign*(1/deno) （term代表级数中的某一项） 第6步 sum=sum+term 第7步 deno=deno+l 第8步 若deno20，转去执行第4步以及其后的各个步骤；否则 执行第9步 第9步 打印sum的值（即所求之总和） 第10步 算法结束 例1.1 求 例1.2 用选择排序法，将N个正整数数列按照从小到大 的顺序排列。 选择排序法基本思想：在选择排序方法中，第 一步在N个元素中选出最小元素，将其与第一个元 素交换。第二步从剩下的N-1个元素中选出最小元素 ，将其与第二个元素交换，如此下去，直到剩下最 后两个元素。 输入：将N个正整数放置在数组aN中。 第1步 使i=1 第2步 若i (2) 分支结构 有以下两种书写格式： 格式1： if() then else 格式2： if() then 多重选择的格式如下： ，执行 ，执行 ，执行 （3）循环结构 有以下三种书写格式： 格式l：do while() 格式2：while() do 格式3：for to 步长 4) 调用算法 书写方式如下： 调用() 5) 需要标明算法的“BEGIN(开始)”和“END(结束)” 点。 例1.9 求 BEGIN sign=1（sign代表数值的符号） sum=1（sum代表累加和变量） deno=2（deno代表分母变量） while deno20 sign=(-1)*sign（求级数中各项的符号,它的值为l或-1） term=sign*1/deno（term代表级数中的某一项） sum=sum+term deno=deno+1 print sum（所求之总和） END 例1.10 将N个正整数数列按照从小到大的顺序排列。 BEGIN for i=1 to N-1 (每循环一次在未排序元素中找出一个最小的元素进行排序) k=i for j=i+1 to N（查找未排序元素中的最小的元素） if( aj #define N 6 main() int i,j,t,exchange; int aN+1; /* aN用于存放 */ printf(“input %d number:“,N); for(i=0;iaj+1) /* 顺序不符合要求时交换位置 */ t=aj; aj=aj+1; aj+1=t; exchange=1; if (!exchange) break; /* 若所有的元素都已排好序，则退出循环 */ for(i=0;iN;i+) printf(“%4d“,ai); printf(“n“); 程序运行结果： input 6 number: 6 8 4 7 2 5 6 8 4 7 2 5 2 4 5 6 7 8 1.7.2 查找算法及其实现 在处理大量数据时，经常要按某种 方法找出所需的数据，这个过程称为查 找。 例如，在学生成绩中查找某位学生 的成绩等。查找方法很多，下面将以例 1.14为例介绍常用的顺序查找法。 例 1.14 编写一个程序，在给定的数组a中查 找用户输入的值，并提示相应的查找结果。 顺序查找法基本思想是：从数组第一个 元素开始，顺序扫描数组，依次将扫描元素 和给定值x相比较，若当前扫描元素与x相等 ，则查找成功；若扫描结束后，仍未找到等 于x的元素，则查找失败。 例 1.14 编写一个程序，在给定的数组a中查找用户输入的值， 并提示相应的查找结果。 #define N 10 main() int a=6,3,9,8,1,5,4,10,2,7; int i=0,x; printf(“input x=“); scanf(“%d“, while(iN if(iN) printf(“find %d it position is :a%d=%dn“,x,i,x); else printf(“%d not been foundn“,x); 程序运行结果： input x=8 find 8 it position is :a3=8 input x=99 99 not been found 1.7.3 穷举算法及其实现 在循环算法中，穷举法是具有代表性 的基本算法，穷举的基本思想是，对问题 的所有可能状态一一测试，直到找到解或 将全部可能状态都测试过为止。 例 1.15 编写一个程序，求这样四位数：该四位数的千位上的 数字和百位上的数字都被擦掉了，知道十位上的数字是1，个 位上的数字是2，又知道这个数如果减去7就能被7整除，减去8 就能被8整除，减去9就能被9整除。 设这个数为n=abl2，则n=lOOO*a+lOO*b+lO+2，且有0a9 ，0b9。 main() int n,a,b; for(a=1;a=9;a+) for(b=0;b=9;b+) n=1000*a+100*b+10+2; if(n-7)%7=0 break; 程序运行结果： n=1512 本 章 小 结 按照现代编程的要求，评价一个程序时，除了要 求程序的正确性和有效性以外，还要求程序具有简 明性、可读性、可靠性、可修改性和可重用性等。 因此，要实现这些要求，选择什么样的算法和如何 正确描述所选择的算法，就成为实现程序过程中最 重要的一个课题。本书在编程时力求在每个程序实 例中体现这些要求，这也是学习和掌握本书内容的 基本观点。 基于上述观点，本章主要介绍了算法的基本概念，算 法的特性、算法的结构、算法的描述方式，同时介 绍了几种典型的常用算法，这些算法有一定的使用 价值，但更重要的是为了使初学者容易理解算法， 从而逐步掌握根据算法编写程序的方法。 本章要求：重点掌握算法的描述方式，理解算法 、算法的特性和算法的结构等基本概念，了解并能 够使用排序、查找和穷举等几种典型的常用算法。 习 题 1.1 什么是算法？算法的5个特性是什么？算法与程序的区别是什么？ 1.2 任何简单或复杂的算法都可以由哪3种基本控制结构组成？ 1.3 分别用自然语言方式、流程图方式、N-S图方式、PAD图方式、伪代码方式、计算机语言方式描述，求10！ 的算法。 1.4 用流程图描述，求 的算法。 1.5 用N-S图描述，在一组整数中求最大数问题 的算法。 1.6 用PAD图描述，求解一元二次方程 实数解的算法。 提示：一元二次方程实数解具有一个普遍的形式，即 。该公式成立的条件是 ， 且只有当 才能有实数解。 1.7 用伪代码描述，将20003000年中所有的闰年年份输出的算法。 提示：年号能被4整除，但不能被100整除的是闰年。 年号能被4、100、400同时整除的也是闰年。 1.8 用计算机语言描述，利用下面级数求的值的算法。 1.9 对下列10