新课标人教A高中数学必修三算法初步小结与复习.pptx
知识结构知识结构算法算法程程序序框框图图算算法法语语句句辗转相除法与辗转相除法与更相减损术更相减损术 秦九韶算法秦九韶算法 进位制进位制第1页/共28页知识梳理知识梳理1.1.算法的概念算法的概念 在数学中，按照一定规则解决某一在数学中，按照一定规则解决某一类问题的类问题的明确明确和和有限有限的步骤的步骤称为算法称为算法.用程序框、流程线及文字说明来表用程序框、流程线及文字说明来表示算法的图形称为示算法的图形称为程序框图程序框图.3.3.程序框图的概念程序框图的概念2.2.算法特征算法特征 明确性、步骤性、不唯一性、普遍性、有限性明确性、步骤性、不唯一性、普遍性、有限性自然语言、程序框图、算法语句自然语言、程序框图、算法语句第2页/共28页基本的程序框和它们各自表示的功能如下基本的程序框和它们各自表示的功能如下:图形符号图形符号名称名称功能功能终端框终端框(起止框起止框)表示一个算法的起始表示一个算法的起始和结束和结束输入、输输入、输出框出框表示一个算法输入和表示一个算法输入和输出的信息输出的信息处理框处理框(执行框执行框)判断某一条件是否成立判断某一条件是否成立,成立时在出成立时在出口处标明口处标明“是是”或或“Y”；不；不”成成立时标明立时标明“否否”或或“N”.判断框判断框赋值、计算赋值、计算流程线流程线连接程序框连接程序框连接点连接点连接程序框图的两部分连接程序框图的两部分第3页/共28页开始开始输入输入ni=2求求n除以除以i的余数的余数ri=i+1in或或r=0?n不是质数不是质数结束结束是是否否是是n是质数是质数否否r=0?顺序结构顺序结构用程序框图来表示算法，有用程序框图来表示算法，有三种不同的基本逻辑结构：三种不同的基本逻辑结构：条件结构条件结构循环结构循环结构第4页/共28页画顺序结构程序框图时注意画顺序结构程序框图时注意事项事项左图中左图中,语句和语句是依次执语句和语句是依次执行的行的,只有在执行完语句指定的只有在执行完语句指定的操作后操作后,才能接着执行语句所指才能接着执行语句所指定的操作定的操作(1)在程序框图中,开始框和结束框不可少；(2)在算法过程中，第一步输入语句是必不可少的;(3)顺序结构在程序框图中的体现就是用流程线将程序框自上而下地连接起来,按顺序执行算法步骤4.顺序结构顺序结构是由若干个依次执行的处理是由若干个依次执行的处理步骤组成的步骤组成的.这是任何一个算法都离不开的这是任何一个算法都离不开的基本结构基本结构.第5页/共28页基本形式基本形式2步骤步骤A是是满足条件?否否基本形式基本形式1步骤步骤A步骤步骤B否否是是满足条件满足条件?条件结构及框图表示条件结构及框图表示5.条件结构条件结构在一个算法中在一个算法中,经常会遇到一经常会遇到一些条件的判断些条件的判断,算法的流向根据条件是否成算法的流向根据条件是否成立有不同的流向立有不同的流向.条件结构就是处理这种过条件结构就是处理这种过程的结构程的结构.第6页/共28页例例.画程序框图画程序框图,对于输入的对于输入的x值值,输出相应的输出相应的y值值.开始开始程序框图程序框图x0?是是y=0否否0 x100?是是输出输出S结束结束否否直到直到型循型循环结环结构构开始开始i=1S=0i100?是是S=S+ii=i+1否否输出输出S结束结束当型循环当型循环结构结构第第1步步:0+1=1;第第2步步:1+2=3;第第3步步:3+3=6;第第4步步:6+4=10第第100步步:4950+100=5050.第10页/共28页INPUT语句PRINT语句赋值语句格式INPUT“提示内容”；变量PRINT“提示内容”；表达式变量=表达式说明1.“提示内容”和它后面的“;”可以省略2.一个语句可以给多个变量赋值，中间用“,”隔开3.无计算功能，不能输入表达式4.输入多个数据时用“,”分隔,且个数要与变量的个数相同1.“提示内容”和它后面的“;”可以省略2.一个语句可以输出多个表达式，不同的表达式之间用“,”隔开3.表达式可以是变量，也可以是计算公式4.有计算功能，能直接输出计算公式的值1.“=”左侧必须是变量,右侧可以是数字、变量或者是计算公式2.赋值号两边不能对换3.对一个变量多次赋值，只保留最后一次的赋值顺序语句、条件语句、循环语句顺序语句、条件语句、循环语句算法语句：算法语句：第11页/共28页10.10.算法的条件语句算法的条件语句IF IF 条件条件 THENTHEN 语句体语句体END IFEND IFIF IF 条件条件 THENTHEN 语句体语句体1 1ELSEELSE 语句体语句体2 2END IFEND IF满足条件？满足条件？步骤步骤1步骤步骤2是是否否满足条件？满足条件？步骤步骤A是是否否第12页/共28页11.11.算法的循环语句算法的循环语句DODO 循环体循环体LOOP UNTIL LOOP UNTIL 条件条件满足条件？满足条件？是是循环体循环体否否WHILE WHILE 条件条件 循环体循环体WEND WEND 循环体循环体满足条件？满足条件？是是否否第13页/共28页12.12.辗转相除法辗转相除法求两个正整数的最大公约数定义：所谓辗转相除法，就是对于给定的两个所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。若余数不为数，用较大的数除以较小的数。若余数不为零，则零，则将除数变被除数，余数变除数将除数变被除数，余数变除数，继续，继续上面的除法，直到大数被小数除尽，则这时上面的除法，直到大数被小数除尽，则这时最后的除数就是原来两个数的最大公约数。最后的除数就是原来两个数的最大公约数。辗转相除法是一个反复执行直到余数等于0停止的算法 第14页/共28页13.13.更相减损术更相减损术求两个正整数的最大公约数第一步：任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数或这个数与约简的数的乘积就是所求的最大公约数。第15页/共28页对该多项式按下面的方式进行改写：对该多项式按下面的方式进行改写：14.14.秦九韶算法秦九韶算法求多项式求多项式f(x)=af(x)=an nx xn n+a+an-1n-1x xn-1n-1+a+a1 1x+ax+a0 0的值的值第16页/共28页要求多项式的值，应该先算最内层的一次多项式的值，即要求多项式的值，应该先算最内层的一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即这种将求一个这种将求一个n次多项式次多项式f(x)的值转化成求的值转化成求n个一个一次多项式的值的方法，称为次多项式的值的方法，称为秦九韶算法秦九韶算法。第17页/共28页15.k15.k进制化十进制的算法进制化十进制的算法16.16.十进制化十进制化k k进制的算法进制的算法除k k取余法任意两进制间的转换任意两进制间的转换先转化为十进制，再将十进制进行转化先转化为十进制，再将十进制进行转化第18页/共28页1.1.当当a=3a=3时，下面的程序段输出的结果是（时，下面的程序段输出的结果是（）（A A）9 9 （B B）3 3 （C C）10 10 （D D）6 6【解析解析】选选D.D.由所给的程序可知，当由所给的程序可知，当a=3a=3时，时，y=23=6,y=23=6,故选故选D.D.例题巩固第19页/共28页2.2.下面程序执行后输出的结果是（下面程序执行后输出的结果是（）（A）1 （B）0 （C）1 （D）2C第20页/共28页3.3.图中所示的是一个算法的流程图，已知图中所示的是一个算法的流程图，已知a a1 1=3=3，输出的，输出的b=7,b=7,则则a a2 2的值是的值是_._.11第21页/共28页42014新课标全国卷 执行如图12所示的程序框图，若输入的a，b，k分别为1，2，3，则输出的M()D第22页/共28页52014新课标全国卷 执行如图12所示的程序框图，如果输入的x，t 均为2，则输出的S()A4 B5 C6 D7B第23页/共28页62014重庆卷 执行如图11所示的程序框图，若输出k的值为6，则判断框内可填入的条件是()B第24页/共28页7.7.如图给出的是计算如图给出的是计算 的值的一个流程图，的值的一个流程图，其中判断框内应填入的条件是其中判断框内应填入的条件是_._.i10第25页/共28页【解析解析】由所给的程序框图可知：由所给的程序框图可知：所给的是直到型的循环所给的是直到型的循环.i=i+1,i=i+1,判断框内填判断框内填i10?i10?答案：答案：i10?i10?第26页/共28页课后活动课后活动1、预习下一节内容。2、完成创新设计“当堂检测”部分.3、P48 1 2第27页/共28页谢谢您的观看！第28页/共28页
