算法的概念

计算机与算法: 在现代社会里，计算机已经成为人 们日常生活和工作不可缺少的工具. 听音乐、看电影、玩游戏、画卡通画 、处理数据…计算机几乎可以是一个 全能的助手，你可以用它来做你想做 的任何事情.那么，计算机是怎样工 作呢？要想弄清楚这个问题，就需要 学习算法.

什么是算法？

问题情境：一个农夫带着一条狼、一头 山羊和一篮蔬菜要过河,但只有一 条小船.乘船时,农夫只能带一样东 西.当农夫在场的时候,这三样东西 相安无事.一旦农夫不在,狼会吃羊, 羊会吃菜.请设计一个方案,使农夫 能安全地将这三样东西带过河.

“鸡兔同笼”是我国隋朝 时期的数学著作《孙子算经》 中的一个有趣而具有深远影响 的问题，从学生熟悉的鸡兔同 笼问题解决引出数学中的算法 问题： 问题1:一个笼子里有一些 鸡和兔，现在知道里面一共35 有个头,94只脚，问鸡和兔各有 多少只？

x y 35 解方程 2 x 4 y 94

(1) (2)(3) (4)

第一步, (1) 2 (2)得： -2 y 24 第二步, 解(3)得： y 12 第三步, (1) 4 (2)得： 第四步, 解(4)得： x 23

2 x 46

x 23 第五步, 得到方程组的解得 y 12

写出一般二元一次方程组的解法步骤. (1) a1 x b1 y c1 a1b2 a2b1 0 (2) a2 x b2 y c2第一步, (1) b2 (2) b 得： 1

a1b2 a2b1 x c1b2 c2b1c1b2 c2b1 第二步,解(3)得 x a1b2 a2b1

(3)

写出一般二元一次方程组的解法步骤. (1) a1 x b1 y c1 a1b2 a2b1 0 (2) a2 x b2 y c2第三步,

a2b1 a1b2 y a2c1 a1c2第四步,解(4)得

(1) a2 (2) a1 得：

(4)

a2c1 a1c2 y a2b1 a1b2

c1b2 c2b1 x a b a b 1 2 2 1 第五步,得到方程组的解为 y a2 c1 a1c2 a2b1 a1b2

广义地说，算法就是做某 一件事的步骤或程序。菜 谱是做菜肴的算法，洗衣 机的使用说明书是操作洗 衣机的算法，

在数学中算法通常指按照一 算法： 定规则 解决某一类问题的明确 和有限的步骤. 现在,算法通常可以编成计算 机程序,让计算机执行并解决问题 .

写出交换两个大小相同的杯子中 的液体 (A 水、 B 酒) 的一个算法. 第一步,找一个大小与A相同的空杯子C. 第二步,将A 中的水倒入C中. 第三步,将B中的酒精倒入A中. 第四步,将C中的水倒入B中,结束.

例1.(1)设计一个算法判断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是质数.

例1.(2)设计一个算法判断35是否为质数 .第一步, 用2除35,得到余数1.因为余数不为0, 所以2不能整除35. 第二步, 用3除35,得到余数2.因为余数不为0, 所以3不能整除35.

第三步, 用4除35,得到余数3.因为余数不为0, 所以4不能整除7. 第四步, 用5除35,得到余数0.因为余数为0, 所以5能整除35.因此，35不是质数.

设计一个算法,判断整数n(n>2)是否为质数? 第一步，给定大于2的整数n。

第二步，令i=2第三步，用i除n,得到余数r。

遍历 法

第四步，判断“r=0”是否成立。 若是，则n不是质 数，结束算法; 否则，将i的值增加1,仍用i表示。

第五步，判断“i>(n-1)”是否成立。 若是，则n不是 质数，结束算法; 否则，返回第三步

例2 用二分法设计一个求方程 x2 – 2 = 0 的近似根的算法。 旧知识回顾 用二分法求函数的零点 ：a b ︱a-b︱1 1 1 1.25 1.375 …… 2 1.5 1.5 1.5 …… + 2 + 2 + 2

0.50.25 0.125

……

1

y x2 2

1

+ 1.5

1

1.25

+ 1.5 + 1.3751.5

1.375

1 1.25

1.5

2

1

1.25

-

+ 2

第一步, 令 f ( x) x 2 .给定精确度d. 第二步, 给定区间[a,b],满足f(a) · f(b)<0.2

第三步, 取中间点 m

a b 2

.

第四步, 若f(a) · f(m) < 0,则含零点的区间为[ a,m]; 否则，含零点的区间为[m, b]. 将新得到的含零点的仍然记为[a,b] .第五步, 判断[a,b]的长度是否小于d或者 f(m)是否等于0. 若是，则m是方程的近似 解;否则，返回第三步.

例3:读下列算法，回答问题： 第一步，令s=0 第二步，令i=1。 第三步，求出s+i,仍用s表示。 第四步，判断i>100是否成立？若是，输出s;若不 是，将i的值增加1,仍用i表示返回第三步。 (1)该算法是解决什么问题的？ (2)最终输出的结果是什么？

练习1.任意给定一个正实数,设计一个算法求以这个数为半径的圆的面积.

第一步:输入任意一个正实数r; 第二步:计算圆的面积: S=πr2;

第三步:输出圆的面积S.

2.任意给定一个大于1 的正整数n,设计一个算 法求出n的所有因数.答案1:第一步：依次以2~(n-1)为除数去除n,检查余数 是否为0,若是,则是n的因数;若不是,则不是n的因数. 第二步：在n的因数中加入1和n. 第三步：输出n的所有因数.答案2:第一步:给定大于1的整数n 第二步:令i=1 第三步:用i除n,得余数r 第四步:判断“ r=0” 是否成立,若是,则i是n的因数,输出i, 第五步:将i的值增加1,仍用i表示. 第六步:判断“i>n结束算法,否则返回第三步.

3、写出求一元二次方程

ax2+bx+c=0 的根的算法.第一步,计算Δ=b2-4ac. 第二步,如

果Δ<0,则原方程无实数解 b , ;否则(Δ≥0)时， x1 2a

b . x2 2a 第三步:输出x1, x2或无实数解的信息.