1.1.1算法的概念
图片预览
文档简介
课件20张PPT。1.1.1 算法的概念学习目标:
通过分析具体问题过程与步骤,体会算法的思想,了解算法的含义,能用自然语言描述解决具体问题的算法.
学习重点(难点):
通过实例体会算法思想,初步理解算法的含义.
什么是算法呢？假设家中生火泡茶有以下几个步骤：
a.生火 b.将水倒入锅中 c.找茶叶
d.洗茶壶茶碗 e.用开水冲茶
请选出一个最优算法（ ）
A.abcde B.bacde C.cadbe D.dcabe两个大人和两名儿童一起渡河，渡口只有一条小船，一次只能渡过一个大人或两名儿童，他们四人都会划船，但都不会游泳。请你帮他们设计一个渡河方案。什么是算法呢？两个大人和两名儿童一起渡河，渡口只有一条小船，一次只能渡过一个大人或两名儿童，他们四人都会划船，但都不会游泳。请你帮他们设计一个渡河方案。第一步：两个小孩同船渡过河去； 第二步：一个小孩划船回来； 第三步：一个大人独自划船渡过河去； 第五步：两个小孩再同船渡过河去； 第六步：一个小孩划船回来；第七步：余下的一个大人独自划船渡过河去； 第八步：对岸的小孩划船回来； 第九步：两个小孩再同船渡过河去。 解：第四步：对岸的小孩划船回来； 第一步:②-①×2得: 5y=3 ③第二步: 解③得:第三步: 将 代入①,解得 .第四步: 得到方程组的解为写出解第二个方程组的算法：第一步：第二步：第三步：③解③，得 ④将④带入①得变一变第四步：得到方程组的解为算法的概念 算法通常指按照一定规则解决某一类问题的明确和有限的步骤说明:
(1)事实上算法并没有精确化的定义.
(2)算法最重要的特征：
1.有序性 2.确定性 3.有限性 4.可执行性 一：两腿并拢，挺胸抬头三：先迈前腿四：再迈后腿…下面的步骤表述明确吗？你对以下的“算法”如何理解？ 要把大象装冰箱，分几步？答：分三步：第一步：打开冰箱门第二步：把大象装冰箱第三步：关上冰箱门问有人对歌德巴赫猜想“任何大于4的偶数都能写成两个奇质数之和”设计了如下操作步骤：第一步：检验6=3+3第二步：检验8=3+5。。。利用计算机无穷地进行下去！请问，利用这种程序能够证明猜想的正确性吗？第三步：检验10=5+5这是一种算法吗？例题精讲例1:如果让计算机判断7是否为质数，如何设计算法步骤？ 第一步，用2除7，得到余数1,所以2不能整除7.第四步，用5除7，得到余数2,所以5不能整除7. 第五步，用6除7，得到余数1,所以6不能整除7. 第二步，用3除7，得到余数1,所以3不能整除7.第三步，用4除7，得到余数3,所以4不能整除7. 因此，7是质数.例2:如果让计算机判断35是否为质数，如何设计算法步骤？ 第一步，用2除35，得到余数1,所以2不能整除35.第二步，用3除35，得到余数2,所以3不能整除35.第三步，用4除35，得到余数3,所以4不能整除35. 第四步，用5除35，得到余数0,所以5能整除35.因此，35不是质数.思考:整数89是否为质数？如果让计算机判断89是否为质数，按照上述算法需要设计多少个步骤？ 第一步，用2除89，得到余数1,所以2不能整除89.第二步，用3除89，得到余数2,所以3不能整除89.第三步，用4除89，得到余数1,所以4不能整除89.第八十七步，用88除89，得到余数1,所以88不能 整除89.因此，89是质数.…… …… …… ……思考:用2～88逐一去除89求余数，需要87个步骤，这些步骤基本是重复操作，我们可以按下面的思路改进这个算法，减少算法的步骤.（1）用i表示2～88中的任意一个整数，并从2开始取数；（2）用i除89，得到余数r. 若r=0，则89不是质数；若r≠0，将i用i+1替代，再执行同样的操作； （3）这个操作一直进行到i取88为止.你能按照这个思路，设计一个“判断89是否为质数”的算法步骤吗？用i除89，得到余数r； 令i=2； 若r=0，则89不是质数，结束算法；若r≠0，将i用i+1替代； 判断“i>88”是否成立？若是，则89是质数，结束算法；否则，返回第二步. 第一步， 第四步， 第三步， 第二步， 算法设计:一般地，判断一个大于2的整数是否为质数的算法步骤如何设计？ 第一步，给定一个大于2的整数n； 第二步，令i=2； 第三步，用i除n，得到余数r； 第四步，判断“r=0”是否成立.若是，则n不是质数，结束算法；否则，将i的值增加1，仍用i表示； 第五步，判断“i>(n-1)”是否成立，若是， 则n是质数，结束算法；否则，返回第三步. 例2 设函数f(x)的图象是一条连续不断的曲线，写出用“二分法”求方程 f(x)=0的一个近似解的算法. 例题精讲第一步，取函数f(x)，给定精确度d. 第二步，确定区间[a，b]，满足f(a)·f(b)<0. 第五步，判断[a,b]的长度是否小于d或f(m)是否等于0. 若是，则m是方程的近似解；否则，返回第三步.第三步，取区间中点 .第四步，若f(a)·f(m)<0,则含零点的区间为[a,m],否则，含零点的区间为[m，b]. 将新得到的含零点的区间仍记为[a,b];对于方程 ,给定d=0.005.现有有限个实数，怎样从中找出最大值？先假定这些实数中的第一个数为“最大值”。将这些实数中的下一个数与“最大值”比较，如果它大于此“最大值”，这时就假定“最大值”是这个实数。如果还有其他实数，重复第二步。一直到没有可比的数为止，这时假定的“最大值”就是这有限个实数的最大值。第一步:第二步:第三步:第四步:思 考
通过分析具体问题过程与步骤,体会算法的思想,了解算法的含义,能用自然语言描述解决具体问题的算法.
学习重点(难点):
通过实例体会算法思想,初步理解算法的含义.
什么是算法呢？假设家中生火泡茶有以下几个步骤：
a.生火 b.将水倒入锅中 c.找茶叶
d.洗茶壶茶碗 e.用开水冲茶
请选出一个最优算法（ ）
A.abcde B.bacde C.cadbe D.dcabe两个大人和两名儿童一起渡河，渡口只有一条小船，一次只能渡过一个大人或两名儿童，他们四人都会划船，但都不会游泳。请你帮他们设计一个渡河方案。什么是算法呢？两个大人和两名儿童一起渡河，渡口只有一条小船，一次只能渡过一个大人或两名儿童，他们四人都会划船，但都不会游泳。请你帮他们设计一个渡河方案。第一步：两个小孩同船渡过河去； 第二步：一个小孩划船回来； 第三步：一个大人独自划船渡过河去； 第五步：两个小孩再同船渡过河去； 第六步：一个小孩划船回来；第七步：余下的一个大人独自划船渡过河去； 第八步：对岸的小孩划船回来； 第九步：两个小孩再同船渡过河去。 解：第四步：对岸的小孩划船回来； 第一步:②-①×2得: 5y=3 ③第二步: 解③得:第三步: 将 代入①,解得 .第四步: 得到方程组的解为写出解第二个方程组的算法：第一步：第二步：第三步：③解③，得 ④将④带入①得变一变第四步：得到方程组的解为算法的概念 算法通常指按照一定规则解决某一类问题的明确和有限的步骤说明:
(1)事实上算法并没有精确化的定义.
(2)算法最重要的特征：
1.有序性 2.确定性 3.有限性 4.可执行性 一：两腿并拢，挺胸抬头三：先迈前腿四：再迈后腿…下面的步骤表述明确吗？你对以下的“算法”如何理解？ 要把大象装冰箱，分几步？答：分三步：第一步：打开冰箱门第二步：把大象装冰箱第三步：关上冰箱门问有人对歌德巴赫猜想“任何大于4的偶数都能写成两个奇质数之和”设计了如下操作步骤：第一步：检验6=3+3第二步：检验8=3+5。。。利用计算机无穷地进行下去！请问，利用这种程序能够证明猜想的正确性吗？第三步：检验10=5+5这是一种算法吗？例题精讲例1:如果让计算机判断7是否为质数，如何设计算法步骤？ 第一步，用2除7，得到余数1,所以2不能整除7.第四步，用5除7，得到余数2,所以5不能整除7. 第五步，用6除7，得到余数1,所以6不能整除7. 第二步，用3除7，得到余数1,所以3不能整除7.第三步，用4除7，得到余数3,所以4不能整除7. 因此，7是质数.例2:如果让计算机判断35是否为质数，如何设计算法步骤？ 第一步，用2除35，得到余数1,所以2不能整除35.第二步，用3除35，得到余数2,所以3不能整除35.第三步，用4除35，得到余数3,所以4不能整除35. 第四步，用5除35，得到余数0,所以5能整除35.因此，35不是质数.思考:整数89是否为质数？如果让计算机判断89是否为质数，按照上述算法需要设计多少个步骤？ 第一步，用2除89，得到余数1,所以2不能整除89.第二步，用3除89，得到余数2,所以3不能整除89.第三步，用4除89，得到余数1,所以4不能整除89.第八十七步，用88除89，得到余数1,所以88不能 整除89.因此，89是质数.…… …… …… ……思考:用2～88逐一去除89求余数，需要87个步骤，这些步骤基本是重复操作，我们可以按下面的思路改进这个算法，减少算法的步骤.（1）用i表示2～88中的任意一个整数，并从2开始取数；（2）用i除89，得到余数r. 若r=0，则89不是质数；若r≠0，将i用i+1替代，再执行同样的操作； （3）这个操作一直进行到i取88为止.你能按照这个思路，设计一个“判断89是否为质数”的算法步骤吗？用i除89，得到余数r； 令i=2； 若r=0，则89不是质数，结束算法；若r≠0，将i用i+1替代； 判断“i>88”是否成立？若是，则89是质数，结束算法；否则，返回第二步. 第一步， 第四步， 第三步， 第二步， 算法设计:一般地，判断一个大于2的整数是否为质数的算法步骤如何设计？ 第一步，给定一个大于2的整数n； 第二步，令i=2； 第三步，用i除n，得到余数r； 第四步，判断“r=0”是否成立.若是，则n不是质数，结束算法；否则，将i的值增加1，仍用i表示； 第五步，判断“i>(n-1)”是否成立，若是， 则n是质数，结束算法；否则，返回第三步. 例2 设函数f(x)的图象是一条连续不断的曲线，写出用“二分法”求方程 f(x)=0的一个近似解的算法. 例题精讲第一步，取函数f(x)，给定精确度d. 第二步，确定区间[a，b]，满足f(a)·f(b)<0. 第五步，判断[a,b]的长度是否小于d或f(m)是否等于0. 若是，则m是方程的近似解；否则，返回第三步.第三步，取区间中点 .第四步，若f(a)·f(m)<0,则含零点的区间为[a,m],否则，含零点的区间为[m，b]. 将新得到的含零点的区间仍记为[a,b];对于方程 ,给定d=0.005.现有有限个实数，怎样从中找出最大值？先假定这些实数中的第一个数为“最大值”。将这些实数中的下一个数与“最大值”比较，如果它大于此“最大值”，这时就假定“最大值”是这个实数。如果还有其他实数，重复第二步。一直到没有可比的数为止，这时假定的“最大值”就是这有限个实数的最大值。第一步:第二步:第三步:第四步:思 考