数据结构暨若干经典问题和算法.doc

.一、迭代法 迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0，用某种数学方法导出等价的形式x=g(x)，然后按以下步骤执行： （1）选一个方程的近似根，赋给变量x0； （2）将x0的值保存于变量x1，然后计算g(x1)，并将结果存于变量x0； （3）当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（2）的计算。 若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为： 【算法】迭代法求方程的根 x0=初始近似根； do x1=x0； x0=g(x1)；/*按特定的方程计算新的近似根*/ while(fabs(x0-x1)Epsilon)； printf(“方程的近似根是%fn”，x0)； 迭代算法也常用于求方程组的根，令 X=（x0，x1，xn-1）