数学：1.1.1算法的概念.ppt

算法的概念[问题 1]请你写出解二元一次方程组的详细求解过程. 2 1 2 1 x y x y ? ????? ??①②第一步:②-①×2得: 5y=3 ③第二步: 解③得: 35 y?第三步: 将代入①,解得. 35 y? 15 x?对于一般的二元一次方程组其中也可以按照上述步骤求解. 1 1 1 2 2 2 a x b y c a x b y c ? ???? ?? 1 2 2 1 0 a b a b ? ?第四步:得到方程组的解为???????5 3y 5 1x 第一步:②× a 1- ①× a 2,得:?? 12211221cacaybaba???③第二步:解③得1221 1221baba cacay???; 第三步:将1221 1221baba cacay???代入①,得1221 2112baba cbcbx???.第四步:得到方程组的解为????????????? 1221 1221 1221 2112baba cacay baba cbcbx算法的概念和特征算法的概念和特征特征: 特征: (1) (1) 有限性:一个算法的步骤序列是有限的,必须在有限操作之有限性:一个算法的步骤序列是有限的,必须在有限操作之后停止,不能是无限的后停止,不能是无限的. . (2) (2) 确定性:算法中的每一步应该是确定的并且能有效地执行且得到确确定性:算法中的每一步应该是确定的并且能有效地执行且得到确定的结果,而不应当是模棱两可定的结果,而不应当是模棱两可. . (3) (3) 逻辑性:算法从初始步骤开始,分为若干明确的步骤,每一个步骤逻辑性:算法从初始步骤开始,分为若干明确的步骤,每一个步骤只能有一个确定的后继步骤,前一步是后一步的前提,只有执行完前只能有一个确定的后继步骤,前一步是后一步的前提,只有执行完前一步才能进行下一步,并且每一步都准确无误,才能完成问题一步才能进行下一步,并且每一步都准确无误,才能完成问题. . (4) (4) 不唯一性:求解某一个问题的解法不一定是唯一的,对于一个问题不唯一性:求解某一个问题的解法不一定是唯一的,对于一个问题可以有不同的算法可以有不同的算法. . (5) (5) 普遍性:很多具体的问题,都可以设计合理的算法去解决。普遍性:很多具体的问题,都可以设计合理的算法去解决。概念:通常指按照一定规则解决某一类问题的明确的和有限的步骤。概念:通常指按照一定规则解决某一类问题的明确的和有限的步骤。(现在,算法通常可以编成程序,让计算机执行并解决问题。) (现在,算法通常可以编成程序,让计算机执行并解决问题。) 例1、设计一个算法,判断 7是否为质数第一步,用 2除7,得到余数 1,所以 2不能整除 7. 第四步,用 5除7,得到余数 2,所以 5不能整除 7. 第五步,用 6除7,得到余数 1,所以 6不能整除 7. 第二步,用 3除7,得到余数 1,所以 3不能整除 7. 第三步,用 4除7,得到余数 3,所以 4不能整除 7. 因此, 7是质数. 类似地,可写出“判断 35是否为质数”的算法: 第一步,用 2除35,得到余数 1,所以 2不能整除 35. 第二步,用 3除35,得到余数 2,所以 3不能整除 35. 第三步,用 4除35,得到余数 3,所以 4不能整除 35. 第四步,用 5除35,得到余数 0,所以 5能整除 35. 因此, 35不是质数. 例例2 2、任意给定一个大于、任意给定一个大于 1 1的整数的整数 n n,试设计一个程序或步骤对,试设计一个程序或步骤对 n n是否为质数做是否为质数做出判断出判断. .解:算法: 解:算法: 第一步:判断第一步:判断 n n是否等于是否等于 2. n=2 n=2 ,则,则 n n是质数;若是质数;若 n n> >2 2,则执行第二步,则执行第二步. . 第二步:依次从第二步:依次从 2~ 2~ ( ( n-1 n-1 )检验是不是)检验是不是 n n的因数,即整除的因数,即整除 n n的数的数. .若有这样的数, 若有这样的数, 则则n n不是质数;若没有这样的数,则不是质数;若没有这样的数,则 n n是质数是质数. . 分析:( 分析:( 1 1)质数是只能被)质数是只能被 1 1和自身整除的大于和自身整除的大于 1 1的整数的整数. . ( (2 2)要判断一个大于)要判断一个大于 1 1的整数的整数 n n是否为质数,只要根据质数的定义, 是否为质数,只要根据质数的定义, 用比这个整数小的数去除用比这个整数小的数去除 n n,如果它只能被,如果它只能被 1 1和本身整除,而不能被其和本身整除,而不能被其它整数整除,则这个