《算法案例1.ppt》由会员分享，可在线阅读，更多相关《算法案例1.ppt（47页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、基本结构基本结构流程图流程图顺序结构顺序结构变量与赋值变量与赋值循环结构循环结构基本语句基本语句循环语句循环语句条件语句条件语句WHILE语句语句UNTIL语句语句IF-THEN语句语句语句适用结构语句适用结构算法算法条件结构条件结构我们这节课就利用基本的算法程序来解决一我们这节课就利用基本的算法程序来解决一些实际问题，进一步体会算法的程序思想。些实际问题，进一步体会算法的程序思想。案例案例1.辗转相除法与更相减损术辗转相除法与更相减损术在初中，我们已经学过求最大公约数的知识，在初中，我们已经学过求最大公约数的知识，你能求出你能求出18与与30的最大公约数吗？的最大公约数吗？ 218 30 3
2、 9 15 3 5所以，所以，18和和30的最大公约数是：的最大公约数是：236互质互质因数因数但是，当我们处理较大数（如：但是，当我们处理较大数（如：8251与与6105）的最大公因）的最大公因数时，如果利用这种方法可能计算量比较大，步骤比较多。数时，如果利用这种方法可能计算量比较大，步骤比较多。下面我们介绍一种古老而有效的算法下面我们介绍一种古老而有效的算法辗转相除法辗转相除法这种算法是这种算法是欧几里得欧几里得公元前公元前300年左右首先提出的，因此又年左右首先提出的，因此又叫欧几里得算法叫欧几里得算法例例1 求两个正数求两个正数8251和和6105的最大公约数。的最大公约数。 分析：分
3、析：8251与与6105两数都比较大，而且没有明显的公约数，两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数如能把它们都变小一点，根据已有的知识即可求出最大公约数 解解8251610512146 显然显然8251和和6105的最大公约数也必是的最大公约数也必是2146的约数，的约数，同样同样6105与与2146的公约数也必是的公约数也必是8251的约数，所以的约数，所以8251与与6105的最大公约数也是的最大公约数也是6105与与2146的最大的最大公约数公约数 继续下去，我们得到：继续下去，我们得到：欧几里得（公元前欧几里得（公元前330-公元前公
4、元前275）：古希）：古希腊数学家，雅典人腊数学家，雅典人欧几里得是欧几里得是柏拉图柏拉图的学生，长期在亚的学生，长期在亚历山大里亚教书。历山大里亚教书。公元前公元前300年左右，代表作年左右，代表作几何原本几何原本13卷问世，创立了著名的卷问世，创立了著名的欧氏几何欧氏几何，至今，至今仍为中学生必学的一门基础知识。欧几里仍为中学生必学的一门基础知识。欧几里得对光学也有一定研究。得对光学也有一定研究。61056105214621462 21813181321462146181318131 1333333181318133333335 51481483333331481482 237371481
5、4837374 40 0则则3737为为82518251与与61056105的最大公约数的最大公约数 这就是辗转相除法，有除法的性质可以知道，这就是辗转相除法，有除法的性质可以知道，对于任意两个正整数，上述除法步骤总可以对于任意两个正整数，上述除法步骤总可以在有限步骤之后完成在有限步骤之后完成利用辗转相除法求最大公约数的步骤如下：利用辗转相除法求最大公约数的步骤如下： 第一步：第一步：用较大的数用较大的数m除以较小的数除以较小的数n得到一个商得到一个商q0和一个余和一个余数数r0； 第二步：第二步：若若r00，则，则n为为m，n的最大公约数；若的最大公约数；若r00，则用，则用除数除数n除以余
6、数除以余数r0得到一个商得到一个商q1和一个余数和一个余数r1；第三步：第三步：若若r10，则，则r1为为m，n的最大公约数；若的最大公约数；若r10，则，则用除数用除数r0除以余数除以余数r1得到一个商得到一个商q2和一个余数和一个余数r2第第n n步：依次计算直至步：依次计算直至r rn n0 0，此时所得到的，此时所得到的r rn n1 1即为所求的即为所求的最大公约数最大公约数 r= m MOD nm=nn=rr=o?否否是是程序图框程序图框带余除法带余除法INPUT “请输入请输入m，n的值的值”；m，nIF mn THEN a=m m=n n=aEND IFDO r=m MOD N
7、 m=n n=rLOOP UNTIL r=0PRINT mEND作用是什么？作用是什么？为什么要用为什么要用直到型循环直到型循环结构？结构？1.1.利用辗转相除法求两数利用辗转相除法求两数40814081与与2072320723的最大公约的最大公约数数 ，写出它的流程框图和，写出它的流程框图和BASICBASIC程序程序更相减损术更相减损术 我国早期也有解决求最大公约数问题的算法我国早期也有解决求最大公约数问题的算法 九章算术九章算术（公元（公元50年年100年或更早年或更早 ）是中国古代数学专著，）是中国古代数学专著，承先秦数学发展的源流，进入汉承先秦数学发展的源流，进入汉朝后又经许多学者的
8、删补才最后朝后又经许多学者的删补才最后成书，这大约是公元一世纪的下成书，这大约是公元一世纪的下半叶。它的出现，标志着中国古半叶。它的出现，标志着中国古代数学体系的形成。代数学体系的形成。 历代数学家把它尊为历代数学家把它尊为“算经之首算经之首”这是世这是世界上最早的印刷本数学书。界上最早的印刷本数学书。 九章算术九章算术共收有共收有 246246个数学问题，分个数学问题，分为九章。分别是：方田、栗米、衰分、少广、为九章。分别是：方田、栗米、衰分、少广、商功、均输、盈不足、方程、勾股。商功、均输、盈不足、方程、勾股。 九章算术九章算术是世界上最早系统叙述了分是世界上最早系统叙述了分数运算的著作；
9、其中盈不足的算法更是一项数运算的著作；其中盈不足的算法更是一项令人惊奇的创造；令人惊奇的创造；“方程方程”章还在世界数学章还在世界数学史上首次阐述了负数及其加减运算法则。史上首次阐述了负数及其加减运算法则。更相减损术求最大公约数的步骤如下：可半者半之，不可半更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。以等数约之。翻译出来为：翻译出来为：第一步：任意给出两个正数；判断它们是否都是偶数。若是，第一步：任意给出两个正数；判断它们是否都是偶数。若是，用用2约简；若不是，执行第二步
10、。约简；若不是，执行第二步。第二步：以较大的数减去较小的数，接着把较小的数与所第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。得的差比较，并以大数减小数。第三部：继续第二步，直到所得的数相等为止，则这个数第三部：继续第二步，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数（等数）就是所求的最大公约数例例2 2 用更相减损术求用更相减损术求9898与与6363的最大公约数的最大公约数. . 解解 由于由于6363不是偶数，把不是偶数，把9898和和6363以大数减小数，以大数减小数，并辗转相减并辗转相减 98-6398-63353563-3563-3528
11、2835-2835-287 728-728-7141414-714-77 7所以，所以，98与与63的最大公约数是的最大公约数是7 比较辗转相除法与更相减损术的区别比较辗转相除法与更相减损术的区别 （1）都是求最大公约数的方法，计算上）都是求最大公约数的方法，计算上辗转相除法辗转相除法以以除法除法为为主，主，更相减损术更相减损术以以减法减法为主，计算次数上辗转相除法计算次为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。别较明显。（2）从结果体现形式来看，辗转相除法体现结果是以相除）从结果体现形式来
12、看，辗转相除法体现结果是以相除余数为余数为0则得到，而更相减损术则以减数与差相等而得到则得到，而更相减损术则以减数与差相等而得到思考一思考一. .用辗转相除法求下列各组数的最大公约数，用辗转相除法求下列各组数的最大公约数，并在自己编写的并在自己编写的BASICBASIC程序中验证。程序中验证。（1 1）225225，135 135 （2 2）9898，196 196 （3 3）7272，168168思考二：思考二：用更相减损法可否求上述用更相减损法可否求上述3组数的最大公约数？可组数的最大公约数？可否利用更相减损法设计出程序框图及程序？若能，在电脑上否利用更相减损法设计出程序框图及程序？若能，
13、在电脑上测试自己的程序；若不能说明无法实现的理由。测试自己的程序；若不能说明无法实现的理由。思考三：思考三：利用辗转相除法是否可以求两数的最大公倍数？利用辗转相除法是否可以求两数的最大公倍数？试设计程序框图并转换成程序在试设计程序框图并转换成程序在BASICBASIC中实现。中实现。 案例二（秦九韶算法）怎样求多项式案例二（秦九韶算法）怎样求多项式1)(2354xxxxxxf当当x=5时的值？时的值？据我们的计算统计可以得出我们共需要据我们的计算统计可以得出我们共需要10次乘法运算，次乘法运算，5次次加法运算加法运算 我们把多项式变形为：我们把多项式变形为： 再统计一下计算当时的值时需要的计算
14、次数，可以得出仅需再统计一下计算当时的值时需要的计算次数，可以得出仅需4次乘法和次乘法和5次加法运算即可得出结果。显然少了次加法运算即可得出结果。显然少了6次乘法运算。次乘法运算。这种算法就叫这种算法就叫秦九韶算法秦九韶算法。1)1 (1 (1 ()(2xxxxxxf秦九韶（秦九韶（1202-1261年），年），字道古，安岳县人。其父秦字道古，安岳县人。其父秦季栖，进士出身，官至工部季栖，进士出身，官至工部郎中、秘书少监。秦九韶性郎中、秘书少监。秦九韶性敏慧，勤奋好学，幼年随父敏慧，勤奋好学，幼年随父居中都（今北京），受到名居中都（今北京），受到名师指导，学习日益增进。及师指导，学习日益增进。
15、及长，随父迁湖州（今浙江吴长，随父迁湖州（今浙江吴兴县），在西门外修建住房，兴县），在西门外修建住房，由秦九韶设计施工，堂分由秦九韶设计施工，堂分7间，间，后为列室，仅中堂后为列室，仅中堂1间，纵横间，纵横7丈，极其宏伟宽敞，显示出丈，极其宏伟宽敞，显示出他在建筑方面的才能他在建筑方面的才能 01210123120132211012211)()()()(aaxaxaxaaxaxaxaxaaxaxaxaxaaxaxaxaxaxfnnnnnnnnnnnnnnnnnnn把一个多项式把一个多项式012211)(axaxaxaxaxfnnnnnn改写为：改写为：求多项式的值时，首先计算最内层括号内的一次
16、多项式的求多项式的值时，首先计算最内层括号内的一次多项式的值，即：值，即：11nnaxav01323212avvaxvvaxvvnnnn再有内向外逐层计算一次多项式的值，即：再有内向外逐层计算一次多项式的值，即：这样将求这样将求n次多项式次多项式f(x)的值转化为求的值转化为求n个一次多项式的值。个一次多项式的值。例例3 3 设计利用秦九韶算法计算设计利用秦九韶算法计算5 5次多项式次多项式 0122334455)(axaxaxaxaxaxf当当0 xx 时的值的程序框图以及时的值的程序框图以及BASIC程序。程序。 ENDvPRINTWEND1nnax*vvav5nWHILEx;XINPUT
17、a,a,a,a,a,a;aa)x( fINPUTn5050O543210n0 的的值值请请输输入入的的系系数数请请输输入入i=0WHILE i5INPUT aiWENDDOv=a5v=v*x0+a5-nn=n+1LOOP UNTIL n6END用秦九韶算法求这个多项式当用秦九韶算法求这个多项式当 时的值。时的值。8 . 07 . 16 . 25 . 325)(2345xxxxxxf5x3. 3. 已知一个已知一个5 5次多项式为次多项式为思考：（思考：（1）例）例1计算时需要多少次乘法计算？多少次加法计算时需要多少次乘法计算？多少次加法计算？计算？ （2）在利用秦九韶算法计算）在利用秦九韶算法
18、计算n次多项式当时需要多少次次多项式当时需要多少次乘法计算和多少次加法计算？乘法计算和多少次加法计算？你会使用这些字典吗？你会使用这些字典吗？为了便于查询和检索，常常需要根据要求将被查寻的对为了便于查询和检索，常常需要根据要求将被查寻的对象按照一定的顺序排列，通常称为排序，象按照一定的顺序排列，通常称为排序，你会从这些书籍中查你会从这些书籍中查阅你想要的东西吗？阅你想要的东西吗？我们在一个已经排好循序的一系列数中插入一个数据，成我们在一个已经排好循序的一系列数中插入一个数据，成为一个新的系列，且仍按原来的规则排序。为一个新的系列，且仍按原来的规则排序。要将要将8插入到插入到1,3,5,7,9,
19、11,13中，中，我们怎样考虑？我们怎样考虑？确定确定8在原系列中的位置，使在原系列中的位置，使8小于或等于原系小于或等于原系列中右边的数据，大于或等于左边的数据列中右边的数据，大于或等于左边的数据将这个位置空出来，将数将这个位置空出来，将数据据8插进去插进去1357911138例例3.将数列将数列49,38,65,97,76,13,27,49按小到大的顺序排列按小到大的顺序排列我们的想法是：我们的想法是：1.先排先排49，38的顺序：的顺序：38，492.比较第三个数与它们的大小得到：比较第三个数与它们的大小得到：38，49，653.比较第四个数与比较第四个数与2的顺序得到：的顺序得到：38
20、，49，65，97n.第第n个数与前面数的关系，得到最后的排序：个数与前面数的关系，得到最后的排序：13，27，38，49，49，65，76，97反复使用直接插入排序算法，即首先把第反复使用直接插入排序算法，即首先把第一个数当作一个基准，插入第二个数变成一个数当作一个基准，插入第二个数变成有两个数据的有序列，再插入第三个数，有两个数据的有序列，再插入第三个数，依此类推，就完成了整个无序列的有序化。依此类推，就完成了整个无序列的有序化。流程图如下：流程图如下：你会设计它的你会设计它的BASIC算法吗？算法吗？1排序号：排序号：数据序号数据序号12345678原始数据原始数据49386597761
21、327 49上述数据我们还可以这样来排序：上述数据我们还可以这样来排序：2排序排序数据序号数据序号12345678原始数据原始数据49386597 7613 27 49现将现将1号数据号数据49和和2号数据号数据38比较，因为比较，因为4938所以，所以，49和和38的位置互换，变为：的位置互换，变为：数据序号数据序号12345678原始数据原始数据38496597761327 49第一次排序第一次排序第一步：第一步：1号号2号排序号排序数据序号数据序号12345678原始数据原始数据38496597761327 49第二步：第二步：2号号3号排序号排序因为因为4965所以这俩数的序号不变所以
22、这俩数的序号不变数据序号数据序号12345678原始数据原始数据38496597761327 49第三步：比较第三步：比较3、4号数据号数据数据序号数据序号12345678原始数据原始数据38496597761327 49方法同第二步，因为方法同第二步，因为6576，所以，所以4、5号数据互换，则：号数据互换，则：第五步：比较第五步：比较5、6号数据：号数据：数据序号数据序号12345678原始数据原始数据38496576971327 49数据序号数据序号12345678原始数据原始数据38496576139727 49方法同第二步，方法同第二步，9713则，交换则，交换5、6号数据，则：号数
23、据，则：第六步：比较第六步：比较6、7号数据号数据数据序号数据序号12345678原始数据原始数据38496576139727 49数据序号数据序号12345678原始数据原始数据38496576132797 49同理，上面的顺序可以变为：同理，上面的顺序可以变为：同理第七步比较同理第七步比较7、8号数据后可以变为：号数据后可以变为：这样就完成了第一次排序，它的基本特征是将最大数排到这样就完成了第一次排序，它的基本特征是将最大数排到了最右边，然后再从头开始，进行第二次排序，将第二大了最右边，然后再从头开始，进行第二次排序，将第二大的数据排到了倒数第二位，反复下去，就可以完成排序。的数据排到了倒
24、数第二位，反复下去，就可以完成排序。一共要进行一共要进行7次才能完成。我们叫它次才能完成。我们叫它冒泡排序（冒泡排序（bubble sorting）你会用冒泡法将上面的数据按从你会用冒泡法将上面的数据按从大到小的顺序排列吗？大到小的顺序排列吗？完成所有的排序需要多少步比较？完成所有的排序需要多少步比较？你还有其他的排序方法将上面的你还有其他的排序方法将上面的数据按从大到小的顺序排列吗？数据按从大到小的顺序排列吗？请你设计一个数据列为请你设计一个数据列为R1,R2,R10,要求从小到大的要求从小到大的顺序排列？顺序排列？1.画出一次冒泡排序的算法流程图画出一次冒泡排序的算法流程图2.画出整个冒泡
25、排序的算法流程图画出整个冒泡排序的算法流程图一次排序一次排序N-1次排完次排完整个排序流程图如图所示整个排序流程图如图所示1.冒泡法排序完成冒泡法排序完成n个数据的一次排序需要个数据的一次排序需要n-1次比较，次比较，完成整个排序需要完成整个排序需要(n-1)！次比较，对于数据较多时，次比较，对于数据较多时，计算量计算量很大很大。2.有些数据的冒泡法排序可能用更少的步骤可以完成，有些数据的冒泡法排序可能用更少的步骤可以完成，后面的步骤可能后面的步骤可能毫无意义，但计算机必须完成。毫无意义，但计算机必须完成。3.交换数据时注意引入交换数据时注意引入第三方变量第三方变量。并请这个人算出并请这个人算
26、出5个数个数 的和的和N，在一种游戏中，魔术师请一个人随意想一个三位数在一种游戏中，魔术师请一个人随意想一个三位数 abcacbbacbcacabcba把把N告诉魔术师，于是魔术师就能说出这个人所想的数告诉魔术师，于是魔术师就能说出这个人所想的数 abc现在设现在设N=3194，请你做魔术师，求出数，请你做魔术师，求出数 的值的值 abc将将 也加到和也加到和N N上，这样上，这样a a、b b、c c就在每一位上就在每一位上都恰好出现两次，所以有都恰好出现两次，所以有 abc分析：分析：)cba(222Nabc 从而从而 3194222(a+b+c)3194+10003194222(a+b+
27、c)3194+1000，而，而a a、b b、c c是整数是整数所以所以 15a+b+c1815a+b+c18因因 222222 15-3194=13615-3194=136，222222 16-3194=35816-3194=358，222222 17-3194=58017-3194=580，222222 18-3194=80218-3194=802其中只有其中只有3+5+8=163+5+8=16能满足式能满足式 事实上，这里面应用到了一个知识：事实上，这里面应用到了一个知识：进位制进位制进位制是人们为了计数和运算方便而约定的计数系统，约进位制是人们为了计数和运算方便而约定的计数系统，约定满
28、二进一，就是二进制；满十进一，就是十进制，等等，定满二进一，就是二进制；满十进一，就是十进制，等等，也就是说也就是说满几进一满几进一就是几进制，几进制的就是几进制，几进制的基数基数就是几就是几大于大于1的整数的整数由于自然数有无限多个，对于每一个自然数如果都用一个由于自然数有无限多个，对于每一个自然数如果都用一个独立的名称或符号来读出它或表示它，那是很不方便的，独立的名称或符号来读出它或表示它，那是很不方便的，也是不可能做到的。因此，需要建立一种读数、写数制度也是不可能做到的。因此，需要建立一种读数、写数制度- - -进位制进位制 12232n1n1nna10a10a10a10a 十进制数十进
29、制数 表示实际数值为：表示实际数值为：1231nnaaaaa 12232n1n1nnakakakaka K进制数进制数 实际表示数为：实际表示数为：)k(1231nnaaaaa 在日常生活中，我们最熟悉的还是十进制数，据说这和古在日常生活中，我们最熟悉的还是十进制数，据说这和古人曾以手指计数有关人曾以手指计数有关为了区别进制，我们就用下标为了区别进制，我们就用下标（k）表示）表示k进制数进制数a n是是09的数子的数子下面我们来用一个具体的例子来分析：下面我们来用一个具体的例子来分析：例例4.将二进制数将二进制数110 011(2)化成十进制数化成十进制数解解 根据根据k进制数的实际意义，我们
30、可以这样来转换：进制数的实际意义，我们可以这样来转换：51121161321212120202121011 110012345(2) INPUT a,b,ci=1b=0WHILE i=n t=GET ai b=b+t*k(i-1) i=i+1WENDPRINT bENDGET函数用函数用于取出于取出a的有的有数第数第i位位例例5.不不89化为二进制数化为二进制数分析：分析：89=2(2(2(2(22+1)+1)+0)+0)+1 = =1 011 001(2)28912440222021112512202 11 0所以上式可以表示为：所以上式可以表示为：1 011 001综合：上述方法叫做综合：上述方法叫做k进制数的进制数的除除k取余法取余法5.把把89化为五进制数化为五进制数思考：思考：1如何将十六进制数如何将十六进制数A1F721化为二进制数化为二进制数一般方法：一般方法：k进制数进制数十进制数十进制数n进制数进制数1010 0001 1111 0111 0010 0001算法算法程序图框程序图框算法语句算法语句辗转相除与更相减损术辗转相除与更相减损术秦秦 九九 韶韶 算算 法法排排 序序进进 位位 制制