数据结构经典问题和算法分析.doc

《数据结构经典问题和算法分析.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构经典问题和算法分析（一）-迭代法来源:  作者:  2007-5-3021:17:53  字体:[大中小]一、迭代法   迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0，用某种数学方法导出等价的形式x=g(x)，然后按以下步骤执行： （1）   选一个方程的近似根，赋给变量x0； （2）   将x0的值保存于变量x1，然后计算g(x1)，并将结果存于变量x0； （3）   当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（2）的计算。 若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法

2、求得的x0就认为是方程的根。上述算法用C程序的形式表示为： 【算法】迭代法求方程的根 {    x0=初始近似根；    do {       x1=x0；       x0=g(x1)；   /*按特定的方程计算新的近似根*/       } while ( fabs(x0-x1)>Epsilon)；    printf(“方程的近似根是%f”，x0)； 字串5} 迭代算法也常用于求方程组的根，令       X=（x0，x1，…，xn-1） 设方程组为：       xi=gi(X)      (I=0，1，…，n-1) 则求方程组根的迭

3、代算法可描述如下： 【算法】迭代法求方程组的根    {    for (i=0;idelta)      delta=fab

4、s(y[i]-x[i])；          } while (delta>Epsilon)；       for (i=0;i

5、近似根选择不合理，也会导致迭代失败。 字串5数据结构经典问题和算法分析（二）穷举搜索法来源:  作者:  2007-5-3021:26:51  字体:[大中小]二、穷举搜索法      穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从众找出那些符合要求的候选解作为问题的解。 【问题】   将A、B、C、D、E、F这六个变量排成如图所示的三角形，这六个变量分别取[1，6]上的整数，且均不相同。求使三角形三条边上的变量之和相等的全部解。如图就是一个解。 程序引入变量a、b、c、d、e、f，并让它们分别顺序取1至6的证书，在它们互不

6、相同的条件下，测试由它们排成的如图所示的三角形三条边上的变量之和是否相等，如相等即为一种满足要求的排列，把它们输出。当这些变量取尽所有的组合后，程序就可得到全部可能的解。细节见下面的程序。 【程序1】 # include  void main() {   int a,b,c,d,e,f;    for (a=1;a<=6;a++)          for (b=1;b<=6;b++)      {          if (b==a)      continue; 字串9         for (c=1;c<=6;c++) 

7、     {             if (c==a)

8、

9、(c==b)   continue;             for (d=1;d<=6;d++)      {                if (d==a)

10、

11、(d==b)

12、

13、(d==c)    continue; for (e=1;e<=6;e++)      {    if (e==a)

14、

15、(e==b)

16、

17、(e==c)

18、

19、(e==d)    continue; f=21-(a+b+c+d+e); if ((a+b+c==c+d+e))&&(a+b+c==e+f+a))   { 

20、printf(“%6d,a);    printf(“%4d%4d”,b,f);    printf(“%2d%4d%4d”,c,d,e