数据结构和算法部分经典例子.doc

《数据结构和算法部分经典例子.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、个人收集整理勿做商业用途数据结构和算法部分经典例子一、迭代法迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=０，用某种数学方法导出等价的形式x=g(x)，然后按以下步骤执行：ﻫ(1）选一个方程的近似根，赋给变量x0；（2）将x0的值保存于变量x1，然后计算g(x1)，并将结果存于变量x0；　ﻫ(3)当ｘ0与x１的差的绝对值还小于指定的精度要求时,重复步骤(2)的计算。　若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的x０就认为是方程的根。上述算法用Ｃ程序的形式表示为:ﻫ【算法】迭代法求方程的根{　ｘ０=初始近似

2、根;ﻫdo{　x1=x0；　ﻫx０=g(ｘ１)；　/＊按特定的方程计算新的近似根*/　}wｈilｅ(　faｂs（x０-ｘ1）>Epsilon)；ﻫprintf(“方程的近似根是％ｆｎ”，ｘ0)；　}　迭代算法也常用于求方程组的根，令X=(x0,x1，…,ｘn-1）ﻫ设方程组为：ﻫxｉ=gｉ（X)　(I＝０,1，…，n-１)ﻫ则求方程组根的迭代算法可描述如下:　【算法】迭代法求方程组的根{for　(ｉ=0；ｉ＜n;i++)　ﻫｘ[i]=初始近似根;do{　ﻫｆor（i=0;i

3、X)；　for（delｔａ=0.０,i=０;iＥpsiloｎ）;for(ｉ=0;i<ｎ;ｉ++)ﻫpｒinｔf(“变量ｘ[%d］的近似根是　%ｆ”，Ｉ,x[i]);ﻫprintf(“ｎ”)；ﻫ｝ﻫ具体使用迭代法求根时应注意以下两种可能发生的情况：ﻫ(1）如果方程无解,算法求出的近似根序列就不会收敛,迭代过程会变成死循环,因此在使用迭代算法前应先考察方程是否有解，并在程序中对迭代的次数给予限制；　(2)方程虽然有解,但迭代

4、公式选择不当，或迭代的初始近似根选择不合理，也会导致迭代失败。二、穷举搜索法穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从众找出那些符合要求的候选解作为问题的解。【问题】　将A、B、C、D、E、Ｆ这六个变量排成如图所示的三角形，这六个变量分别取［1,6]上的整数，且均不相同。求使三角形三条边上的变量之和相等的全部解。如图就是一个解。ﻫ程序引入变量a、b、c、ｄ、e、f,并让它们分别顺序取1至6的证书，在它们互不相同的条件下，测试由它们排成的如图所示的三角形三条边上的变量之和是否相等,如相等即为一种满足要求的排列，把它们输出。当这些变量取尽

5、所有的组合后,程序就可得到全部可能的解。细节见下面的程序。ﻫ【程序１】　ﻫ#　iｎｃｌｕde

6、（c==b）ｃontinｕｅ;ﻫｆｏr　(ｄ=1;ｄ＜=6；d++)　｛ﻫｉｆ(d==a)

7、

8、(d＝＝b)

9、

10、（d==ｃ)ｃｏntinｕｅ;ｆor(e=1；e＜=6;e++){　ｉf(e=＝ａ)｜

11、(e＝=b）

12、

13、(e＝=ｃ)

14、

15、

16、(ｅ=＝d)　coｎtｉｎue;个人收集整理勿做商业用途ｆ=2１-(a+b＋c＋d+e）;　ｉf　((a+b+c==c+d+ｅ））&＆(a+b＋c==e+ｆ+a)）　{prｉntf（“%６d,ａ)；ﻫpriｎtf(“%４d%4d”,ｂ,ｆ)；ｐｒintf(“%2d%４ｄ%4d”,ｃ,d,e);　scaｎf(“%*ｃ”);　ﻫ}｝ﻫ}ﻫ｝ﻫ}ﻫ}　ﻫ按穷举法编写的程序通常不能适应变化的情况。如问题改成有9个变量排成三角形，每条边有４个变量的情况，程序的循环重数就要相应改变。对一组数穷尽所有排列，还有更直接的方法。将一个排列看作一个长整数,则所有排列对应着一组

17、整数。将这组整数按从小到大的顺序排列排成一个整数，从对应最小的整数开始。按数列的递增顺序逐一列举每个排列对应的每个整数,这能更有效地完成排列的穷举。从一个排列找出对应数列的下一个排列可在当前排列的基础上作部分调整来实现。倘若当前排列为１，2,4，6,5，3,并令其对应的长整数为124６５3。要寻找比长整数124653更大的排列，可从该排列的最后一个数字顺序向前逐位考察，当发现排列中的某个数字比它前一个数字大时,如本例中的6比它的前一位数字4大,这说明还有对应更大整数的排列。但为了顺序从小到大列举出所有的排列,不能立即调整得太大，如本例中将数字６与数字４交换得到

18、的排列12６453就不是排列1246５