C语言课件第2章1.ppt

2.1　算法的概念 2.2　简单算法举例 2.3　算法的特性 2.4　怎样表示一个算法 ★ 2.5　结构化程序设计方法 ★ 程 序 包 括 对数据的描述 指定数据的类型、组织形式，即数据结构。 对操作的描述 即操作步骤，也称算法(algorithm)。 著名计算机科学家沃思(Nikilaus Wirth)提出： 程 序 设 计 包 括 采用某种程序设计方法 使用某种计算机语言工具 为解决问题而采取的方法和步骤，称为“算法”。 ——尽量采用简单、有效的算法。 计算机算法分两类： 数值算法（目的是求数值解） 有比较成熟的算法可供选用。 常常把这些算法汇编成册(写成程序形式)，或者将这些程序存放在磁盘或磁带上，供用户调用。 通过对一些典型算法的学习，同学们应学会怎样进行算法设计，包括： 如何提出问题 如何思考问题 如何表示一个算法 算 法 一： 步骤1： 先求1×2，得到2。 步骤2： 将得到的2再乘以3，得到6。 步骤3： 将6再乘以4，得到24。 步骤4： 将24再乘以5，得到120。 算法虽然正确，但太繁琐。 每次都直接使用上一步骤的数值结果，不方便。应找到 一种通用的表示方法。 设两个变量：变量p代表被乘数，变量i代表乘数。 将每一步的乘积放在被乘数变量p中，算法改写如下： S1： 使p=1 S2： 使i=2 S3： 使p×i，乘积放在p中（p×i=p） S4： 使i的值加1（i+1 = i） S5： 若i不大于5，重新执行S3、S4和S5； 否则，算法结束。 如果题目改为： 求1×3×5×7×9×…×99。 则算法二只需作很少改动： S1： 1=p S2： 3=i S3： p×i=p S4： i+2=i S5： 若i≤100，返回S3； 否则，结束。 例2.2 将50个学生中成绩在80分以上者打印出来。 n—学号， ni—第i个学生学号。 g－学生成绩，gi－第i个学生成绩 算法可表示如下： S1：1=i S2：如果gi≥80，则打印ni和gi，否则不打印 S3：i+1=i S4：如果i≤50，返回S2继续执行；否则，算法结束。 例2.3 判定2000—2500年中的每一年是否闰年，将结果输出。 闰 年 的 条 件 ： ① 能被4整除，但不能被100整除的年份是闰年， 如1996年，2004年； ② 能被100整除，又能被400整除的年份是闰年， 如1600年、2000年。 不符合这两个条件的年份不是闰年。 设 y 为被检测的年份，算法如下： S1：2000=y S2：y不能被4整除，则输出y “不是闰年”，转到S6 S3：若y能被4整除，不能被100整除，则输出y “是闰年”， 转到S6 S4：若y能被100整除，又能被400整除，输出y“是闰年”； 转到S6 S5：输出y “不是闰年” S6：y+1=y S7：当y≤2500时，转S2继续执行，如y＞2500，算法停止。 图 2.1 例2.4 求1-1/2+1/3-1/4+…+1/99-1/100。 算法可以表示如下： S1：1=sign S2：1=sum S3：2=deno S4：(-1)×sign=sign S5：sign×(1/deno)=term S6：sum+term=sum S7：deno+1=deno S8：若deno≤100返回S4；否则结束。 例2.5 对一个大于或等于3的正整数，判断它是否为素数。 所谓素数，是指除了1和该数本身之外，不能被其他任何整 数整除的数。 判断数n(n≥3)是否素数的方法： 将n作为被除数，将2到(n-1)各个整数轮流作为除数，若都 不能整除，则n为素数。 实际上n只需被2到n/2间整数除或被2到 之间的整数除即可。 算 法 可 表 示 如 下： S1：输入n的值 S2：2=i （i作为除数） S3：n被i除，得余数r S4：如果r=0，打印n“不是素数”，算法结束；否则执行S5 S5：i+1=i S6：如果i≤ ，返回S3；否则打印 n “是素数”， 算法结束。 一 个 算 法 应 具 有 以 下 特 点： 1.有穷性 一个算法应包含有限步操作。并且还应该“在合理的范围 之内”。究竟什么算“合理限度”，并无严格标准，由人们的 常识和需要而定。 2.确定性 算法中的每一个步骤都应当是确定的，而不应当是含糊的、 模棱两可的。 3.有零个或多个输入 所谓输入是指在执行算法时需要从外界取得的必要的信息。 一个算法也可以没有输入。 4.有一个或多个输出 算法的目的是为了求解，“解” 就是输出。没有输出的算法 是没有意义的。 5.