搜索引擎营销(seo).ppt

复习回顾
基本结构
流程图
顺序结构
变量与赋值
循环结构
基本语句
循环语句
条件语句
WHILE语句
UNTIL语句
IF-THEN语句
语句适用结构
算法
条件结构


在初中,我们已经学过求最大公约数的知识,你能求出18与30的最大公约数吗?
2
30
3
9 15
3 5
所以,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得到一个商q0和一个余数r0;
第二步:若r0=0,则n为m,n的最大公约数;若r0≠0,则用除数n除以余数r0得到一个商q1和一个余数r1;
第三步:若r1=0,则r1为m,n的最大公约数;若r1≠0,则用除数r0除以余数r1得到一个商q2和一个余数r2
第n步:依次计算直至rn=0,此时所得到的rn-1即为所求的最大公约数
………………
r= m MOD n
m=n
n=r
r=o?
否
是
程序图框
带余除法
INPUT “请输入m,n的值”;m,n
IF m>n THEN
a=m
m=n
n=a
END IF
DO
r=m MOD N
m=n
n=r
LOOP UNTIL r=0
PRINT m
END
作用是什么?
为什么要用直到型循环结构?
练一练
,写出它的流程框图和BASIC程序
更相减损术
我国早期也有解决求最大公约数问题的算法
《九章算术》(公元50年~100年或更早)是中国古代数学专著,承先秦数学发展的源流,进入汉朝后又经许多学者的删补才最后成书,这大约是公元一世纪的下半叶。它的出现,标志着中国古代数学体系的形成。