《常用软件算法基础》课件-第章 迭代算法

第十二章迭代算法内容目标：迭代算法基本概念。递推算法案例分析倒推算法案例分析迭代算法求解方程案例分析重难点：各种迭代算法设计思想1.递归算法的基本概念迭代法（Iteration）也称为“碾转法”，是一种不断用变量的旧值递推出新值的解决问题的一种方法。迭代算法一般用于数值计算。迭代法应该是早已熟悉的算法策略。利用迭代算法策略求解问题，设计工作主要3步：确定迭代模型根据问题的描述，分析得出前一个（或几个）值与其下一个值的迭代关系数学模型。当然这样的迭代关系，最终会迭代出解的目标。建立迭代关系递推数学模型一般是带下标的字母，算法设计中要将其转化为“循环不变式”----迭代关系式，迭代关系式就是一个直接或间接地不断由旧值推出新值的表达式，存储新值的变量称为迭代变量。迭代关系式的建立是迭代算法设计的主要工作。对迭代过程进行控制确定在什么时候结束迭代过程，是设计迭代算法时必须考虑的问题。迭代过程的控制通常可分为两种情况：一种是一致或可以计算处理所迭代次数，这时可以构建一个固定次数的循环来实现对迭代过程的控制。另一种是所须的迭代次数无法确定，需要分析出迭代构成的结束条件。2.1递推法案例分析递推法概念：递推（Recursion）算法是迭代算法的最基本的表现形式。一般来讲，一种简单的递推方法，是从小规模的问题推解出大规模问题的一种方法，也称为“正推”。如：累加过程就是在求出前n-1项和的基础上推出前n项和的，递推公式是Sn=Sn-1+An。由于无须保存每次的累加结果，所以用一个迭代变量s存储每次累加的结果，累加对象存储在变量a中，这样递推公式就抽象成“循环不变”的累加式s=s+a。2.2递推法案例分析问题描述：一对兔子从出生后第三个月开始，每月生一对兔子。小兔子到第三个月又开始生下一代兔子。假如兔子只生不死，一月份抱来一对刚出生的小兔子，问一年中每个月各有多少只兔子。2.3递推法案例分析问题分析：寻找问题的规律性，需要通过对现实问题的具体实例进行分析，从而抽象出其中的规律。最基本的分析方法之一是“枚举”，也就是将问题的求解过程及各种可能情况一一枚举出来，从中发现解决问题的方法，下面就分析兔子繁殖的过程。一对兔子从出生后第三个月开始每月生一对兔子，第三个月后每月除了有上一个月的兔子外，还有新下小兔子，在下表中用斜体数字表示。则第三各月以后兔子的对数就是前两个月兔子对数的和。繁殖过程如下。

1月2月3月 4月 5月 6月……1 11+1=22+1=33+2=55+3=8……从上面的分析，我们可以得到如下的数学模型：

y1=y2=1，yn=yn-1+yn-2,n=3,4,5……2.4递推法案例分析代码实现：publicvoidtzfy(){inti,a=1,b=1;//初始化第1、2个月的兔子对数intc;Console.WriteLine("第{0}月,有{1}对兔子",1,a);//打印第一个月的兔子数Console.WriteLine("第{0}月,有{1}对兔子",2,b);//打印第二个月的兔子数

for(i=1;i<=10;i++)//循环递推求其他个月的兔子数

{ c=a+b; Console.WriteLine("第{0}月,有{1}对兔子",i+2,c);//打印第i+2月的兔子数

a=b; b=c; }}

3.1推到法案例分析推到法的基本概念：所谓的倒推法（InvertedRecursion）是对某些特殊问题所采用的违反通常习惯的，从后向前推解问题的方法。在不知前提条件的情况下，经过从后向前递推，来求解问题的初始数据，即由结果倒过来推解它的前提条件。另外在对一些进行分析或建立数学模型时，从前向后分析问题感到比较棘手，而采用倒推法，则问题很容易理解和解决。3.2推到法案例分析问题描述： 猴子吃桃子问题：一只小猴子摘下若干个桃子，每天吃现有的一半多一个，到第10天时就只有一个桃子了，求原有多少个桃子。问题分析：每天的桃子数为：

a10=1; a9=1+a10*2; a8=1+a9*2;……

递推公式为：

ai=1+ai+1*2i=9,8,7,…,13.3推到法案例分析代码实现： publicvoidhzwt() { inti,a; a=1; for(i=9;i>=1;i--) { a=1+a*2; } Console.WriteLine("总的桃子个数为：{0}",a); }

4.1迭代法求解方程的解迭代法求解方程：在科学计算领域，人们时常会遇到求解方程f（x）=0或微分方程的数值解计算问题。可是人们很难或无法找到类似一元二次方程的求根公式那样的解析法（又称直接求解法）去求解任意多项式方程。例如，一般的一元五次或更高次方程，其解都无法用解析方法表达出来。为此，已发明了很多数值算法（也称数值计算方法），用来求解问题的近似解，这是一门专门的学科。这里仅对迭代法进行介绍。迭代法可分为精确迭代和近似迭代。前面的例子属于精确迭代，而迭代法解方程一般属于近似迭代。4.2推到法案例分析问题描述：用二分法求解一元非线性方程f（x）=1/2x3+2x2-8=0在【0，2】的近似根r，精确到0.0001。问题分析：可以用数学方法证明在0到2之间是单调递增的。又x=0时，f（x）=-8；x=2时，f（x）=4，因此曲线f(x)在【0，2】间必与x轴有交点，则交点即是该问题的解。该问题的解可能是个无理数，无法通过计算机得到精确的解，我们只可能得到近似解，根据题意精确到0.0001，即是利用迭代法求得某个x0，使得|f（x0）|<0.0001，我们可认为x0就是该问题的解。4.3迭代法求解方程的解代码实现：publicvoidfx(){floatx,x1=0,x2=2,f1,f2,f;//定义用以计算的局部变量

f1=x1*x1*x1/2+2*x1*x1-8;//计算f（0）的值保存到f1中

f2=x2*x2*x2/2+2*x2*x2-8;//计算f（2）的值保存到f2中

if((f1*f2)>0) //如果f1和f2同号无解

{Console.WriteLine("无解"); return; }do{ x=(x1+x2)/2; //计算x1和x2的中点x f=x*x*x/2+2*x*x-8;//计算中点x所对应的f（x）的值

if(f==0) //如果f（x）=0问题得解

break; if(f1*f>0.0) //f（x）与f（0）同号，迭代右半区【x