1、高中新课程数学必修 第一章 算法初步 1.1 算法与程序框图 1.1.1 算法的概念 1.一个大人和两个小孩一起渡河,渡口只有一条小船,每次只能渡 1 个大人或两个小孩,他们三人都会划船,但都不会游泳。试问他们怎样渡过河去?请写出一个渡河方案。1.一个大人和两个小孩一起渡河,渡口只有一条小船,每次只能渡 1 个大人或两个小孩,他们三人都会划船,但都不会游泳。试问他们怎样渡过河去?请写出一个渡河方案。第一步,两个小孩同船过河去;1.一个大人和两个小孩一起渡河,渡口只有一条小船,每次只能渡 1 个大人或两个小孩,他们三人都会划船,但都不会游泳。试问他们怎样渡过河去?请写出一个渡河方案。第一步,两个
2、小孩同船过河去;第二步,一个小孩划船回来;1.一个大人和两个小孩一起渡河,渡口只有一条小船,每次只能渡 1 个大人或两个小孩,他们三人都会划船,但都不会游泳。试问他们怎样渡过河去?请写出一个渡河方案。第一步,两个小孩同船过河去;第二步,一个小孩划船回来;第三步,一个大人划船过河去;1.一个大人和两个小孩一起渡河,渡口只有一条小船,每次只能渡 1 个大人或两个小孩,他们三人都会划船,但都不会游泳。试问他们怎样渡过河去?请写出一个渡河方案。第一步,两个小孩同船过河去;第二步,一个小孩划船回来;第三步,一个大人划船过河去;第四步,对岸的小孩划船回来;1.一个大人和两个小孩一起渡河,渡口只有一条小船,
3、每次只能渡 1 个大人或两个小孩,他们三人都会划船,但都不会游泳。试问他们怎样渡过河去?请写出一个渡河方案。第一步,两个小孩同船过河去;第二步,一个小孩划船回来;第三步,一个大人划船过河去;第四步,对岸的小孩划船回来;第五步,两个小孩同船渡过河去。知识探究(一):算法的概念思考 1:在初中,对于解二元一次方程组你学过哪些方法?知识探究(一):算法的概念思考 1:在初中,对于解二元一次方程组你学过哪些方法?加减消元法和代入消元法知识探究(一):算法的概念思考 1:在初中,对于解二元一次方程组你学过哪些方法?加减消元法和代入消元法思考 2:用加减消元法解二元一次方程组2121xyxy 的具体步骤是
4、什么?知识探究(一):算法的概念2121xyxy 2121xyxy+2,得 5x=1.2121xyxy+2,得 5x=1.解,得.15x 2121xyxy+2,得 5x=1.解,得.15x 2,得 5y3.2121xyxy+2,得 5x=1.解,得.15x 2,得 5y3.解,得.35y 2121xyxy+2,得 5x=1.解,得.15x 2,得 5y3.解,得.35y 得到方程组的解为.5351yx2121xyxy+2,得 5x=1.解,得.15x 2,得 5y3.解,得.35y 得到方程组的解为.5351yx第一步,2121xyxy+2,得 5x=1.解,得.15x 2,得 5y3.解,得
5、.35y 得到方程组的解为.5351yx第一步,第二步,2121xyxy+2,得 5x=1.解,得.15x 2,得 5y3.解,得.35y 得到方程组的解为.5351yx第一步,第二步,第三步,2121xyxy+2,得 5x=1.解,得.15x 2,得 5y3.解,得.35y 得到方程组的解为.5351yx第一步,第二步,第三步,第四步,2121xyxy+2,得 5x=1.解,得.15x 2,得 5y3.解,得.35y 得到方程组的解为.5351yx第一步,第二步,第三步,第四步,第五步,思考 3:参照上述思路,一般地,解方程组 1111 1222221,02a xb yca ba ba xb
6、 yc的基本步骤是什么?2b1b第一步,得.1 22 12 11 2()a ba b xb cb c2b1b2b1b第一步,得.1 22 12 11 2()a ba b xb cb c第一步,得.1 22 12 11 2()a ba b xb cb c2b1b第一步,得.1 22 12 11 2()a ba b xb cb c2b1b2b1b第一步,得.1 22 12 11 2()a ba b xb cb c第一步,得.1 22 12 11 2()a ba b xb cb c第二步,解,得.2 112122 1b cb cxa ba b第二步,解,得.2 112122 1b cb cxa ba
7、 b2b1b第一步,得.1 22 12 11 2()a ba b xb cb c2b1b2b1b第一步,得.1 22 12 11 2()a ba b xb cb c第一步,得.1 22 12 11 2()a ba b xb cb c第二步,解,得.2 112122 1b cb cxa ba b第二步,解,得.2 112122 1b cb cxa ba b第三步,得.1a2a1 22 11 22 1()a ba b ya ca c第三步,得.1a2a1 22 11 22 1()a ba b ya ca c2b1b第一步,得.1 22 12 11 2()a ba b xb cb c2b1b2b1b
8、第一步,得.1 22 12 11 2()a ba b xb cb c第一步,得.1 22 12 11 2()a ba b xb cb c第二步,解,得.2 112122 1b cb cxa ba b第二步,解,得.2 112122 1b cb cxa ba b第三步,得.1a2a1 22 11 22 1()a ba b ya ca c第三步,得.1a2a1 22 11 22 1()a ba b ya ca c第四步,解,得.12211221a ca cya ba b第四步,解,得.12211221a ca cya ba b2b1b第一步,得.1 22 12 11 2()a ba b xb cb
9、 c2b1b2b1b第一步,得.1 22 12 11 2()a ba b xb cb c第一步,得.1 22 12 11 2()a ba b xb cb c第二步,解,得.2 112122 1b cb cxa ba b第二步,解,得.2 112122 1b cb cxa ba b第三步,得.1a2a1 22 11 22 1()a ba b ya ca c第三步,得.1a2a1 22 11 22 1()a ba b ya ca c第四步,解,得.12211221a ca cya ba b第四步,解,得.12211221a ca cya ba b第五步,得到方程组的解为21121221122112
10、21b cb cxa ba ba ca cya ba b小结:根据上述分析,用加减消元法解二元一次方程组,可以分为五个步骤进行,这五个步骤就构成了解二元一次方程组的一个“算法”。我们再根据这一算法编制计算机程序,就可以让计算机来解二元一次方程组。小结:根据上述分析,用加减消元法解二元一次方程组,可以分为五个步骤进行,这五个步骤就构成了解二元一次方程组的一个“算法”。我们再根据这一算法编制计算机程序,就可以让计算机来解二元一次方程组。在数学中,按照一定规则解决某一类问题的明确和有限的步骤称为算法。知识探究(二):算法的步骤设计知识探究(二):算法的步骤设计思考 1:如果让计算机判断 7 是否为质
11、数,如何设计算法步骤?知识探究(二):算法的步骤设计思考 1:如果让计算机判断 7 是否为质数,如何设计算法步骤?第一步,用 2 除 7,得到余数 1,所以 2 不能整除 7知识探究(二):算法的步骤设计思考 1:如果让计算机判断 7 是否为质数,如何设计算法步骤?第一步,用 2 除 7,得到余数 1,所以 2 不能整除 7第二步,用 3 除 7,得到余数 1,所以 3 不能整除 7知识探究(二):算法的步骤设计思考 1:如果让计算机判断 7 是否为质数,如何设计算法步骤?第一步,用 2 除 7,得到余数 1,所以 2 不能整除 7第二步,用 3 除 7,得到余数 1,所以 3 不能整除 7第
12、三步,用 4 除 7,得到余数 3,所以 4 不能整除 7知识探究(二):算法的步骤设计思考 1:如果让计算机判断 7 是否为质数,如何设计算法步骤?第一步,用 2 除 7,得到余数 1,所以 2 不能整除 7第二步,用 3 除 7,得到余数 1,所以 3 不能整除 7第三步,用 4 除 7,得到余数 3,所以 4 不能整除 7第四步,用 5 除 7,得到余数 2,所以 5 不能整除 7知识探究(二):算法的步骤设计思考 1:如果让计算机判断 7 是否为质数,如何设计算法步骤?第一步,用 2 除 7,得到余数 1,所以 2 不能整除 7第二步,用 3 除 7,得到余数 1,所以 3 不能整除
13、7第三步,用 4 除 7,得到余数 3,所以 4 不能整除 7第四步,用 5 除 7,得到余数 2,所以 5 不能整除 7第五步,用 6 除 7,得到余数 1,所以 6 不能整除 7知识探究(二):算法的步骤设计思考 1:如果让计算机判断 7 是否为质数,如何设计算法步骤?第一步,用 2 除 7,得到余数 1,所以 2 不能整除 7第二步,用 3 除 7,得到余数 1,所以 3 不能整除 7第三步,用 4 除 7,得到余数 3,所以 4 不能整除 7第四步,用 5 除 7,得到余数 2,所以 5 不能整除 7第五步,用 6 除 7,得到余数 1,所以 6 不能整除 7因此,7 是质数思考 2:
14、如果让计算机判断 35 是否为质数,如何设计算法步骤?思考 2:如果让计算机判断 35 是否为质数,如何设计算法步骤?第一步,用 2 除 35,得到余数 1,所以 2 不能整除 35思考 2:如果让计算机判断 35 是否为质数,如何设计算法步骤?第一步,用 2 除 35,得到余数 1,所以 2 不能整除 35第二步,用 3 除 35,得到余数 2,所以 3 不能整除 35思考 2:如果让计算机判断 35 是否为质数,如何设计算法步骤?第一步,用 2 除 35,得到余数 1,所以 2 不能整除 35第二步,用 3 除 35,得到余数 2,所以 3 不能整除 35第三步,用 4 除 35,得到余数
15、 3,所以 4 不能整除 35思考 2:如果让计算机判断 35 是否为质数,如何设计算法步骤?第一步,用 2 除 35,得到余数 1,所以 2 不能整除 35第二步,用 3 除 35,得到余数 2,所以 3 不能整除 35第三步,用 4 除 35,得到余数 3,所以 4 不能整除 35第四步,用 5 除 35,得到余数 0,所以 5 能整除 35思考 2:如果让计算机判断 35 是否为质数,如何设计算法步骤?第一步,用 2 除 35,得到余数 1,所以 2 不能整除 35第二步,用 3 除 35,得到余数 2,所以 3 不能整除 35第三步,用 4 除 35,得到余数 3,所以 4 不能整除
16、35第四步,用 5 除 35,得到余数 0,所以 5 能整除 35因此,35 不是质数思考 3:整数 89 是否为质数?如果让计算机判断 89 是否为质数,按照上述算法需要设计多少个步骤?思考 3:整数 89 是否为质数?如果让计算机判断 89 是否为质数,按照上述算法需要设计多少个步骤?第一步,用 2 除 89,得到余数 1,所以 2 不能整除 89思考 3:整数 89 是否为质数?如果让计算机判断 89 是否为质数,按照上述算法需要设计多少个步骤?第一步,用 2 除 89,得到余数 1,所以 2 不能整除 89第二步,用 3 除 89,得到余数 2,所以 3 不能整除 89思考 3:整数
17、89 是否为质数?如果让计算机判断 89 是否为质数,按照上述算法需要设计多少个步骤?第一步,用 2 除 89,得到余数 1,所以 2 不能整除 89第二步,用 3 除 89,得到余数 2,所以 3 不能整除 89第三步,用 4 除 89,得到余数 1,所以 4 不能整除 89思考 3:整数 89 是否为质数?如果让计算机判断 89 是否为质数,按照上述算法需要设计多少个步骤?第一步,用 2 除 89,得到余数 1,所以 2 不能整除 89第二步,用 3 除 89,得到余数 2,所以 3 不能整除 89第三步,用 4 除 89,得到余数 1,所以 4 不能整除 89 思考 3:整数 89 是否
18、为质数?如果让计算机判断 89 是否为质数,按照上述算法需要设计多少个步骤?第一步,用 2 除 89,得到余数 1,所以 2 不能整除 89第二步,用 3 除 89,得到余数 2,所以 3 不能整除 89第三步,用 4 除 89,得到余数 1,所以 4 不能整除 89 第八十七步,用 88 除 89,得到余数 1,所以 88 不能整除 89思考 3:整数 89 是否为质数?如果让计算机判断 89 是否为质数,按照上述算法需要设计多少个步骤?第一步,用 2 除 89,得到余数 1,所以 2 不能整除 89第二步,用 3 除 89,得到余数 2,所以 3 不能整除 89第三步,用 4 除 89,得
19、到余数 1,所以 4 不能整除 89 第八十七步,用 88 除 89,得到余数 1,所以 88 不能整除 89因此,89 是质数思考 4:用 288 逐一去除 89 求余数,需要 87个步骤,这些步骤基本是重复操作,我们可以按下面的思路改进这个算法,减少算法的步骤思考 4:用 288 逐一去除 89 求余数,需要 87个步骤,这些步骤基本是重复操作,我们可以按下面的思路改进这个算法,减少算法的步骤算法分析:思考 4:用 288 逐一去除 89 求余数,需要 87个步骤,这些步骤基本是重复操作,我们可以按下面的思路改进这个算法,减少算法的步骤算法分析:(1)用 i 表示 288 中的任意一个整数
20、,并从 2开始取数;思考 4:用 288 逐一去除 89 求余数,需要 87个步骤,这些步骤基本是重复操作,我们可以按下面的思路改进这个算法,减少算法的步骤算法分析:(1)用 i 表示 288 中的任意一个整数,并从 2开始取数;(2)用 i 除 89,得到余数 r.若 r=0,则 89 不是质数;若 r0,将 i 的值增加 1,再执行同样的操作;思考 4:用 288 逐一去除 89 求余数,需要 87个步骤,这些步骤基本是重复操作,我们可以按下面的思路改进这个算法,减少算法的步骤算法分析:(1)用 i 表示 288 中的任意一个整数,并从 2开始取数;(3)这个操作一直进行到 i 取 88
21、为止(2)用 i 除 89,得到余数 r.若 r=0,则 89 不是质数;若 r0,将 i 的值增加 1,再执行同样的操作;算法:算法:第一步,算法:令i=2;第一步,算法:令i=2;第一步,第二步,算法:用i除89,得到余数r;令i=2;第一步,第二步,算法:用i除89,得到余数r;令i=2;第一步,第三步,第二步,算法:用i除89,得到余数r;令i=2;第一步,第三步,第二步,若r=0,则89不是质数,结束算法;若r0,将i用i+1替代;若r=0,则89不是质数,结束算法;若r0,将i用i+1替代;将i的值增加1,仍用i表示.算法:用i除89,得到余数r;令i=2;第一步,第四步,第三步,
22、第二步,若r=0,则89不是质数,结束算法;若r0,将i用i+1替代;若r=0,则89不是质数,结束算法;若r0,将i用i+1替代;将i的值增加1,仍用i表示.算法:令i=2;第一步,第四步,第三步,第二步,判断“i88”是否成立?若是,则89是质数,结束算法;否则,返回第二步.用i除89,得到余数r;若r=0,则89不是质数,结束算法;若r0,将i用i+1替代;若r=0,则89不是质数,结束算法;若r0,将i用i+1替代;将i的值增加1,仍用i表示.思考5:一般地,判断一个大于2的整数是否为质数的算法步骤如何设计?思考5:一般地,判断一个大于2的整数是否为质数的算法步骤如何设计?第一步,给定
23、一个大于2的整数n.思考5:一般地,判断一个大于2的整数是否为质数的算法步骤如何设计?第一步,给定一个大于2的整数n.第二步,令i=2思考5:一般地,判断一个大于2的整数是否为质数的算法步骤如何设计?第一步,给定一个大于2的整数n.第二步,令i=2第三步,用i除n,得到余数r思考5:一般地,判断一个大于2的整数是否为质数的算法步骤如何设计?第一步,给定一个大于2的整数n.第二步,令i=2第三步,用i除n,得到余数r第四步,判断“r=0”是否成立.若是,则n不是质数,结束算法;否则,将i的值增加1,仍用i表示思考5:一般地,判断一个大于2的整数是否为质数的算法步骤如何设计?第一步,给定一个大于2
24、的整数n.第二步,令i=2第三步,用i除n,得到余数r第四步,判断“r=0”是否成立.若是,则n不是质数,结束算法;否则,将i的值增加1,仍用i表示第五步,判断“i(n-1)”是否成立,若是,则n是质数,结束算法;否则,返回第三步例:写出用“二分法”求方程x22=0的一个近似解的算法.理论迁移理论迁移第一步:令 f(x)=x22,给定精度 d理论迁移第一步:令 f(x)=x22,给定精度 d第二步:确定区间a,b,满足 f(a)f(b)0理论迁移第一步:令 f(x)=x22,给定精度 d第二步:确定区间a,b,满足 f(a)f(b)0第三步:取区间中点 m=(ab)/2理论迁移第一步:令 f(
25、x)=x22,给定精度 d第二步:确定区间a,b,满足 f(a)f(b)0第三步:取区间中点 m=(ab)/2理论迁移第四步:若 f(a)f(m)0,则含零点的区间为a,m;否则,含零点的区间为m,b将新得到的含零点的区间仍记为a,b.第一步:令 f(x)=x22,给定精度 d第二步:确定区间a,b,满足 f(a)f(b)0第三步:取区间中点 m=(ab)/2第五步:判断a,b的长度是否小于 d 或 f(m)是否等于 0若是,则 m 是方程的近似解;否则,返回第三步理论迁移第四步:若 f(a)f(m)0,则含零点的区间为a,m;否则,含零点的区间为m,b将新得到的含零点的区间仍记为a,b.小结
26、算法是建立在解法基础上的操作过程,算法不一定要有运算结果,问题答案可以由计算机解决设计一个解决某类问题的算法的核心内容是设计算法的步骤,它没有一个固定的模式,但有以下几个基本要求:小结(1)符合运算规则,计算机能操作;算法是建立在解法基础上的操作过程,算法不一定要有运算结果,问题答案可以由计算机解决设计一个解决某类问题的算法的核心内容是设计算法的步骤,它没有一个固定的模式,但有以下几个基本要求:小结(1)符合运算规则,计算机能操作;(2)每个步骤都有一个明确的计算任务;算法是建立在解法基础上的操作过程,算法不一定要有运算结果,问题答案可以由计算机解决设计一个解决某类问题的算法的核心内容是设计算
27、法的步骤,它没有一个固定的模式,但有以下几个基本要求:小结(1)符合运算规则,计算机能操作;(2)每个步骤都有一个明确的计算任务;(3)对重复操作步骤作返回处理;算法是建立在解法基础上的操作过程,算法不一定要有运算结果,问题答案可以由计算机解决设计一个解决某类问题的算法的核心内容是设计算法的步骤,它没有一个固定的模式,但有以下几个基本要求:小结(1)符合运算规则,计算机能操作;(2)每个步骤都有一个明确的计算任务;(4)步骤个数尽可能少;(3)对重复操作步骤作返回处理;算法是建立在解法基础上的操作过程,算法不一定要有运算结果,问题答案可以由计算机解决设计一个解决某类问题的算法的核心内容是设计算
28、法的步骤,它没有一个固定的模式,但有以下几个基本要求:小结(1)符合运算规则,计算机能操作;(2)每个步骤都有一个明确的计算任务;(4)步骤个数尽可能少;(5)每个步骤的语言描述要准确、简明(3)对重复操作步骤作返回处理;算法是建立在解法基础上的操作过程,算法不一定要有运算结果,问题答案可以由计算机解决设计一个解决某类问题的算法的核心内容是设计算法的步骤,它没有一个固定的模式,但有以下几个基本要求:小结思考 1:有人对哥德巴赫猜想“任何大于 4 的偶数都能写成两个质数之和”设计了如下操作步骤:思考 1:有人对哥德巴赫猜想“任何大于 4 的偶数都能写成两个质数之和”设计了如下操作步骤:第一步,检验 6=3+3,第二步,检验 8=3+5,第三步,检验 10=5+5,利用计算机无穷地进行下去!请问:这是一个算法吗?思考 2:一个人带三只狼和三只羚羊过河,只有一条船,同船可以容纳一个人和两只动物。没有人在的时候,如果狼的数量不少于羚羊的数量,狼就会吃掉羚羊设计过河的算法:作业一.作业