1.3 算法案例,第二课时,主讲教师 申 东,问题提出,问题提出,问题提出,问题提出,问题提出,问题提出,问题提出,辗转相除法与 更相减损术,知识探究（一）:辗转相除法,知识探究（一）:辗转相除法,知识探究（一）:辗转相除法,8251=61051+2146，,8251=61051+2146，,6105=21462+1813，,2146=18131+333，,8251=61051+2146，,6105=21462+1813，,2146=18131+333，,1813=3335+148，,8251=61051+2146，,6105=21462+1813，,2146=18131+333，,333=1482+37，,1813=3335+148，,8251=61051+2146，,6105=21462+1813，,2146=18131+333，,148=374+0.,333=1482+37，,1813=3335+148，,8251=61051+2146，,6105=21462+1813，,思考5:该算法的程序框图如何表示？,思考5:该算法的程序框图如何表示？,思考5:该算法的程序框图如何表示？,思考5:该算法的程序框图如何表示？,思考5:该算法的程序框图如何表示？,思考5:该算法的程序框图如何表示？,思考5:该算法的程序框图如何表示？,思考5:该算法的程序框图如何表示？,思考5:该算法的程序框图如何表示？,思考5:该算法的程序框图如何表示？,思考6:该程序框图对应的程序如何表述？,思考6:该程序框图对应的程序如何表述？,INPUT m，n,思考6:该程序框图对应的程序如何表述？,INPUT m，n,DO,思考6:该程序框图对应的程序如何表述？,INPUT m，n,DO,r=m MODn,思考6:该程序框图对应的程序如何表述？,INPUT m，n,DO,r=m MODn,m=n,思考6:该程序框图对应的程序如何表述？,INPUT m，n,DO,r=m MODn,m=n,n=r,思考6:该程序框图对应的程序如何表述？,INPUT m，n,DO,r=m MODn,m=n,n=r,LOOP UNTIL r=0,思考6:该程序框图对应的程序如何表述？,INPUT m，n,DO,r=m MODn,m=n,n=r,LOOP UNTIL r=0,PRINT m,INPUT m，n,INPUT m，n,WHILE n0,INPUT m，n,WHILE n0,r=m MODn,INPUT m，n,WHILE n0,r=m MODn,m=n,INPUT m，n,WHILE n0,r=m MODn,m=n,n=r,INPUT m，n,WHILE n0,r=m MODn,m=n,n=r,WEND,INPUT m，n,WHILE n0,r=m MODn,m=n,n=r,WEND,PRINT m,INPUT m，n,WHILE n0,r=m MODn,m=n,n=r,WEND,PRINT m,END,知识探究（二）:更相减损术,知识探究（二）:更相减损术,知识探究（二）:更相减损术,98-63=35，,知识探究（二）:更相减损术,98-63=35，,63-35=28，,知识探究（二）:更相减损术,98-63=35，,35-28=7，,63-35=28，,知识探究（二）:更相减损术,98-63=35，,28-7=21，,35-28=7，,63-35=28，,知识探究（二）:更相减损术,98-63=35，,21-7=14，,28-7=21，,35-28=7，,63-35=28，,知识探究（二）:更相减损术,98-63=35，,14-7=7.,21-7=14，,28-7=21，,35-28=7，,63-35=28，,思考3:该算法的程序框图如何表示？,思考3:该算法的程序框图如何表示？,INPUT m，n,INPUT m，n,WHILE mn,INPUT m，n,WHILE mn,k=m-n,INPUT m，n,WHILE mn,k=m-n,IF nk THEN,INPUT m，n,WHILE mn,k=m-n,IF nk THEN,m=n,INPUT m，n,WHILE mn,k=m-n,IF nk THEN,m=n,n=k,INPUT m，n,WHILE mn,k=m-n,IF nk THEN,m=n,n=k,ELSE,INPUT m，n,WHILE mn,k=m-n,IF nk THEN,m=n,n=k,ELSE,m=k,INPUT m，n,WHILE mn,k=m-n,IF nk THEN,m=n,n=k,ELSE,m=k,END IF,INPUT m，n,WHILE mn,k=m-n,IF nk THEN,m=n,n=k,ELSE,m=k,END IF,WEND,INPUT m，n,WHILE mn,k=m-n,IF nk THEN,m=n,n=k,ELSE,m=k,END IF,WEND,PRINT m,INPUT m，n,WHILE mn,k=m-n,IF nk THEN,m=n,n=k,ELSE,m=k,END IF,WEND,PRINT m,END,理论迁移,理论迁移,理论迁移,小结作业,小结作业,