第一章算法初步 第一章 算法( algorith●)这个词出现于12世纪,指的是用 据说英文 gorithm来源于 阿拉伯数字进行算术运算的过程.在数学中,现代意义上的 阿拉伯数学家花拉 算法”通常是指可以用计算机来解决的某一类问题的程序 米的拉丁译名 或步骤,这些程序或步骤必須是明确和有效的·而且能够在 有限步之内完成 按照这样的理解,我们可以设计出很多具体数学问题的 算法.下面看几个例子 例1任意给定一个大于1的整数n,试设计一个程序 命只能被】和J或步骤对n是否为质数●做出判定 自身整除的大于1 的整数叫质数 算法分析:根据质数的定义,很容易设计出下面的 步骤 第一步:判断n是否等于2.若n=2,则n是质数;若 n>2,则执行第二步 第二步:依次从2~(n-1)检验是不是n的因数,即 整除n的数.若有这样的数,则n不是质数;若没有这样的 数,则n是质数 这是判断一个大于1的整数n是否为质数的最基本 例2用二分法设计一个求方程x2-2=0的近似根的 算法 算法分析:回顾二分法解方程的过程,并假设所求近似 根与精确解的差的绝对值不超过0.005,则不难设计出以下 步骤 第一步:令f(x)=x2-2.因为f(1)<0.f(2)>0 所以设n=1,x2=2 第二步;令m=+,判断f(m)是否为0.若是,则 m为所求;若否,则继续判断f(x1)·f(m)大于0还是小 第三步:若f(x1)·f(m)>0.则令x1=m;否则,令 第四步:判断|x1-x21<0.005是否成立?若是,则 x1、x?之间的任意取值均为满足条件的近似根;若否,则 画3
CHAPTER 通离中课程标准实拉教科书数攣3 返回第二步 按照以上步骤,我们将依次得到表1-1和图1.1-1 表1-1 1.25 1.375章1475 0.0625 1.40625 4375 0.03125 玉25,山4218500562 1.41406251,421875 0.0078125 1440625画412987aoo25 于是,开区间(1,4140625,1.41796875)中的实数都是 满足假设条件的原方程的近似根 际上,上述步骤就是在求2的近似值 计算机解决任何问题都要依赖于算法。只有将解决问题 的过程分解为若干个明确的步骤,即算法,并用计算机能够 接受的“语言”准确地描述出来,计算机才能够解决问题 你能举出更多的算法的例子 般的解决问题的过程比较,你 认为算法最重要的特征是什么? 练习 任意给定一个正实数,设计一个算法求以这个数为半径的园的面积 2.任意给定一个大于1的正整数n,设计一个算法求出n的所有因数
5第一章算法初步 第一章 112程序框图 算法可以用自然语言来描述,但为了使算法的程序或步 骤表达得更为直观,我们更经常地用图形方式来表示它.例 如,1.1.1节例1的算法步骤就可以用以下形式(图1.1-2) 来表达 0n是大于1 的整数 整 0□h n是质数
CHAPTER 通高中课程标准实验教科书戴学3 框图中的自ag是用来记录判断结果的,如果最后fag的 值为1,则n是质数,如果fag的值为0.则n不是质数 1.框图中的d有什么作用?d=d+1是怎么回事儿? 2.通过以上算法的两种不同表达方式的比较,你觉得用程序框图来 表达算法有哪些特点? 程序框图又称流程图,是一种用规定的图形、指向线及 文字说明来准确、直观地表示算法的图形 通常,程序框图由程序框和流程线组成,一个或几个程 序框的组合表示算法中的一个步骤;流程线是方向箭头,按 照算法进行的顺序将程序框连接起米,表12列出了儿个基 本的程序框和它们各自表示的功能 事框名称 终端框(起止框)表示一个算法的起始和结束 输入,输出框表示一个算法输人和输出的 处理框(执行框)赋值,计算 判断某一条件是否成立,成立 判断框 」在出口处标明“是”或 Y”;不成立时标明“否”或 用程序框图来表达算法,算法的基本逻辑结构展现得非 常清楚.从上面的程序框图中,不难看出以下三种不同的基 本逻辑结构 6
第一算活初步 第一章 是质数 不是质数 图1.13 图1.1-4 d整除n? d=d+1 图1.15 这三种结构分别称为顺序结构、条件结构和循环结构 尽管不同的算法千差万别.但都是由这三种基本的逻辑结构 构成的 阝3, 你能说出这三种基本的逻辑结构的特点吗?条件结构与循环结构有 什么区别和联系? 0已知三角形三边 (1)顺序结构 边长分别为a、b、c 很明显顺序结构是由若干个依次执行的处理步 骤组成的,这是任何一个算法都离不开的基本结 √p(p-a)(p-b)(p- 其中p=+2 例3已知一个三角形的三边边长分别为2,3, 公人“,利用海伦秦九公式设计一个算法,求出它的 国量7