数学算法PPT课件.ppt

1、2020年9月28日1第一章第一章 算法初步算法初步 1.3 1.3 算法案例算法案例2020年9月28日2例：求下面两个正整数的最大公约数：例：求下面两个正整数的最大公约数：（1）求）求25和和35的最大公约数的最大公约数（2）求）求49和和63的最大公约数的最大公约数25（1） 5535749（2） 77639所以，所以，25和和35的最大公的最大公约数为约数为5所以，所以，49和和63的最大公的最大公约数为约数为7思考：除了用这种方法外还有没有其它方法？思考：除了用这种方法外还有没有其它方法？例：如何算出例：如何算出8251和和6105的最大公约数？的最大公约数？辗转相除法与更相减损术2

2、020年9月28日3一、辗转相除法（欧几里得算法）一、辗转相除法（欧几里得算法）1、定义：、定义：所谓辗转相除法，就是对于给定的两个数，用较大的数除以所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。若余数不为零，则将余数和较小的数构成新的一对数，继续较小的数。若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数。最大公约数。 2、步骤、步骤（以求（以求8251和和6105的最大公约数的过程为例）的最大公约数的过程为例）第一步第一步 用两数中较大的数

3、除以较小的数，求得商和余数用两数中较大的数除以较小的数，求得商和余数8251=61051+2146结论：结论： 8251和和6105的公约数就是的公约数就是6105和和2146的公约数，求的公约数，求8251和和6105的最大公约数，的最大公约数，只要求出只要求出6105和和2146的公约数就可以了。的公约数就可以了。第二步第二步 对对6105和和2146重复第一步的做法重复第一步的做法6105=21462+1813同理同理6105和和2146的最大公约数也是的最大公约数也是2146和和1813的最大公约数。的最大公约数。 2020年9月28日4完整的过程完整的过程8251=61051+214

4、6 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的最大公约数的最大公约数 思考：从上面的两个例子中可思考：从上面的两个例子中可以看出计算的规律是什么？以看出计算的规律是什么？ S1：用大

5、数除以小数：用大数除以小数S2：除数变成被除数，余数：除数变成被除数，余数变成除数变成除数S3：重复：重复S1，直到余数为，直到余数为02020年9月28日5 辗转相除法是一个反复执行直到余数等于辗转相除法是一个反复执行直到余数等于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思考：辗转相

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

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

8、以，所以，9898和和6363的最大公约数等于的最大公约数等于7 7 2020年9月28日9INPUT 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思考：你能根据更相减损术设计程序，求两个正整数的最大公约数吗？2020年9月28日10（1）设计求多项式）设计求多项式763452)(2345xxxxxxf当当x=5时的值的

9、算法，并写出程序。时的值的算法，并写出程序。（2）有没有更高效的算法？能否探求更好的算法，来解决任意多项式的）有没有更高效的算法？能否探求更好的算法，来解决任意多项式的求解问题？求解问题？引导学生把多项式变形为：引导学生把多项式变形为：7)6) 3)4)52(763452)(2345xxxxxxxxxxxf思考：从内到外，如果把每一个括号都看成一个常数，那么变形思考：从内到外，如果把每一个括号都看成一个常数，那么变形后的式子中有哪些后的式子中有哪些“一次式一次式”？x的系数依次是什么？的系数依次是什么？2020年9月28日11（3）若将）若将x的值代入变形后的式子中，那么求值的计算过程是怎样的

10、值代入变形后的式子中，那么求值的计算过程是怎样的？的？ 将变形前将变形前x的系数乘以的系数乘以x的值，加上变形前的第的值，加上变形前的第2个系数，得到一个新个系数，得到一个新的系数；将此系数继续乘以的系数；将此系数继续乘以x的值，再加上变形前的第的值，再加上变形前的第3个系数，又得到一个系数，又得到一个新的系数；继续对新系数做上面的变换，直到与变形前的最后一个系数个新的系数；继续对新系数做上面的变换，直到与变形前的最后一个系数相加，得到一个新的系数为止。这个系数即为所求多项式的值。这种算法相加，得到一个新的系数为止。这个系数即为所求多项式的值。这种算法即是即是“秦九韶算法秦九韶算法” （4）用

11、秦九韶算法求多项式的值，与多项式组成有直接关）用秦九韶算法求多项式的值，与多项式组成有直接关系吗？用秦九韶算法计算上述多项式的值，需要多少次乘系吗？用秦九韶算法计算上述多项式的值，需要多少次乘法运算和多少次加法运算法运算和多少次加法运算？ 2020年9月28日12数书九章数书九章秦九韶算法秦九韶算法0111)(axaxaxaxfnnnn设设)(xf是一个是一个n 次的多项式次的多项式对该多项式按下面的方式进行改写：对该多项式按下面的方式进行改写：0111)(axaxaxaxfnnnn01211)(axaxaxannnn012312)(axaxaxaxannnn0121)(axaxaxaxann

12、n这是怎样的一种改写方式？最后的结果是什么？2020年9月28日130121)()(axaxaxaxaxfnnn要求多项式的值，应该先算最内层的一次多项式的值，即要求多项式的值，应该先算最内层的一次多项式的值，即11nnaxav然后，由内到外逐层计算一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即212naxvv323naxvv01axvvnn最后的一最后的一项是什么？项是什么？这种将求一个这种将求一个n次多项式次多项式f(x)的值转化成求的值转化成求n个一个一次多项式的值的方法，称为次多项式的值的方法，称为秦九韶算法秦九韶算法。2020年9月28日14程序框图：程序框图：这是一个在

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

14、xv=ai=n-1WHILE i=0 PRINT “i=“;i INPUT “ai=“;a v=v*x+a i=i-1WENDPRINT vEND2020年9月28日161 1、什么是进位制？、什么是进位制？进位制是人们为了计数和运算方便而约定的记数系统。进位制是人们为了计数和运算方便而约定的记数系统。进位制是一种记数方式，用有限的数字在不同的位进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值。可使用数字符号的个数称为基置表示不同的数值。可使用数字符号的个数称为基数，基数为数，基数为n n，即可称，即可称n n进位制，简称进位制，简称n n进制。进制。 比如：比如： 满二进一，就是

15、二进制；满二进一，就是二进制； 满十进一，就是十进制；满十进一，就是十进制； 满十二进一，就是十二进制；满十二进一，就是十二进制； 满六十进一，就是六十进制满六十进一，就是六十进制基数：基数：“满几进一满几进一”就是几进制，几进制的基数就是几就是几进制，几进制的基数就是几. .2020年9月28日172 2、最常见的进位制是什么？除此之外还有哪些常见、最常见的进位制是什么？除此之外还有哪些常见的进位制？请举例说明的进位制？请举例说明 最常见的进位制应该是我们数学中的十进制最常见的进位制应该是我们数学中的十进制, ,比如比如一般的数值计算，但是并不是生活中的每一种数一般的数值计算，但是并不是生活

16、中的每一种数字都是十进制的字都是十进制的. . 古人有古人有半斤八两半斤八两之说，就是十六进制与十进制的之说，就是十六进制与十进制的转换转换. . 比如时间和角度的单位用六十进位制比如时间和角度的单位用六十进位制, , 计算计算“一一打打”数值时是数值时是1212进制的。进制的。 电子计算机用的是二进制电子计算机用的是二进制 。 2020年9月28日18 式中式中1 1处在百位，第一个处在百位，第一个3 3所在十位，第二个所在十位，第二个3 3所在所在个位，个位，5 5和和9 9分别处在十分位和百分位。十进制数是逢分别处在十分位和百分位。十进制数是逢十进一的。十进一的。 我们最常用最熟悉的就是

17、十进制数，它的数值我们最常用最熟悉的就是十进制数，它的数值部分是十个不同的数字符号部分是十个不同的数字符号0 0，1 1，2 2，3 3，4 4，5 5，6 6，7 7，8 8，9 9来表示的。来表示的。十进制：十进制：例如例如133.59133.59，它可用一个多项式来表示：，它可用一个多项式来表示：133.59=1133.59=1* *10102 2+3+3* *10101 1+3+3* *10100 0 +5+5* *1010-1-1+9+9* *1010-2-22020年9月28日19 实际上，十进制数只是计数法中的一种，但它不是实际上，十进制数只是计数法中的一种，但它不是唯一记数法。

18、除了十进制数，生产生活中还会遇到非十唯一记数法。除了十进制数，生产生活中还会遇到非十进制的记数制。如时间：进制的记数制。如时间：6060秒为秒为1 1分，分，6060分为分为1 1小时，它小时，它是六十进制的。两根筷子一双，两只手套为一副，它们是六十进制的。两根筷子一双，两只手套为一副，它们是二进制的。是二进制的。其它进制：其它进制：二进制、七进制、八进制、十二进制、六十进制二进制、七进制、八进制、十二进制、六十进制二进制只有0和1两个数字，七进制用06七个数字十六进制有09十个数字及ABCDEF六个字母.2020年9月28日20 为了区分不同的进位制，常在数的右下角标明基数，为了区分不同的进

19、位制，常在数的右下角标明基数，十进制一般不标注基数十进制一般不标注基数. .例如十进制的例如十进制的133.59133.59，写成，写成133.59133.59(10)(10)七进制的七进制的1313，写成，写成1313(7)(7)；二进制的；二进制的1010，写成，写成1010(2) (2) 一般地，若一般地，若k k是一个大于是一个大于1 1的整数，那么以的整数，那么以k k为基数的为基数的k k进制可以表示为一串数字连写在一起进制可以表示为一串数字连写在一起的形式：的形式：11 0( )110(0,0, , ,).n nknnaaaaa kaa a k 2020年9月28日21十进制的构

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

21、满十进一”2020年9月28日22110( )110110(10)nnknnnna aa aakakakak其它进制数化成十进制数公式2020年9月28日23二进制二进制二进制是用二进制是用0 0、1 1两个数字来描述的如两个数字来描述的如1100111001二进制的表示方法二进制的表示方法区分的写法：区分的写法：1100111001（2 2）或者或者(11001)(11001)2 201234(2)212020212111001八进制呢？八进制呢？ 如如73427342(8)(8)k k进制呢？进制呢？ a an na an-1n-1a an-2n-2a a1(k)1(k)？2020年9月2

22、8日24二进制与十进制的转换二进制与十进制的转换1 1、二进制数转化为十进制数、二进制数转化为十进制数例例1 1：将二进制数：将二进制数110011110011(2)(2)化成十进制数。化成十进制数。解：解：根据进位制的定义可知根据进位制的定义可知012345)2(21212020212111001112116132151所以，所以，110011110011（2 2）=51=512020年9月28日25例例2 2、设计一个算法，将、设计一个算法，将k k进制数进制数a(a(共有共有n n位位) )转换为十进转换为十进制数制数b b。(1)(1)算法步骤算法步骤: :第一步，输入第一步，输入a,

23、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 b的值的值. .2020年9月28日26(2)程序框图程序框图:开始开始输入输入a,k,nb=0i=1把把a的右数第的右数第i位数字赋给位数字赋给tb=b+t*ki-1i=i+1in?否否是是输出输出b结束结束2020

24、年9月28日27(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 bEND2020年9月28日28*上面的程序如采用上面的程序如采用get函数函数,可简化为：可简化为：INPUT a,k,nINPUT a,k,ni=1i=1b=0b=0WHILE i=nWHILE i=nt=GET ait=GET aib=tb=t* *k(i-1)+bk(i-1)+bi=i+1i=i+1WENDWENDPRINT bPRINT bENDEND备注备注:GET

25、函数用于取出函数用于取出a的右数第的右数第i位数位数2020年9月28日29方法：除方法：除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（221）1）0）0）189126025124123022021120所以：所以：89=1011001（2）2（2（2（2321）0）0）12（2（242220）0）12（2

26、523+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、十进制转换为二进制、十进制转换为二进制2020年9月28日30注意：注意：1. 1.最后一步商为最后一步商为0 0，2.2.将上式各步所得的余数将上式各步所得的余数从下到上排列从下到上排列，得到：，得到： 89=101100189=1011001（2 2）另解（另解（除除2 2取余法的另一直观写法取余法的另一直观写法）：）：5 52 22 22 21 12 20 01 10 0余数余数

27、11112222444489892 22 22 22 20 01 11 10 01 1练习练习将下面的十进制数化为二进制数？将下面的十进制数化为二进制数？（1 1）1010（2 2）20202020年9月28日312020年9月28日32演讲完毕，谢谢观看！Thank you for reading! In order to facilitate learning and use, the content of this document can be modified, adjusted and printed at will after downloading. Welcome to download!汇报人：XXX 汇报日期：20XX年10月10日