第一章第一章 算法初步算法初步 1.3 算法案例算法案例 例：求下面两个正整数的最大公约数：例：求下面两个正整数的最大公约数：（（1）求）求25和和35的最大公约数的最大公约数（（2）求）求49和和63的最大公约数的最大公约数25（（1））5535749（（2））77639所以，所以，25和和35的最大公约数的最大公约数为为5所以，所以，49和和63的最大公约数的最大公约数为为7思考：除了用这种方法外还有没有其它方法？思考：除了用这种方法外还有没有其它方法？例：如何算出例：如何算出8251和和6105的最大公约数？的最大公约数？辗转相除法与更相减损术 一、辗转相除法（欧几里得算法）一、辗转相除法（欧几里得算法）1、定义：、定义：所谓辗转相除法，就是对于给定的两个数，用较所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数若余数不为零，则将余数和较小的数大的数除以较小的数若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数则这时较小的数就是原来两个数的最大公约数。
2、步骤、步骤（以求（以求8251和和6105的最大公约数的过程为例）的最大公约数的过程为例）第一步第一步 用两数中较大的数除以较小的数，求得商和余数用两数中较大的数除以较小的数，求得商和余数8251=6105×1+2146结论：结论： 8251和和6105的公约数就是的公约数就是6105和和2146的公约数，求的公约数，求8251和和6105的最大公约数，的最大公约数，只要求出只要求出6105和和2146的公约数就可以了的公约数就可以了第二步第二步 对对6105和和2146重复第一步的做法重复第一步的做法6105=2146×2+1813同理同理6105和和2146的最大公约数也是的最大公约数也是2146和和1813的最大公约数的最大公约数 完整的过程完整的过程8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0例：例： 用辗转相除法求用辗转相除法求225和和135的最大的最大公约数公约数225=135×1+90135=90×1+4590=45×2显然显然37是是148和和37的最大公约的最大公约数，也就是数，也就是8251和和6105的最的最大公约数大公约数 显然显然45是是90和和45的最大公约数，也就是的最大公约数，也就是225和和135的最大公约数的最大公约数 思考：从上面的两个例子中可以看思考：从上面的两个例子中可以看出计算的规律是什么？出计算的规律是什么？ S1：用大数除以小数：用大数除以小数S2：除数变成被除数，余数变成：除数变成被除数，余数变成除数除数S3：重复：重复S1，直到余数为，直到余数为0 辗转相除法是一个反复执行直到余数等于辗转相除法是一个反复执行直到余数等于0才停止的步骤，才停止的步骤，这实际上是一个循环结构。
这实际上是一个循环结构m = n × q ＋＋ r用程序框图表示出右边的过程用程序框图表示出右边的过程r=m MOD nm = nn = rr=0?是否8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0思考：辗转相除法中的关键步骤是哪种逻辑结构？ 程序框图：程序框图：开始开始输入输入m,n r=m MOD n m=nr=0?是是否否 n=r 输出输出m结束结束思考：你能把辗转相除法编成一个计算机程序吗？ 程序：程序：INPUT “m,n=”;m,nDO r=m MOD n m=n n=rLOOP UNTIL r=0PRINT mEND 1.定义：定义：所谓更相减损术，就是对于给定的两个数，用较大所谓更相减损术，就是对于给定的两个数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，的数减去较小的数，然后将差和较小的数构成新的一对数，再用较大的数减去较小的数，反复执行此步骤直到差数和再用较大的数减去较小的数，反复执行此步骤直到差数和较小的数相等，此时相等的两数便为原来两个数的最大公较小的数相等，此时相等的两数便为原来两个数的最大公约数。
约数二、更相减损术二、更相减损术2、方法：、方法：例例: 用更相减损术求用更相减损术求98与与63的最大公约数的最大公约数.解：由于解：由于63不是偶数，把不是偶数，把98和和63以大数减小数，并辗以大数减小数，并辗转相减转相减 98－－63＝＝3563－－35＝＝2835－－28＝＝728－－7＝＝2121－－7＝＝1414－－7＝＝7所以，所以，98和和63的最大公约数等于的最大公约数等于7 INPUT m, nIF mn IF d>n THEN m=d ELSE m=n n=d END IF d=m-nWENDd=2 k*dPRINT dEND思考：你能根据更相减损术设计程序，求两个正整数的最大公约数吗？ （（1）设计求多项式）设计求多项式当当x=5时的值的算法，并写出程序。
时的值的算法，并写出程序2）有没有更高效的算法？能否探求更好的算法，来解决任）有没有更高效的算法？能否探求更好的算法，来解决任意多项式的求解问题？意多项式的求解问题？三、秦九韶算法三、秦九韶算法三、秦九韶算法三、秦九韶算法引导学生把多项式变形为：引导学生把多项式变形为：思考：从内到外，如果把每一个括号都看成一个常数，思考：从内到外，如果把每一个括号都看成一个常数，那么变形后的式子中有哪些那么变形后的式子中有哪些“一次式一次式”？？x的系数依次的系数依次是什么？是什么？ （（3）若将）若将x的值代入变形后的式子中，那么求值的计算过的值代入变形后的式子中，那么求值的计算过程是怎样的？程是怎样的？ 将变形前将变形前x的系数乘以的系数乘以x的值，加上变形前的第的值，加上变形前的第2个系数，得个系数，得到一个新的系数；将此系数继续乘以到一个新的系数；将此系数继续乘以x的值，再加上变形前的的值，再加上变形前的第第3个系数，又得到一个新的系数；继续对新系数做上面的变个系数，又得到一个新的系数；继续对新系数做上面的变换，直到与变形前的最后一个系数相加，得到一个新的系数为换，直到与变形前的最后一个系数相加，得到一个新的系数为止。
这个系数即为所求多项式的值这种算法即是止这个系数即为所求多项式的值这种算法即是“秦九韶算秦九韶算法法” （（4）用秦九韶算法求多项式的值，与多项式组）用秦九韶算法求多项式的值，与多项式组成有直接关系吗？用秦九韶算法计算上述多项式成有直接关系吗？用秦九韶算法计算上述多项式的值，需要多少次乘法运算和多少次加法运算？的值，需要多少次乘法运算和多少次加法运算？ 计算只与多项式的系数计算只与多项式的系数有关，有关， 《《数书九章数书九章》》——秦九韶算法秦九韶算法设设是一个是一个n 次的多项式次的多项式对该多项式按下面的方式进行改写：对该多项式按下面的方式进行改写：这是怎样的一种改写方式？最后的结果是什么？ 要求多项式的值，应该先算最内层的一次多项式的值，即要求多项式的值，应该先算最内层的一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即最后的一最后的一项是什么项是什么？？这种将求一个这种将求一个n次多项式次多项式f(x)的值转化成求的值转化成求n个一次多项式个一次多项式的值的方法，称为的值的方法，称为秦九韶算法秦九韶算法 程序框图：程序框图：这是一个在这是一个在秦九韶算法中反秦九韶算法中反复执行的步骤，因此可用循复执行的步骤，因此可用循环结构来实现。
环结构来实现输入输入ai开始开始输入输入n,an,xi>=0?输出输出v结束结束v=vx+aii=i-1YNi=n-1V=an秦九韶算法的特点：秦九韶算法的特点： 通过一次式的反复计算，逐步得通过一次式的反复计算，逐步得出高次多项式的值，对于一个出高次多项式的值，对于一个n次多次多项式，只需做项式，只需做n次乘法和次乘法和n次加法即次加法即可 程序：程序：INPUT “n=”；；nINPUT “an=“;aINPUT “x=“;xv=ai=n-1WHILE i>=0 PRINT “i=“;i INPUT “ai=“;a v=v*x+a i=i-1WENDPRINT vEND 四、进位制四、进位制四、进位制四、进位制1、什么是进位制？、什么是进位制？进位制是人们为了计数和运算方便而约定的记数系统进位制是人们为了计数和运算方便而约定的记数系统进位制是一种记数方式，用有限的进位制是一种记数方式，用有限的数字数字在不同的位置表示不在不同的位置表示不同的数值可使用数字符号的个数称为基数，基数为同的数值可使用数字符号的个数称为基数，基数为n，即可，即可称称n进位制，简称进位制，简称n进制。
进制 比如：比如： 满二进一，就是二进制；满二进一，就是二进制； 满十进一，就是十进制；满十进一，就是十进制； 满十二进一，就是十二进制；满十二进一，就是十二进制； 满六十进一，就是六十进制满六十进一，就是六十进制基数：基数：“满几进一满几进一”就是几进制，几进制的基数就是几就是几进制，几进制的基数就是几. 2、最常见的进位制是什么？除此之外还有哪些常见的进位制、最常见的进位制是什么？除此之外还有哪些常见的进位制？请举例说明．？请举例说明．•最常见的进位制应该是我们数学中的十进制最常见的进位制应该是我们数学中的十进制,比如一般的数比如一般的数值计算，但是并不是生活中的每一种数字都是十进制的值计算，但是并不是生活中的每一种数字都是十进制的.•古人有古人有半斤八两半斤八两之说，就是十六进制与十进制的转换之说，就是十六进制与十进制的转换.•比如时间和角度的单位用六十进位制比如时间和角度的单位用六十进位制, 计算计算“一打一打”数值数值时是时是12进制的•电子计算机用的是二进制电子计算机用的是二进制 式式中中1处处在在百百位位，，第第一一个个3所所在在十十位位，，第第二二个个3所所在在个个位位，，5和和9分别处在十分位和百分位。
十进制数是逢十进一的分别处在十分位和百分位十进制数是逢十进一的 我们最常用最熟悉的就是十进制数，它的数值部分是十我们最常用最熟悉的就是十进制数，它的数值部分是十个不同的数字符号个不同的数字符号0，，1，，2，，3，，4，，5，，6，，7，，8，，9来表示来表示的十进制：十进制：例如例如133.59，它可用一个多项式来表示：，它可用一个多项式来表示：133.59=1*102+3*101+3*100 +5*10-1+9*10-2 实际上，十进制数只是计数法中的一种，但它不是实际上，十进制数只是计数法中的一种，但它不是唯一记数法除了十进制数，生产生活中还会遇到非十唯一记数法除了十进制数，生产生活中还会遇到非十进制的记数制如时间：进制的记数制如时间：60秒为秒为1分，分，60分为分为1小时，它小时，它是六十进制的两根筷子一双，两只手套为一副，它们是六十进制的两根筷子一双，两只手套为一副，它们是二进制的是二进制的其它进制：其它进制：二进制、七进制、八进制、十二进制、六十进制二进制、七进制、八进制、十二进制、六十进制……二进制只有0和1两个数字，七进制用0~6七个数字十六进制有0~9十个数字及ABCDEF六个字母. 为了区分不同的进位制，常在数的右下角标明基数，十进制一为了区分不同的进位制，常在数的右下角标明基数，十进制一般不标注基数般不标注基数.例如十进制的例如十进制的133.59，写成，写成133.59(10)七进制的七进制的13，写成，写成13(7)；二进制的；二进制的10，写成，写成10(2) 一般地，若一般地，若k是一个大于是一个大于1的整数，那么以的整数，那么以k为基数的为基数的k进制可以表示为一串数字连写在一起进制可以表示为一串数字连写在一起的形式：的形式： 十进制的构成十进制的构成十进制由两个部分构成十进制由两个部分构成例如：例如：3721其它进位制的数又是如何的呢？其它进位制的数又是如何的呢？第一、它有第一、它有0～～9十个数字；十个数字；第二、它有第二、它有“数位数位”，即，即从右往左从右往左为个位、十位、百位、为个位、十位、百位、千位等等。
千位等等用用10个数字来记数，称基数为个数字来记数，称基数为10)表示有：表示有：1个个1，，2个十，个十， 7个百即个百即7个个10的平方，的平方，3个千即个千即3个个10的立方的立方十进制：十进制：“满十进一满十进一” 其它进制数化成十进制数公式 二进制二进制二进制是用二进制是用0、、1两个数字来描述的．如两个数字来描述的．如11001二进制的表示方法二进制的表示方法区分的写法：区分的写法：11001（（2））或者或者(11001)2八进制呢？八进制呢？如如7342(8)k进制呢？进制呢？anan-1an-2…a1(k)？？ 二进制与十进制的转换二进制与十进制的转换1、二进制数转化为十进制数、二进制数转化为十进制数例例1：将二进制数：将二进制数110011(2)化成十进制数化成十进制数解：解： 根据进位制的定义可知根据进位制的定义可知所以，所以，110011（（2））=51．． 例例2、设计一个算法，将、设计一个算法，将k进制数进制数a(共有共有n位位)转换为十进制数转换为十进制数b1)算法步骤算法步骤:第一步，输入第一步，输入a,k和和n的值；的值；第二步，将第二步，将b的值初始化为的值初始化为0,i的值初始化为的值初始化为1；；第三步，第三步，b=b+ai*ki-1, i=i+1第四步，判断第四步，判断i>n是否成立是否成立.若是若是,则执行第五步则执行第五步,否则否则,返回第三返回第三步；步；第五步，输出第五步，输出b的值的值. (2)程序框图程序框图:开始开始输入输入a,k,nb=0i=1把把a的右数第的右数第i位数字赋给位数字赋给tb=b+t*ki-1i=i+1i>n?否否是是输出输出b结束结束 (3)程序：程序：INPUT “a,k,n=”;a,k,nb=0i=1t=a MOD 10DO b=b+t*k^(i-1) a=a\10 t=a MOD 10 i=i+1LOOP UNTIL i>nPRINT bEND **上面的程序如采用上面的程序如采用get函数函数,可简化为：可简化为：INPUT a,k,ni=1b=0WHILE i<=nt=GET a[i]b=t*k^(i-1)+bi=i+1WENDPRINT bEND备注备注:GET函数用于取出函数用于取出a的右数第的右数第i位数位数 方法：除方法：除2取余法，即用取余法，即用2连续去除连续去除89或所得的商，然后取余数。
或所得的商，然后取余数例、例、 把把89化为二进制数化为二进制数解：解：根据根据“逢二进一逢二进一”的原则，有的原则，有89＝＝2×44＋1＝ 2× (2×22＋＋0)+1＝ 2×( 2×( 2×11＋＋0)+0)+1＝ 2× (2× (2× (2× 5＋＋1)+0)+0)+15＝ 2× 2＋＋1＝＝2×（（2×（（2×（（2×（（22＋＋1））＋＋1）＋）＋0）＋）＋0）＋）＋189＝＝1×26＋＋0×25＋＋1×24＋＋1×23＋＋0×22＋＋0×21＋＋1×20所以：所以：89=1011001（（2））＝＝2×（（2×（（2×（（23＋＋2＋＋1））＋＋0）＋）＋0）＋）＋1＝＝2×（（2×（（24＋＋22＋＋2＋＋0））＋＋0）＋）＋1＝＝2×（（25＋＋23+22＋＋0＋＋0））＋＋1＝＝26＋＋24+23＋＋0＋＋0＋＋2089＝＝2×44＋144＝＝ 2×22＋＋022＝ 2×11＋＋011＝ 2× 5＋＋1＝ 2× (2× (2× (2× (2× 2＋＋1)+1)+0)+0)+1所以所以89＝＝2×（（2×（（2×（（2×（（2 × 2 ＋＋1））＋＋1）＋）＋0）＋）＋0）＋）＋12、十进制转换为二进制、十进制转换为二进制 注意：注意：1.最后一步商为最后一步商为0，，2.将上式各步所得的余数将上式各步所得的余数从下到上排列从下到上排列，得到：，得到： 89=1011001（（2））另解（另解（除除2取余法的另一直观写法取余法的另一直观写法）：）：522212010余数余数11224489222201101练习练习将下面的十进制数化为二进制数？将下面的十进制数化为二进制数？（（1））10（（2））20 把把89化为五进制数。
化为五进制数3、十进制转换为其它进制、十进制转换为其它进制解：解：根据根据除除k取余法取余法以以5作为除数，相应的除法算式为：作为除数，相应的除法算式为：所以，所以，89=324（（5））895175350423余数余数 。