算法案例

基本结构程序框图顺序结构变量与赋值循环结构基本语句循环语句条件语句WHILE语句UNTIL语句IF-THEN语句语句适用结构算法条件结构我们这节课就利用基本的算法程序来解决一些实际问题，进一步体会算法的程序思想。案例1.辗转相除法与更相减损术在初中，我们已经学过求最大公约数的知识，你能求出18与30的最大公约数吗？21830391535所以，18和30的最大公约数是：2×3＝6互质但是，当我们处理较大数（如：8251与6105）的最大公因数时，如果利用这种方法可能计算量比较大，步骤比较多。下面我们介绍一种古老而有效的算法——辗转相除法这种算法是欧几里得公元前300年左右首先提出的，因此又叫欧几里得算法例1求两个正数8251和6105的最大公约数。分析：8251与6105两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数解8251＝6105×1＋2146显然8251和6105的最大公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数继续下去，我们得到：欧几里得（公元前330-公元前275）：古希腊数学家，雅典人欧几里得是柏拉图的学生，长期在亚历山大里亚教书。公元前300年左右，代表作《几何原本》13卷问世，创立了著名的欧氏几何，至今仍为中学生必学的一门基础知识。欧几里得对光学也有一定研究。6105＝2146×2＋18132146＝1813×1＋3331813＝333×5＋148333＝148×2＋37148＝37×4＋0则37为8251与6105的最大公约数这就是辗转相除法，有除法的性质可以知道，对于任意两个正整数，上述除法步骤总可以在有限步骤之后完成利用辗转相除法求最大公约数的步骤如下：第一步：给定两个正整数m,n.第二步：计算m除以n的余数.第三步：m=n,n=r.第四步：若r＝0,则m,n的最大公约数等于m;否则,返回第二步.r=mMODnm=nn=rr=o?否是程序图框带余除法INPUT“请输入m，n的值”；m，nDOr=mMODNm=nn=rLOOPUNTILr=0PRINTmEND为什么要用直到型循环结构？1.利用辗转相除法求两数4081与20723的最大公约数，写出它的流程框图和BASIC程序更相减损术我国早期也有解决求最大公约数问题的算法《九章算术》（公元50年～100年或更早）是中国古代数学专著，承先秦数学发展的源流，进入汉朝后又经许多学者的删补才最后成书，这大约是公元一世纪的下半叶。它的出现，标志着中国古代数学体系的形成。历代数学家把它尊为“算经之首”．这是世界上最早的印刷本数学书。《九章算术》共收有246个数学问题，分为九章。分别是：方田、栗米、衰分、少广、商功、均输、盈不足、方程、勾股。《九章算术》是世界上最早系统叙述了分数运算的著作；其中盈不足的算法更是一项令人惊奇的创造；“方程”章还在世界数学史上首次阐述了负数及其加减运算法则。更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。翻译出来为：第一步：任意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数例1用更相减损术求98与63的最大公约数.解由于63不是偶数，把98和63以大数减小数，并辗转相减98-63＝3563-35＝2835-28＝728-7＝1414-7＝7所以，98与63的最大公约数是7比较辗转相除法与更相减损术的区别（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到思考一.用辗转相除法求下列各组数的最大公约数，并在自己编写的BASIC程序中验证。（1）225，135（2）98，196（3）72，168思考二：用更相减损法可否求上述3组数的最大公约数？可否利用更相减损法设计出程序框图及程序？若能，在电脑上测试自己的程序；若不能说明无法实现的理由。思考三：利用辗转相除法是否可以求两数的最大公倍数？试设计程序框图并转换成程序在BASIC中实现。案例二（秦九韶算法）怎样求多项式1)(2354xxxxxxf当x=5时的值？据我们的计算统计可以得出我们共需要10次乘法运算，5次加法运算我们把多项式变形为：再统计一下计算当时的值时需要的计算次数，可以得出仅需4次乘法和5次加法运算即可得出结果。显然少了6次乘法运算。这种算法就叫秦九韶算法。1)))1(1(1()(2xxxxxxf秦九韶（1202--1261年），字道古，安岳县人。其父秦季栖，进士出身，官至工部郎中、秘书少监。秦九韶性敏慧，勤奋好学，幼年随父居中都（今北京），受到名师指导，学习日益增进。及长，随父迁湖州（今浙江吴兴县），在西门外修建住房，由秦九韶设计施工，堂分7间，后为列室，仅中堂1间，纵横7丈，极其宏伟宽敞，显示出他在建筑方面的才能01210123120132211012211)))((())(()()(aaxaxaxaaxaxaxaxaaxaxaxaxaaxaxaxaxaxfnnnnnnnnnnnnnnnnnnn把一个多项式012211)(axaxaxaxaxfnnnnnn改写为：求多项式的值时，首先计算最内层括号内的一次多项式的值，即：11nnaxav01323212avvaxvvaxvvnnnn再有内向外逐层计算一次多项式的值，即：这样将求n次多项式f(x)的值转化为求n个一次多项式的值。例2已知一个5次多项式为5432()423.52.61.70.8fxxxxxx当5x用秦九韶算法求这个多项式的值。012345()((((42)3.5)2.6)1.7)0.84;45222;223.5113.5;113.552.6564.9;564.951.72826.2;2826.250.814130.2.,5,fxxxxxxvvvvvvx根据秦几韶算法,把多项式改写成如下形式:按照从内到外的顺序,依次计算一次多项式当绵值:所以当时多项式的值等于14130.2.用秦九韶算法求这个多项式当时的值。8.07.16.25.325)(2345xxxxxxf5x3.已知一个5次多项式为思考：（1）例1计算时需要多少次乘法计算？多少次加法计算？（2）在利用秦九韶算法计算n次多项式当时需要多少次乘法计算和多少次加法计算？进位制是人们为了计数和运算方便而约定的计数系统，约定满二进一，就是二进制；满十进一，就是十进制，等等，也就是说满几进一就是几进制，几进制的基数就是几大于1的整数由于自然数有无限多个，对于每一个自然数如果都用一个独立的名称或符号来读出它或表示它，那是很不方便的，也是不可能做到的。因此，需要建立一种读数、写数制度--进位制12232n1n1nna10a10a10a10a十进制数表示实际数值为：1231nnaaaaa12232n1n1nnakakakakaK进制数实际表示数为：)k(1231nnaaaaa在日常生活中，我们最熟悉的还是十进制数，据说这和古人曾以手指计数有关为了区别进制，我们就用下标（k）表示k进制数a[n]是0～9的数子下面我们来用一个具体的例子来分析：例3.将二进制数110011(2)化成十进制数解根据k进制数的实际意义，我们可以这样来转换：51121161321212120202121011110012345(2)INPUTa,b,cb=0i=1T=aMOD10DOb=b+t*k^(i-1)a=a\10t=aMOD10i=i+1LOOPUNTILinPRINTbEND例4设计一个算法,把k进制数a(共n位)转化为十进制数b.缺少算法分析和程序框图例5.把89化为二进制数分析：89=2×(2×(2×(2×(2×2+1)+1)+0)+0)+1=…=1011001(2)28912440222021112512202110所以上式可以表示为：1011001综合：上述方法叫做k进制数的除k取余法5.把89化为五进制数思考：1如何将十六进制数A1F721化为二进制数一般方法：k进制数十进制数n进制数101000011111011100100001算法程序图框算法语句辗转相除与更相减损术秦九韶算法进位制