1.1.1算法的概念1.ppt
算法内容的设计与安排算法内容的设计与安排算法是计算机工作的算法是计算机工作的基础，算法的发展推基础，算法的发展推动了计算机的发展动了计算机的发展创设情境创设情境 给出定义给出定义问题问题1 1：有一个农夫带一条：有一个农夫带一条狼狼、一只、一只羊羊和一筐和一筐白菜白菜过河。如果没有农夫看管，过河。如果没有农夫看管，则狼要吃羊，羊要吃白菜。但是船很小，则狼要吃羊，羊要吃白菜。但是船很小，只够农夫带一样东西过河。问农夫该如只够农夫带一样东西过河。问农夫该如何解此难题？何解此难题？解决步骤：解决步骤：1、带羊到对岸，返回；、带羊到对岸，返回；2、带菜到对岸，并把羊带回；、带菜到对岸，并把羊带回；3、带狼到对岸，返回；、带狼到对岸，返回；4、带羊到对岸。、带羊到对岸。我有2条腿一个脑袋我有4条腿一个脑袋问题问题2：“一群小兔一群小鸡，两群一群小兔一群小鸡，两群合合 到一群中，腿一共有到一群中，腿一共有48条，脑条，脑 袋共有袋共有17个，问一共有多少小个，问一共有多少小 鸡？多少小兔？鸡？多少小兔？解决步骤解决步骤：1.设未知数：设未知数：设有设有x只小鸡，只小鸡，y只小兔只小兔 X+Y=172.列方程组；列方程组；2X+4Y=483.解方程组；解方程组；X=10 y=74.得到实际问题的答案。得到实际问题的答案。小鸡小鸡10只，小兔只，小兔7只只你能写出求解这个方程组的你能写出求解这个方程组的步骤步骤吗？吗？2X+4Y=48 (1)X+Y=17 (2)什么是算法？什么是算法？探究探究1：写出求解下列方程组的：写出求解下列方程组的步骤步骤。算法的含义（广义）完成某项工作的方法和步骤（广义）完成某项工作的方法和步骤（广义）完成某项工作的方法和步骤（广义）完成某项工作的方法和步骤（现代）可以用计算机来解决的一类问题的（现代）可以用计算机来解决的一类问题的程序程序和和 步骤步骤.（数学中）算法通常是指按照一定规则解决（数学中）算法通常是指按照一定规则解决 某一类问题的某一类问题的明确和有限明确和有限的的步骤步骤.l菜谱是做菜的算法；菜谱是做菜的算法；l歌谱是一首歌曲的算法；歌谱是一首歌曲的算法；l空调说明书是空调使用的算法等空调说明书是空调使用的算法等算法的基本特性算法的基本特性明确性：明确性：算法的每一个步骤都是确切的，能算法的每一个步骤都是确切的，能有效执行且得到确定的结果，不能模棱两可。有效执行且得到确定的结果，不能模棱两可。顺顺序序性性：算算法法从从初初始始步步骤骤开开始始，分分为为若若干干明明确确的的步步骤骤，每每一一步步都都只只能能有有一一个个确确定定的的继继续续，只只有有执执行行完完前前一一步步才才能能进进入入到到后后一一步步，并且每一步都确定无误后，才能解决问题。并且每一步都确定无误后，才能解决问题。有限性：有限性：算法应在有限步内结束，并给出算法应在有限步内结束，并给出计算结果。计算结果。不不唯唯一一性性：求求解解某某一一个个问问题题的的算算法法不不一一定定是是唯唯一一的的，对对于于同同一一个个问问题题可可以以有有不不同同的的算算法。法。普遍性：普遍性：很多具体的问题，都可以设计很多具体的问题，都可以设计合理的算法去解决某一类问题，如计算器计合理的算法去解决某一类问题，如计算器计算都要经过有限的、事先设计好的步骤加以算都要经过有限的、事先设计好的步骤加以解决。解决。1、写出的算法必须能解决一类问题，并且能够、写出的算法必须能解决一类问题，并且能够重复使用。重复使用。2、要使算法尽量简单，步骤尽量少。、要使算法尽量简单，步骤尽量少。3、算法的过程要一步步执行，每一步都准确无、算法的过程要一步步执行，每一步都准确无误，且在有限步后能得出结果。误，且在有限步后能得出结果。4、必须有输入和输出窗口（语句）。、必须有输入和输出窗口（语句）。算法的设计要求算法的设计要求例例1 1、（1 1）设计一个算法，判断）设计一个算法，判断7 7是否为质数。是否为质数。（2 2）设计一个算法，判断）设计一个算法，判断3535是否为质数。是否为质数。算法（算法（1 1）第一步，用第一步，用2 2除除7 7，得到余数，得到余数1 1。因为余数不。因为余数不为为0 0，所以，所以2 2不能整除不能整除7 7。第二步，用第二步，用3 3除除7 7，得到余数，得到余数1 1。因为余数不。因为余数不为为0 0，所以，所以3 3不能整除不能整除7 7。第三步，用第三步，用4 4除除7 7，得到余数，得到余数3 3。因为余数不。因为余数不为为0 0，所以，所以4 4不能整除不能整除7 7。第四步，用第四步，用5 5除除7 7，得到余数，得到余数2 2。因为余数。因为余数不为不为0 0，所以，所以5 5不能整除不能整除7 7。第五步，用第五步，用6 6除除7 7，得到余数，得到余数1 1。因为余数不。因为余数不为为0 0，所以，所以6 6不能整除不能整除7 7。因此，。因此，7 7是质数是质数例例1 1、（1 1）设计一个算法，判断）设计一个算法，判断7 7是否为质数。是否为质数。（2 2）设计一个算法，判断）设计一个算法，判断3535是否为质数。是否为质数。算法（算法（2 2）第一步，用第一步，用2 2除除3535，得到余数，得到余数1 1。因为余数。因为余数不为不为0 0，所以，所以2 2不能整除不能整除3535。第二步，用第二步，用3 3除除3535，得到余数，得到余数2 2。因为余数。因为余数不为不为0 0，所以，所以3 3不能整除不能整除3535。第三步，用第三步，用4 4除除3535，得到余数，得到余数3 3。因为余数。因为余数不为不为0 0，所以，所以4 4不能整除不能整除3535。第四步，用第四步，用5 5除除3535，得到余数，得到余数0 0。因为余数。因为余数为为0 0，所以，所以5 5能整除能整除3535。因此，。因此，3535不是质数不是质数你能写出你能写出“判断整数判断整数n(nn(n2)2)是否为质数是否为质数”的算法吗？的算法吗？第一步，给定大于第一步，给定大于2 2的整数的整数n n。第二步，令第二步，令i=2.i=2.第三步，用第三步，用i i除除n n，得到余数，得到余数r r。判断余数。判断余数r r是否是否为为0 0，若是则，若是则n n不是质数，结束算法；否则，将不是质数，结束算法；否则，将i i的的值增加值增加1 1，仍用，仍用i i表示。表示。第四步，判断第四步，判断i i是否大于是否大于(n-1)(n-1)，若是，则，若是，则n n是是质数；否则，返回第三步质数；否则，返回第三步 算法分析：对于任意的整数n(n2),若用i表示2-（n-1)中的任意整数，则“判断n是否为质数“的算法包含下面的重复操作：用i除n，得到余数r，判断余数r是否为0，若是，则n不是质数；否则，将i的值增加1，再执行同样的操作这个操作一直要进行到i的值等于(n-1)为止。因此，”判断i是否为质数“的算法可以写成：例例2用二分法设计一个求方程用二分法设计一个求方程 的近似正根的算法，精确度的近似正根的算法，精确度0.05。算法分析：算法分析：令令f(x)=x2-2=0(x0)，则方程，则方程x2-2=0的解就是函数的解就是函数f(x)的零点。的零点。“二分法二分法”的基本思想是：把函数的基本思想是：把函数f(x)的零点所在的零点所在的区间的区间a,b(满足满足f(a)f(b)0)“一分为二一分为二”。得到。得到a,m和和m,b。根据。根据“f(a)f(m)0”是否成立，取是否成立，取出零点所在的区间出零点所在的区间a,m或或m,b，仍记为，仍记为a,b，对所，对所得的区间得的区间a,b重复上述步骤，直到包含零点的区间重复上述步骤，直到包含零点的区间a,b“足够小足够小“，则，则a,b内的数可以作为方程的近内的数可以作为方程的近似解。似解。1.jpg例例2用二分法设计一个求方程用二分法设计一个求方程 的近似正根的算法的近似正根的算法解解课后练习1、任意给定一个正实数，设计一个算法求以这个数为、任意给定一个正实数，设计一个算法求以这个数为半径的圆的面积。半径的圆的面积。算法步骤：第一步：输入任意一个正实数r。第二步：计算以r为半径的圆的面积 。第三步：输出圆的面积S。2、任意给定一个大于、任意给定一个大于1的正整数的正整数n，设计一个算法，设计一个算法求出求出n的所有因数。的所有因数。算法步骤：第一步：依次以2（n-1）为除数去除n，判定余数是否为0，若是，则n是因数；若不是，则不是n的因数。第二步：在n的因数中加入1 和n。第三步：输出n的所有因数。作业：作业：1.必做题：课本第必做题：课本第5页练习页练习1、22.选做题：写出用二分法求方程选做题：写出用二分法求方程x2-5=0的近似解的一个算法的近似解的一个算法（精确到（精确到0.01）
