高三数学基本算法语句和算法案例
- 格式:ppt
- 大小:1.29 MB
- 文档页数:42
算法案例(讲义)➢ 知识点睛典型算法举例: 1. 辗转相除法①方法概述:两数相除,较大数除以较小数,得商和余数,继而较小数除以余数,重复操作,直至除尽,此时除数即为最大公约数.②原理:在a =bq +r 中,除数b 和余数r 能被同一个数整除,那么被除数a 也能被这个数整除.或者说,除数与余数的最大公约数,就是被除数与除数的最大公约数. 2. 秦九韶算法把一个n 次多项式改写成如下形式:1110121102312101210()()(())((()))n n n n n n n n n n n n n n n f x a x a x a x a a x a x a x a a x a x a x a x a a x a x a x a x a ----------=++++=++++=+++++==+++++……………… 记0n v a =,11n n v a x a -=+,…,10n n v v x a -=+.求多项式的值时,首先计算最内层括号内一次多项式的值,即v 1,然后由内向外逐层计算. 3. 进位制①k 进制:若k 是一个大于1的整数,那么以k 为基数的k 进制数可以表示为一串数字连写在一起的形式.110()n n k a a a a -…11011000n n n n a a a a N a k a a a k --∈<<<≤(,,…,,,,,…,,)②进位制数相互转化:k 进制转十进制,计算k 进制数a 的右数第i 位数字i a 与1i k -的乘积1i i a k -⋅,再将其累加,重复操作求和.十进制数转k 进制数(除k 取余法): 如右图,十进制数化为二进制数, 89=1011001(2).➢ 精讲精练1. 用“辗转相除法”求下列数的最大公约数:(1)459和357的最大公约数是____________;余数2222222012511224489(2)三个数324243135,,的最大公约数是____________.2. 用秦九韶算法求多项式的值:(1)计算多项式x x x x x x x f 876543)(23456+++++=在1.0=x 时的值时,需要做乘法和加法的次数分别是_______,_______;(2)求多项式23456()1235879653f x x x x x x x =+-++++在x =-4的值时,4v 的值为_______;(3)计算多项式5432()853261f x x x x x x =+++++,当2x =时的值为________. 3. 完成下列进制的转化:(3)(10)10202____=; (10)__________(8)101=;1231(5)=_____________(7).4. 三位七进制的数表示的最大的十进制的数是( )A .322B .402C .342D .3655. 在下列各数中,最小的数是( )A .)9(85B .)6(210C .)4(1000D .(2)1111116. 已知三个数12(16),25(7),33(4),按照从小到大的顺序排列为________________.7. 已知()175r =(10)125,则r =________.8. 如图所示的程序框图的算法思路来源于我国古代数学名著《九章算术》中的“更相减损术”,执行该程序框图,若输入的a ,b 的值分别为14,18,则输出的a 的值为( ) A .0B .2C .4D .149. 如图所示的程序框图给出了利用秦九韶算法求多项式值的一个实例,若输入n ,x 的值分别为3,2,则输出v 的值为( ) A .35B .20C .18D .910.下面是把二进制数(2)11111化为十进制数的一个程序框图,判断框内应填入的条件是()A.5i>?B.4i≤?C.4i>?D.5i≤?11.执行如图所示的程序框图后,输出的值为4,则P的取值范围是()A.715816P<≤B.1516P>C.3748P<≤D.715816P<≤12.设a是一个各位数字都不是0且没有重复数字的三位数.将组成a的3个数字按从小到大排成的三位数记为I(a),按从大到小排成的三位数记为D(a)(例如a=815,则I(a)=158,D(a)=851).阅读如图所示的程序框图,运行相应的程序,任意输入一个a,输出的结果b=________.13. 已知函数232 1 01 012 1x x y x x x x x -<⎧⎪=+<⎨⎪+⎩≤≥()()(),写出求该函数的函数值的算法,并画出程序框图.14. 设计一算法,求使20063212222>++++n Λ成立的最小正整数n 的值.15.设计算法计算:1112131415167S=++++++,画出程序框图.【参考答案】1. (1)51;(2)272. (1)6;5;(2)220;(3)3813. 101 145 3624. C5. D6. (4)(16)(7)331225<<7. 88. B9. C 10. C 11. C 12. 495 13. 略 14. 略 15. 略算法案例(随堂测试)1. 372和684的最大公约数是( )A .36B .186C .12D .5892. 用秦九韶算法计算多项式65432()3567983512f x x x x x x x =+++-++在x =-4时的值时,v 2的值为( )A .-57B .-22C .34D .743. 1234(8)=________(10);300=________(5);300=_______(6).4. 设计一个算法,输入正整数n ,输出111123n++++….【参考答案】1. C2. C3. 668;2 200;1 2204. 略算法案例(习题)➢ 巩固练习5. 求下列数的最大公约数:(1)1 443与999的最大公约数是_____________;(2)319,377,116的最大公约数是___________.6. 用秦九韶算法求n 次多项式1110()n n n n f x a x a x a x a --=++++…,当x =x 0时,0()f x 需要算乘法、加法的次数分别为( ) A .n 2,nB .2n ,nC .n ,2nD .n ,n7.已知532=++++,运用秦九韶算法计算x=3时的值时,v3的值为()()231f x x x x xA.27 B.11 C.109 D.368.用秦九韶算法求多项式765432=++++++在x=3时的值为________.()765432f x x x x x x x x9.把21化为二进制数,则此数为()A.10011(2)B.10110(2)C.10101(2)D.11001(2)10.一个k进制的三位数与某六进制的二位数等值,则k不可能是()A.3 B.4 C.5 D.711.下列各数中,最小的数是()A.75B.210(6)C.111111(2)D.85(9)12.若a=33(10),b=52(6),c=11111(2),则三个数的大小关系是()A.c>b>a B.b>c>a C.c>a>b D.a>b>c13.中国古代有计算多项式值的秦九韶算法,如图是实现该算法的程序框图.执行该程序框图,若输入的x=2,n=2,依次输入的a为2,2,5,则输出的s=()A.7B.12C.17D.34第9题图第10题图14.如图是一个算法的程序框图,该算法所输出的结果是()A.11112310++++…B.11113519++++…C.111124620++++…D.231011112222++++…15.某程序框图如图所示,若输出的S=57,则判断框内为()A.k>4?B.k>5?C.k>6?D.k>7?11第11题图 第12题图16. 执行如图所示的程序框图,若输入k 的值为8,则判断框图可填入的条件是( )A .S ≤34?B .S ≤56?C .S ≤1112? D .S ≤1524?17. 设计一个算法,输入两个数,输出两个数中较大的一个.18.已知函数21111131x x y x x x x ⎧-<-⎪=+-⎨⎪+>≤≤()()(),试画出求函数值的程序框图.19. 对任意给定的正整数n ,写出一个求13+23+33+…+n 3的算法程序框图.20.设计算法求111112233499100++++⨯⨯⨯⨯…的值,要求画出程序框图.【参考答案】1.(1)111 (2)292.D3.D4.213245.C6.D7.C8.D9.C10.C11.A12.C13.略14.略15.略16.略12。
算法案例知识图谱算法案例知识精讲一.更相减损术应用:求两个整数的最大公约数的算法更相减损术的步骤:1.任意给定两个正整数;判断它们是否都是偶数.若是,则用2约简;若不是则执行第二步.2.以两个数中较大的数减去较小的数,以差数和较小的数构成一对新的数,对这一对数再用大数减小数,以同样的操作一直做下去,直到产生一对相等的数为止,则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数.等值算法:用“更相减损术”设计出来的算法求最大公约数的算法称为“等值算法”,用等值算法可以求任意两个正整数的最大公约数.说明:《九章算法》是中国古代的数学专著,其中的“更相减损术”可以用来求两个数的最大公约数.以具体的例子来说明更相减损术求最大公约数的原理:以求117和182的最大公约数为例:,,,,,,,,(117182)(11765)(6552)(5213)(1339)(1326)(1313)→→→→→→每次操作后得到的两个数与前两个数的最大公约数相同,而且逐渐减少,故总能得到相等的两个数,即为所求的最大公约数.二.辗转相除法又称欧几里得算法,是由欧几里得在公元前300年左右首先提出来的求两个数的最大公约数的算法.辗转相除法的步骤:对于给定的两个数,以其中较大的数除以较小的数得到一个余数,将较小的数与余数看成一对新的数,重复上面的步骤,直到余数为零为止,此时上一步中较小的数即为所求的最大公约数.以求117和182的最大公约数为例:,,,,,,故13即为所求.→→→→(117182)(11765)(6552)(5213)(130)三.秦九韶算法—求多项式的值的算法应用:快速的求解对于任意一个n次的多项式在某点所取到的值.秦九韶算法:已知一个多项式函数,计算多项式在某点处的函数值的一种算法,是我国古代数学家秦九韶提出的,具体如下.对任意一个n 元多项式1110()n n n n f x a x a x a x a --=++++ ,改写成如下形式:12110()()n n n n f x a x a x a x a ---=++++ 231210(())n n n n a x a x a x a x a ---=+++++ = 1210((()))n n n a x a x a x a x a --=+++++ ,求多项式的值时,先计算最内层括号内的一次多项式的值,即11n n v a x a -=+,然后由内向外逐层计算一次多项式的值,即212n v v x a -=+,323n v v x a -=+, ,10n n v v x a -=+.这样,求一个n 次多项式的值,就转化为求n 个一次多项式的值.令1(1)(())k n n n k n k v a x a x a x a ----=++++ ,则递推公式为01n kk n k v a v v x a --=⎧⎨=+⎩,其中12k n = ,,,.到目前为止,此算法仍然是世界上多项式求值的最先进的算法.秦九韶算法与其它算法在计算量上面的比较:1110()n n n n f x a x a x a x a --=++++ ,1.直接求和法:先计算各个单项式的值,再把它们相加,乘法次数为(1)(1)212n n n n ++-+++= ,加法次数n ;2.逐项求和法:先计算x 的各项幂的值,再分别相乘,计算幂值需要乘法1n -次,将幂值与多项式系数k a 相乘需要乘法n 次,故共需要乘法21n -次,加法n 次.此方法对直接求和法有所改进,但仍然比秦九韶算法计算量大很多.3.秦九韶算法:计算量仅为乘法n 次,加法n 次.<备注>秦九韶算法是多项式求值的优秀算法,秦九韶算法的特点:(1)化高次多项式求值为一次多项式求值;(2)减少了运算次数,提高了效率;(3)步骤重复执行,容易用计算机实现.利用秦九韶算法计算多项式的值关键是能正确地将所给多项式改写,然后由内向外逐次计算,由于后项计算用到前项的结果,故应认真、细心,确保中间结果的准确性.若在多项式中有几项不存在时,可将这些项的系数看成0,即把这些项看做0·x n .三点剖析一.注意事项1.辗转相除法与更相减损术联系(1)都是求最大公约数的方法,计算上,辗转相除法以除法为主,更相减损术以减法为主,计算次数上,辗转相除法计算次数相对较少,特别当两个数大小差距较大时,计算次数的区别比较明显;(2)从结果的体现形式来看,辗转相除法体现结果是以相除余数为零而得到,而更相减损术则是以减数与差相等而得到;(3)辗转相除法与更相减损术是统一的,因为做一次除法与做若干次减法的效果相同.二.方法点拨1.两个整数的最大公约数是两个整数的公约数中最大的数,与此类似,两个整数的最小公倍数是两个整数的公倍数中最小的数.2.穷举法是将集合中的元素进行一一列举,逐个条件进行验证,知道找出满足条件的元素为止,穷举法可以解决所有问题看,但是一般来说常常可以用来解决一些无规律可循的问题,例如求不定方程的解或者不定方程组的解,运用穷举法思想设计算法时,常常采用循环结构,将验证条件为循环结构的判断条件,将每一个元素作为循环体.求两个正整数的最大公约数例题1、8251与6105的最大公约数是____.例题2、用更相减损来求80和36的最大公约数?例题3、用更相减损术求294与84的最大公约数.随练1、两个数153和119的最大公约数是______________.随练2、用更相减损术求294与84的最大公约数.随练3、有甲、乙、丙三种溶液分别重147g、343g、133g,现要将它们分别全部装入小瓶中,每个小瓶装入液体的质量相同,问每瓶最多装多少?秦九韶算法例题1、用秦九韶算法求多项式f(x)=x4+2x3+x2-3x-1,当x=2时的值,则v3=______例题2、使用秦九韶算法计算x=2时f(x)=6x6+4x5-2x4+5x3-7x2-2x+5的值,所要进行的乘法和加法的次数分别为________随练1、用秦九韶算法求多项式f(x)=1+2x+x2-3x3+2x4在x=-1时的值,v2的结果是______随练2、用秦九韶算法计算多项式f(x)=5x5+4x4+3x3-2x2-x-1在x=-4时的值时,需要进行的乘法、加法的次数分别是_______拓展1、用更相减损术求78和36的最大公约数_________.2、三个数208,351,429的最大公约数是()A.65B.91C.26D.133、用“辗转相除法”求得459和357的最大公约数是()A.3B.9C.17D.514、用秦九韶算法求多项式f(x)=12+35x-8x2+79x3+6x4+5x5+3x6在x=-4的值时,其中V1的值=_______5、用秦九韶算法计算多项式f(x)=3x6+4x5+5x4+6x3+7x2+8x+1当x=0.4时的值时,需要做乘法和加法的次数分别是。
高三数学一轮复习必备精品16:基本算法语句第16讲基本算法语句一.【课标要求】1.经历将具体问题的程序框图转化为程序语句的过程,理解几种基本算法语句――输入语句、输出语句、赋值语句、条件语句、循环语句,进一步体会算法的基本思想;2.通过阅读中国古代数学中的算法案例,体会中国古代数学对世界数学发展的贡献。
二.【命题走向】算法是高中数学课程中的新内容,本章的重点是算法的概念和算法的三种逻辑结构预测2021年高考对本章的考察是:以选择题或填空题的形式出现,分值在5分左右,本讲考察的热点是识别程序和编写程序三.【要点精讲】1.输入语句输入语句的格式:INPUT “提示内容”;变量例如:INPUT “x=”; x功能:实现算法的输入变量信息(数值或字符)的功能。
要求:(1)输入语句要求输入的值是具体的常量;(2)提示内容提示用户输入的是什么信息,必须加双引号,提示内容“原原本本”的在计算机屏幕上显示,提示内容与变量之间要用分号隔开;(3)一个输入语句可以给多个变量赋值,中间用“,”分隔;输入语句还可以是““提示内容1”;变量1,“提示内容2”;变量2,“提示内容3”;变量3,??”的形式。
例如:INPUT“a=,b=,c=,”;a,b,c。
2.输出语句输出语句的一般格式:PRINT“提示内容”;表达式例如:PRINT“S=”;S功能:实现算法输出信息(表达式)要求:(1)表达式是指算法和程序要求输出的信息;(2)提示内容提示用户要输出的是什么信息,提示内容必须加双引号,提示内容要用分号和表达式分开。
(3)如同输入语句一样,输出语句可以一次完成输出多个表达式的功能,不同的表达式之间可用“,”分隔;输出语句还可以是“提示内容1”;表达式1,“提示内容2”;表达式2,“提示内容3”;表达式3,??”的形式;例如:PRINT “a,b,c:”;a,b,c。
3.赋值语句赋值语句的一般格式:变量=表达式赋值语句中的“=”称作赋值号作用:赋值语句的作用是将表达式所代表的值赋给变量;要求:(1)赋值语句左边只能是变量名字,而不是表达式,右边表达式可以是一个常量、变量或含变量的运算式。
15、算法初步15.2 基本算法语句与算法案例【知识网络】1.理解用伪代码表示的几种基本算法语句:赋值语句、输入语句、输出语句、条件语句、循环语句。
2.能用自然语言、流程图和伪代码表述算法,会用“While循环”和“For循环”语句或GoTo语句实施循环(注意:优先使用While和For语句,尽量少用GoTo语句)。
【典型例题】[例1](1)下列问题所描述出来的算法,其中不包含条件语句的为()A.读入三个表示三条边长的数,计算三角形的面积B.给出两点的坐标,计算直线的斜率C.给出一个数x,计算它的常用对数的值D.给出三棱锥的底面积与高,求其体积(2)设计一个计算1×3×5×7×9×11×13的算法.图中给出了程序的一部分,则在横线①上不能填入下面的那一个数?答:()A.13B.13.5C.14D.14.5(3)若mod(m,3)=1,则m的取值不可以是()A.2005 B.2006 C.2008 D.2020(4)下面的表述:①6←p;②t←3×5+2;③b+3←5;④p←((3x+2)-4)x+3;⑤a←a3;⑥x,y,z←5;⑦ab←3;⑧x ←y+2+x .其中正确表述的赋值语句有 . (注:要求把正确的表述全填上)(5)下面程序的运行结果为4[例2] 某百货公司为了促销,采用打折的优惠办法:每位顾客一次购物①在100元以上者(含100元,下同),按九五折优惠; ②在200元以上者,按九折优惠; ③在300元以上者,按八五折优惠; ④在500元以上者,按八折优惠. 试写出算法、画出流程图、伪代码,以求优惠价.[例3] 定义运算“!”为:n!=1×2×3×…×n ,其中n 为正整数,并且读作“n 的阶乘”,例如,5!=1×2×3×4×5=120,10!=9!×10= 3628800. 计算2007!写出算法分析与伪代码,并画出流程图。
1.2基本算法语句1.2.1输入、输出语句和赋值语句1.输入语句在该程序中的第1行中的INPUT语句就是输入语句.这个语句的一般格式是:其中,“提示内容”一般是提示用户输入什么样的信息.如每次运行上述程序时,依次输入-5,-4,-3,-2,-1,0,1,2,3,4,5,计算机每次都把新输入的值赋给变量“x”,并按“x”新获得的值执行下面的语句.2.输出语句在该程序中,第3行和第4行中的PRINT语句是输出语句.它的一般格式是:3.赋值语句用来表明赋给某一个变量一个具体的确定值的语句.除了输入语句,在该程序中第2行的赋值语句也可以给变量提供初值.它的一般格式是:4.INPUT语句不但可以给单个变量赋值,还可以给多个变量赋值,其格式为:5.(1)赋值语句中的“=”叫做赋值号.(2)赋值语句的作用:先计算出赋值号右边表达式的值,然后把这个值赋给赋值号左边的变量,使该变量的值等于表达式的值.(3)赋值号左边只能是变量名字,而不能是表达式.如:2=X是错误的.(4)赋值号左右不能对换.如“A=B”“B=A”的含义运行结果是不同的.(5)不能利用赋值语句进行代数式的演算.(如化简、因式分解、解方程等)(6)赋值号“=”与数学中的等号意义不同.1.3算法案例1.利用辗转相除法求最大公约数的步骤如下:(1)用较大的数m 除以较小的数n 得到一个商0S 和一个余数0R ;(2):若0R =0,则n 为m ,n 的最大公约数;若0R ≠0,则用除数n 除以余数0R 得到一个商1S 和一个余数1R ;(3):若1R =0,则1R 为m ,n 的最大公约数;若1R ≠0,则用除数0R 除以余数1R 得到一个商2S 和一个余数2R ;……依次计算直至n R =0,此时所得到的1n R 即为所求的最大公约数.2.直接插入排序的基本思想:插入排序的思想就是读一个,排一个.将第1个数放入数组的第1个元素中,以后读入的数与已存入数组的数进行比较,确定它在从大到小的排列中应处的位置.将该位置以及以后的元素向后推移一个位置,将读入的新数填入空出的位置中.(由于算法简单,可以举例说明)3.冒泡排序的基本思想:依次比较相邻的两个数,把大的放前面,小的放后面.即首先比较第1个数和第2个数,大数放前,小数放后.然后比较第2个数和第3个数......直到比较最后两个数.第一趟结束,最小的一定沉到最后.重复上过程,仍从第1个数开始,到最后第2个数...... 由于在排序过程中总是大数往前,小数往后,相当气泡上升,所以叫冒泡排序.4.进位制是一种记数方式用有限的数字在不同的位置表示不同的数值.可使用数字符号的个数称为基数,基数为n ,即可称n 进位制,简称n 进制.现在最常用的是十进制,通常使用10个阿拉伯数字0-9进行记数.对于任何一个数,我们可以用不同的进位制来表示.比如:十进数57,可以用二进制表示为111001,也可以用八进制表示为71、用十六进制表示为39,它们所代表的数值都是一样的.5.辗转相除法与更相减损术的区别:(1)都是求最大公约数的方法,计算上辗转相除法以除法为主,更相减损术以减法为主,计算次数上辗转相除法计算次数相对较少,特别当两个数字大小区别较大时计算次数的区别较明显.(2)从结果体现形式来看,辗转相除法体现结果是以相除余数为0则得到,而更相减损术则以减数与差相等而得到6. 一般地,若k 是一个大于一的整数,那么以k 为基数的k 进制可以表示为: 110()110...(0,0,...,,)n n k n n a a a a a k a a a k --<<≤<,而表示各种进位制数一般在数字右下脚加注来表示,如111001(2)表示二进制数,34(5)表示5进制数.。
高三数学必修三算法知识点一、算法概述算法是指解决问题的一系列明确指令的有限序列。
在高三数学必修三中,算法是解决数学问题的基本工具,它可以用来求解数值计算问题、优化问题以及数学模拟等。
二、二分法1. 概述:二分法是一种通过将问题分解为更小的子问题进行求解的算法。
它适用于有序列表的搜索和函数求根等计算问题。
2. 原理:二分法的基本思想是不断将搜索范围缩小一半,通过将目标值与中间值进行比较,逐步逼近目标值。
3. 实例:求解有序列表中某个元素的位置。
三、迭代法1. 概述:迭代法是一种通过不断逼近目标值的方法来求解问题的算法。
它适用于函数求解、线性方程组求解、递归关系求解等问题。
2. 原理:迭代法的基本思想是通过不断迭代计算的方式,逐步逼近目标值。
通常通过设置初始值和递推公式来实现迭代。
3. 实例:使用牛顿迭代法求解方程的根。
四、贪心法1. 概述:贪心法是一种通过每一步选择当前最优解来求解问题的算法。
它适用于某些优化问题,如最小生成树、背包问题等。
2. 原理:贪心法的基本思想是每一步都选择当前最优解,以期望整体解能够达到最优。
贪心法通常需要证明某种贪心策略的正确性。
3. 实例:使用贪心法求解背包问题。
五、动态规划1. 概述:动态规划是一种通过将问题分解为相互重叠的子问题,并保存子问题的解来求解问题的算法。
它适用于具有重叠子问题和最优子结构性质的问题。
2. 原理:动态规划的基本思想是通过解决子问题的方式,逐步构建最优解。
动态规划一般需要设计递推关系和确定初始条件。
3. 实例:使用动态规划求解最长公共子序列问题。
六、快速排序1. 概述:快速排序是一种通过将数组分为两个子数组并对每个子数组进行排序来实现整体排序的算法。
它是一种高效的排序算法。
2. 原理:快速排序的基本思想是选择基准元素,将数组分为小于基准元素和大于基准元素的两部分,然后递归地对这两部分进行排序。
3. 实例:使用快速排序对数组进行排序。
七、图论算法1. 概述:图论算法是解决图相关问题的一类算法。