概念c语言程序设计.ppt

《概念c语言程序设计.ppt》由会员分享，可在线阅读，更多相关《概念c语言程序设计.ppt（125页珍藏版）》请在三一办公上搜索。

1、第4章 算法设计策略,4.1 分治策略 4.2 回溯策略4.3 贪心策略4.4 分枝界定策略4.5 动态规划,算法设计策略,4.1 分治策略,任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。直接求解一个规模较大的问题，往往是相当困难的。但是当问题的规模缩小到一定程度时，一个量变到质变的现象就可能发生，问题的求解变得比较容易。这时，如果能找到小规模的该类问题与大规模的该类问题之间的关系，就可以使用分治策略对大规模的问题进行求解了。分治法所能解决的问题一般具有以下几个特征：（1）该问题可以分解为若干个规模较小的相同问题。（2）各个子问题相互独立，子问题之间不包含公共的子子问题。（3）该

2、问题的规模缩小到一定的程度可以容易地求解。（4）利用该问题分解出的子问题的解可以合并为该问题的解。,4.1.1 二分查找4.1.2 快速排序4.1.3 自行车带人问题,分治法往往要依靠递归过程，并且大致有如下三个步骤：分解：将原问题分解为若干个规模较小、相互独立，与原问题形式相同的子问题。解决：若子问题规模较小而容易被解决则直接解决，否则递归地解决各个子问题。合并：将各个子问题的解合并为原问题的解。这一节，介绍几种使用分治策略的例子。,4.1.1 二分查找,一、问题描述在N个已排序（设为从小到大）的数据（数或字符串），查询某一个数据：如果找到了，就指出其在N个数据中的位置；否则给出无该数据的信

3、息，如给出“-1”。,查询是在一个数据集中，查找给定数据的过程。查询的结果有两种情形：找到给定的数据，并给出其位置；找不到给定数据。,二、算法分析,采用二分法求解本问题的基本思路是：如图4.1所示，设数列为a1、a2、an，被查找的数据为x，则查找首先对am(m=(1+n)/2)进行，于是得到如下3种情形：若xam，则x可能在区间 am+1,an中。若xam，则x可能在区间a1,am-1中。若x=am，则以am为所查找数据x，求解结束。这样，当一次搜索没有找到解时，便把搜索范围缩小一半，可以再在新的搜索范围内按上述原则进行搜索，不断二分，直到得出结论（找到或找不到）为止。,为了使算法更具一般性

4、，设数列为as、as+1、ar、s为数列的起始元素序号（开始时为1），r为数列的终止元素序号（开始时为n），则利用二分查找法在其中找出元素x的递归函数binsrch（s,r,x）可描述为：binsrch（s,r,x）m=(s+r)/2;if(x=am)打印找到信息后返回;else if(s=r)打印找不到信息,结束程序执行;else if(xam)调用函数binsrch（m+1,r,x）;else 调用函数binsrch（s,m-1,x）;,三、程序,include float a10=1.1,1.3,1.5,1.7,1.9,2.1,2.3,2.5,2.7,2.9;/*数组声明及初始化，外部数

5、组*/void main()float x=2.3;int s=0,r=9;void binsrch(int s,int r,float x);/*函数声明*/binsrch(s,r,x);/*函数调用*/,三、程序（续）,void binsrch(int s,int r,float x)int m;m=(s+r)/2;if(am=x)printf(The order of%5.1f is%d in this sequence.,x,m+1);return;else if(s=r)printf(%f is not exist in the seguense.,x);exit(-1);else

6、if(xam)binsrch(m+1,r,x);/*递归调用*/elsebinsrch(s,m-1,x);/*递归调用*/,四、说明,1.外部数组在本例中，声明语句 float a10=1.1,1.3,1.5,1.7,1.9,2.1,2.3,2.5,2.7,2.9;定义在所有函数的外部，即不在任何一个函数内。这种定义在函数外部的数组，称为外部数组。一般来说，定义在外部的变量称为外部变量。外部变量是在每一个函数中都可以使用的变量。相对而言，前面使用过的、定义在某一个函数内部的变量称为局部变量，它只能在所定义的局部使用。,五、编程练习,1.用二分法求一元方程式的根（提示：用二分迭代法）。2.用二分

7、法计算xn的值（提示：当n为偶数时，使用xn=xp*xp；当n为奇数时，使用xn=x*xp*xp）。3.用二分法找出一个数组中的最大值和最小值。,4.1.2 快速排序,一、快速排序的基本思想：,快速排序（quick sort）是由著名计算机科学家根据分治策略给出的一种高效率的排序方法。它的基本思想是：在待排序序列中选定一个元素X(可以任选，也可以选第一个元素)，称为划分元素，用它将原序列整理划分（partitioning）为两个子序列，使其左边的元素不比它大，使其右边的元素不比它小；然后再对两个子序列进行上述划分；经过不断划分，直至将原序列整理完毕为止，如图4.2所示。,图4.2 快速排序示例

8、,二、算法框架,qksort(int m,int n)/*序列由m到n*/if(mn)调用划分函数part(m,n,i);递归调用qksort(m,i-1);递归调用qksort(i+1,m);else 输出排序结束信息return;下面进一步考虑如何描述函数part()。基本思路如下：,基本思路,步骤1：准备：步骤1.1：设置两个指针i和j，分别指向待划分序列的首尾元素am和an；步骤1.2：选取划分元素p=ak（k属于m,n），将am移至k，即令ak=am。步骤2：划分：当ip,则令j-（j左移一个数据位）;否则，令ai=aj(将aj放在i位置);步骤2.2：逐步增加i：将ai与p比较，若

9、aip,则令i+（i右移一个数据位）;否则，令aj=ai(将ai放在j位置)。步骤3：如果i=j,放置划分元素：令Ai=p。,图4.3 一次划分示意图,划分函数,int part(int low,int high)int i,j;float p;i=low;j=high;/*准备*/p=alow;while(i=p)/*逐步减小j*/j-;ai=aj;while(ij,三、程序,#include#define N 10 float a=2.1,1.7,1.5,2.9,2.7,2.3,1.3,2.5,1.1,1.9;void main()int m=0,n=N-1;void qksort(int

10、 m,int n);int part(int m,int n);void prnt();qksort(m,n);prnt();,三、程序（续）,void qksort(int low,int high)int i;if(lowhigh)i=part(low,high);qksort(low,i-1);qksort(i+1,high);elsereturn;,三、程序（续）,int part(int low,int high)参见前面“划分函数”部分void prnt()int i;printf(nsorted sequence is:n);for(i=0;i=N-1;i+)printf(%5.

11、1f,ai);,四、运行结果,sorted sequenc is:1.1,1.3,1.5,1.7,1.9,2.1,2.3,2.5,2.7,2.9,五、编程练习,1.归并排序（Merging sort）：“归并”的含义是将两个或两个以上的有序表列合并为一个新的有序表列。归并排序就是把一个具有n 个数据的序列看作n个有序的子序列，不断两两归并，最后形成一个有序序列。显然这是一种分治策略。归并排序的关键是归并。下面介绍一种归并算法：设序列a(low,high)由两个有序子序列组成：a(low,mid)和a(mid,high)。归并按如下步骤进行：（1）设置一个与序列a大小相等的数组b，用三个指针i,

12、j,k,分别指向a(low,mid)，a(mid,high)和b的首部；（2）重复执行下列操作：如果ai=aj，则执行bk+=ai+；否则执行bk+=aj+。直至有一个子序列取完。将未取完的子序列放入b的尾部；将b复制到a。请设计一个归并排序的C语言程序。,4.1.3 自行车带人问题,一、问题描述,A、B两地相距S公里。甲、乙、丙三人要利用一辆自行车从A地赶往B地。但是该自行车只能带一人。若人的步行速度为a公里/小时，自行车的速度为b公里/小时（ba）。问如何利用自行车，才能使三人尽快全部到达B？,二、算法分析,1.基本思路,若要三人尽快到达B，就要考虑当一个人骑自行车带一个人走的同时，另一个

13、人也同时开始步行，并且自行车不是到达B后再返回去接步行的人，而是在中途返回去接步行的人，让原来带的人步行到终点。选择合适的自行车返回点，使自行车接上原来步行的人后，与中途下车的人同时到达。这样用的时间最短。图4.4为一个基本的解题思路。,图4.4 自行车带人问题,假定甲被带到C点后开始步行，这时乙步行到了E点，丙返回的途中在D遇到乙，然后带上乙到B时，甲也正好步行到B。问题的关键是求C的位置。设AC=L，那么:甲从A到B的时间为：t1=AC/b+CB/a=L/b+(S-L)/a乙从A到B的时间为：t2=AE/a+ED/a+DC/b+CB/b并且,并且，由于甲到C与乙到E用的时间相等，所以：AE

14、/a=L/b；由于当自行车返回到D时，乙步行到D，所以EC/(a+b)=ED/a=DC/b，即:ED=（L-L/b*a）/(a+b)*a/*ED=EC/(a+b)*a=(AC-EC)/(a+b)*a*/DC=（L-L/b*a）/(a+b)*b/*DC=EC/(a+b)*b=(AC-EC)/(a+b)*b*/这样，t1和t2都描述成了关于L的函数。如果任意给定一个L，就可以通过判定t1与t2是否相等，得知该L是否正确。,2.用二分法试探确定C,下面用试探方法来确定L（即C的位置）。首先考虑用二分法，进行试探。即先以中点作为设想的C，后分别计算t1与t2：如果t1=t2，该点即为C；如果t1t2，

15、说明甲坐自行车少了（ba），即C的实际位置应当在该C点与B之间，应当继续在CB之间找下一个C；如果t1t2，说明甲坐自行车多了，即C的实际位置应当在该C点与A之间，应当继续在AC之间找下一个C。如此反复，就会越来越接近真正的C点。由于，查找的区间越来越小，当上一个C与新的C之间的距离小于某个给定的误差范围时，就可以认为找到了C。,函数框架,#define ERR 20double putLen(double pf,double pt)double lenth,ed,dc,t1,t2;lenth=(pf+pt)/2;ed=（lenth-lenth/b*a）/(a+b)*a;dc=（lenth-l

16、enth/b*a）/(a+b)*b;t1=lenth/b+(S-lenth)/a;t2=lenth/b+ed/a+dc/b+(S-lenth)/b;if(abs(t1-t2)t2)putLen(pf+pt)/2,pt);if(t1 t2)putLen(pf,(pf+pt)/2);,3.使用优选法代替二分法,优选法比二分法具有较快的收敛性。用优选法代替二分法，就是用0.618代替0.5。,三、程序,#include#include#define S 120000#define ERR 200#define a 30#define b 70double putLen(double pf,doubl

17、e pt)double lenth,ed,dc,t1,t2;lenth=(pf+pt)*0.618;ed=（lenth-lenth/b*a）/(a+b)*a;dc=（lenth-lenth/b*a）/(a+b)*b;t1=lenth/b+(S-lenth)/a;t2=lenth/b+ed/a+dc/b+(S-lenth)/b;if(abs(t1-t2)t2)putLen(pf+pt)*0.618,pt);if(t1 t2)putLen(pf,(pf+pt)*0.618);void main()printf(“n甲乘自行车行%7.1f米后步行，三人到B的时间最短“，putLen(0,S)）;,四

18、、运行结果,甲乘自行车行74160.0米后步行，三人到B的时间最短。,五、编程练习,1.邮局的位置。某小区有n户居民，各家的人口分别为W1、W2、Wn。现要修建一所邮局，若要使所有的人都方便，邮局应建在什么位置上？提示：设邮局的位置为P(xp,yp)；第i家的位置为pi，它与邮局之间的距离为d（p，pi）。2.棋子移动问题。（1）起始条件：有黑白各n个棋子（n4）排成一行，开始时白色棋子全部在左边，黑色棋子全部在右边。（2）移动规则：每次移动两个棋子，颜色不限；可以移动到左边的空位，也可以移动到右边的空位上；不能调换两个棋子的左右位置；每次移动必须跳过若干棋子（不可平移）。（3）要求：最后移成

19、黑白相间的一行。试给出移动程序。,五、编程练习（续）,3.大整数乘法问题描述：通常在计算机中，整数的乘法运算都是当作基本运算进行的。但是，它的前提是计算机硬件要能够对参加运算的整数以及积直接表示和处理。这当然是有限度的。为了处理很大的整数，一种办法是用浮点数来表示，但只能近似地表示它们的大小，并且计算结果中的有效数字也受到限制。另一种办法就是用软件的方法来实现大整数的算术运算，实现大整数的精确表示并在计算结果中得到所有位数上的数字。程序设计要求：设计一个有效的算法，进行两个n位大整数的乘法运算。提示：设X和Y分别是m位和n位的整数，为了计算它们的乘积X*Y，可以用大小分别为m-1和n-1的两个

20、整型数组，存储这两个整数中的各位。存储时，将个位、十位、百位、千位、万位，分别存储在下标为0、1、2、3、4、的数组元素中。另外再定义一个大小为（m-1）*（n-1）的整型数组，存放积的各位。这样，就可以按照小学中学习的算式方法来进行计算了。设用x、y、z分别存储整数X、Y和积，则可以先用下面的算法：用y0依次去乘数组x的元素，把积中的个位存入z0，把十位存入z1；用y1依次去乘数组x的元素，积与z1相加，再把个位存入z1，把十位存入z2；用yi依次去乘数组x的元素，积与zi相加，再把个位存入zi，把十位存入zi+1；这就说明，当规模较小时，问题非常容易求解。这里，考虑另一种思路，就是将X和Y

21、用二分求解。具体算法请读者自己考虑。,五、编程练习（续）,4.循环赛日程表 问题描述：设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：每个选手必须与其他n-1个选手各赛一次 每个选手一天只能参赛一次 循环赛在n-1天内结束。程序设计要求：请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手。其中1in，1jn-1。提示：按分治策略，可以将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简

22、单。这时只要让这两个选手进行比赛就可以了。图4.5列出的正方形表是8个选手的比赛日程表。,首先考虑排选手14前3天的比赛日程（如左上角一块）和选手58前3天的比赛日程（如左下角一块）；然后，将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这样就分别安排好了选手14和选手58在后4天的比赛日程。按此思路容易构思具有任意多个选手的比赛日程表。,图4.5 八个选手的比赛日程表,4.2 回溯算法,经常玩象棋的人，最不愿意对手悔棋。所谓悔棋，就是下棋下到感觉情况不妙时，要退回到前一步的状态上重新考虑。有时，退一步不行，还可能要退回几步。这种不良的棋风，用

23、到解题上却倒是一种非常有用的方法，称之为回溯（back tracking）。它是一种系统的地穷举问题解答的方法。使用回溯策略一般有如下的过程：,回溯策略的过程：（1）为问题定义一个解空间（solution space），这个空间必须至少包含问题的一个解（可能是最优的）；（2）以某个已知解（输入）为根，把解空间组织成树结构；（3）从树根出发，按照深度优先方法，对解空间的每个状态进行搜寻，直到找到需要的解或最终得到没解的结论为止；（4）在搜寻过程中，发现在所在的支路上无法再向前推进时，即返回到前一个节点，找没有搜寻过的支路进行搜寻。回溯过程可以用递归方法实现，也可以用迭代方法实现。,4.2.1 迷

24、宫问题,一、问题,在远古时候的克里特岛上，有一座有无数宫殿的迷宫宫殿的通道曲折复杂，进去很难找到出口。统治这个地方的国王在宫殿深处供养着一头怪兽弥诺陶罗斯牛。为了养活它，国王要希腊的雅典每9年进贡7对青年男女来。当第四次轮到雅典进贡时，雅典国王爱琴的儿子狄修斯王子已长成英俊青年，他不忍人民再遭受这种灾难，决定跟随不幸的青年男女一起去克里特岛杀死弥诺陶罗斯。在克里特岛，英俊的王子以机智和勇敢赢得了聪明的克里特公主的芳心。在公主的帮助下，狄修斯王子终于杀死怪物，顺利地走出宫殿。试用C程序找出一条探索迷宫的路径。,二、克里特方法,1.基本思路,为了说明该题的解法，首先来看看聪明的克里特公主教给狄修斯

25、王子探索迷宫的方法。公主送给狄修斯王子一把剑和一团线，要狄修斯按照下面的规则边走边放线：凡是走过的路径，都铺上一条线；每到一个岔口，先走没有放过线的路走；凡是铺有两条线的路一定是死胡同，不应再走。这个规则说明了一种回溯算法：向一个特定的方向探索前进，找不到解，就返回去，找另一条可能的路径往下搜索；凡是已搜索过的状态（位置），不再搜索。这种算法称为回溯（backtracking）。回溯是人们求解复杂问题时常用的一种方法。,2.迷宫的表示数据结构设计,迷宫的表示方法很多，最直接的方法是采用矩阵模拟法，即把迷宫用一个二维数组来模拟。在图4.6中，把(a)所示的迷宫模拟为图（b）所示的二维数组，用“0

26、”表示可通行部分，用“2”表示不可通行部分。后面的解法都是基于该矩阵的。除此之外，还有状态图、邻接矩阵等表示法，它们都要使用二维数组，这里暂不介绍。,(a)一个迷宫（b）模拟矩阵,图4.6 迷宫的模拟表示,3.算法,用数组maze存储迷宫矩阵，则迷宫问题的求解，可以归结为在任一个节点mazeij上，向四个候选节点：mazeij+1、mazei+1j、mazeij-1、mazei-1j的搜索前进过程。如图4.7所示。,图4.7 一个节点（i，j）上的搜索,这样将会出现如下三种情形：,（1）若4个候选节点中有3个节点为不可到达节点，则称该节点为“死点”（死胡同尽头）。为防止以后再搜索该节点，应将其

27、设置为不可到达点令mazeij=2，相当于狄修斯放了第2条线，也相当于将该点垒住。判断死点并进行处理的算法为：if(mazei-1j=2,（2）若该点不为死点，下一步将向一个候选节点搜索，称其为已通过点，记以标志：令mazeij=1，相当于狄修斯放了一条线。同时，不管该点是否岔口，一律先选未通过节点，即先选值为0的节点走，再走值为1的点走，算法为：,if(mazei-1j=0)/*按顺时针顺序先走没有走过的点*/i-;mazeij=1;else if(mazeij+1=0)j+;mazeij=1;else if(mazei+1j=0)i+;mazeij=1;else if(mazeij-1=0

28、)j-;mazeij=1;else if(mazei-1j=1)/*按顺时针顺序走走过的点*/mazeij=2;i-;else if(mazeij+1=1)mazeij=2;j+;else if(mazei+1j=1)mazeij=2;i+;else if(mazeij-1=1)mazeij=2;j-;,这里没有将原来为1的点置2，是因为岔口往往会经过多次，置2就将其当作直通处理了，使某些支路无法搜索。,（3）探索结束的条件为：i=Ei&j=Ej，即继续探索的条件为：iEi|jEj。,4.程序,#include void main()int maze7=2,2,2,2,2,2,2,2,0,0,

29、0,0,0,2,2,0,2,0,2,0,2,2,0,0,2,0,2,2,2,2,0,2,0,2,2,2,0,0,0,0,0,2,2,2,2,2,2,2,2;int Si=1,Sj=1,Ei=5,Ej=5;/*入口与出口*/int i=Si,j=Sj;int count=0;/*记录搜索步数变量*/while(jEj|iEi)/*在点（i,j）上探索，不达出口时，反复进行搜索*/*处理死点*/if(mazei-1j=2,4.程序（续）,/*按顺时针顺序先走没有走过的点*/if(mazei-1j=0)i-;mazeij=1;else if(mazeij+1=0)j+;mazeij=1;else i

30、f(mazei+1j=0)i+;mazeij=1;else if(mazeij-1=0)j-;mazeij=1;/*按顺时针顺序走走过的点*/else if(mazei-1j=1)mazeij=2;i-;else if(mazeij+1=1)mazeij=2;j+;else if(mazei+1j=1)mazeij=2;i+;else if(mazeij-1=1)mazeij=2;j-;count+;/*记录走过点数*/,4.程序（续）,/*打印探索结果*/for(i=0;i=6;i+)for(j=0;j=6;j+)printf(%d,mazeij);printf(n);printf(coun

31、t=%dn,count);/*打印搜索步数*/,5.执行结果,2,2,2,2,2,2,22,1,2,2,2,2,22,1,2,2,2,2,22,1,1,2,2,2,22,2,1,2,2,2,22,0,1,1,1,1,22,2,2,2,2,2,2 count=19结果矩阵中的“1”为搜索后，找到的穿过迷宫的路线；“0”为未搜索过的节点。,三、使用堆栈组织搜索过程,1.基于堆栈的回溯,求解本题的基本算法是回溯，而基于堆栈的回溯可以使人思路更为清晰。其基本思路如图4.8所示，把对迷宫的搜索，看成一棵搜索树的生成过程：（1）首先将根节点（入口处）压入堆栈；（2）按照下面的规则考察栈顶节点（图中灰色节点

32、）的可扩展性（即前面还有路可走），直到找到一个解或得出无解（堆栈空即返回到入口）的结论为止：可扩展，则将下一层的各个可能的节点按照某种顺序（如顺时针）压入堆栈；不可扩展，则将栈顶节点弹出（图中黑色的节点），继续考察下一个节点。这下一个节点可能是同层的兄弟节点，也可能是一个上层节点（回溯）。,图4.8 基于堆栈的回溯算法,与克里特算法相比,（1）往栈中压入一个节点，就说明该节点可达，相当于铺了第1条线。为了避免以后对该点重复压入，应在压入的同时，将该节点的置1，即只压入节点值为0的节点。（2）将栈顶节点弹出，说明该节点是死节点，相当于铺了第2条线。为了将来能在迷宫矩阵中表明该点已经被探索过，将其

33、置一个特殊的数3。,2.定义数据结构,基于栈的迷宫探索，需要建立两种基本的数据结构：表示迷宫的数据结构这在前面已经介绍过了，就是用矩阵（二维数组）表示。用于回溯控制的数据结构堆栈。这里首先考虑如何建立基于数组的堆栈。（1）模拟迷宫的数据结构int maze7=2,2,2,2,2,2,2,2,0,0,0,0,0,2,2,0,2,0,2,0,2,2,0,0,2,0,2,2,2,2,0,2,0,2,2,2,0,0,0,0,0,2,2,2,2,2,2,2,2;int Si=1,Sj=1,Ei=5,Ej=5;/*入口与出口*/,（2）迷宫中某个节点的表示和探索栈/*在type.h函数中表示*/#defi

34、ne N 100typedef struct Node int x,y;/*节点位置*/int nodeState;/*节点状态*/MAZE_NODE;typedef struct ExploreStack MAZE_NODE explStackN;/*数组栈*/EXP_STACK;,3.算法设计初步,（1）扩展栈顶节点的算法void mazeExpand(EXP_STACK*s)获取栈顶节点在迷宫中的坐标x,y;if(探索栈空)printf(“此迷宫找不到出口，探索过程如下：)；return;else if(栈顶节点位于出口)printf(“探察结束，探察过程如下：“)；return;els

35、eif(死点)置以死点标记,重新获取栈顶节点进行拓展；else 先将此节点压栈;将此节点周围值为0（不是墙以及未压过栈）的节点压栈，同时将它们的置1；重新获取栈顶节点进行拓展；,程序框架,（2）程序框架定义迷宫矩阵为静态数组定义入口、出口坐标定义探索栈定义栈的压入函数定义栈的弹出函数定义栈顶节点扩展函数定义迷宫矩阵打印函数void main()从入口节点开始调用栈顶节点扩展函数；调用迷宫矩阵打印函数；,4.程序设计,（1）push操作和pop操作,/*在stack.h函数中*/int top=-1;EXP_STACK*s;MAZE_NODE*pop(EXP_STACK*s)/*pop操作*/M

36、AZE_NODE*npop;if(top=-1)printf(stack underflow!);exit(-1);else*npop=(*s).explStacktop;top=top-1;return npop;,（1）push操作和pop操作（续）,/*在stack.h函数中*/int top=-1;EXP_STACK*s;MAZE_NODE*pop(EXP_STACK*s)/*pop操作*/MAZE_NODE*npop;if(top=-1)printf(stack underflow!);exit(-1);else*npop=(*s).explStacktop;top=top-1;re

37、turn npop;,（2）栈顶节点扩展函数设计,/*在expand.h函数中*/int Ei=5,Ej=5;/*判断是为出口*/void mazeExpand(MAZE_NODE*old)extern maze7;/*引用性声明*/MAZE_NODE*new1;int i,j;MAZE_NODE end;end.x=Ei;/*出口的设置*/end.y=Ej;end.nodeState=0;if(top=-1)/*探索栈空*/printf(n此迷宫找不到出口，探索过程如下：n);return;,（2）栈顶节点扩展函数设计（续）,else if(*old).x=end.x,（2）栈顶节点扩展函数

38、设计（续）,else if(mazeij+1=2,（2）栈顶节点扩展函数设计（续）,else mazeij=1;push(old);/*不是死点,则压入栈*/*针对不同情况，分别进行处理压栈*/if(mazei-1j=0)(*new1).x=i-1;(*new1).y=j;(*new1).nodeState=1;mazei-1j=1;push(new1);if(mazeij+1=0)(*new1).x=i;(*new1).y=j+1;(*new1).nodeState=1;mazeij+1=1;push(new1);,（2）栈顶节点扩展函数设计（续）,if(mazei+1j=0)(*new1)

39、.x=i+1;(*new1).y=j;(*new1).nodeState=1;mazei+1j=1;push(new1);if(mazeij-1=0)(*new1).x=i;(*new1).y=j-1;(*new1).nodeState=1;mazeij-1=1;push(new1);/*else*/mazeExpand(pop(s);/*扩展新栈顶节点*/,（3）输出函数,/*在print.h函数中*/prnt()int i,j;printf(n);for(i=0;i=6;i+)for(j=0;j=6;j+)printf(%d,mazeij);printf(n);,四、测试程序,#inclu

40、de#include type.h#include stack.h#include expand.h#include print.hint maze7=2,2,2,2,2,2,2,2,0,0,0,0,0,2,2,0,2,0,2,0,2,2,0,0,2,0,2,2,2,2,0,2,0,2,2,2,0,0,0,0,0,2,2,2,2,2,2,2,2;/*初始化迷宫矩阵*/int Si=1,Sj=1;/*入口坐标*/MAZE_NODE*start;main()(*start).x=Si;(*start).y=Sj;/*入口的初始化*/(*start).nodeState=1;mazeSiSj=1;p

41、ush(start);mazeExpand(start);/*从入口节点开始调用栈顶节点扩展函数*/prnt();/*调用迷宫矩阵打印函数*/,五、编程练习,1.三个猎人杂技团的三位训兽师带着三只猴子过河，只有一条最多只能乘二人的船，人猴体重相当，且猴子也会划船。在穿梭过河的过程中，若留在岸上的猴子数多于人数，猴子就会逃跑。请为三位训兽师设计一个安全的渡河方案。2.自然数的拆分：任何一个大于1的自然数N，总可以拆分为若干个自然数之和，并且有多种拆分方法。例如自然数5，可以有如下一些拆分方法：5=1+1+1+1+15=1+1+1+25=1+2+25=1+1+35=1+4（与5=4+1看成同一种拆

42、分）5=2+3请设计一个对任意自然数，找出所有拆分方法的程序。,五、编程练习（续）,3.机器设计问题：某机器由n 个部件组成，每一个部件可从3个投资者那里获得。令wij 是从投资者j 那里得到的零件i 的重量，cij 则为该零件的耗费。编写一个回溯算法，找出耗费不超过c的机器构成方案，使其重量最少。4.邮票问题：设想一个国家发行的几种面值不同的邮票。若每个信封上至多只允许贴m枚邮票。当邮资从1开始，在增量为1的情况下，请给出可能获得的邮资值的最大连续区及获得此区域的各种面值的集合。如，对于n=4，m=5，有面值(1，4，12，21)四种邮票。用回溯法求解本题。,5.控制方格棋盘游戏：如图4.9

43、所示的55的方格棋盘，若在某一方格内放入一个黑子，则与该方格相邻的上、下、左、右4各方格中都不可再放黑子。于是，在棋盘的X个位置各放一个黑子，就可以控制整个棋盘。请设计在棋盘上放7个黑子就可以控制整个棋盘的所有方案。,图4.9 控制方格棋盘游戏,五、编程练习（续）,6.魔板问题：Rubik先生发明了一种玩具，称为魔板。它由8块同样大小的方块组成，这8个方块分别涂以不同的颜色或编号。它有3种基本玩法，以图4.10（a）为初始状态这3种玩法分别如图4.10（b）、（c）、（d）所示。应用三种基本操作，可以由一种状态到达另一种状态。,（a）魔板的一个初始状态,（b）上下行互换,（c）两行同时循环右移

44、一格,（d）中间4块顺时针旋转一格,图4.10 魔板,请编写一个程序，通过一系列基本操作，可以将魔板从原始状态变为一个输入的目标状态。,五、编程练习（续）,7.四色问题：在彩色地图中，相邻区块要用不同的颜色表示。那么印制地图时，最少需要准备几种颜色就能达到相邻区块要用不同的颜色表示的要求呢？一百多年前，英国的格色离提出了最少色数为4的猜想（4-colours conjecture）。为了证实这一猜想，许多科学家付出了艰巨的劳动，但一直没有成功。直到1976年，美国数学家K.Appl和M.Haken借助电子计算机才证明了这一猜想，并称之为四色定理。请按四色定理为图4.11所示地图进行着色。,图4

45、.11 一张地图,4.3 贪心策略,贪心策略（greedy method）是一种企图通过局部最优达到全局最优的策略，犹如登山，并非一开始就选择出一条到达山顶的最佳路线，而是首先在视力能及的范围内，看中一个高处目标，选择一条最佳路径；然后在新的起点上，再选择一条往上爬的最佳路径；企图通过每一阶段的最佳路径，构造全局的最佳路径。也就是说，贪心策略总是不断地将原问题变成一个相似、而规模更小的问题，然后做出当前看似最好的局部意义上的最优选择。显然，贪心策略不能保证对所有的问题求得的最后解都是最优的，特别是不能用来求最大或最小解问题。但是许多情况下，用贪心策略可以得到最优解的接近结果。因此，初学者应当通

46、过分析和经验积累，了解哪些问题适合用贪心策略，并掌握如何选择合适的贪心策略。,4.3.1 旅行费用问题,一、问题描述,一个游客要到如图4.12（a）所示的A、B、C、D、E五个景点旅行。图中标出了五个景点之间的交通费用。试问，该游客从A出发，如何以最小费用走过每一个景点最后返回A？,图4.12（a）旅行费用拓扑,二、解题策略,按照贪心策略，在局部寻优的过程可以用图4.12（b）表示，得到的路径为A-B-E-C-D-A，总费用为10+30+20+12+80=152。显然，这一结果并非最优。因为，最优路径为A-B-E-D-C-A，总费用为10+30+30+12+21=103。,（a）旅行费用拓扑,

47、（b）贪心法求解问题,图4.12 旅行费用问题,程序框架,1.数据结构,（1）费用网络描述(用图的邻接矩阵的描述)：int expense4=0,10,21,80,50,10,0,36,43,30,21,36,0,12,20,80,43,12,0,30 50,30,20,30,0;（2）定义枚举变量 enum scenesa,b,c,d,e;这样，就会形成如下对应关系：expenseab expense01 10expenseac expense02 21expensead expense03 80expensebc expense04 50expensebc expense12 36expe

48、nsebd expense13 43expenseae expense14 30,2.贪心过程,初始化所有节点的费用标志；设置出发节点V；for(i=1;i=n-1;i+)s=从V至所有未曾到过的景点中费用最少的景点；累加费用；V=s；/*新的起点*/设置V的已访问标志；最后一个景点返回第一个景点，累加费用；,三、程序的实现,#define N 5/*节点个数*/main()int expenseNN=0,10,21,80,50,10,0,36,43,30,21,36,0,12,20,80,43,12,0,30,50,30,20,30,0;enum scenesa,b,c,d,e;enum s

49、cenes v,s;enum scenes start,j;unsigned int sum=0,min;int flagN=0,0,0,0,0;int i;v=a;/*设置出发节点*/start=v;,三、程序的实现（续）,for(i=1;i=N-1;i+)min=65535;/*设置一个尽量大的值*/for(j=a;j=N-1;j+)if(flagj=0,四、程序测试,（1）测试1当v=a时，sum=152（2）测试2当v=b时，sum=103（3）测试3当v=c时，sum=103,五、编程练习,用贪心法求解下列问题，并分析这些问题用贪心法能否得到整体最优解。1.背包问题：一个强盗进入一家

50、商店要拿走一批物品。强盗只有一个最多只能装W斤的背包。他拿东西的原则是背一包最值钱的东西。该商店中有N件物品，每件物品的重量和价值都是不一样的：第i件物品值vi元，重wi斤（1iN）。这就是著名的背包问题。子问题1：当每一件物品都不可分割时，强盗只能对某件物品选择带走，还是不带走。这就是0-1背包问题。子问题2：当每一件物品都可分割时，强盗只能对某件物品选择带走，还是不带走。这就是部分背包问题。要求分别考虑下列策略：（1）每次挑选价值最大的物品装入背包，得到的结果是否最优？（2）每次挑选所占空间最轻的物品装入，是否能得到最优解？（3）每次选取单位容量价值最大的物品，成为解本题的策略。,五、编程