高中数学必修3《算法初步》知识点讲义

第一章算法初步1.算法的概念1、算法定义在数学上，现代意义上的“算法”通常是指可以用计算机来解决的某一类问题是程序或步骤，这些程序或步骤必须是明确和有效的，而且能够在有限步之内完.2.算的点有穷性：一个算法在执行有限个步骤之后，必须结.确定性：算法的每一个步骤和次序应该是确定.可行性：原则上算法能够精确地元算，而且人们用笔和纸做有限次即可完.不唯一性：求某一个问题的解法不一定是唯一的，对于一个问可以有不同的算.输出：一个算法有0个多个输入，以刻画运对象的初始条.所谓0个输是指算法本身已经给出了初始条件.输出：一个算法有1个或个输出以反映对输入数据加工的果没有输出的算法是毫无意义.3．算法的描：自然语言、程序框图、程序语言。例1、写1×2×3×4×5×6的一算法.解:按照逐一相乘的程序行第一步计1×2,得到2；第二步将一步的运算果2与3相乘得6；第三步将二步的运算果6与4相,得24；第四步将三步的运算果24与相,得到120；第五步将四的运算结120与6相乘得720；第六步输结果/9例2、写按从小到大的顺序重新排列

,,

三个数值的算法解:（1）.输入

xy,

三个数值；（2）.从三个数值中挑出最小者并到中（3）.从

y,z

中挑出最小者并换到

中；（4）.输出排序的结果1、程序框图本概念：（一）程序构的概念：程序框图又称流程图，是一种用规的图形、指向线及文字说明来准确、直观地表示算的图形。一个程序框图包括以下几部分：表示相应操作的程序框；带箭头的流程线；程序框外必要文字说明。（二）构成程框的图形符号及其作用程框

名称

功能表示一个算法的起始和束何程图起止框输入、输出框处理框判断框

不可少的。表示一个算法输入和输的息在法中任何需要输入、输的置。赋值、计算，算法中处数需的算、公式等分别写在不同的以理据的处理框内。判断某一条件是否成立时出口处标是立标否学习这部分知识的时候，要掌握各个图形的形状、作用及使用规则，画程序框图的规则如下：使用标准的图形符号。框图一般按从上到下、从左到右的方向画。除判断框外，大多数流程图符号只有一个进入点和一个退出点。判断框具有超过一个退出点的唯一符号。判断框分两大类，一类判断框“是”与“否”两分支的判断，而且有且仅有两个结果；另一类是多分支判断，有几种同的结果。在图形符号内描述的语言要非常简练清楚。/9开始输入≥0?Yx2

N

yx输出

结束（三法三基本逻结构：顺序结构、条件结构、循环结构。1步骤n步骤2、条件结构/93、循环结构：1终止2在循。算……+100/91、输入语句“提示内容量

图形计算器格式

“提示内容量2、输出语句提示内容达式

图形计算器格式

Disp“提示内容量3、赋值语句图形计算器变量＝表达式

格式

表达式

变量条件语句的一般格式有种）IF—THEN—ELSE语句）IF语。IF—THEN语IF—THEN—ELSE语句一格式为图1，对应的程序框图为图2。IF条件THEN语句语句ENDIF图1

满足条件？是语句图2

否语句23、IF—THEN语句IF—THEN句的一般格式为图3，对应的程序框图图4。IF条件THEN

是语句ENDIF

满足条件？（图3

否

语句（图4/9循环结构是由循环语句来实现的。对应于程序框图中的两种循环结构，一般程序设计语言中也有当型WHILE型）和直到型（UNTIL型）种语句结构。即WHILE语和UNTIL语句。1、WHILE语

循环

条件WHILE语的一般格是

循环体

对应的程序框图是

是WEND

满足条件？否2、UNTIL语UNTIL语的一般格式是

DO循环体

对应的程序图是

循环UNTIL条件

满足条件？是

否1、辗转相除与更相减损术（1转相除法。也叫欧几里德算法，用辗转相除法求最大公约数的步骤如下：（1定个正整数，n；：计算m以n所的数r；：m=n，n=r若r=0则，n的最大公约数等于m；则，返回第二步。/9f(x)=axf(x)=axn（2相减损术我国早期也有求最大公约数问题的算法，就是更相减损术。在《九章算术》中有更相减损术求最大公约数的步骤：可半者半之，不可半者，副置分母•子之数，以少减多，更相减损，求其等也，以等数约之。翻译为意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。（2较的减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）就是所的最大公约数。2、秦九韶算与排序1、秦九韶算概念：

n+ax+….+ax+an-110

求值题把个n次项

f(x)=axnxn-1+….+ax+ann-110

改写成如下式：f(x)=an+axn-1+….+ann-110=(an-1+ax+….+ann-110=((an-2+axn-3+….+ann-1210=......=(...(ax+a)x+a)x+...+a)x+ann-1n-210求多项式的值，首先计算最内层括号内依次多项式的值，即的，即

v=ax+a1nn-1

然由向逐计一多项式v=v21n-2

v=vx+a3n-3

......v=vx+ann-10这样，把次多式的求值问题转化成求n个一次多项的值的题。/9例、已知一个5次多项式为(x)x

0.8.用秦九韶算法求这个多项式当x时值f(x3.5)xvv27;v3.5138.5;v138.5689.9;v3451.2;v3451.20.817255.2.所以，当x=5时，多项式的值等于7255.2.例、例、3、位制概念：进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值。可使用数字符号的个数称为基数，基数为，即可称n进制，简称n进。现在常用的是十制通使用10个拉伯数字0-9进记数。对于任何一个数，我们可以用不同的进位制来表示。比如：十进，以用二进制表示为111001，也可以用八进制表示为、十六进制表示为39，它们所代表的数值都是一的。一般地若k是个大于一的整数那以k为数的k进可表为aaaa)

,...,,

，而表示各种进位制数一般在数字右下脚加注来表,如111001表二进制数,34表5进数