高中数学《算法》知识梳理(A版)

高中数学《算法》知识梳理(A版)

《算法》知识梳理(A版)

一、要点提示

1.算法

现代意义上的算法通常是指可以用计算机来解决某一类问题的程序或步骤，其基本要求有：①步骤有限步完成；②步骤确定有效；③步骤有顺序.

注意：一类问题的算法往往不唯一.

2.程序框图

用一种规定的图形、指向线及文字说明来准确、直观的表示算法的图形，叫做程序框图，又称流程图.

各种不同的运算步骤必须用规定的程序框图来表达.起止框是所有算法程序框图必有的，表示算法的开始和结束.除判断框外，其余的程序框均只有一个进入点和一个输出点（起止框只有一个），判断框一般有一个进入点和两个输出点.

三种基本的框图结构需能熟练根据具体问题选择和画出.

3.程序语句

五种基本语句（赋值、输入、输出、条件、循环），须熟练应用，并能根据需要灵活选择各种不同的循环结构，及对条件结构进行多层套用.

4.算法案例

辗转相除法与更相减损术本质是相同的，常用来求两个或多个整数的公约数.

秦九韶算法用以解决多项式求解问题.

直接插入排序和冒泡排序用来对多个数进行排序，比较体会二者的相同与不同之处.

各种进位制的转化基本方法是“除k取余法”.

二、思想与方法

1.算法的思想

体会算法的思想，培养算法意识，能做到自觉在算法思想的引导下进行学习，在学习新内容时自觉的去总结一类问题的算法，形成规律，以真正的提高学习效率.

2.类比

类比电脑算法与人脑算法，体会其相同与不同.类比程序框图算法与自然语言算法，体会程序框图的优越性.类比当型循环和直到型循环，体会前测与后测.类比计数变量型循环与非计数变量型循环结构，体会循环结构的控制技巧.类比判断结构中常见的条件类型：大于、小于、等于、不等于及AND、OR的应用等，便于分类和记忆.类比循环结构与判断结构，体会其程序结构的相似性与本质的差别等等.

3.程序的动态分析

对于程序的分析理解，应从程序运行的角度去进行，特别是较复杂的程序，应按照程序的运行顺序一步一步动态地去分析，这是最简单、高效和科学的分析方法.例如求解１＋２＋３＋…＋100的程序，可作如下分析：

程序：

I=1

S=0

WＨＩＬＥI<=100

S=S+I

I=I+1

WＥＮＤ

PＲＩＮＴＳ

高中数学《算法》知识梳理(A版)

EＮＤ

分析：

I=1

S=0

I<=100，开始运行循环体部分；

循环体运行1次后：Ｓ=1，I=2.I<=100成立，继续运行循环体；

循环体运行2次后：Ｓ=1+2，I=3.I<=100成立，继续运行循环体；

循环体运行3次后：Ｓ=1+2+3，I=4.I<=100成立，继续运行循环体；

循环体运行4次后：Ｓ=1+2+3+4，I=5.I<=100成立，继续运行循环体；

…；

循环体运行99次后：Ｓ=1+2+3+…+99，I=100.I<=100成立，继续运行循环体；

循环体运行100次后：S=1+2+3+…+100，I=101.I<=100不成立，退出循环体，向下继续运行循环体后面的部分.

PＲＩＮＴＳ，即输出Ｓ的值.

结束.

特别的，在每一步运算Ｓ的过程中，运算结果用式子来写，而不要直接求出结果，这样思路会更清晰地展示出来.

三、疑点解惑

1.算法程序的运行

事实上，算法中出现的程序只是用基本的语句把程序的主要结构描述出来，与真正的程序还有差距，所以算法描述的许多程序并不能直接运行，要运行程序，还要把程序按照某种语言的严格要求重新改写才行.

2.赋值语句a=a+3

赋值语句与方程不同，这一点需很好地理解.作为方程a=a+3是无解的，但作为赋值语句a=a+3却是完全正确可行的，它的意思是把原来的a的值加3后重新赋给a，注意运行此语句后a的值与运行前不同.

3.交换问题为什么引进中间变量

因为当a=b运行完毕后，a的值已经变为与b相同的值，此时若直接运行b=a，则达不到交换的效果，所以需引进中间变量把a的值先进行保存.

4.联合判断与标志思想

求质数的框图中，出现了两个条件用“且”相连的联合判断问题.另外，此框图中引进“flag=1”作为判断的标志，这是算法设计的基本技巧之一，即在不同的过程中赋予标志不同的值，最后根据标志的值作出判断.两种技巧均需仔细体会学习.

5.分段函数的算法设计

在分段函数

1(0)

0(20)

1(2)

x

y x

x

>

?

?

=-<

?

?--

?

，

，

≤

≤

的算法设计中，有同学总认为如下程序语句更好：

IＦx>0ＴＨＥＮ

y=1

ＥＬＳＥ

ＩＦx>-2ＡＮＤx<=0ＴＨＥＮy=0

ＥＬＳＥ

高中数学《算法》知识梳理(A版)

y=-1

ＥＮＤＩＦ

ＥＮＤＩＦ

ＥＮＤ

事实上，程序中的“x<=0”是多余的，只要程序能运行到这一步，自然有“x<=0”成立，所以只需要一个条件“x>-2”即可.

四、误区提醒

1.框图中的流程线不能出现交叉的现象.如用二分法求方程的近似根的算法框图中，若有交叉，则程序语句无法写出.

2.各种框图有其固定的格式和作用，不要乱用.如条件结构中不要忘了“是”与“否”，流程线不要忘记画箭头，

3.算法语句要求书写格式要严格，需注意遵循其要求和规范，如a×b应写作a*b，不要忘记“ＥＮＤＩＦ”、“ＷＥＮＤ”等.

4.条件分支结构的方向要准确.

5.循环结构中，计数变量要赋初值，计数变量的自加不要忘记，自加多少不能弄错.另外计数变量一般只负责计数任务，在程序中若对其进行调用，需注意不要让其值发生改变（除自加以外的）.

6.循环结构中循环的次数要严格把握，区分“＜”与“＜＝”等.循环变量的取值与循环结构（当型与直到型）有关，需区分清楚.另外，同一问题用两种不同的结构解决时，其判断条件恰是相反的.

7.程序或程序框图不要出现死循环（无限步的循环）.

8.语句正确但程序运行结果与预想的不同，可能有多种情况，需仔细分析.

9.冒泡排序时思维要清晰，不可比错要比较的对象.

10.进位制中，n进位制的数中不会出现大于等于n的数字.