C语言第02章课件.pptVIP

第2章 程序的灵魂------算法 2.0 引言 2.1 算法的概念 2.2 简单算法举例 2.3 算法的特性 2.4 怎样表示一个算法 2.5 结构化程序设计方法 Return 2.1 算法的概念 算法:解决一个问题而采取的方法和步骤 做任何事情都有一定的步骤.如开会,购物,考大学,按一定顺序进行，缺一不可，日常生活中人们意识不到每件事都需事先设计出“行动步骤”。 并不是只有“计算”的问题才有算法.例如:太极拳的拳谱,乐谱 不仅要保证算法正确,还要考虑的是算法的质量.例如求解 本书只考虑计算机算法. 数值算法: 目的是求数值解. 如求方程的根,求积分等 非数值算法: 包括的面非常广泛.最常见的用在事物管理领域 Return 2.2 简单算法举例 [案例2.1]求 5! 。 方法1： 步骤1：先求1×2，得结果2 步骤2：将步骤1的结果乘以3，得结果6 步骤3：6再乘以4，得24 步骤4：24再乘以5，得最后的结果120。 分析：算法正确，但太烦琐。若要求1000 !，要写多少步骤呢？且不方便的是每次都直接使用上一步骤的结果 方法2：设变量p为被乘数(乘积)，i为乘数，改写如下 S1：使p=1 S2：使i=2 S3：p ×i?p S4：i+1 ?i S5：若i不大于5，则回到S3；否则算法结束。最后的p就是5！ 分析：若求1 ×3 ×5 ×7 ×9 ×11，只做很少的改动即可。S2：i=3 S4：i+2 ?i S5：i?11，回到S3，否则结束。说明方法2简练且通用。若条件改成i11,结果会怎样？ [案例2.2]有50个学生，要求将他们之中成绩在80分以上者打印出来。变量i作为下标,用它来控制序号, ni代表第i个学生学号，gi代表第i个学生的成绩。算法如下： S1：1?i S2：gi?80，则打印ni和gi，否则不打印 S3：i+1 ?i S4：若i ? 50，返回S2；否则算法结束 [案例2.3]判定2000?2500年中的每一年是否是闰年，将结果输出 分析：满足下列条件之一就是闰年：条件1，能被4整除，但不能被100整除；条件2，能被100整除同时又能被400整除 设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继续执行。否则算法停止。 [案例2.4]求级数的和： 用有含义的单词作变量名，易于理解。sum表示累加和，deno是分母denominator缩写，sign代表数值的符号，term代表某一项，算法如下： 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的正整数，判断它是否是素数。 分析：素数的概念；判断一个数n是否素数的方法，将n作为被除数，将2到（n-1）各个整数轮流作除数，若都不能被整除，则n是素数。算法如下 S1：输入n的值 S2：2?i S3：n被i除，得余数r S4：若r为0，表示n能被i整除，则打印n“不是素数”，算法结束；否则执行S5 S5： i+1?i S6：若i?n-1，返回S3；否则打印n“是素数”，然后结束 实际上，n不必被2到n-1的所有整数除，只需被2到n/2间整数除即可，甚至只需被2到 之间的整数除即可。 Return 2.3 算法的特性 有穷性 一个算法应包含有限的操作步骤，而不能是无限的。如算法包含语句：for( i=1 ; i0 ; i++ ){} 。实际上，“有穷性”是指在一个“合理的范围内”。若让计算机执行一个历时几千年才结束的算法，虽然是有穷的，但超过了合理的限度。“合理限度”无严格标准，根据常识和需要而定 确定性 算法中的每一步骤的含义都应当是确定唯一的，不应当产生“歧义性”。如“手举过头顶” “n被一个整数除，得余数r。” 有零个或多个输入 输入是指在执行算法时需要从外界取得必要的信息。例如，算法：判断一个数是否是素数，求2个整数的最大公约数，求n个数的方差等。当然也可以没有输入。 有一个或多个输出 算法的目的就是求解，解就是输出。不一定是计算机打印输出。没有输出的算法