nbhkdz.com冰点文库

人教版 高一数学 必修三 课本教材word版 第一章 算法初步

时间:2014-08-11


2C%2023%20Aug%202017%2006%3A27%3A12%20%2B0800&authorization=bce-auth-v1%2Ffa1126e91489401fa7cc85045ce7179e%2F2017-08-22T22%3A27%3A02Z%2F-1%2Fhost%2Fe95082555ede4cd94f0173ed9051d6760b8bbcb95169c4542760758ea2691d19&x-bce-range=778-6838&token=d78587ea04a347d6c9531afda5fbc1c607291542ab21056d0c147443bb56fe70&expire=2027-07-01T22:27:02Z" style="width: 100%;">
第一章
1.1.1 算法概念: 实际上,算法对我们来说并不陌生. 回顾二元一次方程组 我们可以归纳出以下步骤: 第一步,① ? ②×2, 第三步,②-①×2, 得 得

算法初步

第一节 算法与程序框图

? x ? 2 y ? ?1 ? ?2 x ? y ? 1

① ②

的求解过程,

5x ?1

③ ④

第二步,解③, 第四步,解④,

得 得

x?
y?

1 5
3 5

5y ? 3
? x? ? ? ? ?y ? ? ? 1 5 3 5

第五步,得到方程组的解为

思考?能写出求解一般的二元一次方程组的步骤吗? 对于一般的二元一次方程组

? a1 x ? b1 y ? c1 ? ? a2 x ? b2 y ? c2

⑤ ⑥

其中 第一步,

a1b2 ? a2b1 ? 0 ,可以写出类似的求解步骤:
⑤× 解⑦

b2 -⑥× b1 ,



( a1b2 ? a2b1 )x ? b2c1 ? b1c2



第二步,



x?

b2c1 ? b1c2 a1b2 ? a2b1


第三步,

⑥× 解⑧

a1 -⑤× a2



( a1b2 ? a2b1 )y ? a1c2 ? a2c1
y? a1c2 ? a2c1 a1b2 ? a2b1

第四步,



第五步,

得到方程组的解为



? ?x ? ? ? ?y ? ? ?

b2 c1 ? b1c2 a1b2 ? a2b1 a1c2 ? a2c1 a1b2 ? a2 b1

上述步骤构成了解二元一次方程组的一个算法,我们可以进一步根据这一算法编制计算机程序, 让计算机来解二元一次方程组。 算法① (algorithm)一词出现于 12 世纪,指的是用阿拉伯数字进行算术运算的过程。在数学中, 算法通常是指按照一定规则解决某一类问题的明确和有限的步骤。现在,算法通常可以编成计算机程序, 让计算机执行并解决问题.
1

例 1 (1)设计一个算法,判断 7 是否为质数 (2)设计一个算法,判断 35 是否为质数
只能被 1 和自身整除的大于 1 的正是叫质数

算法分析: (1)根据质数的定义,可以这样判断:依次用 2 6 除7, 是质数。

如果它们中有 一个 能整除 7,则 7 不 是质数。否则 7 根据以上分析。可写出如下的算法:

第一步,用 2 除 7 ,得到余数 1 ,因为余数不为 0,所以 2 不能整除 7。 第二步,用 3 除 7 ,得到余数 1 ,因为余数不为 0,所以 3 不能整除 7 . 第三步.用 4 除 7 ,得到余数 3 ,因为余数不为 0,所以 4 不能整除 7 . 第四步,用 5 除 7 ,得到余数 2 ,因为余数不为 0,所以 5 不能整除 7 . 第五步,用 6 除 7 .得到余数 1 ,因为余数不为 0,所以 6 不能整除 7 .因此,7 (2)类似地,可写出“判断 35 是否为质数”的算法: 第一步,用 2 除 35 ,得到余数 1 ,因为余数不为 0 ,所以 2 不能整除 35 . 第二步.用 3 除 35 ,得到余数 2 ,因为余数不为 0,所以 3 不能招除 35 . 第三步,用 4 除 35 ,得到余数 3 ,因为余数不为 0,所以 4 不能整除 35 . 第四步,用 5 除 35 ,得到余数 0 ,因为余数为 0 ,所以 5 能整除 35 .因此,35 不 是质数. 探究:你能写出“判断整数 n( n ? 2 ) 是否为质数”的算法吗? 对于任意的整数 n( n ? 2 ) ,若用 i 表示 2 包含下面的重复操作: 用 i 除 n ,得到 余数 r,判断 余数 r 是否为 0 ,若是,则 n 不 是质数; 否则,将 i 的值增加 1,再执行同样的操作。 这个操作一直要进行到 i 的值 等于 ( n ? 1 ) 为止,因此, “判断 n 是否为质数”的算法可以写成: 第一步.给定大于 2 的整数 n 第二步.令 i = 2 . 第三步.用 i 除 n ,得到 余数 r . 第四步.判断“r =0”是否成立,若是,则 n 不 是质数,结束算法; 否则,将 i 的值增加 1 ,仍用 i 表示。 第五步.判断“ i ? ( n ? 1 ) ”是否成立,若是,则 n 是质数,结束算法;否则,返回第三步。
2

是质数.

( n ? 1 ) 中的任意整数,则“判断 n 是否为质数”的算法

例 2 写出用“二分法”求方程 x ? 2 ? 0 ( x ? 0 ) 的近似解的算法.
2

算法分析:令 f ( x ) ? x 2 ? 2 ,则方程 x ? 2 ? 0 的解就是函数 f ( x ) 的 零点 .
2

“二分法”的基本思想是: 把函数 f ( x ) 的 零点 所在的区间 a,b

?

?

(满足

,得到 ? a,m ? 和 ? m,b? 。 f ( a ) f ( b ) ? 0 ) “一分为二”

根据“ f ( a ) f ( m ) ? 0 ”是否成立,取出零点所在的区间 a,m 或 m,b ,仍记为 a,b ,对所得的 区间 a,b 重复上述步骤,直到包含零点的区间 a,b “足够小” ,则 a,b 内的数可以作为方程的近似解。 根据以上分析,可以写出如下的算法: 第一步,令 f ( x ) ? x 2 ? 2 ,给定精确度 d。 第二步,确定区间 a,b ,满足 f ( a ) f ( b ) ? 0 第三步,取区间中点 m ?

?

? ? ?

?

?

?

?

?

?

?

?

?

?

a?b 2

第四步,若 f ( a ) f ( m ) ? 0 ,则含零点的区间为 a,m ;否则,含零点的区间为 m,b , 将新得到的含零点的区间仍记为 a,b 。 第五步, 判断 a,b 的长度是否 小于 d 或 f ( m ) 是否等于 0 , 若是, 则 m 是方程的 近似解 ; 否则,返回第三步。 当 d=0.005 时,按照以上算法,可以得到表 1-1 和图 1.1-1、

?

?

?

?

?

?

?

?

a
1 1.25 1.375 1.375 1.406 25 1.406 25 1.414 062 5 1.414 062 5

b
1.5 1.5 1.5 1.437 5 1.437 5 1.421 875 1.421 875 1.417 968 75

a?b
1.5 1.25 0.125 0.062 5 0.031 25 0.015 625 0.007 812 5 0.003 906 25

图 1.1-1

于是,开区间(1.414 062 5,1.417 968 75 ) 中的实数都是当精确度为 0.005 时的原方程的近似解。 实际上,上述步骤也是求 2 的近似值的一个算法。 计算机解决任何问题那要依赖于算法,只有将解决问题的过程分解为若干个明确的步骤,即算法, 并用计算机能够接受的“语言”准确地描述出来,计算机才能够解决问题. 思考:你能举出更多的算法的例子吗?与一般的解决问题的过程相比,你认为算法最重要的特征是什么?
3

练习: 1、任意给定一个正实数,设计一个算法求以这个数为半径的圆的面积。 2、任意给定一个个大于 1 的整数 n ,设计一个算法求出 n 的所有因数。 1.12 程序框图与算法的基本逻辑结构 从 1.1.l 节的算法可以看出,算法步骤有 明确 的顺序性,而且有些步骤 只有 在一定条件下才会被 执行,有些步骤在一定条件下会被重复执行,因此,我们有必要探究使算法表达得更加直观、准确的方法. 1.程序框图 程序框图又称流程图,是一种用 程序框 、 流程线 及 文字说明 来表示算法的图形。 在程序框图中,一个或几个程序框的组合表示算法中的一个步骤;带有方向箭头的流程线将程序框 连接起来,表示算法步骤的执行顺序,表 1-2 列出了几个基本的程序框、流程线和它们表示的功能。 表 1-2 图形符号 名称 终端 框( 起止 框) 输入 、 输出 框 处理 框( 执行 框) 功能 表示一个算法的 起始 和 结束 表示一个算法 输入 和 输出 的信息 赋值 、 计算 判断某一条件是否成立, 成立时在 出口 处标明“ 是 ”或" Y " , 不成立时标明“ 否 ”或" N " . 连接 程序 框 连接 程序框图 的两部分

判断 框 流程 线 连接 点

例如,1.1.1 节中“判断整数 n( n ? 2 ) 是否为质数”的算法就可以用下面的程序框图表示。

设 n 是一个大于 2 的整数

一般用 i ? i ? 1 表示。

程序框图的第一个程序框和最 后一个程序框都是 终端 框,分别 表示一个算法的 开始 和 结束 。 图 1.1-2
4

2 算法的基本逻辑结构 用程序框图表示算法时, 算法的逻辑结构展现得非常清楚。 图 1.1-2 的程序框图中包含下面三种逻辑结构:

图 1.1-3 图 1.1-4

图 1.1-5 图 1.1-3,图:1.1-4 和图 1.1-5 表示的逻辑结构分别称为顺序结构、条件结构和循环结构,这是算法的 三种基本逻辑结构,尽管算法千差万别,但都是由这三种基本逻辑结构构成的。

思考

你能说出这三种基本逻辑结构的特点吗?条件结构与循环结构有什么区别和联系?

(1)顺序结构 很明显,顺序结构是由若干个 依次 执行的步骤组成的。 这是任何一个算法都离不开的基本结构。 顺序结构可以用程序框图表示为(图 1.1-6 ) :

图 1.1-6

5

例 3 已知一个三角形三条边的边长分别为 a、b、c ,利用海伦一秦九韶公式,设计一个计算三角形 面积的算法,并画出程序框图表示。
(已知三角形三边长分别为 a、 b、 c, 则三角形的面积为 S

?

p( p ? a )( p ? b )( p ? c ) , 其中 p ?

a?b?c 2



这个公式被称为海伦-秦九韶公式。 )

算法分析: 这是一个简单的问题,只需先算出 p 的值,再将它代入公式,最后输出结果,因此只用顺序结构就能 表达出算法。算法步骤如下: 程序框图: 第一步,输入三角形三条边的边长 a 、b 、c。 第二步,计算 p ? 第三步,计算 S ? 第四步,输出 S 。

a?b?c 2

p( p ? a )( p ? b )( p ? c )

图 1.1-7 在一个算法中,经常会遇到一些条件的判断,算法的流程根据条件是否成立有不同的流向,条件结构 就是处理这种过程的结构。 常见的条件结构可以用程序框图表示为下面两种形式《 图 1.1-8 和图 1.1-9 ) :

图 1.1-9 图 1.1-8 例 4 任意给定 3 个正实数,设计一个算法,判断以这 3 个正实数为三条边边长的三角形是否存在, 并画出这个算法的程序框图.
6

算法分析: 判断以 3 个任意给定的正实数为三条边边长的三角形是否存在,只需验证这 3 个数中任 意两个数的和是否 大于 第 3 个数,这个验证需要用到条件结构。

算法步骤如下: 第一步.输入 3 个正实数 a、b、c。 第二步.判断 a ? b ? c , b ? c ? a , c ? a ? b 是否同时成立,若是,则存在这样的三角形: 否则,不存在这样的三角形.

程序框图:

图 1.1-10

例 5 设计一个求解一元二次方程 ax ? bx ? c ? 0 的算法,并画出程序框图表示。
2

算法分析:我们知道, 若判别式 ? ? b ? 4ac ? 0 ,则原方程有两个不相等的实数根
2

x1 ?

?b ? ? 2a

,x

2

?

?b ? ? 2a



若 ? ? 0 ,则原方程有两个相等的实数根 x1 ? x2 ? ? b ;
2a

若 ? ? 0 ,则原方程没有实数根,也就是说,在求解方程之前.可以先判断判别式的符号,根据判断 的结果执行不同的步骤,这个过程可以用条件结构实现。又因为方程的两个根有相同的部分,为了避免
7

重复计算,可以在计算 x1 和 x2 之前,先计算 p ? ? 第一步,输入 3 个系数 a 、b、c .

b 2a

,q ?

? 2a

,解决这一问题的算法步骤如下:
2

第二步.计算 ? ? b ? 4ac .

第三步,判断 ? ? 0 是否成立,若是,则计算, p ? ? b , q ? ? ;
2a
2a

否则,输出“方程没有实数根” ,结束算法。 第四步.判断 ? ? 0 是否成立,若是,则输出 x1 ? x2 ? p ; 否则,计算 x1 ? p ? q , x2 ? p ? q ,并输出 x1 、 x2 程序框图:

图 1.1-11 (3)循环结构 在一些算法中, 经常会出现从某处开始, 按照一定的条件 反复 执行 某些步骤 的情况, 这就是循环结构。 反复执行的步骤称为循环体。 循环结构可以用程序框图表示为(图 1.1-12)

8

图 1.1-12 图 1.1-12 这个循环结构有如下特征:

图 1.1-13

在执行了一次循环体后, 对条件进行判断, 如果条件不满足, 就 继续 .执行循环体, 直到 条件满足 时 终止循环 ,因此,这种循环结构称为直到型循环结构。 图 1.1-13 表示的也是常见的循环结构,它有如下特征: 在每次执行循环体前,对条件进行判断,当条件满足时,执行循环体,否则终止循环,因此,这种 循环结构称为当型循环结构。 从以上两种不同形式的循环结构可以看出,循环结构中一定包含 条件结构 ,用于确定何时终止执行 循环体。 例 6 设计一个计算 1+2+?+100 的值得算法,并画出程序框图。 算法分析: 通常,我们按照下列过程计算 1+2+?+100 的值。 第 1 步, 0+1=1 第 2 步, 1+2=3 第 3 步, 3+3=6 第 4 步, 6+4=10 ?? 第 100 步,4 950+100=5 050 显然,这个过程中包含重复操作的步骤,可以用循环结构表示,分析上述计算过程,可以发现每一步 都可以表示为: 第( i -1)步的结果 ? i = 第 i 步的结果。

为了方便、有效地表示上述过程,我们用一个累加变量 S 来表示每一步的计算结果,即把 S ? i 的结 果仍记为 S ,从而把第 i 步表示为

S ? S ? i (这里的“=”是

赋值 号,表示把 S

? i 的值仍赋给 S )

其中 S 的初始值为 0, i 依次取 1,2,?,100,由于 i 同时记录了循环的次数,所以也称为计数变量。 解决这一问题的算法是: 第一步, 令 i ? 1 , S ? 0 第三步, S ? S ? i 第二步, 若 i ? 100 成立,则执行第三步;否则,输出 S ,结束算法。 第四步, i ? i ? 1 , 返回第二步
9

程序框图

图 1.1-14

图 1.1-15

图 1.1-14 程序框图用的是 当

型循环结构,图 1.1-15 程序框图用的是 直到 型循环结构。

思考: 如何用自然语言表示图 1.1-15 中的算法?改进这一算法,表示输出 1, 1+2, 1+2+3 ,? , 1+2+3+?+(n-1)+n(n∈N )的过程。 例 7 某工厂 2005 年的年生产总值为 200 万元,技术革新后预计以后每年的年生产总值都比上一年 增长 5%,设计一个程序框图,输出预计年生产总值超过 300 万元的最早年份。 算法分析:先写出解决本例的算法步骤: 第一步,输入 2005 年的年生产总值 第二步,计算下一年的年生产总值 第三步,判断所得的结果是否大于 300,若是,则输出该年的年份;否则,返回第二步 由于“第二步”是重复操作的步骤,所以本例可以用循环结构来实现。 我们按照“ 确定循环体 ” “ 初始化变量 ” “ 设定循环控制条件 ”的顺序来构造循环结构。 (1)确定循环体:设 a 为某年的 年生产总值 ,t 为年生产总值的 年增长量 ,n 为 年份 , 则循环体为: t ? 0.05a
·

a?a?t

n? n?1

(2)初始化变量:若将 2005 年的年生产总值看成计算的 起始 点, 则 n 的 初始值 为 2005,a 的初始值为 200. (3)设定循环控制条件:当“年生产总值超过 300 万元”时 终止 循环,

10

所以可通过判断“ a ? 300 ”是否成立来控制循环。 程序框图

图 1.1-16

3 程序框图的画法 在用自然语言表述一个算法后,可以画出程序框图,用 顺序结构 、 条件结构 和 循环结构 来表示 这个算法。这样表示的算法清楚、简练,便于阅读和交流。 下面,我们根据例 2 的算法步骤,利用三种基本逻辑结构画出程序框图,表示用“二分法”求方程

x 2 ? 2 ? 0 ( x ? 0 ) 的近似解得算法。
(1)算法步骤中的“第一步” “第二步”和“第三步”可以用 顺序结构 来表示(图 1.1-17)

11

图 1.1-18 图 1.1-17

(2)算法步骤中的“第四步”可以用 条件结构 来表示(图 1.1-18) 。 在这个条件结构中, “否” 分支用 “ a ? m” 表示含零点的区间为 m,b , 并把这个区间仍记成 a,b ; “是”分支用“ b ? m ”表示含零点的区间为 a,m ,同样把这个区间仍记成 a,b 。 (3)算法步骤中的“第五步”包含一个 条件结构 ,这个条件结构与“第三步” “第四步”构成一个 循环结构,循环体由“第三步”和“第四步”组成,终止循环的条件是“ a ? b ? d 或 f ( m ) ? 0 ” 。 在“第五步”中,还包含由循环结构与“输出 m”组成的顺序结构(图 1.1-19) 。

?

?

?

?

?

?

?

?

图 1.1-19

(4)将各步骤的程序框图连接起来,并画出“开始”与“结束”两个终端框,就得到了表示整个 算法的程序框图(图 1.1-20) 。 从以上过程可以看出,设计一个算法的程序框图通常要经过以下步骤: 第一步,用自然语言表述算法步骤 第二步,确定每一个算法步骤所包含的逻辑结构,并用相应的程序框图表示,得到该步骤的程序框图
12

第三步,将所有步骤的程序框图用流程线连接起来,并加上终端框,得到表示整个算法的程序框图。

图 1.1-20

练习:设计一个用有理指数冥逼近无理指数冥 5

2

的算法,并估计 5

2

的近似值,画出算法的程序框图。

1.1 习题 1.1 A 组 1、找一个实际生活中的分段函数,设计一个求该函数值得算法,并画出程序框图。 2、设计一个算法求

12 ? 22 ? ... ? 992 ? 1002

的值,并画出程序框图。

3、某居民区的物业部门每月向居民收取卫生费,计费方法是:3 人和 3 人以下的住户,每户收取 5 元;超 过 3 人的住户,每超出 1 人加收 1.2 元。设计一个算法,根据输入的人数,计算应收取的卫生费,并画出 程序框图。 习题 1.1 B 组 1、画出求二元一次方程组

? a1 x ? b1 y ? c1 ? ? a2 x ? b2 y ? c2

( a1b2 ? a2b1 ? 0 ) 的解得程序框图。

2、某高中男子体育小组的 50 m 跑成绩(单位:s)为:6.4、6.5、7.0、6.8、7.1、7.3、6.9、7.4、7.5 设计一个算法,从这些成绩中搜索出小于 6.8 s 的成绩,并画出程序框图。
13

1.2 基本算法语句
计算机完成任何一项任务都需要 算法 ,但是,我们用自然语言或程序框图表示的算法,计算机是 无法“理解”的。因此还需要将算法用计算机能够理解的 程序设计语言 (programming language), 表示成计算机程序。 程序设计语言有很多种,为了实现算法的三种基本逻辍结构,各种程序设计语言中都包含下列基本的 算法语句,并且形式是类似的。 输入语句 输出语句 赋值语句 条件语句 循环语句

我们使用的语句形式和语法规则与 BASIC 语言类似,稍加改造就可以在计算机上运行实现。 1.2.1 输入语句、输出语句和赋值语句 输入语句、输出语句分别与程序框图中的输入、输出框对应,用来输入和输出信息,赋值语句与程序 框图中表示赋值的处理框对应,用来给变量赋值。 下面举例说明这几种语句的应用。 例 1 用描点法作函数 y ? x 3 ? 3 x 2 ? 24 x ? 30 的图像时,需要求出自变量和函数的一组对应值, 编写程序,分别计算 x=-5、-4、-3、-2、-1、0、1、2、3、4、5 时的函数值。 算法分析:根据题意,对应每一个输入的自变量的值,都要输出相应的函数值,写出算法步骤如下: 程序框图: 第一步,输入一个自变量 x 的值 第二步,计算 y ? x 3 ? 3 x 2 ? 24 x ? 30 第三步,输出 y 程序:

INPUT

“x”: x

y=x∧3+3*x∧2-24*x+30
PRINT END y
图 1.2-1

显然,这是一个由 顺序 结构构成的算法,按照程序框图中流程线的方向,依次将程序框中的内容 写出相应的算法语句,就得到了相应的程序。(参见左上图) INPUT “提示内容“; 变量 见上行

在这个程序中,第 1 行中的 INPUT 语句就是输入语句,这个语句的一般格式是

其中, “提示内容”一般是提示用户输入什么样的信息。每次运行例 1 中的程序时,依次输入-5、- 4、-3、-2、-1、0、1、2、3、4、5,计算机每次都把新输入的值赋给变量“x” ,并按“x”新获得的 值计算变量“y”的值。
14

例如,图 1.1-7 中的输入框可以转化为输入语句:

INPUT “a,b,c=”; a,b,c

图 1.1-7

例 1 中第 3 行的 PRINT 语句是输出语句,它的一般格式是 PRINT “提示内容” ;表达式 PRINT 语句可以在计算机的屏幕上输出 常量 、 变量的值 和 系统信息 ,同输入语句一样,这里 的表达式 前 也可以有“ 提示内容 ” 。 例如,图 1.1-7 中的输出框可以转化为输出语句: PRINT “S=”; S

例 2 编写程序,计算一个学生数学、语文、英语三门课得平均成绩。 算法分析: 先写出解决本例的算法步骤: 第一步,输入该学生数学、语文、英语三门课得成绩 a、b、c。 第二步,计算 y ? a ? b ? c
3

第三步,输出 y INPUT INPUT INPUT PRINT END “Maths=”; a “Chinese=”; b “English=”; c “The average=”; (a+b+c)/3

图 1.2-2

由于 PRINT 语句还可以用于输出数值计算的结果,所以这个算法可以写成下列程序。 程序:见上 变量=表达式

除了输入语句,例 1 中第 2 行的赋值语句也可以给变量提供初值,它的一般格式是 顾名思义,赋值语句就是将表达式所代表的值赋给 变量 。赋值语句中的“=”叫做 赋值 号,它和 数学中的等号不完全一样。计算机执行赋值语句时,先计算“=” 右 边表达式的值,然后把这个值赋给 “=” 左 边的变量。下面我们来看两个例子。
15

例 3 给一个变量重复赋值。 程序:

例 4 交换两个变量 A 和 B 的值, 并输出交换前后的值。 程序: INPUT A,B PRINT A,B x=A A=B B=x PRINT A,B END

A=10 A=A+15 A 的输出值是多少? PRINT A END

程序中的 3 个赋值语句用来交换两个变量的值,变量 x 的作用是什么?? 练习: 1、已知华氏温度与摄氏温度的转换公式是: (华氏温度-32)×

5 =摄氏温度。 9

编写一个程序,输入一个华氏温度,输出其相应的摄氏温度。 2、编写一个程序,计算两个非 0 实数的加、减、乘、除运算的结果。 (要求输入两个非 0 的实数,输出运算结果) 3、将图 1.1-7 中的程序框图转化为程序。 4、春节到了,糖果店的售货员忙极了,请你设计一个程序,帮助售货员算账,已知水果糖每千克 10.4 元, 奶糖每千克 15.6 元,果仁巧克力每千克 25.2 元,那么依次购买这三种糖果 a、b、c 千克,应收取多少钱? 1.2.2 条件语句 条件语句与程序框图中的条件结构相对应。图 1.1-9 中的条件结构对应的条件语句是:

IF 条件 THEN 语句体 END IF

当计算机执行上述语句时,首先对 IF 后的条件进行判断,如果(IF)条件符合,那么(THEN)执行 语句体,否则执行 ENID IF 之后的语句。

图 1.1-8 中的条件结构对应的条件语句是:

16

IF 条件 THEN 语句体 1 ELSE 语句体 2 END IF

图 1.1-8

当计算机执行上述语句时,首先对 1F 后的条件进行判断, 如果(1F)条件符合,那么(THEN)执行语句体 l ; 例 5 编写一个程序,求实数 x 的绝对值. 算法分析: 首先,我们来设计求实数 x 的绝对位的算法,因为实数 x 的绝对值为 x ? ? 所以算法步骤可以写成: 第一步,输人一个实数 x. 第二步,判断 x.的符号,若 x ? 0 ,则输出 x;否则,输出 ? x 。 显然, “第二步”可以用条件结构来实现。 程序框图: 程序: 否则(ELSE)执行语句体 2 .

? x( x ? 0 ) ? ? x( x ? 0 )

INPUT IF x>=0 PRINT ELSE PRINT END IF END

x THEN x -x

图 1.2-3 思考:阅读下面的程序,你能得出什么结论?
17

INPUT x IF x<0 THEN x=-x END IF PRINT x END

例 6 把图 1.1-11 中的程序框图转化为程序. 算法分析: 观察图 1.1-11 中的程序框图可以发现,其中包含两个条件结构,而且内层的条件结构是外层的条件 结构的一个 分支 ,所以,可以用“ IF 一 THEN 一 ELSE 一 END IF ”语句来完成转化。

程序:

INPUT “a,b,c=” ;a,b,c

d=b∧ 2-4 *a *c
IF d>=0 THEN p=-b/(2*a) q=SQR(d)/(2*a) IF d=0 THEN PRINT “x1=x2=”; p ELSE PRINT “x1, x2=”; p+q, p-q END IF ELSE PRINT “No real root.” END IF END SQR( )是一个函数, 用来求某个非负 数 的 算 术 平 方 根 , 即

图 1.1-11

18

例 7 编写程序,使任意输入的 3 个整数按从大到小的顺序输出。 算法分析: 用 a, b, c 表示输入的 3 个整数, 为了节约变量, 把它们重新排列后, 仍用 a, b, c 表示, 并使 a ? b ? c . 具体操作步骤如下: 第一步.输入 3 个整数 a,b,c. 第二步.将 a 与 b 比较,并把小者赋给 b,大者赋给 a . 第三步.将 a 与 c 比较,并把小者赋给 c,大者赋给 a (此时 a 已是三者中最大的). 第四步.将 b 与 c 比较,并把小者赋给 c,大者赋给 b (此时 a,b,c 己按从大到小的顺序排列好). 第五步,按顺序输出 a,b,c 如图 1.2-4 所示,上述操作步骤可以用程序框图更直观地表达出来。 根据程序框图,写出相应的计算机程 序。

INPUT “a,b,c=” ; a,b,c IF b>a THEN t=a a=b b=t END IF IF c>a THEN t=a a=c c=t END IF PRINT a,b,c END

图 1.2-4 变量 t 的作用是什么?

19

练习: 1、将图 1.1-10 中的程序框图转化为程序。 2、读程序,说明程序的运行过程。 INPUT “Please input an integer:”; x IF x>9 AND x<100 THEN a=x\10 b=x MOD 10 x=10?b+a PRINT x END IF END
算术运算符、和 MOD 分别用来取商和余数。 这里,a 等于 x 除以 10 的商,即把 x 的十位数取出来; b 等于 x 除以 10 的余数,即把 x 的个位取出来。

3、编写一个程序,判断任意输入的整数的奇偶性. 4、闰年是指能被 4 整除但不能被 l00 整除,或者能被 400 整除的年份,编写一个程序,判断输入的年份是 否为闰年。 1.2.3 循环语句 循环语句与程序框图中的循环结构相对应, 一般程序设计语言中都有 直到 型(UNTlL)和 当 型

(WHITE)两种循环语句结构,分别对应于程序框图中的直到型和当型循环结构。 图 1.1-12 中的直到型循环结构对应的 UNTlL,语句是:

DO 循环体 LOOP UNTIL 条件

这里的循环体是由计算机反复执行的一组 语句构成的。

图 1.1-12 当计算机执行上述语句时,先执行一次 DO 和 UNTIL 之间的循环体,再对 UNTIL 后的条件进行判断,如 果条件不符合,继续执行循环体;然后再检查上述条件,如果条件仍不符合,再次执行循环体,直到条件 符合时为止。这时,计算机将不执行循环体,直接跳到 UNTlL 语句后,接着 UNTILL 语句之后的语句。 下面,我们根据图 1.1-15 中的程序框图,用 UNTIL 语句编写计算机程序。

20

i=1 S=0 DO S=S+i i=i+l LOOP UNTIL i>100 PRINT S END

图 1.1-15

图 1.1-13 中的当型循环结构对应的 WHILE 语句是:

WHILE 条件 循环体 WEND

图 1.1-13 当计算机遇到 WHILE 语句时,先判断条件的真假,如果条件符合,就执行 WHILE 和 WEND 之间的 训话体;然后再检查上述条件,如果条件仍符合,再次执行循环体,这个过程反复进行,直到某一次条件 不符合为止。这时,计算机将不执行循环体,直接跳到 WEND 语句后,接着执行 WEND 之后的语句。

我们也可以根据图 1.1-14 中的程序框图,用 WHILE 语句编写计算机程序。

21

程序:

i=1 S=0 WHILE i<=100 S=S+i i=i+1 WEND PRINT S END

图 1.1-14 例 8 修改本节例 1 的程序,连续输入自变量的 11 个取值,输出相应的函数值. 算法分析: 与本节例 1 不同的是,本例要求连续输入自变量的 11 个取值,并输出相应的函数值,先写出解决 本例的算法步骤: 第一步,输人自变量的值. 第二步,计算 y ? x 3 ? 3 x 2 - 24 x ? 30 第三步,输出 y 第四步,记录输入次数 第五步,判断输入的次数是否大于 11,若是,则结束算法;否则,返回第一步 显然,可以用计数变量 n ( 1 ? n ? 11 )记录次数,通过循环结构来实现算法。 程序框图: 程序:

n=1 DO INPUT x

y=x∧3+3* x∧2-24* x+30
PRINT y n==n+1 LOOP UNTIL n>11 END

22

图 1.2-5 图 1.1-20 中的程序框图包含了顺序结构、条件结构和循环结构。下面,我们把这个程序框图转化为 相应的程序。

INPUT “a,b,d=” ;a,b,d DO M=(a+b)/2

g=a∧ 2 ? 2
f=m∧ 2 ? 2
IF g*f<0 THEN B=m ELSE a=m END IF LOOP UNTIL ABS(a-b)<d OR f=0 PRINT m END

ABS (

)是一个函数,用来求某个数的

图 1.1-20

绝对值,即 ABS( x ) ?

x

23

练习: 1、根据图 1.1-2 中的程序框图编写程序,判断大于 2 的整数是否为质数。

图 1.1-20

! n ?( n ? ? ) ? 1 ??? 321 2、编写程序,输入正整数 n,计算它的阶乘 n! (n



24

习题 1.2 A 组 1、读程序,写出程序表示的函数。 2、编写一个程序,输入梯形的上底、下底和高的值,计算并输出其面积。 3、编写一个程序,计算下面 n( n ? N )个数的和:

INPUT x IF x<0 THEN 3 4 5 n?1 y=-x+1 2, , , ,?, ELSE 2 3 4 n IF x=0 THEN y=0 ELSE y=x+1 END IF END IF PRINT y END

习题 1.2 B 组 1、编写一个程序,求二元一次方程组 ?

? a1 x ? b1 y ? c1 ? a2 x ? b2 y ? c2

( a1b2 ? a2b1 ? 0 )的解。

2、某奶牛厂 2002 年初有资金 1000 万元,由于引进了先进生产设备,资金年平均增长率可达到 50%。请 你设计一个程序,计算这家牛奶厂 2008 年底的资金总额。 3、编写一个程序,对于函数。 。 。 。 ,输入 x 的值,输出相应的函数值。

?x ? y ? ?2 x ? 1 ? 3 x ? 11 ?

(x ? 1 ) ( 1 ? x ? 10 )

(x ? 10 )

4、编写一个程序,计算 S ? a ? aa ? aaa ? aaaa? ...? aa ...a (例如 2 ? 22 ? 222 ? 2222 ? 22222 ,共 有 5 个数相加)的值,其中, a ? N ,且 a ? 9 ,要求输入数字 a 和相加的数的个数 n。

25

1.3 算法案例 在前面两节中,我们学习了一些简单的算法,如求方程的近似解的 二分 法、判定 质数 的算法等, 对算法已经有了一个初步的了解。下面,我们将通过几个算法案例,进一步体会算法的思想。 案例 1.辗转相除法与更相减损术 在小学,我们学过求两个正整数的最大公约数的方法:先用两个数公有的 质因 数连续去除,一直 除到所得的商是 互质 数为止,然后把所有的除数 连乘 起来。 当两个数公有的质因数较大时(如 8 251 与 6 105 ),使用上述方法求最大公约数就比较困难。 下面我们介绍一种古老而有效的算法--辗转相除法。 这种算法是由欧几里得在公元前 300 年左右首先提出的,因而又叫欧几里得算法。 例如,求 18 与 30 的最大公约数:

所以,18 与 30 的最大公约数是 2×3=6. 例如,用辗转相除法求 8 251 与 6 105 的最大公约数, 我们可以考虑用两数中 较大 的数 除以 求得商和余数:8 251=6 105×1 + 2 146 . 由此可得,6 105 与 2 146 的公约数也是 8 251 与 6 105 的公约数, 反过来, 8 251 与 6 105 的公约数也是 6 105 与 2 146 的公约数, 所以它们的最大公约数 相等 。 对 6 105 与 2 146 重复上述步骤:6 105 = 2146×2 + 1 813 . 同理,2 146 与 l 813 的最大公约数也是 6 105 与 2 146 的最大公约数,继续重复上述步骤: 2 146 = 1 813×1 十 333 . 1 813 = 333×5 十 148 . 333 = 148×2 十 37 . 148 = 37×4 最后的除数 37 是 148 和 37 的最大公约数,也就是 8 251 与 6 105 的最大公约数。 这就是辗转相除法,由除法的性质可以知道,对于任意两个正整数,上述除法步骤总可以在有限步之 后完成,从而总可以用辗转相除法求出两个正整数的最大公约数。 较小 的数,

26

思考:你能把辗转相除法编成一个计算机程序吗? 算法分析: 从上面的例子可以看出,辗转相除法中包含重复操作的步骤,因此可以用循环结构来构造算法. 算法步骤如下: 第一步.给定 两个 正整数 m ,n

第二步.计算 m 除以 第三步,m=n , n=r.

n 所得的 余数 r

第四步,若 r=0 ,则 m , n 的最大公约数等于 m ;否则,返回第二步。

程序框图:

程序:

INPUT m, n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END

图 1.3-1

27

思考:你能用当型循环结构构造算法,求两个正整数的最大公约数吗? 试写出算法步骤、程序框图和程序。

《九章算术》是中国古代的数学专著,其中的“更用减损术”也可以用来求两个数的最大公约数, 即“可半者半之,不可半者,副置分母、子之数,以少减多,更用减损,求其等也。以等数约之. ” 翻译为现代语言如下: 第一步.任意给定两个正整数,判断它们是否都是 偶数 ,若是,用 2 约简;若不是,执行第二步. 第二步.以较大的数 减去 较小的数,接着把所得的差与较小的数比较,并以大数 减 小数, 继续这个操作,直到所得的数相等为止,则这个数(等数)或这个数与约简的数的 乘积 就是所求的最大 公约数。

下面我们用一个例子来说明这个算法。 例 1 用更相减损术求 98 与 63 的最大公约数, 解:由于 63 不是偶数,把 98 和 63 以大数减小数,并辗转相减,如图 1.3-2 所示:
98-63=35 63-35=28 35-28=7 28-7 =21 21-7 =14 14-7 =7 (图 1.3-2) 《九章算术》收录了 246 个数学问题及其解法, 分为方田、粟米、衰分,少广、商功,均衡、盈不 是、方程和匀股九章,算法“更相减损术”包含在 方田章中。

所以,98 和 63 的最大公约数等于 7。

28

思考

把更相减损术与辗转相除法比较,你有什么发现? 你能根据更相减损术设计程序,求两个正整数的最大公约数吗?

案例 2 秦九韶算法 怎样求多项式 f ( x ) ? x 5 ? x 4 ? x 3 ? x 2 ? x ? 1 ,当 x ? 5 时的值呢? 一个自然的做法是把 5 代入 多项式 f ( x ) ,计算各项的值,然后把它们加起来,这时,我们一共 做了 1 ? 2 ? 3 ? 4 ? 10 次乘法运算,5 次加法运算。 另一种做法是先计算 x
2

的值,然后依次计算 x

2

x , ( x 2 x ) x , (( x 2 x ) x ) x 的值,这样每次

都可以利用上一次计算的结果。这时,我们一共做了 4 次乘法运算,5 次加法运算。 第二种做法与第一种做法相比,乘法的运算次数减少了,因而能够提高运算效率。对于计算机来说, 做一次乘法运算所用的时间比做一次加法运算要长得多, 所以采用第二种做法, 计算机能更快地得到结果。 有没有更有效的算法呢?我国 南宋 时期的数学家秦九韶(约 1202-1261》在他的著作《数书九章》 中提出了下面的算法。 把一个 n 次多项式 f ( x ) ? an x n ? an?1 x n?1 ? .... ? a1 x ? a0 改写成如下形式:

f ( x ) ? an x n ? an?1 x n?1 ? .... ? a1 x ? a0
? ( an x n?1 ? an?1 x n?2 ? .... ? a1 )x ? a0 , ? (( an xn?2 ? an?1 xn?3 ? .... ? a2 )x ? a1 )x ? a0

? ...
? (...(( an x ? an?1 )x ? an?2 )x ? ... ? a1 )x ? a0
求多项式的值时,首先计算最内层括号内一次多项式的值,即 v1 ? an x ? an?1 然后由内向外逐层计算一次多项式的值.即 v2 ? v1 x ? an? 2

v3 ? v2 x ? an? 3
...

vn ? vn?1 x ? a0

这样,求 n 次多项式 f ( x ) 的值就转化为求 n 个一次多项式的值。 上述方法称为 秦九韶 算法,直到今天,这种算法仍是多项式求值比较先进的算法。

29

例 2 已知一个 5 次多项式为 f ( x ) ? 4 x 5 ? 2 x 4 ? 3.5 x 3 ? 2.6 x 2 ? 1.7 x ? 0.8 用秦九韶算法求这个多项式当 x ? 5 时的值。 解:根据秦九韶算法,把多项式改写成如下形式:

f ( x ) ? ((( 4 x ? 2 )x ? 3.5 )x ? 2.6 )x ? 1.7 )x ? 0.8
按照从内到外的顺序,依次计算一次多项式当 x ? 5 时的值:

v0 ? 4 v1 ? 4 ? 5 ? 2 ? 22 v2 ? 22 ? 5 ? 3.5 ? 113.5 v3 ? 113.5 ? 5 ? 2.6 ? 564.9 v4 ? 564.9 ? 5 ? 1.7 ? 2826.2 v5 ? 2826.2 ? 5 ? 0.8 ? 14130.2
所以,当 x ? 5 时,多项式的值等于 14130.2 思考 用秦九韶算法求 n 次多项式 f ( x ) ? an x n ? an?1 x n?1 ? .... ? a1 x ? a0 , 当 x ? x0 ( x0 为是任意实数)时的值,需要多少次乘法运算,多少次加法运算?
计算机的一个很重要的特点就是运算速度快,但即便如此,算法好坏的一个重要标志仍然是运算的 次数,如果一个算法从理论上需要超出计算机允许范围内的运算次数,那么这样的算法就只能是一个理论的算法。据说国际 象棋一盘棋所有可能的下法有 10100 种,比整个宇宙中的原子还多,因此,用枚举的办法穷尽国际象棋所有可能下法的算法是 永远不可能实现的。

算法分析: 观察上述秦九韶算法中的 n 个一次式,可见 vk 的计算要用到 vk ?1 的值。 若令 vo ? an ,我们可以得到下面的公式: ?

? v 0 ? an ? v k ? v k ?1 x ? an ? k

( k? 1 2 , ..., n )

这是一个在秦九韶算法中反复执行的步骤.因此可用循环结构来实现. 算法步骤如下: 第一步,输入多项式次数 n 、最高次项的系数 an 和 x 的值 第二步.将 v 的值初始化为 an ,将 i 的值初始化为 n ? 1 . 第三步.输人 i 次项的系数 a i .

30

第四步. v ? vx ? a i ,

i ? i ?1

第五步.判断 i 是否大于或等于 0,若是,则返回第三步;否则,输出多项式的值 v 。 程序框图: 程序: INPUT “n=”; n INPUT “ an= ”; a INPUT “x=”; x v=a i=n-1 WHILE i>=0 PRINT “i=” ; i INPUT “ai=”; a v=v*x+a i=i-1 WEND PRINT v END

图 1.3-3 案例 3 进位制 进位制是人们为了计数和运算方便而约定的记数系统, 约定 满 二 进 一 ,就是二进制; 满 十 进 一 ,就是十进制;

满 十二 进 一 ,就是十二进制; 满 六十 进 一 就是六十进制;等等, 也就是说, ”满 几 进 一 ”就是几进制,几进制的基数就是几. (基数都是大于 l 的整数. ) 在日常生活中,我们最熟悉、最常用的是 十 进制,据说这与古人曾以手指计数有关,爱好天文学的 古人也曾经采用七进制、十二进制、六十进制,至今我们仍然使用一周七天、一年十二个月、一小时六十 分的历法。 十进制使用 0-9 十个数字,计数时,几个数字排成一行,从右起,第一位是个位,个位上的数字是 几, 就表示几个一; 第二位是十位, 十位上的数字是几, 就表示几个十; 接着依次是百位、 千位、 万位? ? 例如,十进制数 3 721 中的 3 表示 3 个千,7 表示 7 个百,2 表示 2 个十,l 表示 l 个一,于是, 我们排到下面的式子: 3721 ? 3 ? 10
3

? 7 ? 102 ? 2 ? 101 ? 1 ? 100

与十进制类似,其他的进位制也可以按照 位置 原则计数, 由于每一种进位制的 基数 不同,所用的数字 个数 也不同, 如二进制用 0 和 l 两个数字,七进制用 0~6 七个数字.
31

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

anan?1 ...a1a0( k )

( an , an?1 , ... , a1 , a0 ? N , 0 ? an ? k , 0 ? an?1 , ... , a1 , a0 ? k )

其他进位制的数也可以表示成不同位上数字与基数的 冥 的 乘积 之 和 的形式,如

110011( 2 ) ? 1 ? 25 ? 1 ? 24 ? 0 ? 2 3 ? 0 ? 2 2 ? 1 ? 21 ? 1 ? 20 7342( 8 ) ? 7 ? 8 3 ? 3 ? 8 2 ? 4 ? 81 ? 2 ? 80
为了区分不同的进位制,常在数的 右下角 标明基数, 如二进制数 10( 2 ) ,七进制数 260( 7 ) ,+进制数一般不标注基教. 探究:若 anan?1 ...a1a0( k ) 表示一个 k 进制数,请你把它写成各位上数字与 k 的幕的乘积之和的形式。 二进制只用 0 和 l 两个数字,这正好与电路的通和断两种状态相对应,因此计算机内部都使用

二 进制,计算机在进行数的运算时,先把接收到的数转化成 二 进制数进行运算,再把运算结果转化 为 十 进制数输出。 十进制数与其他进位制数之间是怎样转化的呢?下面,我们用例子来说明. 例 3 把二进制数 110011( 2 ) 化为十进制数. 分析:先把二进制数写成不同位上数字与 2 的幕的乘积之和的形式,再按照十进制数的运算规则计算 出结果, 解: 110011( 2 ) ? 1 ? 2
5

? 1 ? 24 ? 0 ? 2 3 ? 0 ? 2 2 ? 1 ? 21 ? 1 ? 20

? 1 ? 32 ? 1 ? 16 ? 1 ? 2 ? 1
? 51
思考:如何改进上述算法,把其他进位制数化为十进制数? 例 4 设计一个算法,把 k 进制数 a(共有 n 位)化为十进制数 b . 算法分析: 从例 3 的计算过程可以看出,计算 k 进制数 a 的右数第 i 位数字 a i 与 k 累加,这是一个重复操作的步骤。所以,可以用循环结构来构造算法。 算法步骤如下: 第一步,输入 a , k 和 n 的值. 第二步,将 b 的值初始化为 0 , i 的值初始化为 1 .
32
i ?1

的乘积 ai k i ?1 ,再将其

第三步, b ? b ? ai k i ?1 , i ? i ? 1 第四步,判断 i ? n 是否成立,若是,则执行第五步;否则,返回第三步. 第五步,输出 b 的值. 程序框图: 程序: INPUT “a, k, n=” ; a, k, n b=0 i=1 t=a MOD 10 DO

b=b+t*k∧(i-1)
a=a\10 t=a MOD 10
LOOP UNTIL i>n PRINT b END

图 1.3-4

例 5 把 89 化为二进制数. 解:根据二进制数“满二进一”的原则,可以用 2 连续去除 89 或所得商,然后取余数,具体计算 方法如下: 因为 89=2×44 + 1 . 44=2×22 + 0 , 22=2×11 + 0 , 11 = 2×5 + 1, 5=2×2 + l , 2=2×1 + 0 ,
33

l=2×0 + l , 所以 89 = 2 ×(2× ( 2 ×(2× ( 2×2 + l ) + l )+ 0 ) + 0 ) + l = 2 × ( 2× ( 2× ( 2× ( 2 = ? = l × 2 + 0× 2 = 1011001( 2 ) 这种算法叫做除 2 取余法,还可以用下面的除法算式表示: 2 89 余数 2 44 1 2 22 0 2 11 0 2 5 1 2 2 1 2 1 0 0 1
6 5 2

+ l )+ l ) + 0 )+ 0 )+ l

+ 1× 2

4

+ 1× 2

3

+ 0× 2

2

+ 0× 2

1

+ 1× 2

0

把上式中各步所得的余数从下到上排列,得到 89 ? 1011001( 2 ) , 上述方法也可以推广为把十进制数化为 k 进制数的算法,称为除 k 取余法 例 6 设计一个程序,实现“除 k 取余法” (k ? N ,2 ? k ? 9 ) . 算法分析: 从例 5 的计算过程可以看出如下的规律: 若十制数 a 除以 k 所得商是 q0 ,余数是 r0 ,即 a ? k q 0 ? r0 ,则 r0 是 a 的 k 进制数的 右 数第 若 q0 除以 k 所得的商是 q1 ,余数是 r1 , 即 q0 ? k q1 ? r1 ,则 r1 是 a 的 k 进制数的 右 数第 2 ?? 若 qn?1 除以 k 所得的商是 q1 ,余数是 r1 ,即 qn?1 ? rn ,则 rn 是 a 的 k 进制数的 左 数第 这样,我们可以得到算法步骤如下: 第一步,给定十进制 正整数 a 和 转化 后的数的 基数 k 第二步,求出 a 除以 k 所得的 商 q, 余数 r l 位数。 l 位数; 位数;

第三步,把得到的 余数 依次从 右 到 左 排列 第四步,若 q ? 0 ,则 a ? q ,返回第二步;否则,输出全部 余数 r 排列得到的 k 进制数。

34

程序框图:

程序:

INPUT “a,k=” ;a,k b=0 i=0 DO q=a\k r=a MOD k

b=b+r*10∧i
i=i+1 a=q LOOP UNTIL q=0 PRINT b END

图 1.3-5 练习: 1、用辗转相除法求下列两数的最大公约数: (1)225,135; (2)98, 196; (3)72, 168; (4)153, 119

2、按照图 1.3-3 中的程序框图给出的步骤,求
4 f ( x? ) 0 8. 3 5 x ? 0 4 .1 x ?

0. 1 36 ? x

2 0 .3 3 ?x

0. ?5 x

1

当 x ? 5 时的值。 3、用“除 k 取余法”将十进制数 2008 转化为二进制数和八进制数。 阅读与思考: 割圆术

“割圆术”是求 圆周率 的一种算法,圆周率在解决有关 圆 和 球 的计算问题中是非常重要的 一个 常数 。在古代,各国数学家都把求出 ? 的尽量准确的近似值作为一个重要课题。 历史上对于 ? 的研究,在一定程度上反映了一个时代或地区的数学和计算技术发展的水平。 我国最早采用的 ? 值为 3 ,即所谓“径一周三” ( 直径 为 1, 周长 为 3) 。 做法是将圆内接 正六边形 周长作为圆的 周长 ,从而求出圆周率。 263 年左右,我国数学家刘徽发现当圆内接正多边形的边数无限增加时,多边形面积可无限逼近圆 面积,即所谓“割之弥细,所失弥少,割之又割,以至于不可割,则与圆周合体而无所失矣” 。另一方面, 这些圆内接正多边形每边外有一 余径 ,用边长乘以 余径 ,加到正多边形的面积上,则大于圆的面积,
35

这样就可以得到圆面积的 上限 和 下限 。于是,刘徽采用了以直代曲、无限趋近、 “内外夹逼”的思想, 创立了“割圆术” 。 “割圆术”的具体操作步骤是这样的: 第一步,从半径为 1 尺的圆内接正六边形开始,计算它的面积 S6 第二步,逐步加倍圆内接正多边形的边数,分别计算圆内接正十二边形、正二十四边形、正四十八边 形??的面积,到一定的边数(设为 2m)为止,得到一列递增的数 S6 、 S12 、 S 24 、?、 S2 m 第三步,在第二步中各正 n 边形每边外作一高为余径(如图 1 中 AB 所示)的矩形,把其面积

2( S2m ? Sm ) 与 相 应 的 正 n 边 形 的 面 积 Sn 相 加 , 得 Sn ? 2( S2m ? Sm ) ; 这 样 又 得 到 一 列 递 增 数
, S24 ? (S24 ? S12 ) , S48 ? (S48 ? S24 ) ,?, S2m ? ( S2m ? Sm ) S1 2? (S1 2? S 6 ) 第四步,有 S2 m < S 圆 < S2 m ?( S2m ? Sm ) ,估计 S 圆的近似值,即圆周率的近似值。 “割圆术”从理论上能够把 ? 的值计算到任意精度,刘徽一直计算到 192 边形,得到了圆周率精确到 小数点后两位的近似值 3.14,化成分数为

157 ,这就是著名的“徽率” 。我国南北朝时期的数学家祖冲之 50

继承并发展了刘徽的“割圆术” ,求得 ? 的范围为 3.1415926 ? ? ? 3.1415927 。 后人曾推算,若单纯使用“割圆术” ,需要计算到圆内接正 12288 边形,才能得到这样精确的结果。 这不但是当时最精密的圆周率,而且在世界上处于领先地位达 1000 多年。 现在,我们可以利用计算机来计算圆周率了,为此,我们先来分析一下圆内接正六边形、正十二边形、 正二十四边形??的面积之间的关系,寻求它们的递增规律。

如图 1,设圆的半径为 1,弦心距为 hn ;正 n 边形的边长为 xn ,面积为 Sn ,由勾股定理,

?x ? 得 hn = 1- ? n ? , ? 2 ?
容易知道 x6 ? 1

2

?x ? 2 (1-hn) x2 n = ? n ? ? 2 ? ?

2

(n ? 6 )

观察图 1,不难发现,正 2n 边形的面积等于正 n 边行的面积加上 n 个等腰三角形的面积, 即

S2n ? Sn ? n

1 x ( 1 ? hn ) 2 n

(n ? 6 )

36

利用这个递推公式,我们可以得到: 正六边形的面积 S6 ? 6 ? 3 4 正十二边形的面积 S12 ? 正二十四边形的面积 S 24 ? ?? 由于圆的半径是 1,所以随着 n 的增大, S 2 n 的值不断趋近于 ? 。 我们已经知道,递推公式可以用循环结构来表达,因此,上述步骤可以写成如下的程序。 INPUT “n=”; n i=6 x=1 s=6*SQR(3)/4 WHILE i<=n/2
∧ h=SQR(1-(x/2) 2)

图1

在这个程序中,n 的输入值满足什么条件?

s=s+i*x*(1-h)/2
∧ ∧ x=SQR((x/2) 2+(1-h) 2)

i=2*i WEND PRINT n, s END 你能进一步完善这个程序,把“割圆术”编成计算机程序吗? 随着计算机计算速度的高速发展,到 1973 年,人们已把圆周率算到了小数点后 100 万位,1989 年突 破了 10 亿位大关,1999 年超过了 2061 亿位。 现在,数学家们所关心的问题,已不是如何打破纪录,酸菜更高精度的 ? ,而是如何在算法上取得突 破,让计算机更加有效地计算 ? 值。 目前,在几何、微积分和概率领域,都有求圆周率的近似值的算法。有兴趣的同学可以查找相关资料, 或在互联网上搜索相关算法。

37

习题 1.3 A 组 1、用辗转相除法求下列两数的最大公约数,并用更相减损术检验你的结果 ( l ) 228, 1995 ( 2 ) 5280, 12155 . 2、用秦九韶算法求多项式

f ( x ) ? 7 x7 ? 6 x6 ? 5 x5 ? 4 x4 ? 3 x 3 ? 2 x 2 ? x
3、完成下列进位制之间的转化: (1) 10212( 3 ) ? (3) 2376( 8 ) ?
( 10 )

当 x ? 3 时的值.



(2) 412( 5 ) ? (4) 119( 10 ) ?

(7)

( 10 ) ;

(6)

4、根据阅读与思考“割圆术”中的程序画出程序框图, 习题 1.3 B 组 1、某班有 45 名学生,设计一个算法,输人姆个学生的数学纯碱后,分别统计在区间 0 , 60

?

? ?60,80?

? 80,100?

内的成绩的个数,用自然语言描述算法步骤,可用 a ( i )表示第 i 个学生的成绩。

2、更相减损术、秦九韶算法和割圆术都是中国古代数学中的优秀算法,查找资料,搜集其他中国古代数 学中的算法.


一、本章知识结构



二、回顾与思考 1、算法, 是我们既熟悉又陌生的,而且非常有用,在计算机科学和数学领域中都占据着重要地位。 算法的基本思想在我吗的日常生活中是很有用的,学习算法对于发展我们有条理的思考与表达能力,提高 我们的逻辑思维能力也是很有帮助的。通过本章的学习,请你说一说算法的涵义是什么,它有什么特点, 举出几个蕴涵某种算法的问题,并谈一谈学习算法的体会。 2、算法的三种基本逻辑结构是什么?你能用相应的程序框图表达吗? 3、我们可以用自然语言叙述算法,也可以用程序框图表示算法,还可以通过算法语句编写程序使
38

计算机执行算法。自然语言描述的算法步骤、程序框图和程序是不同形式的算法,体现了算法逐渐“精确” 的过程。请你说一说完成一个算法的基本步骤。 4、本章介绍了 3 个典型的算法案例,想一想它们各蕴涵了怎样的算法.各举一个应用这 3 个算法的 例子.

复习参考题 A组 1、画程序框图,对于输入的 x 值,输出相应的 y 值:

(1)

?0 ? y ? ?1 ?x ?

( x ? 0) (0 ? x ? 1) (x ? 1 )

(2)

? ( x ? 2 )2 ? y ? ?4 ? 2 ?( x ? 2 )

( x ? 0) ( x ? 0) ( x ? 0)

2、把你画出的求解二元一次方程组的程序框图转化为程序语句. 3、某市固定电话(市话)的收费标准为:3 分钟之内(包括 3 分钟)收取 0.20 元;超过 3 分钟,每分钟 (不足一分钟.按一分钟计算)按 0.10 元收费.设计一个算法.根据通话时间计算话费. 4、对任意正整数 n,设计一个程序框图求 S ? 1 ?

1 1 1 ? ? ... ? 的值,并写出程序。 2 3 n

5、一个球从 100m 高处自由落下,每次着地后又跳回到原高度的一半再落下,编写程序,求当它第 10 次 着地时, (1)向下的运动共经过多少米? (2)第 10 次着地后反弹多高? (3)全程共经过多少米?

B组 1、编写程序.将用户输入的正整数转换成相应的星期值输出.如用户输入 3 ,则输出 Wednesday; 用户输入 0,则输出 Sunday。如果用户输入的大于 6 .则用这个数除以 7 所得的余效进行上述操作.
39

2、画出程序框图,用二分法求方程 1.3 x ? 26.013 x ? 0.975 x ? 19.50975 ? 0 在 ( 20 , 21 ) 之间的近似
3 2

根(精确度为 0.005) 3、设计一个算法,判断一个正的 n(n>2 ) 位数是不是回文数,用自然语言描述算法步骤. 回文数是指从左到右读与从右到左读都是一样的正整数。如 121,676, 94249 等。

40


人教版高中数学必修三第一章算法初步测试卷

人教版高中数学必修三第一章算法初步测试卷_高一数学_数学_高中教育_教育专区。高中数学必修三第一章测试卷 (时间 90 分钟,满分 120 分) 一、选择题(本大题共...

人教版必修3数学第一章算法初步练习题及答案

人教版必修3数学第一章算法初步练习题及答案_数学_高中教育_教育专区 暂无评价|0人阅读|0次下载人教版必修3数学第一章算法初步练习题及答案_数学_高中教育_教育...

必修三第一章《算法初步》

必修三第一章算法初步》_数学_高中教育_教育专区...第一章 算法初步章教材分析 算法是数学及其应用...在小学, 我们学过求两个正整数的最大公约数的方法...

人教版高中数学A版必修三第一章算法初步导学案

人教版高中数学A版必修三第一章算法初步导学案_数学_高中教育_教育专区。高中数学...【学习难点】写出解决一类问题的算法. 【学习过程】 一、自主学习(阅读课本 2...

必修3第一章《算法初步》训练题(含答案)

必修3第一章算法初步》训练题(含答案)_数学_高中教育_教育专区。必修三算法初步题 必修③第一章算法初步》练习题一、选择题: 1.下面对算法描述正确的一项...

高中数学 第一章 算法初步 教案新 新人教A版必修3

高中数学 第一章 算法初步 教案新 新人教A版必修3_高一数学_数学_高中教育_教育...例 5 课本上的例 1 上述两个算法都涉及到了“遍历”算法思想。 说明:在这...

必修三第一章算法初步练习题及解析

必修三第一章算法初步练习题及解析_高二数学_数学_高中教育_教育专区。高中数学必修三第一章算法初步练习题及解析 一.选择题(共 21 小题) 1. (2015?重庆)...

数学必修3第一章算法初步单元检测题及答案

数学必修3第一章算法初步单元检测题及答案_数学_高中教育_教育专区。数学必修3第123章单元检测题及答案 第一章一、选择题. 算法初步 ). 1.看下面的四段话,...

必修3,第一章,算法初步

必修3,第一章,算法初步_其它课程_高中教育_教育专区。必修 3,第一章,算法初步一.选择题(共 32 小题) 1. 阅读程序框图, 如果输出的函数值在区间[1, 3]上...

必修3第一章算法初步全章知识点例题练习章节测试

必修3第一章算法初步全章知识点例题练习章节测试_高一数学_数学_高中教育_教育专区。知识点例题练习和全面 第一章:算法初步教学目标 1、理解算法的概念、特征,熟悉...

更多相关标签