算法的概念(1)

1、算法的概念一、引入一、引入 问题二：在实数范围内如何求解实系数一问题二：在实数范围内如何求解实系数一元二次方程元二次方程 的解？的解？ 问题一：如何把大象装进冰箱？问题一：如何把大象装进冰箱？20(0)axbxca算法的含义算法的含义对于一类有待求解的问题，如果建立了一对于一类有待求解的问题，如果建立了一套通用的求解方法，按部就班地实施就能套通用的求解方法，按部就班地实施就能使问题得以解决，那么这套解题方法就是使问题得以解决，那么这套解题方法就是求解该类问题的一种算法。求解该类问题的一种算法。简单而言，就是对一类问题的简单而言，就是对一类问题的机械的、统机械的、统一的一的求解方法称为算法。求解

2、方法称为算法。n蓝墨水瓶里错装了红墨水，红墨水瓶里错蓝墨水瓶里错装了红墨水，红墨水瓶里错装了蓝墨水，请你设计一个算法将它们改装了蓝墨水，请你设计一个算法将它们改正过来。正过来。 想一想想一想n有人对哥德巴赫猜想有人对哥德巴赫猜想“任何大于任何大于4的偶数都能写的偶数都能写成两个奇质数之和成两个奇质数之和”设计了如下操作步骤：设计了如下操作步骤：n第一步：检验第一步：检验6=3+3n第二步：检验第二步：检验8=3+5n第三步：检验第三步：检验10=5+5n请问，按照这种程序利用计算机无穷地进行下去，请问，按照这种程序利用计算机无穷地进行下去，能够证明猜想的正确性吗？能够证明猜想的正确性吗？n这是

3、一种算法吗？这是一种算法吗？想一想想一想算法是这样的：算法是这样的：n找到了某种算法，是指使用一系列运算规找到了某种算法，是指使用一系列运算规则能在则能在有限步骤有限步骤内求解某类问题，其中的内求解某类问题，其中的每条规则必须是每条规则必须是明确定义的、可行的明确定义的、可行的 算法有时被表示成一个算法有时被表示成一个计算公式计算公式,有时被有时被表示为一系列表示为一系列可执行的步骤可执行的步骤.二、例题选讲二、例题选讲n例例1 设计算法：求设计算法：求1+2+3+4+5 解法一：解法一： 求求1+21+2，得到，得到3 3； 将得到的将得到的3 3再加再加3 3，得到，得到6 6； 6+46

4、+4得到得到1010； 10+510+5得到得到1515。一共一共4个步骤依次执行个步骤依次执行,都是可行的乘法运算都是可行的乘法运算,各步各步骤前后顺序不能交换骤前后顺序不能交换,这种结构为这种结构为顺序结构顺序结构n例例1 设计算法：求设计算法：求1+2+3+4+5解法二：解法二：可以运用公式可以运用公式1+2+3+n n(n+1)/2 直接计算直接计算取取n=5n=5；运用公式计算运用公式计算n(n+1)/2 ；得到结果得到结果例题选讲例题选讲n例例1 设计算法：求设计算法：求1+2+3+4+5解法三：设计解法三：设计2个变量个变量把把1 1赋给赋给p p，把，把2 2赋给赋给i i；计

5、算计算p+ip+i，结果赋给，结果赋给p p；i+1i+1赋给赋给i i；如果如果i5,i5,返回重新执行；否则，输出返回重新执行；否则，输出p p例题选讲例题选讲P的值就是计算结果的值就是计算结果解法三：设计解法三：设计2个变量个变量把把1 1赋给赋给p p，把，把2 2赋给赋给i i；计算计算p+ip+i，乘积赋给，乘积赋给p p；i+1i+1赋给赋给i i；如果如果i5,i5,返回重新执行返回重新执行；否则，输出；否则，输出p p这种语句叫做算法中的这种语句叫做算法中的条件结构条件结构，它的基本形式是：如果它的基本形式是：如果“条件条件”成立，那么执行指成立，那么执行指令（指令组）令（指

6、令组）A A；如果；如果“条条件件”不成立，那么执行指令不成立，那么执行指令（指令组）（指令组）B B。 反复多次执行反复多次执行步骤，这种重复执步骤，这种重复执行同样指令的结构叫做算法中的行同样指令的结构叫做算法中的循环结构循环结构。 其中变量其中变量i的数值决定循环的的数值决定循环的“继续继续”还还是是“结束结束”，故称，故称i i为为循环变量循环变量，称重复执，称重复执行的指令组为行的指令组为循环体循环体。（1）有限性：有限性： 一个算法必须保证执行有限步后获得结论一个算法必须保证执行有限步后获得结论.算法的特点：算法的特点：（5）每个算法必须有已知信息的输入和运算结果输出每个算法必须有

7、已知信息的输入和运算结果输出.（4）非唯一性：非唯一性：求解某个问题的算法不一定是唯一的，允求解某个问题的算法不一定是唯一的，允许有不同的算法许有不同的算法.（3）可行性：可行性： 前一步是后一步的基础；每一步都是可行的前一步是后一步的基础；每一步都是可行的.（2）确定性：确定性： 每一步操作都有确定意义，不允许产生歧义每一步操作都有确定意义，不允许产生歧义.12-1-21,1,(3),nnnfffffn 例例2 2 对于第对于第7 7章阅读材料中给出的斐波那契数列：章阅读材料中给出的斐波那契数列：20f20.S 计算并输出计算并输出和前和前2020项的和项的和 分析：因为斐波那契数列是以递推

8、形式给出的，所以要逐分析：因为斐波那契数列是以递推形式给出的，所以要逐项计算项计算3420.SSS、 、3420fff、 、和和（1 1）把）把1 1赋予赋予和和，把，把2 2赋予赋予，把，把3 3赋予赋予n.n.1f2f2S12nnnfff 1.nnnSSf （2 2）计算）计算，计算，计算（3 3）把）把 n+1 n+1 赋予赋予 n. n. 20n 20,n 20f20S（4）如果）如果，那么再执行第（，那么再执行第（2）步；如果）步；如果那么输出那么输出和和并结束计算并结束计算. 2 0f2 0S求求和和的一种算法的一种算法. 例题选讲例题选讲n例例3：设计算法，找出三个数：设计算法，

9、找出三个数a,b,c中的最大中的最大数数.n把把a a赋给赋给M M；n如果如果MbMb，则，则b b赋给赋给M M； 如果如果MbMb，则，则M M不变；不变；nMcMc，则，则c c赋给赋给M M； 如果如果McMc，则，则M M不变；不变；例题选讲例题选讲n设计算法，找出五个数设计算法，找出五个数x1,x2,x3,x4,x5中的最中的最大数大数练一练练一练n设计算法，找出任意设计算法，找出任意N个数个数x1,x2,x3,xN中的最大数中的最大数三、小结三、小结n算法的含义算法的含义：一般而言，对一类问题的机械的、一般而言，对一类问题的机械的、统一的求解方法称为算法。统一的求解方法称为算法。n算法的基本思想：探求解决问题的一般性方法，算法的基本思想：探求解决问题的一般性方法，并将解决问题的步骤用具体化