浙教版信息技术高中选修1 数据与数据结构5.2.1 迭代-教学课件.pptxVIP

浙教版信息科技

迭代

网上有一个比较火的存钱法:第一天存一块，第二天存两块，第三天存三块……这样一年你能存多少钱？

第n天的时候一共能攒多少钱？

n

结果a

关于a的迭代

1

2

3

4

……

……

……

n

a1=1

a2=1+2

a3=1+2+3

a4=1+2+3+4

……

a1=1

a2=a1+2

a3=a2+3

a4=a3+4

an=an-1+n

an=1+2+3+……+n-1+n

从1累加至n的和

1

1+2

1+2+3

计算1累加至整数n的结果（n≥1）。

迭代，就是重复反馈过程的活动，目的通常是为了逼近所需达到的目标或结果。

每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果会作为下一次迭代的初始值。

#每一次循环，a的值由旧的值变成新的值

迭代，最初是一个科学概念，通常应用于数学和计算机领域。但生活中有很多地方用到迭代思想。

雪花图案

反复练习投篮

产品开发、更新

思考：你的身边还有哪些事物运用了迭代？

迭代

计算机解决问题时，也会经常采用迭代的方式，称为迭代算法。

它利用了计算机运算快、适合做重复性操作的特点，让计算机重复执行一组指令（或一些步骤），这组指令（或这些步骤）每执行一次，都会将变量从原值递推出一个新值。

教材119页

迭代算法

1.确定迭代变量。

迭代算法三要素

2.建立迭代关系式。

3.控制迭代过程。

至少具有一个（可以多个）不断由旧值递推出新值得变量。

迭代变量如何从前一个值推出其下一个值的公式。

递推过程在经过若干次重复执行后要能结束，因此

要设定迭代结束的条件。

1.确定迭代变量。

2.建立迭代关系式。

3.控制迭代过程。

设定迭代变量a

加至n，迭代结束

a=a+i

思考：这个例子中，迭代的三要素分别怎么表示？

例1：采用迭代算法求a的平方根。

以a=2为例。

可估测一个近似值（如x0=1）作为初值，

设定前后两次求出的x的值绝对值小于10-5。

1.确定迭代变量。

2.建立迭代关系式。

3.控制迭代过程。

设定迭代变量x的初值，如x0=1

xn+1=(xn-a/xn)/2公式的由来

xn

xn+1

f（xn）

x2=a

f（x）=x2-a=0

0=x02-2x0(x-x0)

x1=x0-(x02-a)/2x0

x1=(x0-a/x0)/2

xn+1=(xn-a/xn)/2

例1：采用迭代算法求a的平方根。

以a=2为例。

可估测一个近似值（如x0=1）作为初值，

设定前后两次求出的x的值绝对值小于10-5。

1.确定迭代变量。

2.建立迭代关系式。

3.控制迭代过程。

设定迭代变量x的初值，如x0=1

迭代结束

例1：采用迭代算法求a的平方根。

迭代次数

1

1

1.5

0.5

2

1.5

1.416667

0.083333

3

1.416667

1.414216

0.002451

4

1.414216

1.414214

0.000002

迭代过程：

例1：采用迭代算法求a的平方根。

程序

测试结果

例1：采用迭代算法求a的平方根。

修改预估的初始值，是否会影响输出结果和迭代次数？

校验输出结果：

修改预估的初值即可，可以尝试输入a=2的情况下，修改x的初值为1、5、10等等即可验证是否会影响输出结果。

例1：采用迭代算法求a的平方根。

修改预估的初始值，是否会影响输出结果和迭代次数？

校验迭代次数：

1.引入变量s，计算迭代次数的代码。

2.尝试输入a=2的情况下，修改x的为不同初值进行调试。

例2：欧几里得算法，又称辗转相除法，用于计算两个整数a，b的最大公约数。

较大的数÷较小的数=商……余数

……

被除数÷除数=商……0

较小的数÷第一次的余数=商……第二次的余数

第一次的余数÷第二次的余数=商……第三次的余数

例2：欧几里得算法，又称辗转相除法，用于计算两个整数a，b的最大公约数。

a

b

a%b

91

49

42

49

42

7

42

7

0

辗转相处法为什么可以求出最大公约数

假设ab（a、b都非零）

a=mb+r（其中a、b、m、r都为整数，且rb）

得到

等式1：r=mb-a

设a和b的最大公约数为x，得到

r/x=mb/