铁道C第3章.ppt

程序设计算法基础 做任何事情都要提前想好进行的步骤，然后再去进行，这样可以避免发生错误。例如烧饭，你必须先淘米，再把米和水放放入锅中，然后开始煮饭。这些步骤都是按顺序进行的，缺一不可，次序错了也不行。对于不同的问题有不同的步骤，对于同一个问题也可以有不同的步骤，在计算机中解决问题的步骤是怎样的呢？怎样表示这些步骤呢？下面先看一个实例。 3.0引例 【引例】求1×2×3×4×5的值 那我们先用原始的方法进行： 步骤1：先求1×2，得到结果2。 步骤2：将步骤1得到的结果乘以3，得到结果6。 步骤3：将6乘以4，得到24。 步骤4：将24乘以5，得到120。 这样的结果虽然是正确的，但是太烦琐，如果要求算1×2×3×……×1000，则要写999个步骤，显然是不可取的。而且每次都要使用上一步骤的数值结果，不大方便。 那我们再使用计算机逻辑的方法算这个题。 S1：使K=1 S2：使W=2 S3：使K×W，乘积仍放在变量K中，可表示K×W→K S4：使W的值加1，即W+1→W S5：如果W不大于5，返回重新执行S3以及其后的步骤S4、S5；否则，算法结束，最后得到的值为5！的值。 3.1 算法的概念 上一节我们了解一个问题的计算机解题过程，也就是算法，那什么是算法呢？在计算机科学中，算法是指描述用计算机解决给定问题的过程，是解题方案的准确而完整的描述。它是在有限步骤内求解某一问题所使用的一组定义明确的规则。算法不等于程序，也不等于计算机方法，算法的设计优于程序的编制。程序设计语言只是一个工具, 只懂得语言的规则并不能保证编制出高质量的程序, 程序设计的关键是设计算法。那一个程序究竟应包括那些内容？ 2.对数据处理的描述，即计算机算法。算法是为解决一个问题而采取的方法和步骤，是程序的灵魂。为此，著名计算机科学家沃思（Niklaus Wirth）提出一个公式： 程序=数据结构+算法 实际上，一个程序除了数据结构和算法外，还必须使用一种计算机语言，并采用结构化方法来表示。故又有如下公式： 程序=数据结构+算法+程序设计方法+语言工具和环境 3.1.1 算法的概念 在日常生活中做任何一件事情，都是按照一定规则，一步一步进行。比如在工厂中修理一部机器，先把零件按一定顺序进行解体，然后，对损坏的部件进行修复，再把各部件按一定法则组装成一部完整机器，它们的工艺流程就是算法；在农村中种庄稼有耕地、播种、育苗、施肥、中耕、收割等各个环节，这些栽培技术也是算法。简单的说,算法就是进行操作的方法和操作步骤。 计算机解决问题的方法和步骤，就是计算机的算法。如科学计算中的数值积分、解线性方程等的计算方法，就是数值计算算法；如用于管理、文字处理、图像图形等的排序、分类、查找，就是非数值计算的算法。 3.1.2 算法举例 【例3-1】判定2000 — 2500年中的每一年是否闰年，将结果输出。 在此算法中，我们只要从2000年到2500年依次判断每一年是否为闰年，如果是闰年就输出该年是闰年，否则输出该年不是闰年。 润年的条件： ①．能被4整除，但不能被100整除的年份； ②．能被100整除，又能被400整除的年份； 设year为被检测的年份，则算法可表示如下： S1：2000→year S2：若year不能被4整除，则输出year“不是闰年”，然后转到S6 S3：若year能被4整除，不能被100整除，则输出year“是闰年”，然后转到S6 S4：若year能被100整除，又能被400整除，输出year“是闰年” 否则输出year“不是闰年”，然后转到S6 S5：输出year“不是闰年”。 S6：year+1→year S7：当year≤2500时, 返回S2继续执行，否则，结束。 【例3-2】对一个大于或等于3的正整数，判断它是不是一个素数。 因为素数是不能被除了自己和1以外的数整除的数是素数，所以在此算法中，我们只要把该数拿来依次除以2到该数减1为止，只要能被其中的一个数整除，打印该数不是素数，否则打印该数为素数。 设输入的数为n，算法可表示如下： S1: 输入n的值 S2: i=2 S3: n被i除，得余数r S4：如果r=0，表示n能被i整除，则打印n“不是素数”，算法结束；否则执行S5 S5: i+1→i S6：如果i≤n-1，返回S3；否则打印n“是素数”；然后算法结束。 改进： S6：如果i≤ 返回S3；否则打印n“是素数”;然后算法结束。 【例3-3】输入三个数，然后输出其中最大的数。 在该算法中，首先，得先有个地方装这三个数，我们定义三个变量A、B、S，将三个数依次输入到A、B、C中，另外，再准备一个M A X装最大数。由于计算机一次只能比较两个数，我们首先把A与B比，大的数放入MAX中，再把MAX与C比，又把大的数放入MAX中。最后，