数学算法学习.pptx

《数学算法学习.pptx》由会员分享，可在线阅读，更多相关《数学算法学习.pptx（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、例：求下面两个正整数的最大公约数：例：求下面两个正整数的最大公约数：（1）求）求25和和35的最大公约数的最大公约数（2）求）求49和和63的最大公约数的最大公约数25（1）5535749（2）77639所以，25和35的最大公约数为5所以，49和63的最大公约数为7思考：除了用这种方法外还有没有其它方法？例：如何算出8251和6105的最大公约数？辗转相除法与更相减损术第1页/共31页一、辗转相除法（欧几里得算法）一、辗转相除法（欧几里得算法）1、定义：、定义：所谓辗转相除法，就是对于给定的两个数，用较大的数除以所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。若余数不为零，则将

2、余数和较小的数构成新的一对数，继续较小的数。若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数。最大公约数。2、步骤、步骤（以求（以求8251和和6105的最大公约数的过程为例）的最大公约数的过程为例）第一步 用两数中较大的数除以较小的数，求得商和余数8251=61051+2146结论：8251和6105的公约数就是6105和2146的公约数，求8251和6105的最大公约数，只要求出6105和2146的公约数就可以了。第二步 对6105和2146重复第一步的

3、做法6105=21462+1813同理6105和2146的最大公约数也是2146和1813的最大公约数。第2页/共31页完整的过程完整的过程8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0例：用辗转相除法求225和135的最大公约数225=1351+90135=901+4590=452显然显然37是是148和和37的最大的最大公约数，也就是公约数，也就是8251和和6105的最大公约数的最大公约数 显然显然45是是90和和45的最大公约数，的最大公约数，也就是也就是225和和135的最

4、大公约数的最大公约数 思考：从上面的两个例子中可以看出计算的规律是什么？S1：用大数除以小数：用大数除以小数S2：除数变成被除数，余数：除数变成被除数，余数变成除数变成除数S3：重复：重复S1，直到余数为，直到余数为0第3页/共31页 辗转相除法是一个反复执行直到余数等于0才停止的步骤，这实际上是一个循环结构。m=n q r用程序框图表示出右边的过程用程序框图表示出右边的过程r=m MOD nm=nn=rr=0?是否8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0思考：辗转相除法中的关

5、键步骤是哪种逻辑结构？第4页/共31页程序框图：程序框图：开始开始输入输入m,n r=m MOD n m=nr=0?是是否否 n=r 输出输出m结束结束思考：你能把辗转相除法编成一个计算机程序吗？第5页/共31页程序：程序：INPUT “m,n=”;m,nDO r=m MOD n m=n n=rLOOP UNTIL r=0PRINT mEND第6页/共31页1.定义：定义：所谓更相减损术，就是对于给定的两个数，用较大的数减去较所谓更相减损术，就是对于给定的两个数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，再用较大的数减去较小小的数，然后将差和较小的数构成新的一对数，再用较大的数

6、减去较小的数，反复执行此步骤直到差数和较小的数相等，此时相等的两数便为的数，反复执行此步骤直到差数和较小的数相等，此时相等的两数便为原来两个数的最大公约数。原来两个数的最大公约数。二、更相减损术二、更相减损术2、方法：、方法：例例:用更相减损术求用更相减损术求9898与与6363的最大公约数的最大公约数.解：由于解：由于6363不是偶数，把不是偶数，把9898和和6363以大数减小数，并辗转相减以大数减小数，并辗转相减 989863633535636335352828353528287 728287 7212121217 7141414147 77 7所以，所以，9898和和6363的最大公约

7、数等于的最大公约数等于7 7 第7页/共31页INPUT m,nIF mn THEN a=m m=n n=aEND IFK=0WHILE m MOD 2=0 AND n MOD 2=0 m=m/2 n=n/2 k=k+1WENDd=m-nWHILE dn IF dn THEN m=d ELSE m=n n=d END IF d=m-nWENDd=2 k*dPRINT dEND思考：你能根据更相减损术设计程序，求两个正整数的最大公约数吗？第8页/共31页（1）设计求多项式当x=5时的值的算法，并写出程序。（2）有没有更高效的算法？能否探求更好的算法，来解决任意多项式的求解问题？三、秦九韶算法引导

8、学生把多项式变形为：思考：从内到外，如果把每一个括号都看成一个常数，那么变形后的式子中有哪些“一次式”？x的系数依次是什么？第9页/共31页（3）若将x的值代入变形后的式子中，那么求值的计算过程是怎样的？将变形前x的系数乘以x的值，加上变形前的第2个系数，得到一个新的系数；将此系数继续乘以x的值，再加上变形前的第3个系数，又得到一个新的系数；继续对新系数做上面的变换，直到与变形前的最后一个系数相加，得到一个新的系数为止。这个系数即为所求多项式的值。这种算法即是“秦九韶算法”（4）用秦九韶算法求多项式的值，与多项式组成有直接关系吗？用秦九韶算法计算上述多项式的值，需要多少次乘法运算和多少次加法运

9、算？计算只与多项式的系数有关，第10页/共31页数书九章秦九韶算法设设是一个是一个n 次的多项式次的多项式对该多项式按下面的方式进行改写：对该多项式按下面的方式进行改写：这是怎样的一种改写方式？最后的结果是什么？第11页/共31页要求多项式的值，应该先算最内层的一次多项式的值，即要求多项式的值，应该先算最内层的一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即最后的一最后的一项是什么项是什么？这种将求一个这种将求一个n次多项式次多项式f(x)的值转化成求的值转化成求n个一个一次多项式的值的方法，称为次多项式的值的方法，称为秦九韶算法秦九韶算法。第

10、12页/共31页程序框图：程序框图：这是一个在这是一个在秦九韶算法中反复执行秦九韶算法中反复执行的步骤，因此可用循环结构来实现。的步骤，因此可用循环结构来实现。输入输入ai开始开始输入输入n,an,xi=0?输出输出v结束结束v=vx+aii=i-1YNi=n-1V=an秦九韶算法的特点：秦九韶算法的特点：通过一次式的反复计算，逐步得出高通过一次式的反复计算，逐步得出高次多项式的值，对于一个次多项式的值，对于一个n次多项式，只需次多项式，只需做做n次乘法和次乘法和n次加法即可。次加法即可。第13页/共31页程序：程序：INPUT “n=”；nINPUT“an=“;aINPUT“x=“;xv=a

11、i=n-1WHILE i=0 PRINT“i=“;i INPUT“ai=“;a v=v*x+a i=i-1WENDPRINT vEND第14页/共31页四、进位制1 1、什么是进位制？、什么是进位制？进位制是人们为了计数和运算方便而约定的记数系统。进位制是人们为了计数和运算方便而约定的记数系统。进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值。可使用数字符号的个数称为基数，基数为n n，即可称n n进位制，简称n n进制。比如：比如：满二进一，就是二进制；满十进一，就是十进制；满十二进一，就是十二进制；满六十进一，就是六十进制基数：“满几进一满几进一”就是几进制，几进制的基数就是几

12、就是几进制，几进制的基数就是几.第15页/共31页2 2、最常见的进位制是什么？除此之外还有哪些常见的进位制？请举例说明最常见的进位制应该是我们数学中的十进制,比如一般的数值计算，但是并不是生活中的每一种数字都是十进制的.古人有半斤八两之说，就是十六进制与十进制的转换.比如时间和角度的单位用六十进位制,计算“一打”数值时是1212进制的。电子计算机用的是二进制 。第16页/共31页 式中1 1处在百位，第一个3 3所在十位，第二个3 3所在个位，5 5和9 9分别处在十分位和百分位。十进制数是逢十进一的。我们最常用最熟悉的就是十进制数，它的数值部分是十个不同的数字符号0 0，1 1，2 2，3

13、 3，4 4，5 5，6 6，7 7，8 8，9 9来表示的。十进制：十进制：例如133.59133.59，它可用一个多项式来表示：133.59=1*10133.59=1*102 2+3*10+3*101 1+3*10+3*100 0+5*10+5*10-1-1+9*10+9*10-2-2第17页/共31页 实际上，十进制数只是计数法中的一种，但它不是唯一记数法。除了十进制数，生产生活中还会遇到非十进制的记数制。如时间：6060秒为1 1分，6060分为1 1小时，它是六十进制的。两根筷子一双，两只手套为一副，它们是二进制的。其它进制：二进制、七进制、八进制、十二进制、六十进制二进制、七进制、

14、八进制、十二进制、六十进制二进制只有0和1两个数字，七进制用06七个数字十六进制有09十个数字及ABCDEF六个字母.第18页/共31页 为了区分不同的进位制，常在数的右下角标明基数，为了区分不同的进位制，常在数的右下角标明基数，十进制一般不标注基数十进制一般不标注基数.例如十进制的133.59133.59，写成133.59133.59(10)(10)七进制的1313，写成1313(7)(7)；二进制的1010，写成1010(2)(2)一般地，若一般地，若k k是一个大于是一个大于1 1的整数，那么以的整数，那么以k k为基数的为基数的k k进制可以表示为一串数字连写在一起进制可以表示为一串数

15、字连写在一起的形式：的形式：第19页/共31页十进制的构成十进制的构成十进制由两个部分构成例如：例如：37213721其它进位制的数又是如何的呢？其它进位制的数又是如何的呢？第一、它有0 09 9十个数字；第二、它有“数位”，即从右往左为个位、十位、百位、千位等等。(用1010个数字来记数，称基数为10)10)表示有：表示有：1 1个个1 1，2 2个十，个十，7 7个百即个百即7 7个个1010的平方，的平方，3 3个千即个千即3 3个个1010的立方的立方十进制：“满十进一”第20页/共31页其它进制数化成十进制数公式第21页/共31页二进制二进制二进制是用二进制是用0 0、1 1两个数字

16、来描述的如两个数字来描述的如1100111001二进制的表示方法二进制的表示方法区分的写法：区分的写法：1100111001（2 2）或者或者(11001)(11001)2 2八进制呢？八进制呢？如如73427342(8)(8)k k进制呢？进制呢？a an na an-1n-1a an-2n-2a a1(k)1(k)？第22页/共31页二进制与十进制的转换二进制与十进制的转换1 1、二进制数转化为十进制数、二进制数转化为十进制数例例1 1：将二进制数：将二进制数110011110011(2)(2)化成十进制数。化成十进制数。解：解：根据进位制的定义可知根据进位制的定义可知所以，所以，1100

17、11110011（2 2）=51=51第23页/共31页例例2 2、设计一个算法，将、设计一个算法，将k k进制数进制数a(a(共有共有n n位位)转换为十进转换为十进制数制数b b。(1)(1)算法步骤算法步骤:第一步，输入第一步，输入a,ka,k和和n n的值；的值；第二步，将第二步，将b b的值初始化为的值初始化为0,i0,i的值初始化为的值初始化为1 1；第三步，第三步，b=b+ab=b+ai i*k*ki-1i-1,i=i+1,i=i+1第四步，判断第四步，判断inin是否成立是否成立.若是若是,则执行第五步则执行第五步,否则否则,返回第三步；返回第三步；第五步，输出第五步，输出b

18、b的值的值.第24页/共31页(2)程序框图程序框图:开始开始输入输入a,k,nb=0i=1把把a的右数第的右数第i位数字赋给位数字赋给tb=b+t*ki-1i=i+1in?否否是是输出输出b结束结束第25页/共31页(3)程序：程序：INPUT“a,k,n=”;a,k,nb=0i=1t=a MOD 10DO b=b+t*k(i-1)a=a10 t=a MOD 10 i=i+1LOOP UNTIL inPRINT bEND第26页/共31页*上面的程序如采用上面的程序如采用get函数函数,可简化为：可简化为：INPUT a,k,nINPUT a,k,ni=1i=1b=0b=0WHILE i=n

19、WHILE i=nt=GET ait=GET aib=t*k(i-1)+bb=t*k(i-1)+bi=i+1i=i+1WENDWENDPRINT bPRINT bENDEND备注备注:GET函数用于取出函数用于取出a的右数第的右数第i位数位数第27页/共31页方法：除方法：除2取余法，即用取余法，即用2连续去除连续去除89或所得的商，然后取余数。或所得的商，然后取余数。例、例、把把89化为二进制数化为二进制数解：解：根据根据“逢二进一逢二进一”的原则，有的原则，有892441 2(2220)+1 2(2(2110)+0)+1 2(2(2(2 51)+0)+0)+15 2 212（2（2（2（2

20、21）1）0）0）189126025124123022021120所以：所以：89=1011001（2）2（2（2（2321）0）0）12（2（242220）0）12（2523+2200）12624+23002089244144 222022 211011 2 51 2(2(2(2(2 21)+1)+0)+0)+1所以所以892（2（2（2（2 2 1）1）0）0）12、十进制转换为二进制第28页/共31页注意：注意：1.1.最后一步商为最后一步商为0 0，2.2.将上式各步所得的余数将上式各步所得的余数从下到上排列从下到上排列，得到：，得到：89=101100189=1011001（2 2）另解（另解（除除2 2取余法的另一直观写法取余法的另一直观写法）：）：5 52 22 22 21 12 20 01 10 0余数余数11112222444489892 22 22 22 20 01 11 10 01 1练习练习将下面的十进制数化为二进制数？将下面的十进制数化为二进制数？（1 1）1010（2 2）2020第29页/共31页第30页/共31页感谢您的观看！第31页/共31页