1.1.1算法的概念(精品).ppt

《1.1.1算法的概念(精品).ppt》由会员分享，可在线阅读，更多相关《1.1.1算法的概念(精品).ppt（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 一个笼子里有一些鸡和兔，现在知道里面一一个笼子里有一些鸡和兔，现在知道里面一共有共有3535个头个头,94,94只脚，问鸡和兔各有多少只？只脚，问鸡和兔各有多少只？第一步第一步:设设有有 只只鸡鸡，只兔只兔第二步：第二步：列方程组列方程组 第四步：第四步：答：笼子里有答：笼子里有2323只鸡，只鸡，1212只兔只兔.第三步：第三步：解方程组得解方程组得用二元一次方程组解应用问题的算法用二元一次方程组解应用问题的算法第一步第一步:设设未知数未知数第二步：第二步：列方程组列方程组 第四步：第四步：作答作答第三步：第三步：解方程组解方程组 你能写出求解二元一次方程组：你能写出求解二元一次方程组：的

2、步骤吗？的步骤吗？解：解：第一步第一步：（2）（1）2得得2y=24;(3)第二步：第二步：解（解（3）得）得 y=12；第三步第三步：将将 y=12 代入代入(1),得得 x=23。第四步第四步：得到方程组的解为得到方程组的解为 。y=12x=23解：解：第一步第一步：2 2得得 2y=24 2y=24；(3)(3)第二步：第二步：解解得得 y=12；第三步：第三步：4-4-得得 2x=46 2x=46；第五步：第五步：得到方程组的解为得到方程组的解为 。y=12x=23第四步：第四步：解解得得 x=23x=23；你能写出求解二元一次方程组：你能写出求解二元一次方程组：的步骤吗？的步骤吗？解

3、：解：第一步第一步：得得 第二步：第二步：解解得得第三步第三步：得得第四步第四步：解解得得第五步：第五步：得到方程得到方程组组的解的解为为 。第二步：第二步：解（解（3）得）得 y=12；第三步第三步：将将 y=12 代入代入(1),得得 x=23。第四步第四步：得到方程组的解为得到方程组的解为 。y=12x=23第一步第一步：（2）（1）2得得2y=24;(3)第一步第一步:设有设有 只鸡，只鸡，只兔只兔第二步：第二步：列方程组列方程组 第四步：第四步：答：笼子里有鸡答：笼子里有鸡2323只，兔只，兔1212只只.第三步：第三步：解方程组得解方程组得第一步第一步：得得 第二步：第二步：解解得

4、得第三步第三步：得得第四步第四步：解解得得第五步：第五步：得到方程得到方程组组的解的解为为 第一步第一步:设设未知数未知数第二步：第二步：列方程组列方程组 第四步：第四步：作答作答第三步：第三步：解方程组解方程组 算法通常是指按照一定规则解决某一类问题的算法通常是指按照一定规则解决某一类问题的明确和有限的步骤明确和有限的步骤 算法（算法（algorithmalgorithm）的概念）的概念 现在，算法通常可以编成计算机程序，现在，算法通常可以编成计算机程序，让计算机执行并解决问题让计算机执行并解决问题到底什么是算法？到底什么是算法？第二步：第二步：计算计算 你能写出求解二元一次方程组：你能写出

5、求解二元一次方程组：的步骤吗？的步骤吗？解：解：第一步第一步：得得 第二步：第二步：解解得得第三步第三步：得得第四步第四步：解解得得第五步：第五步：得到方程得到方程组组的解的解为为 。第三步第三步：计算计算第四步：第四步：输输出出 x,y。解：解：第一步第一步:输入输入思考思考1:1:如果让计算机判断如果让计算机判断7 7是否为质数，如是否为质数，如何设计算法步骤？何设计算法步骤？第一步：第一步：用用2 2除除7 7，得到余数，得到余数1,1,因为余数不为因为余数不为0 0，所以，所以2 2不能整除不能整除7.7.第四步第四步：用用5 5除除7 7，得到余数，得到余数2,2,因为余数不为因为余

6、数不为0 0，所以，所以5 5不能整除不能整除7.7.第五步：第五步：用用6 6除除7 7，得到余数，得到余数1,1,因为余数不为因为余数不为0 0，所以，所以6 6不能整除不能整除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.因此，因此，7 7是质数是质数.第二步：第二步：用用3 3除除7 7，得到余数，得到余数1,1,因为余数不为因为余数不为0 0，所以，所以

7、3 3不能整除不能整除7.7.第二步：第二步：用用3 3除除3535，得到余数，得到余数2 2,因为余数不为因为余数不为0 0，所以，所以3 3不能整除不能整除3535.思考思考1:1:如果让计算机判断如果让计算机判断7 7 是否为质数，如是否为质数，如何设计算法步骤？何设计算法步骤？第一步：第一步：用用2 2除除7 7，得到余数，得到余数1,1,因为余数不为因为余数不为0 0，所以，所以2 2不能整除不能整除7.7.第四步第四步：用用5 5除除7 7，得到余数，得到余数2,2,因为余数不为因为余数不为0 0，所以，所以5 5不能整除不能整除7.7.第五步：第五步：用用6 6除除7 7，得到余

8、数，得到余数1,1,因为余数不为因为余数不为0 0，所以，所以6 6不能整除不能整除7.7.第三步：第三步：用用4 4除除7 7，得到余数，得到余数3,3,因为余数不为因为余数不为0 0，所以，所以4 4不能整除不能整除7.7.因此，因此，7 7是质数是质数.思考思考2:2:如果让计算机判断如果让计算机判断3535是否为质数，如是否为质数，如何设计算法步骤？何设计算法步骤？第一步：第一步：用用2 2除除3535，得到余数，得到余数1 1,因为余数不为因为余数不为0 0，所以，所以2 2不能整除不能整除3535.第三步：第三步：用用4 4除除3535，得到余数，得到余数3 3,因为余数不为因为余

9、数不为0 0，所以，所以4 4不能整除不能整除3535.第四步第四步：用用5 5除除3535，得到余数，得到余数0 0,因为余数为因为余数为0 0，所以，所以5 5能整除能整除3535.因此，因此，3535不是质数不是质数.思考：思考：判断判断7 7是否是质数的算法和判是否是质数的算法和判断断3535是否是质数的算法有是否是质数的算法有何异何异同？同？思考思考3:3:如果让计算机判断如果让计算机判断8989是否为质数，是否为质数，如何设计算法步骤？如何设计算法步骤？第一步第一步：用用2 2除除8989，得到余数，得到余数1 1,因为余数不为因为余数不为0 0，所以，所以2 2不能整除不能整除8

10、9.89.第二步：第二步：用用3 3除除8989，得到余数，得到余数2 2,因为余数不为因为余数不为0 0，所以，所以3 3不能整除不能整除8989.第三步第三步：用用4 4除除8989，得到余数，得到余数1 1,因为余数不为因为余数不为0 0，所以，所以4 4不能整除不能整除8989.第八十七步第八十七步：用用8888除除8989，得到余数，得到余数1 1,因为余数不为因为余数不为0 0，所以，所以8888不能不能整除整除8989.因此，因此，8989是质数是质数.思考思考4:4:每一步都用一个数去除每一步都用一个数去除8989求余数，每次得到的求余数，每次得到的余数都不为余数都不为0 0，

11、除数是变化的，下一步的除数比上一步，除数是变化的，下一步的除数比上一步的除数增加的除数增加1 1，这些步骤基本是重复操作，共有，这些步骤基本是重复操作，共有8787个步个步骤，除数从骤，除数从2 2开始一直到开始一直到8888停止。停止。思考思考4:4:如果让计算机判断如果让计算机判断8989是否为质数，如是否为质数，如何设计算法步骤？何设计算法步骤？你能根据这样的规律，设计一个你能根据这样的规律，设计一个“判断判断8989是否为质数是否为质数”的算法步骤吗？的算法步骤吗？令令i=2i=2；第一步第一步：判断判断“i i8888”是否成立？若是，是否成立？若是，则则8989是质数，结束算法；否

12、则，是质数，结束算法；否则，返回执行第二步返回执行第二步.第四步：第四步：用用i i除除8989，得到余数，得到余数r r，因为，因为r r0 0，所以所以i i不能整除不能整除8989；第二步：第二步：将将i+1i+1仍用仍用i i表示表示第三步第三步：若不是执行第二步若不是执行第二步再继续重复这样的操作再继续重复这样的操作思考思考5:5:判断一个大于判断一个大于2 2的整数的整数n n是否为质数的是否为质数的算法步骤如何设计？算法步骤如何设计？判断判断“i i(n-1n-1)”是否成立？若是否成立？若是，则是，则8989是质数，结束算法；否是质数，结束算法；否则，返回执行第二步则，返回执行

13、第二步.第四步：第四步：判断判断“i(i(n-1n-1)”是否成立，若是否成立，若是，则是，则n n是质数，结束算法；否是质数，结束算法；否则，返回执行第三步则，返回执行第三步.用用i i除除8989，得到余数，得到余数r r，因为，因为r r0 0，所以所以i i不能整除不能整除8989；用用i i除除 n n，得到余数，得到余数r r，因为，因为r r0 0，所以所以i i不能整除不能整除 n n；判断判断“i i8888”是否成立？若是，是否成立？若是，则则8989是质数，结束算法；否则，是质数，结束算法；否则，返回执行第二步返回执行第二步.第四步：第四步：令令i=2i=2；第一步第一步

14、：第二步：第二步：将将i+1i+1仍用仍用i i表示表示第三步第三步：第四步第四步：第一步第一步:给定一个大于给定一个大于2 2的整数的整数n n；判断判断“r=0r=0”是否成立是否成立.若是，则若是，则n n不是质数，结束算法；否则，将不是质数，结束算法；否则，将i i的值增加的值增加1 1，仍用，仍用i i表示；表示；第三步第三步：第二步第二步:第三步第三步:第四步第四步:第五步第五步:你学到了什么？你学到了什么？算法通常是指按照一定规则解决某一类算法通常是指按照一定规则解决某一类问题的明确和有限的步骤问题的明确和有限的步骤 一、算法的概念：一、算法的概念：现在，算法通常可以编成计算机程

15、序，现在，算法通常可以编成计算机程序，让计算机执行并解决问题让计算机执行并解决问题二、算法具有以下重要特征：二、算法具有以下重要特征：（4）普遍性普遍性（1）明确性）明确性（2）有限性有限性三、算法的设计：三、算法的设计：（3）程序性程序性解二元一次方程组的算法解二元一次方程组的算法学习了两个典型的算法案例学习了两个典型的算法案例判断一个大于判断一个大于2正整数是否为质数算法正整数是否为质数算法 在解决问题过程中反复进行的步骤在解决问题过程中反复进行的步骤,要学要学会用循环结构描述会用循环结构描述.用循环结构描述时用循环结构描述时,通常分三个步骤通常分三个步骤:首先要给一个初始值首先要给一个初

16、始值,接接着表达重复做的事情着表达重复做的事情,最后判断终止条件。最后判断终止条件。突破了设计算法过程的一个难点突破了设计算法过程的一个难点例例2 用二分法设计一个求方程用二分法设计一个求方程 x2 2=0 的近似根的算法。的近似根的算法。分析：分析：回顾二分法的解方程的过程，并假设所求近似根回顾二分法的解方程的过程，并假设所求近似根与准确解的差的绝对值不超过与准确解的差的绝对值不超过0.005,则不难设计则不难设计出以下步骤：出以下步骤：第一步：第一步：令令 f(x)=x2-2 ,第二步：第二步：令令m=（a+b)2,判断判断f(m)是否为是否为 0，若是，则，若是，则m为所求，为所求，算法

17、结束，否则继续判断算法结束，否则继续判断 f(a)f(m)大于大于0 还是小于还是小于0；第三步：第三步：若若f(a)f(m)0则令则令a=m,否则，令否则，令b=m；第五步：第五步：判断判断|ab|d是否成立？若是，则是否成立？若是，则a,b之间的任意取之间的任意取值均为满足条件的近似根；若否，则返回第三步。值均为满足条件的近似根；若否，则返回第三步。确定区间确定区间a,b,满足满足f(a)f(b)0第四步：第四步：给定精确度给定精确度d课堂反馈课堂反馈练习练习2 2、写出求写出求1+2+3+n1+2+3+n的一个算法的一个算法练习练习1 1、写出交换两个大小相同的杯子中的写出交换两个大小相同的杯子中的 液体液体(A(A水、水、B B酒酒)的一个算法。的一个算法。练习练习3 3、任意给定一个大于、任意给定一个大于 1 1 的正整数的正整数 n n，设计一个算法求出设计一个算法求出 n n 的所有因数。的所有因数。课堂后作业课堂后作业