高中数学必修3第一章算法初步

第一章 算法初步

算法知识结构：
基本概念 表示方法
自然语言 程序框图 基本算法语句 输入、输出语句 赋值语句 条件语句 循环语句

算 法

顺序结构

基本结构

条件结构 循环结构 辗转相除法和更相减损数

应用

秦九韶算法 进位制

算法的定义：
通常指可以用计算机来解决的某一类 问题的程序或步骤，这些程序或步骤必 须是明确和有效的，而且能够在有限步 之内完成。 算法最重要的特征： 1.有序性 2.确定性 3.有限性

算法的基本特点

1、有限性 一个算法应包括有限的操作步骤，能在执 行有穷的操作步骤之后结束。 2、确定性 算法的计算规则及相应的计算步骤必须是唯 一确定的，既不能含糊其词，也不能有二义 性。 3、有序性 算法中的每一个步骤都是有顺序的,前一步 是后一步的前提,只有执行完前一步后,才 能执行后一步,有着很强逻辑性的步骤序列。

二、程序框图
用程序框、流程线及文字说明来表示算 法的图形称为程序框图，它使算法步骤显得 直观、清晰、简明.
○

终端框 (起止框)

输入、 输出框

处理框 (执行框)

判断框

流程线

连接点

程序框图又称流程图，是一种用规定的图形，指向线及 文字说明来准确、直观地表示算法的图形。 程序框 名称 功能

终端框（起 表示一个算法的起始和结束 止框） 输入、输出 表示算法的输入和输出的信 框 息
处理框（执 赋值、计算 行框） 判断框 判断一个条件是否成立，用 “是”、“否”或“Y”、 “N”标明

二、程序框图
?1、顺序结构

步骤n

步骤n+1

满足条件？

否

满足条件？

否

?

2、条件结构

是 步骤A 步骤B

先做后判， 否去循环
循环体

是 先判后做， 步骤 A 是去循环

循环体

?

3、循环结构

否 满足条件?

是

满足条件? 否

是

二、程序框图
?1、顺序结构
开始
输入n=100 s=(n+1)n/2 输出s 结束

设计一算法,求和1+2+3+ … +100， 并画出程序框图。 算法： 第一步：取n=100； 第二步：计算
n ( n ? 1) ； 2

第三步：输出结果。

二、程序框图
?2、条件结构

设计一个算法，求数x的绝对值，并画出程序框图。
算法分析：实数X的绝对值
开始 输入x
N Y

?x x ?? ?? x

( x ? 0) ( x ? 0)

算法： 第一步：输入x; 第二步：如果x≥0； 则输出x；否则输出 － x。

x≥0
输出x

输出-x

结束

二、程序框图
?3、循环结构
直到型循环结构 当型循环结构

A
P
是 否 否

A P
是 是

A P
否 否

A P
是

（A）

（B）
A D

（C）

（D）

直到型循环结构对应的程序框图是 当型循环结构对应的程序框图是

设计一个计算1+2+3+……+100的值的算法，并画出程序框图。 程序框图如下： 算法： 开始 第一步：令i=1,s=0; 第二步：s=s+i i=1 第三步：i=i+1； 循环结构 第四步： 直到i＞100时,输出S， s=0 结束算法，否则返回第二步。

s=s+i
i=i+1 i>100? 是 输出s 结束

循环体 条件
是
否

直到型循环结构

设计一个计算1+2+3+……+100的值的算法，并画出程序框图。 算法： 第一步：令i=1,s=0; 第二步：若i<=100成立，则执行第三步；否则，输出s，结束算法； 第三步：s=s+i； 第四步：i=i+1,返回第二步。

程序框图如下：
循环体 条件
否 是

开始 i=1 s=0 i<=100?

当型循环结构

i=i+1 是 s=s+i

否 输出s
结束

三．五种基本算法语句
语句 一般格式 主要功能
可对程序中 的变量赋值

说明
（1）提示内容和它后面 的“；”可以省略 （2）一个语句可以给多个变 量赋值，中间用“，”分隔 （3）无计算功能

1.输入 INPUT “提示内容”;变量 语句

2.输出 PRINT “提示内容”;表达式 语句

（1）表达式可以是变量， 可输出表达式 计算公式，或系统信息 （2）一个语句可以输入多

的值，计算

3.赋值 语句

变量＝表达式

个表达式，中间用“，”分隔 （3）有计算功能 （1）“=”的右侧必须是表达 可对程序中 式，左侧必须是变量 的变量赋值， （2）一个语句只能给一个 变量赋

计算

（3）有计算功能

（4）条件语句
IF-THEN-ELSE格式
IF 条件 语句1 ELSE 语句2 END IF
?

THEN

满足条件？
是 语句1

否 语句2

IF-THEN格式
是 满足条件？ 否 语句

IF 条件 THEN 语句 END IF

（5）循环语句
①WHILE语句
WHILE 条件 循环体 WEND
循环体

满足条件？
否

是

②UNTIL语句
DO 循环体 LOOP UNTIL 件
循环体

条
满足条件？ 是

否

两种循环结构有什么差别？
While（当型）循环

先判断 后执行
先判断指定的条件是否为真， 若条件为真，执行循环条件， 条件为假时退出循环。

A P
不成立 成立

Until（直到型）循环

先执行 后判断
A
P
成立 不成立

先执行循环体，然后再检查条 件是否成立，如果不成立就重 复执行循环体，直到条件成立 退出循环。

编写程序,求和1+2+3+ … +n。 顺序结构：
开始 输入n
输入语句

程序语句： INPUT n
变量=表达式

s=(n+1)n/2
输出s

赋值语句

s=(n+1) * n/2
输出语句

PRINT “S=” ; S

结束

END

练：编写一程序，求实数X的绝对值。

开始 输入X

程序: 条件结构：
N

INPUT X

条件语句：

X≥0 Y 输出X

输出－X

IF X>=0 THEN PRINT X ELSE PRINT -X END IF

结束

END

当型循环语句 练：设计一算法,求和1+2+3+ … +100。 程序框图：
开始
i ?1

程序语句：
i=1 条件
否

循环体
是

S?0

当型循环结构

S=0
WHILE i<=100

i ? i ?1
当型循环语句

S=S+i i=i+1 WEND PRINT S END

WHILE 循环体 WEND

条件

S ? S?i
i ? 100?

否 输出S 结束

是

直到型循环语句
循环体
开始

i ?1
S?0

i=1
直到型循环结构

S=0
DO

条件
是

否

S ? S?i

i ? i ?1

直到型循环语句

S=S+i i=i+1 LOOP UNTIL i>100
DO

i ? 100?

否

是
输出S

循环体
LOOP UNTIL 条件

PRINT S
END

结束

一、辗转相除法（欧几里得算法）

1、定义： 所谓辗转相除法，就是对于给定的两个 数，用较大的数除以较小的数。若余数不为 零，则将余数和较小的数构成新的一对数， 继续上面的除法，直到大数被小数除尽，则 这时较小的数就是原来两个数的最大公约数。

(1)、算法步骤： 第一步：输入两个正整数

m,n(m>n).
第二步：计算m除以n所得的余

数r.
第三步：m=n,n=r.

第四步：若r＝0,则m,n的最大
公约数等于m；否则 转到第二步. 第五步：输出最大公约数m.

以求8251和6105的最大公约数的过程为例 步骤： 8251=6105×1+2146
6105=2146×2+1813

2146=1813×1+333 显然37是148和37的最大公约数， 也就是8251和6105的最大公约 数

1813=333×5+148

333=148×2+37

148=37×4+0

更相减损术
1、背景介绍：
（1）、《九章算术》中的更相减损术：
可半者半之，不可半者，副置分母、子之数，以少减多， 更相减损，求其等也，以等数约之。 （2）、现代数学中的更相减损术： 第一步：任意给定两个正整数；判断他们是否都是偶数。 若是，则用2约简；若不是则执行第二步。 第二步：以较大的数减较小的数，接着把所得的差与较小 的数比较，并以大数减小数。继续这个操作，直到所得的 减数和差相等为止，则这个等数就是所求的最大公约数。

2、定义：

所谓更相减损术，就是对于给定的两个 数，用较大的数减去较小的数，然后将差和 较小的数构成新的一对数，再用较大的数减 去较小的数，反复执行此步骤直到差数和较 小的数相等，此时相等的两数便为原来两个 数的最大公约数。

3、方法： 例: 用更相减损术求98与63的最大公约数.

解：由于63不是偶数，把98和63以大数减小数， 并辗转相减 98－63＝35 63－35＝28 35－28＝7 28－7＝21 21－7＝21 14－7＝7 所以，98和63的最大公约数等于7

比较辗转相除法与更相减损术的区别
（1）都是求最大公约数的方法，计算上辗转相除 法以除法为主，更相减损术以减法为主，计算次数

上辗转相除法计算次数相对较少，特别当两个数字
大小区别较大时计算次数的区别较明显。 （2）从结果体现形式来看，辗转相除法体现结果 是以相除余数为0则得到，而更相减损术则以减数与 差相等而得到。

练习：
1、用更相减损术求两个正数84与72的最大公约数． 思路分析：先约简，再求21与18的最大公约数, 然后乘以两次约简的质因数4。 2、求324、243、135这三个数的最大公约数。 思路分析：求三个数的最大公约数可以先求出两个 数的最大公约数，第三个数与前两个数的最大公约 数的最大公约数即为所求。

《数书九章》——秦九韶算法 设 f ( x ) 是一个n 次的多项式

f ( x ) ? a n x ? a n ?1 x ? ? ? a1 x ? a 0 对该多项式按下面的方式进行改写：
n

n ?1

f ( x ) ? a n x n ? a n ?1 x n ?1 ? ? ? a1 x ? a 0
? ( a n x n ?1 ? a n ?1 x n ? 2 ? ? ? a1 ) x ? a 0

? ??

? (( a n x

n?2

? a n ?1 x

n ?3

? ? ? a 2 ) x ? a1 ) x ? a 0

? (? ( a n x ? a n ?1 ) x ? a n ? 2 ) x ? ? ? a1 ) x ? a 0

f ( x ) ? (? ( a n x ? a n ?1 ) x ? a n ? 2 ) x ? ? ? a1 ) x ? a 0
要求多项式的值，应该先算最内层的一次多项式的值，即

v1 ? a n x ? a n ?1
然后，由内到外逐层计算一次多项式的值，即

v 2 ? v1 x ? a n ? 2

??

v3 ? v 2 x ? a n ? 3 v n ? v n ?1 x ? a 0

这种将求一个n次多项式f(x)的值转化成求n个一 次多项式的值的方法，称为秦九韶算法。

秦九韶算法的特点：
通过一次式的反复计算，逐步得出高次多 项式的值，对于一个n次多项式，只需做n次乘 法和n次加法即可。
在秦九韶算法中反复执行的步骤，可用循环结 构来实现。
?v 0 ? a n ? ?循环体： ?v ? v x ? a (k ? 1, 2,? ,n ) k ?1 n ?k ? k

例:用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值. 解法一:首先将原多项式改写成如下形式 : f(x)=((((2x-5)x-4)x+3)x-6)x+7 然后由内向外逐层计算一次多项式的值,即
v0=2
v1=v0x-5=2×5-5=5 v2=v1x-4=5×5-4=21 v3=v2x+3=21×5+3=108 v4=v3x-6=108×5-6=534 v5=v4x+7=534×5+7=2677

所以,当x=5时,多 项式的值是2677.

例.用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值. 解法二:列表 2 x=5 -5 10 5 -4 25 21 3 105
原多项式 的系数

-6 7 540 2670 534 2677
多项式 的值.

2

108

所以,当x=5时,多项式的值是2677.

一、进位制
进位制是人们为了计数和运算方便而约定的记数系统。 进位制是一种记数方式，用有限的数字在不同的位 置表示不同的数值。可使用数字符号的个数称为基 数，基数为n，即可称n进位制，简称n进制。

基数： “满几进一”就是几进制，几进制的基数就是几.
二进制、七进制、八进制、十二进制、六十进制等 二进制只有0和1两个数字，七进制用0~6七个数字

十六进制有0~9十个数字及ABCDEF六个字母.

十进制：
我们最常用最熟悉的就是十进制数，它的数值部分是十个不 同的数字符号0，1，2，3，4，5，6，7，8，9来表示的。

例如133.59，它可用一个多项式来表示：

133.59=1*102+3*101+3*100 +5*10-1+9*10-2
式中 1 处在百位，第一个 3 所在十位，第二个 3 所在 个位，5 和9 分别处在十分位和百分位。十进制数是逢 十进一的。

为了区分不同的进位制，常在数的右下角标明基数， 十进制一般不标注基数.

例如十进制的133.59，写成133.59(10)
七进制的13，写成13(7)；二进制的10，写成10(2)

一般地，若k是一个大于1的整数，那么以k
为基数的k进制可以表示为一串数字连写在一起

的形式：

anan?1 ?a1a0(k ) (0 ? an ? k,0 ? an?1,?, a1, a0 ? k ).

二进制与十进制的转换 1、二进制数转化为十进制数 例1：将二进制数110011(2)化成十进制数。

解：根据进位制的定义可知

110011( 2 ) ? 1 ? 2 ? 1 ? 2 ? 0 ? 2 ? 0 ? 2 ? 1 ? 2 ? 1 ? 2
5 4 3 2 1

0

? 51

? 1 ? 32 ? 1 ? 16 ? 1 ? 2 ? 1

所以，110011（2）=51．

把其他进位制的数化为十进制数的公式是什么？

an an ?1 ? a1a0( k ) ? an ? k n ? an ?1 ? k n ?1 ? ? ? a1 ? k 1 ? a0 ? k 0 (10)

十进制转换为二进制
方法：除2取余法，即用2连续去除89或所得的商，然后取余数。 例、 把89化为二进制数 解： 根据“逢二进一”的原则，有 89＝2×44＋1 89＝2×44＋1 ＝ 2× (2×22＋0)+1 44＝ 2×22＋0 ＝ 2×( 2×( 2×11＋0)+0)+1 22＝ 2×11＋0 ＝ 2× (2× (2× (2× 5＋1)+0)+0)+1 11＝ 2× 5＋1 ＝ 2× (2× (2× (2× (2× 2＋1)+1)+0)+0)+1 5＝ 2× 2＋1 所以89＝2×（2×（2×（2×（2 × 2 ＋1）＋1）＋0）＋0）＋1 ＝2×（2×（2×（2×（22＋1）＋1）＋0）＋0）＋1 ＝2×（2×（2×（23＋2＋1）＋0）＋0）＋1 ＝2×（2×（24＋22＋2＋0）＋0）＋1 ＝2×（25＋23+22＋0＋0）＋1 ＝26＋24+23＋0＋0＋20 89＝1×26＋0×25＋1×24＋1×23＋0×22＋0×21＋1×20 所以：89=1011001（2）

另解（除2取余法的另一直观写法）： 2 2 2 2 2 2 2

注意： 1.最后一步商为0， 2.将上式各步所得的余数从下到上排列，得到： 89=1011001（2） 练习 将下面的十进制数化为二进制数？ （1）10 （2）20

89 44 22 11 5 2 1 0

余数 1 0 0 1 1 0 1

例：把89化为五进制数。 解：根据除k取余法 以5作为除数，相应的除法算式为：
5 5 89 17 5 3 0 余数

4 2 3

所以，89=324（5）

除k取余法：十进制数转化为k进制数的方法 用k连续去除该十进制数或所得的商，直 到商为零为止，然后把每次所得的余数倒着 排成一个数，就是相应的k进制数。

考题剖析
例、（2007海南、宁夏）如果执行下面的程序框图， 那么输出的 s =（ ）。 开始 A 2450 B 2500 C 2550 D 2652 k ＝１ 解：由程序知 s=2×1+2×2+┄+2×50 1 ? 50 ? 2? ? 50 2 =2550 故选（C） ｓ＝０
k ≤50？

否

是 s ＝ s ＋2 k k ＝ k＋1

输出ｓ 结束

［点评］本小题考查程序框图中的循环结构，主 要是根据框图，找到规律。

考题剖析
例、（2008海南、宁夏）右面的程序框图，如果输入三个 实数a，b，c，要求输出这三个数中最大的数，那么在空白 的判断框中，应该填入下面四个选项中的（ ）。 A c>x B x>c
开始
输入a，b，c x ＝a 是 b > x? 否 是 否 输出x 结束 x ＝c

C c>b D b>c 解:由程序框图可知第一个判断框 作用是比较x与b的大小,故第二个 判断框的作用应该是比较x与c的 大小。故选（A） ［点评］本题考查条件结构的程 序框图，求解时，对字母比较难理解， 可以取一些特殊的数值，代进去，方 便理解。

x＝b

（2010安徽理数）如图所示，程序框图（算法流程图） 的输出值

x?

________。

【解析】 程序运行如下:

x ? 1, x ? 2, x ? 4, x ? 5, x ? 6, x ? 8, x ? 9, x ? 10, x ? 12
输出12

解析：因为第一次判断 执行后 i ? 2, s ? 12 , 第二次判断执行后， i ? 3, s ? 12 ? 2 2
．

题目要求计算 12 ? 22 ? 32 ? ? ? ? ? 1002

故，n ? 100

例、如图给出了一个算法流程图，该算法流程 图的功能是（ ） A.求a，b，c三数的最大数 B.求a，b，c三数的最小数 C.将a，b，c按从小到大排序 D.将a，b，c按从大到小排序