资源描述
第一章第一章 算法初步算法初步1.1.1 1.1.1 算法的概念算法的概念算筹算筹算盘算盘计算器计算器计算机计算机1、分析：解二元一次方程组的主要思想是消元的思想，分析：解二元一次方程组的主要思想是消元的思想，有代入消元和加减消元两种消元的方法，下面用加减有代入消元和加减消元两种消元的方法，下面用加减消元法写出它的求解过程消元法写出它的求解过程 (3) 35y212 得：得：第一步：第一步：53y3）得：第二步：解（ )2(12)1(12yxyx152)2()1 (x得第三步：将(4)51)4(x得：第四步：解5153xy解为：第五步：所得方程组的111222?a xb yca xb yc一般二元一次方程组的解法步骤探究探究:对于一般的二元一次方程组来说，上述步骤应该对于一般的二元一次方程组来说，上述步骤应该怎样进一步完善？怎样进一步完善？ ( )( )()(3) ca -cay aa1-a21221121=122bab -得：得：第一步：第一步：12211221=babacaca-y3）得：）得：第二步：解（第二步：解（1221211212211221x(1)babacbcbbabacacay 得：得：代入代入第三步：将第三步：将算法的概念算法的概念 算法通常指按照一定规则解决某一类问题的步骤算法通常指按照一定规则解决某一类问题的步骤或程序，这些步骤或程序必须是明确的和有效的，或程序，这些步骤或程序必须是明确的和有效的，而且能够在有限步之内完成的。而且能够在有限步之内完成的。一般来说，一般来说，“用算法解决问题用算法解决问题” 可以利用计算机帮助可以利用计算机帮助完成完成。算法的特点算法的特点:有限性、确定性、顺序性和正确性、不唯一性、普遍性有限性、确定性、顺序性和正确性、不唯一性、普遍性1.下列对算法描述正确的一项是（ ）A. 某一个具体问题的一系列解决步骤B. 数学问题的解题过程C. 某一类问题的一系列解决步骤D. 计算机程序 C2.算法具有精确性，指的是（ ）A. 算法的步骤是有限的B. 算法一定包含输出C. 算法的每个步骤是具体的、可操作D. 以上说法都不正确C3.3.算法具有有穷性，指的是（算法具有有穷性，指的是（ ）A.A.算法的每个步骤都是可执行的算法的每个步骤都是可执行的B.B.算法的步骤是有限的算法的步骤是有限的C.C.算法一定包含输出算法一定包含输出D. D. 以上说法都不正确以上说法都不正确B4.4.下列对算法描述正确的一项是（下列对算法描述正确的一项是（ ）A. A. 算法只能用自然语言来描述算法只能用自然语言来描述B. B. 算法只能用图形方式来表示算法只能用图形方式来表示C. C. 同一问题可以有不同的算法同一问题可以有不同的算法D. D. 同一问题的算法不同，结果必然不同同一问题的算法不同，结果必然不同C5.5.下面关于算法的说法，正确的是（下面关于算法的说法，正确的是（ ）(1)(1)求解某一类问题的算法是唯一的求解某一类问题的算法是唯一的(2)(2)算法必须在有限步操作之后停止算法必须在有限步操作之后停止(3)(3)算法的每一步操作必须是明确的，不能有歧义或模糊算法的每一步操作必须是明确的，不能有歧义或模糊(4)(4)算法执行后一定产生确定的结果算法执行后一定产生确定的结果(2) (3) (4) 例例1 1：（：（1 1）设计一个算法，判断设计一个算法，判断7 7是否为质数是否为质数 （2 2）设计一个算法，判断）设计一个算法，判断3535是否是质数是否是质数分析：根据质数的定义，依次用分析：根据质数的定义，依次用2-62-6除除7 7，如果它，如果它们中的一个能整除们中的一个能整除7 7，则，则7 7不是质数，否则不是质数，否则7 7是质数是质数第一步：用第一步：用2 2除除7 7得到余数得到余数1 1，因为余数，因为余数1 1不为不为0 0，所，所以不能被以不能被2 2整除整除第二步：用第二步：用3 3除除7 7得到余数得到余数1 1，因为余数，因为余数1 1不为不为0 0，所，所以不能被以不能被3 3整除整除第三步：用第三步：用4 4除除7 7得到余数得到余数3 3，因为余数，因为余数3 3不为不为0 0，所，所以不能被以不能被4 4整除整除第四步：用第四步：用5 5除除7 7得到余数得到余数2 2，因为余数，因为余数2 2不为不为0 0，所，所以不能被以不能被5 5整除整除第五步：用第五步：用6 6除除7 7得到余数得到余数1 1，因为余数，因为余数1 1不为不为0 0，所，所以不能被以不能被6 6整除整除第六步：得到第六步：得到7 7是质数。是质数。（2 2）类似地，可以写出）类似地，可以写出“3535是否是质数是否是质数”的算的算法：法：第一步：用第一步：用2 2除除3535得到余数得到余数1 1，因为余数，因为余数1 1不为不为0 0，所以不能被，所以不能被2 2整除整除第二步：用第二步：用3 3除除3535得到余数得到余数2 2，因为余数，因为余数2 2不为不为0 0，所以不能被，所以不能被3 3整除整除第三步：用第三步：用4 4除除3535得到余数得到余数3 3，因为余数，因为余数3 3不为不为0 0，所以不能被，所以不能被4 4整除整除第四步：用第四步：用5 5除除3535得到余数得到余数0 0，因为余数，因为余数0 0为为0 0，所以能被，所以能被5 5整整除，则除，则3535不是质数。不是质数。已知直角三角形两直角边长为已知直角三角形两直角边长为a a、b b，求，求斜边斜边c c的一个算法可分下列三步：的一个算法可分下列三步： 计算计算 输入直角三角形两直角边长输入直角三角形两直角边长a a、b b的值的值 输出斜边输出斜边c c的值的值正确的顺序是正确的顺序是_22cab 例例2 2：设计一个算法，判断设计一个算法，判断19971997是否为质数是否为质数 第一步：用第一步：用2 2除除19971997得到余数不是得到余数不是0 0，所以不能被，所以不能被2 2整除整除第二步：用第二步：用3 3除除19971997得到余数不是得到余数不是0 0，所以不能被，所以不能被3 3整除整除第三步：用第三步：用4 4除除19971997得到余数不是得到余数不是0 0，所以不能被，所以不能被4 4整除整除第一九九五步：用第一九九五步：用19961996除除19971997得到余数不是得到余数不是0 0，所以不，所以不能被能被19961996整除整除例例2 2：设计一个算法，判断设计一个算法，判断19971997是否为质数是否为质数 第一步：令第一步：令i=2i=2第二步：用第二步：用i i除除19971997得余数得余数r r第三步：判断第三步：判断“r=0r=0”是否成立，若是则是否成立，若是则19971997不是质数，不是质数，结束算法，否则将结束算法，否则将i i的值增加的值增加1 1，仍用，仍用i i表示表示第四步：判断第四步：判断“i1996i1996”是否成立，若是则是否成立，若是则19971997是是质数，结束算法，否则返回第二步质数，结束算法，否则返回第二步例例3 3：任意给定一个大于任意给定一个大于1 1的整数的整数n n，试设计一个，试设计一个程序或步骤对程序或步骤对n n是否为质数做出判断是否为质数做出判断 第二步：判断第二步：判断“n=2n=2”是否成立，若是否成立，若n=2n=2，则，则n n是质数；若是质数；若n2,n2,则执行第三步则执行第三步第三步：令第三步：令i=2i=2第五步：判断第五步：判断“ii（n-1n-1）”是否成立，若是，则是否成立，若是，则n n是质数，是质数，结束算法，否则返回第四步结束算法，否则返回第四步第一步：给定正整数第一步：给定正整数n n第四步：用第四步：用i i除除n n，得到余数，得到余数r r。判断。判断“r=0r=0”是否成立，若是是否成立，若是则则n n不是质数，结束算法，否则将不是质数，结束算法，否则将i i的值增加的值增加1 1，仍用，仍用i i表示表示例例4 4、用二分法设计一个求方程、用二分法设计一个求方程 的近似正根的算法，精确度的近似正根的算法，精确度0.050.05。220 x 2122.(1)0,(2)0 1,2xffxx第一步：令f x因设1212().2 ( )0( )0, xxxxf mf mm第二步：令m因方程的根在区间（ ， ）内判断是否为 。若则 为所求；若否，则进行第三步。1112()( )0,; ()( )0,.f xf mxmf xf mxm第三步：若则令 若则令 12120.05 xxxx第四步：判断是否成立？若是，则 ， 之间的任意取值均为满足条件的近似根；若否，则返回第二步。解解有人对歌德巴赫猜想有人对歌德巴赫猜想“任何大于任何大于4 4的偶数都能写成两个质数之的偶数都能写成两个质数之和和”设计了如下操作步骤：设计了如下操作步骤：第一步：检验第一步：检验6=3+36=3+3第二步：检验第二步：检验8=3+58=3+5。利用计算机无穷地进行下去！利用计算机无穷地进行下去！请问，利用这种程序能够证明猜想的正确性吗？请问，利用这种程序能够证明猜想的正确性吗？第三步：检验第三步：检验10=5+510=5+5这是一种算法吗？这是一种算法吗？练习练习1 1：有蓝和黑两个墨水，但现在却错把蓝墨水装在了黑：有蓝和黑两个墨水，但现在却错把蓝墨水装在了黑墨水瓶中，黑墨水装在了蓝墨水瓶中，要求将其互换，请墨水瓶中，黑墨水装在了蓝墨水瓶中，要求将其互换，请你设计算法解决这一问题你设计算法解决这一问题分析：由于两个墨水瓶中的墨水不能直接交换，故可以考分析：由于两个墨水瓶中的墨水不能直接交换，故可以考虑通过引入第三个空墨水瓶的办法进行交换虑通过引入第三个空墨水瓶的办法进行交换第二步：将黑墨水瓶中的蓝墨水倒入白瓶中第二步：将黑墨水瓶中的蓝墨水倒入白瓶中第三步：将第三步：将蓝墨水瓶中的黑墨水倒入黑瓶中蓝墨水瓶中的黑墨水倒入黑瓶中第五步：交换结束第五步：交换结束第一步：取一只空墨水瓶，设其为白色第一步：取一只空墨水瓶，设其为白色第四步：将白第四步：将白瓶中的蓝墨水倒入蓝瓶中瓶中的蓝墨水倒入蓝瓶中练习练习2:2:任意给定一个正实数，试设计一个算法求以这个数任意给定一个正实数，试设计一个算法求以这个数为半径的圆的面积。为半径的圆的面积。解解第一步：给定一个正实数第一步：给定一个正实数r.r.第二步第二步: :计算以计算以r r为半径的圆的面积为半径的圆的面积第三步第三步: :得到圆的面积得到圆的面积s s2= rs练习练习3:3:任意给定一个大于任意给定一个大于1 1的正整数的正整数n n，试，试设计一个算法求出设计一个算法求出n n的所有因数。的所有因数。第一步：给定一个大于第一步：给定一个大于1 1的正整数的正整数 n n第二步：令第二步：令 i=1i=1第三步：用第三步：用 i i 除除 n n 得余数得余数 r r第四步：判断第四步：判断“ r=0 r=0 ”是否成立：若是，则是否成立：若是，则 i i 是是 n n 的因数；的因数；否则，否则，i i 不是不是 n n 的因数的因数 第五步：使第五步：使 i i 的值增加的值增加1 1，仍用，仍用 i i 表示表示第六步：判断第六步：判断“ in-1 in-1 ” 是否成立：若是，则结束算法；是否成立：若是，则结束算法；否则，返回第三步否则，返回第三步小结：小结：算法的特征是什么？算法的特征是什么？n明确性明确性n有效性有效性n有限性有限性算法的概念：算法的概念：算法通常指可以用来解决的某算法通常指可以用来解决的某一类问题的步骤或程序，这些步骤或程序必须是明一类问题的步骤或程序，这些步骤或程序必须是明确的和有效的，而且能够在有限步之内完成的。确的和有效的，而且能够在有限步之内完成的。
展开阅读全文