下载文档原格式
算法案例⑴1.回顾算法的三种表述：自然语言程序框图（三种逻辑结构）程序语言（五种基本语句）2.思考：小学学过的求两个数最大公约数的方法先用两个公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来.辗转相除法（欧几里得算法）观察用辗转相除法求8251和6105的最大公约数的过程第一步用两数中较大的数除以较小的数, 求得商和余数8251=6105 X1 +2146 结论：8251和6105的公约数就是6105 和2146的公约数，求8251和6105的最大公约数，只要求出6105和2146的公约数就可以了。
为什么呢?思為从上述的过程你体会到了也? 第二步对6105和2146重复第一步的做法6105=2146 X 2+1813 同理6105 和2146 的最大公约数也是2146和1813的最大公约数。
完整的过程 例2用辗转相除法求225和135的最大公约数8251=6105X1+2146 6105^146X^8132146=^813^J^3331813=333X5+148333=148X2+37148=37 X 4+0 显然37是148和37的最大公 约数，也就是8251和6105 的最大公约数1(欧几里得算法)225=135X1+90// 135=90X1+45 / / 90=45X2 显然45是90和45的最大公约数，也就是 225和135的最大公约数 思考1:从上面的两个例子可以看出计算的规律是什么？(1)算理：所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。
若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数。
148=37X4+0曙相除法是十复执行宜到余数等 于0停止的步骤，这实际上是一个循环结构。
i nm = n X q + r8251=6105X1+2146用程序框图表示出右边的过程 6105=2146X2+18132146=1813X1+3331813=333X5+148(2) 算法步骤第三步：m=n,n=r. 否则转到第二步・ 第五步：输出最大公约数m.第一步: 输入两个正整数m ，n(m>n)・ 第二步:计算m 除以n 所得的余数匸 第四步:若r=0,则m ，n 的最大公约数等于m ；(3)程序框图(4)程INPUT 沁n=“;m，n DOr=m MOD n m=nn=rLOOP UNTIL r=0 PRINT mEND序/输出m/结束《九章算术》——更相减损术第一步：任意给定两个正整数；判断他们是否都是偶数。
若是，则用2约简；若不是则执行第二得的差与较小的数比较，并以大数减小数。
继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。
2、更相减损术(1)算理：所谓更相减损术，就是对于给定的两个数，用较大的数减去较小的数, 然后将差和较小的数构成新的一对数，再用较大的数减去较小的数，反复执行此步骤直到差数和较小的数相等，此时相等的两数便为原来两个数的最大公约数。
例3用更相减损术求98与63的最大公约数解：由于63不是偶数，把98和63以大数减小数，并辗转相减98—63=3563 — 35=28 所以，98和63的35-28=7 最大公约数等于7 28-7=2121-7=2114-7=7练习:用更相减损术求两个正数84与72的最大公约数.12(2)算法步骤第_步：输入两个正整数a，b(a>b);第二步：若a不等于b，则执行第三步；否则转到第五步；第三步：把a・b的差赋予巧第四步：如果b>r,那么把b赋给％把r赋给b;否则把r赋给a,执行第二步；第五步：输出最大公约数b・WHILE aobr=a-bIF b>r THENa=bb=rELSEa=rEND IF WEND PRINT b序结束比较辗转相除法与更相减损术的区别(1)都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。
(2)从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到算法案例(2)1、求两个数的最大公约数的两种方法分别是()和()。
2、两个数21672, 8127的最大公约数是＜)A、2709B、2606C、2703D、2706案例2、秦九韶算法怎样求多项式f (x)x=5时的值呢？=x5+x4+x3+x2+x+1 当+(n T + (T :+g)x g x g x g )x % T+( ：( T + (T :+g T g )x g )x g x % T： + ( T ： + ( T： + g+¥,x 9)x %i:+ ( t:+g + Q d g x S 929+ 92Leut+g +0d g +s舊)* O1x+CN X +M X +寸x+尺図 L +S m算法1 因为fix) =X S + X4 + X3 + X2 + X + 1所以f(5^=55 +54 +53 +52 +5+ 1=3125 + 625 +125 + 25 + 5+ 1= 3906共做了1+2+3+4=10次乘法运算，5次加法运算算法2:£(6=55+54+53+52+5+ 1=5x(54+53+52+5+ 1) + 1=5x(5x(53 +52 +5 + 1J+ 1) + 1=5X(5X(5X(52+5+1)+1 ) + 1 ) + 1=5x(5x(5x(5x(5+l) + l )+1)+1) + 1共做了4次乘法运算，5次加法运算。
《数书九章》 ---- 秦九韶算法 设f ⑴是一个门次的多项式 于⑴二％*+0门兀门+ A + a {x + a Q对该多项式按下面的方式进行改写：/(%)二 a n xn + a n _x x n^ + A + g + S 二(ci n x n i+ 0”_1兀"2 + A + °])x + a 。
n_2+ a n _.x n^ + A +。
2)兀 + %)兀 +。
0这是怎样的 一种改写方 式？最后的 结果是什么?二(A (a n x + a n _l )x + a n _2)x+A +a {)x +af (x) = (A (a n x + a n ^)x + a n _2)x + A +a i )x + a Q要求多项式的值 ＞应该先算最内层的一次多项式的 纂倉 由内到外椽虐存学%發项式的值f 即卩2 =叫兀+an-2 叫=M + an-3 /\ /\5 =乙一"+硯°这种将求一个n 次多项式/(x)的值转化成求n在求多««匕O1I1-W W.ISH1!个一次多项式的值的方法＞称为秦九韶算法。
算法步骤:的系数和x 的值.第二步：将v 的值初始化为％，将i 的值 初始化为1・输入i 次项的系数富・ v=vx+a n4,i=i+l>第五步：判断i 是否小于或等于n,若是, 则返回第三步；否则，输出多项式的值V 。
第一步：输入多项式次数n 、 最高次项 第三步: 第四步:开始\ __________ ______________ /输入叭岸 /V=a ni=l叫二色—F儿=+ a n _k (k = 1,2,A /)这是一个在秦九韶 算法中反复执行的 步骤，因此可用循 环结构来实程序框图:/输讣/Y/输出v/现。
特点：通过一次式的反复计算，逐步得出高次多项式的值，对于一个n次多项式，只需做n 次乘法和n次加法即可。
例2已知一个五次多项式为f (x) — 5%5 + 2%4 + 3.5%3 — 2.6%2+1.7% — 0.8 用秦九韶算法求这个多项式当x = 5的值。
解将多项式变形:/(%) = ((((5兀+ 2)兀+ 3.5)兀一 2.6)兀+ 1.7)兀一 0.8 按由里到外的顺序,依此计算一次多项式当x = 5时的值: 心=5 片= 5x5 + 2 = 27 卩2 = 27x 5 + 3.5 = 13&5 ( 5=138.5x5 —2.6 = 689 耳二 689.9x5 + 1.7 二3451.2&v 5=3451.2x5-0.8 = 17255.2所以,当x = 5时,多项式的值等于17255.2你从中看到了怎样的规律？怎么用程序框 图来描述呢眞［开始］程序框图:输入f(x)的系数:a0^a b a2^a3^a4a5人="+心氐=1，2,A /)这是一个在秦九韶算法中反复执行的步骤，因此可用循环结构来实现。
n=ln<5?n=n+lv=vx0+a5.nNY输出「7练习、已知多项式f(x)=x5+5x4+1 Ox3+10x2+5x+1用秦九韶算法求这芒多项式当x=・2时的值的过程中，求片与卩厶尊该案例(3)一、进位制1、什么是进位制？2、最常见的进位制是什么？除此之外还有哪些常见的进位制？请举例说明.进位制是人们为了计数和运算方便而约定的记数系统。
进住制是一种记数方式，用有限的数李A不同的住置表示不同的数值。
可使用数合符号的个数隸为基数，基数为n,即可隸n进後制简称n进制半斤=八两•我们常见的数字都是十进制的，比如一般的数值计算，但是并不是生活中的每一种数字都是十进制的.•古人有半斤八两之说，就是十六进制与十进制的转换.•比如时间和角度的单位用六十进位制，计算“一打”数值时是12进制的。
•电子计算机用的是二进制3.我们了解十进制吗？所谓的十进制,它是如何构成的? 十进制由两个部分构成十进制：“满十进第一、它有0〜9十个数学-------------------- '例如：3721表示有：1个1, 2个十，7个百即7个10的平方，3个千即3个10的立方3721 = 3xl03+7xl02 + 2xl01+ 1x10°其它进位制的数又是如何的呢?二、二进制二进制的表示方法二进制是甩g两个数字来描述的・如11001区分的写法：11001（2）或者1X24+1X23+0X22+0X21+1X2°八进制呢勿7342轻）k进制呢？a n a n-l a n-2-a l（k） ?三、二进制与十进制的转换1.二进制数转化为十进制数例］将二进制数llOOlA⑵化成十进制数解:根据进位制的走义可知110011 ⑵二lx2'+lx24 +0x23 +0x22+1x2】+1x2°=1x32+1x16+1x2+1=51所以f 110011(2)=51.练习将下面的二进制数化为十进制数？(1) 11 (2) 1102、十进制转换为二进制 例2把89化为二进制数 余数 1 0 0 1 1 0 1练习将下面的十进制数化为二进制数?(1) 10 (2)20 3、十进制转换为其它进制 例3把89化为五进制数 解：根据除k 取余法 以5作为除数，相应的除法算式2 89 2 2 2 2 2 2 1 注意： 1 •最后一步商为0,2•将上式各步所得的余数从下到上排列，得到:89=1011001 ⑵为:175 n余数423练习：完成下列进位制之间的转化:(1) 10231 (4)=(10) 5(2) 235 ⑺二(10) 5(3) 137(10)=⑹；(4) 1231 ⑸=(7)；(5) 213 ⑺=⑶；(6) 1010111 ⑵二 --------------- (4) °小结• 1.进位制是一种记数方式，用有限的数室在不同的位置表示不同的数值。
