算法设计与分析实验 .pdf

《算法设计与分析实验 .pdf》由会员分享，可在线阅读，更多相关《算法设计与分析实验 .pdf（44页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、算法设计与分析选做实验名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 44 页 -实验一单链表的建立插入及删除 实验目的 1掌握单链表的建立插入及删除的算法；2进一步熟悉指针的用法；预习要求 1.认真阅读教材或参考书,掌握线性表算法的基本思想；2.写出求解本实验的程序；3.设计好相应的测试用例。类型定义 typedef struct Lnodeint data;struct Lnode*next;Lnode,*linklist;实验提示 void create(link*h,int n)/创建单链表link p,q;int i;p=(link)malloc(sizeof(node

2、);p-next=null;*h=p;q=p;for(i=1;idata);p-next=null;q-next=p;q=p;void print(link h)/输出单链表link p;p=h-next;while(p)printf(%d ,p-data);p=p-next;void insertlist(linklist*L,int i,int e)/在单链表的第i 个元素之前插入元素值为e 的结点 void dellist(linklist*L,int i,int*e)/删除单链表的第i 个结点，被删结点通过 e 返回 实验步骤 名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，

3、共 44 页 -1.先用插表头或插表尾的方法建立单链表并输出，并测试你的程序，直至正确为止；2.再进行插入和删除程序的设计；3.将你的程序和实录的界面存盘备用。实验报告要求 1.阐述实验目的和实验内容；2.提交模块化的实验程序源代码；3.简述程序的测试过程，提交实录的输入、输出文件；4.提交思考与练习题的代码和测试结果。思考与练习 怎样用链表实现循环队列。名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 44 页 -实验二多项式加法 实验目的 1熟练掌握在单链表中进行结点的插入和删除操作；2进一步熟悉指针的用法；预习要求 1.认真阅读教材或参考书,掌握线性表算法的基本思想；2.写出

4、求解本实验的程序；3.设计好相应的测试用例。类型定义 typedef struct Lnodeint coef,exp;struct Lnode*next;Lnode,*linklist;实验提示 void create(link*h,int n)/创建一元多项式link p,q;int i;p=(link)malloc(sizeof(node);p-next=null;*h=p;q=p;for(i=1;icoef,&p-exp);p-next=null;q-next=p;q=p;void print(link h)/输出单链表link p;p=h-next;while(p)printf(%d

5、,%d,p-coef,p-exp);p=p-next;void addlist(linklist*A,linklist B)/将 A和 B相加并通过A返回 实验步骤 1 先用插表尾的方法建立一元多项式，并将一元多项式输出，并测试你的程序，直至正确为止；2 进行一元多项式相加程序的设计；名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 44 页 -3 将你的程序和实录的界面存盘备用。实验报告要求 1阐述实验目的和实验内容；2提交模块化的实验程序源代码；3简述程序的测试过程，提交实录的输入、输出文件；4提交思考与练习题的代码和测试结果。思考与练习 写出约瑟夫问题的求解算法，即n 个人坐

6、成一圈，报m出圈，输出最后一个报m的人。名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 44 页 -实验三集合的表示与操作算法设计实验目的 .了解集合的不同表示方法,掌握集合的树结构表示方法;.掌握树结构表示下集合的并运算与查找算法;.编程实现集合的表示与操作算法.预习要求 1.认真阅读教材内容,熟悉树结构表示的原理和操作算法;2.设计和编制实验程序.参考数据类型或变量 typedef ElemType int/*实型或任意其它元素类型*/typedef struct ElemType elem;int tag;/*根节点为负的整数,表示该集合的基数的负值,否则为父节点索引指针*

7、/NODE;NODE*set;/*用动态存储分配实现集合的树表示与存储*/参考子程序接口与功能描述 void InitSet(NODE*set)功能:根据集合的基数动态分配存储,输入各元素,初始化子集森林.int Find(NODE*set,ElemType elem)功能:在数组 set中顺序查找元素elem,如果不成功,返回-1;否则,使用带压缩规则的查找算法,返回所在子集的根节点索引.int Union(NODE*set,ElemType elem1,ElemType elem2)功能:应用 Find 算法首先找到elem1 和 elem2 所在的子集,然后应用带加权规则的并运算算法合并

8、两个子集.不成功时,返回-1;否则,返回并集的根节点索引.实验步骤 .设计 Find 的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;.设计 Union 的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;.待各功能子程序调试完毕,去掉测试程序,将你的程序整理成功能模块存盘备用.实验报告要求 .阐述实验目的和实验内容;.提交实验程序的功能模块;.记录最终测试数据和测试结果。思考题 试用 C 语言实现集合的位向量表示,并设计相应的并、交与查找运算算法.名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 44 页 -实验四迷宫问题求解 实验目的 1熟悉栈用法；2掌

9、握回朔法及试探法的程序设计；预习要求 1.认真阅读教材或参考书,掌握栈用法的用法；2.写出求解本实验的程序；3.设计好相应的测试用例。实验提示 设迷宫中数组的元素为1 表示该点道路主的阻塞，为0 表示可通。设 maze11为入口，mazemn 为出口。在 maze11和 mazemn 的元素值必为0。在任意时刻，老鼠在迷宫中的位置可以用所在点的行下标与列下标（i,j）来表示，这样，老鼠在迷宫中的某点mazeij时，其可能的运动方向有八个。下图+表示某时刻老鼠所在的位置（i,j）,相邻的八个位置分别标以N、NE、E、SE、S、SW、W、NW（分别代表+点的北、东北、东、东南、南、西南、西、西北方

10、向）；同时，相对于（i,j），这八个相邻位置的坐标的值都可以计算出来。但是，并非迷宫中的每一个点都有八个方向可走，四个角上就只有三个方向可供选择，边上只有五个方向可供选择。为了不在算法中每次都去检查这些边界条件，在迷宫外面套上一圈，其元素值均为1。NW（I-1，J-1）N（I-1，J）NE（I-1，J+1）W（I，J-1）+（I，J）E（I，J+1）SW（I+1，J-1）S（I+1，J）SE（I+1，J+1）为了简化算法，根据上图所示的位置（i,j）与其相邻的八个位置的坐标关系，建立一个下图所示的表move,表中给出相对于位置（I,j）的八个方向上的i 与 j 的增量值。Move -1 0-1

11、 1 0 1 1 1 1 0 1-1 0-1-1-1 若老鼠在（i,j）位置，要进入SW 方向(g,h)点，则由该增量值表来修改坐标。g=i+move50;h=j+move51;例如：若（i,j）为（3，4），则 SW 的相邻点的坐标为（3+1，4-1）。在每个位置上都从N方向试起，若不通，则顺时针方向试NE方向，其余类推。名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 44 页 -当选定一个可通的方向后，要把目前所在的位置以及所选的方向记录下来，以便往下走时可依次一点一点退回来，每退一步后接着试在该点未试过的方向。为了避免走回到已经进入过的点，mazeij=2.为了记录当前位置

12、以及该位置上所选择的方向数需设一个堆栈。#define m 6#defing n 9 void path()int mazem+2n+2;int move82;int s543;int top=0;int i,j,k,pf=0;for(i=0;im+2;+i)for(j=0;jn+2;+j)scanf(“%d”,&mazeij);maze11=2;stop0=1;stop1=1;stop2=0;+top;while(top!=0&f=0)-top;i=stop0;j=stop1;k=stop2;while(k8)g=i+movek0;h=j+movek1;if(g=m&h=n&mazegh=0

13、)for(p=0;pm=n;for(j=0;jdataj.firstadj=NULL;g-dataj.vex=j;for(j=0;jadjvex=k;p-next=NULL;if(g-datai.firstadj=NULL)g-datai.firstadj=p;else q=g-datai.firstadj;while(q-next)q=q-next;q-next=p;/*向图的深度优先遍历*/void dfs(adjlist g,int v)node*p;printf(%3d,v);visitedv=1;p=g.datav.firstadj;while(p)if(visitedp-adjve

14、x=0)dfs(g,p-adjvex);p=p-next;/*图的广度优先遍历程序*/*void bfs(adjlist g,int v)*/*定义空队列*/*int Q100;int front=0,rear=0;node*p;visitedv=1;printf(%3d,v);Qrear+=v;while(front!=rear)v=Qfront+;p=g.datav.firstadj;while(p)if(visitedp-adjvex=0)visitedp-adjvex=1;printf(%3d,p-adjvex);Qrear+=p-adjvex;p=p-next;名师资料总结-精品资料

15、欢迎下载-名师精心整理-第 12 页，共 44 页 -*/void print(adjlist g)int i;node*p;for(i=0;iadjvex);p=p-next;printf(n);实验步骤 1先建立图的邻接表，并将邻接表输出，并测试你的程序，直至正确为止；3 进行深度优先遍历和广度优先遍历；4 将你的程序和实录的界面存盘备用。实验报告要求 1 阐述实验目的和实验内容；2 提交模块化的实验程序源代码；3 简述程序的测试过程，提交实录的输入、输出文件；4提交思考与练习题的代码和测试结果。思考与练习 写出图的邻接矩阵表示法的定义，并实现求最短路径的算法。名师资料总结-精品资料欢迎下

16、载-名师精心整理-第 13 页，共 44 页 -实验七哈希表的设计 实验目的 1掌握的哈希表定义和存储2掌握查找常用方法及过程3实现哈希表的综合操作 预习要求 1认真阅读和掌握本实验的算法。2上机将本算法实现。3保存和打印出程序的运行结果，并结合程序进行分析。类型定义#define MAXSIZE 12/哈希表的最大容量，与所采用的哈希函数有关enum BOOLFalse,True;enum HAVEORNOTNULLKEY,HAVEKEY,DELKEY;/哈希表元素的三种状态，没有记录、有记录、有过记录但已被删除typedef struct/定义哈希表的结构int elemMAXSIZE;/

17、数据元素体HAVEORNOT elemflagMAXSIZE;/元素状态标志，没有记录、有记录、有过记录但已被删除int count;/哈希表中当前元素的个数HashTable;typedef struct int keynum;/记录的数据域，只有关键字一项Record;实验提示 void InitialHash(HashTable&H)/哈希表初始化 void PrintHash(HashTable H)/显示哈希表所有元素及其所在位置 BOOL SearchHash(HashTable H,int k,int&p)/在开放定址哈希表H中查找关键字为k 的数据元素，若查找成功，以p 指示/

18、待查数据元素在表中的位置，并返回True；否则，以p 指示插入位置，并/返回 False BOOL InsertHash(HashTable&H,Record e)/查找不成功时插入元素e 到开放定址哈希表H中，并返回True，否则返回False BOOL DeleteHash(HashTable&H,Record e)/在查找成功时删除待删元素e，并返回True，否则返回False int Hash(int kn)名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 44 页 -/哈希函数：H(key)=key MOD 11 return(kn%11);实验步骤 1.先将哈希表初始

19、化并显示哈希表所有元素及其所在位置，并测试你的程序，直至正确为止；2.在开放定址哈希表中查找关键字为的数据元素；3.查找不成功时插入元素到开放定址哈希表中。实验报告要求 1.阐述实验目的和实验内容；2.提交模块化的实验程序源代码；3.简述程序的测试过程，提交实录的输入、输出文件；4提交思考与练习题的代码和测试结果。思考与练习 写出约瑟夫问题的求解算法，即n 个人坐成一圈，报m出圈，输出最后一个报m的人。名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 44 页 -实验八Kruskal 算法的设计实验目的 .根据算法设计需要,掌握连通网的灵活表示方法;.掌握最小生成树的Kruska

20、l 算法;.基本掌握贪心算法的一般设计方法;.进一步掌握集合的表示与操作算法的应用.预习要求 .认真阅读算法设计教材和数据结构教材内容,熟习连通网的不同表示方法和最小生成树算法;.设计 Kruskal 算法实验程序.参考数据类型或变量 typedef NodeNumber int;/*节点编号*/typedef CostType int;/*成本值类型*/typedef ElemType NodeNumber/*实型或任意其它元素类型*/typedef struct int ElemType;int tag;NODE;typedef struct CostType cost;NodeNumbe

21、r node1,node2;EDGE;NODE set=1,-1,n,-1;/*节点集,n 为连通网的节点数*/EDGE es=values of e1,values of em;/*边集,m 为连通网的边数*/EDGE stn-1;/*最小生成树的边集*/参考子程序接口与功能描述 int Find(NODE*set,ElemType elem)功能:在数组 set中顺序查找元素elem,如果不成功,返回-1;否则,使用带压缩规则的查找算法,返回所在子集的根节点索引.int Union(NODE*set,ElemType elem1,ElemType elem2)功能:应用 Find 算法首先

22、找到elem1 和 elem2 所在的子集,然后应用带加权规则的并运算算法合并两个子集.不成功时,返回-1;否则,返回并集的根节点索引.void Sort(EDGE*es,int n)功能:用任意分类算法将连通图的边集按成本值的非降次序分类.void Kruskal(EDGE*es,int m,NODE*set,int n,EDGE*st)功能:对有 n 个节点,m 条边的连通网,应用 Kruskal 算法生成最小生成树,最小生成树的边存储在数组st 中.void Output(EDGE*st,int n)功能:输出最小生成树的各条边.实验步骤 1.设计测试问题,修改并调试程序,输出最小生成树

23、的各条边,直至正确为止;名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 44 页 -2.待各功能子程序调试完毕,去掉测试程序,将你的程序整理成功能模块存盘备用.实验报告要求 1.阐述实验目的和实验内容;2.阐述 Kruskal 算法的原理方法;3.提交实验程序的功能模块;4.提供测试数据和相应的最小生成树.思考与练习 1.设计由连通网初始边集数组生成最小堆的算法;2.设计输出堆顶元素,并将剩余元素调整成最小堆的算法;3.针对连通网初始边集最小堆表示,设计 Kruskal 算法;4.采用成本邻接矩阵表示连通网时,在剩余边中如何实现最小成本边的查找?采用成本邻接矩阵表示连通网时,用

24、 C 语言实现Prim 算法.名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 44 页 -实验九归并排序的分治策略设计实验目的 .熟悉二分检索问题的线性结构表示和二分检索树表示;.熟悉不同存储表示下求解二分检索问题的递归算法设计;.通过实例转换,掌握将递归算法转换成迭代算法的方法;.掌握应用递归或迭代程序设计实现分治法求解问题的抽象控制策略.预习要求 .认真阅读算法设计教材和数据结构教材内容,熟悉不同存储表示下求解二分检索问题的原理或方法;.针对线性结构表示和二分检索树表示设计递归算法;.参考教材和课堂教学内容,根据将递归算法转换成迭代算法的一般步骤将二分检索递归算法转换成相应

25、的迭代算法.算法或程序设计参考 线性结构int data10=/*10个互异的、无序的原始整数*/;typedef struct int s100;int top;STACK;int Partition(int*data,int low,int high)功能:将 datalow,high 进行快速分类划分,返回枢轴记录关键字的位置索引.int QSort1(int*data,int low,int high)功能:将 datalow,high 进行快速分类的递归算法.int QSort2(int*data,int low,int high)功能:将 datalow,high 进行快速分类的迭

26、代算法.int BSearch1(int*data,int key)功能:在 data数组中检索key 的二分检索递归算法,成功时返回位置索引,否则返回-1.int BSearch2(int*data,int key)功能:在 data数组中检索key 的二分检索迭代算法,成功时返回位置索引,否则返回-1.树结构typedef struct NODE int key;struct NODE*lch,*rch;TNODE,*BT;typedef struct Parameters BT*t;int key;BT f;BT*p PARA;typedef struct PARA s100;int t

27、op;STACK;int InsertBT(BT*t,int key)功能:在二分检索树t 中插入关键字为key 的元素,成功时返回1,否则返回 0.int TSearch1(BT*t,int key,BT f,BT*p)功能:用递归算法在二分检索树t 中查找关键字为key 的元素,成功时返回1,p 指向该元素节点,否则 p 指向查找路径上最后一个节点并返回0,f 指向 t 的双亲,其初始调用值为NULL.名师资料总结-精品资料欢迎下载-名师精心整理-第 18 页，共 44 页 -int TSearch2(BT*t,int key,BT f,BT*p)功能:用迭代算法在二分检索树t 中查找关键

28、字为key 的元素,成功时返回1,p 指向该元素节点,否则 p 指向查找路径上最后一个节点并返回0,f 指向 t 的双亲,其初始调用值为NULL.实验步骤 1.调试线性结构表示下的快速分类与二分检索递归程序,直至正确为止;2.调试线性结构表示下的快速分类与二分检索迭代程序,直至正确为止;3.待各功能子程序调试完毕,去掉测试程序,将程序整理成功能模块存盘备用.实验报告要求 1.阐述实验目的和实验内容;2.提交实验程序的功能模块;3.阐述将递归算法改写成迭代算法的一般方法;4.用类 C 语言阐述分治法递归与迭代实现抽象控制策略.思考与练习 1.怎样优化由递归程序改写的迭代程序?2.设计二分检索树的

29、构造与检索递归程序,并将其改写成相应的迭代算法.名师资料总结-精品资料欢迎下载-名师精心整理-第 19 页，共 44 页 -实验十哈夫曼编码的贪心算法设计实验目的 .根据算法设计需要,掌握哈夫曼编码的二叉树结构表示方法;.编程实现哈夫曼编译码器;.掌握贪心算法的一般设计方法。预习要求 1.认真阅读数据结构教材和算法设计教材内容,熟悉哈夫曼编码的原理;2.设计和编制哈夫曼编译码器。参考数据类型或变量 typedef ElemType char；typedef struct node int w;int flag;ElemType c;struct node*plink,*llink,*rlink

30、;char codem;Node;Node*numn,*root;参考子程序接口与功能描述 void SetTree(NODE*root)功能:从终端读入字符集大小n，以及 n 个字符和n 个权值，建立哈夫曼树void EnCode(Node*p)功能:利用已建好的哈夫曼树，对输入的正文进行编码void DeCode(void)功能:利用已建好的哈夫曼树，将输入的代码进行译码实验步骤 1.设计 SetTree的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;2.设计 EnCode 的 测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;3.设计 DeCode 的测试方案和程

31、序,输入测试数据,修改并调试程序,直至正确为止;4.将你的程序整理成功能模块存盘备用。实验报告要求 1.阐述实验目的和实验内容;2.提交实验程序的功能模块;3.记录最终测试数据和测试结果。思考题 1.试证明哈夫曼问题具有贪心选择性质；2.试证明哈夫曼问题具有最优子结构性质。名师资料总结-精品资料欢迎下载-名师精心整理-第 20 页，共 44 页 -实验十一递归与迭代程序设计实验目的 .熟悉二分检索问题的线性结构表示和二分检索树表示;.熟悉不同存储表示下求解二分检索问题的递归算法设计;.通过实例转换,掌握将递归算法转换成迭代算法的方法;.掌握应用递归或迭代程序设计实现分治法求解问题的抽象控制策略

32、.预习要求 .认真阅读算法设计教材和数据结构教材内容,熟悉不同存储表示下求解二分检索问题的原理或方法;.针对线性结构表示和二分检索树表示设计递归算法;.参考教材和课堂教学内容,根据将递归算法转换成迭代算法的一般步骤将二分检索递归算法转换成相应的迭代算法.算法或程序设计参考 线性结构int data10=/*10个互异的、无序的原始整数*/;typedef struct int s100;int top;STACK;int Partition(int*data,int low,int high)功能:将 datalow,high 进行快速分类划分,返回枢轴记录关键字的位置索引.int QSort

33、1(int*data,int low,int high)功能:将 datalow,high 进行快速分类的递归算法.int QSort2(int*data,int low,int high)功能:将 datalow,high 进行快速分类的迭代算法.int BSearch1(int*data,int key)功能:在 data数组中检索key 的二分检索递归算法,成功时返回位置索引,否则返回-1.int BSearch2(int*data,int key)功能:在 data数组中检索key 的二分检索迭代算法,成功时返回位置索引,否则返回-1.树结构typedef struct NODE in

34、t key;struct NODE*lch,*rch;TNODE,*BT;typedef struct Parameters BT*t;int key;BT f;BT*p PARA;typedef struct PARA s100;int top;STACK;int InsertBT(BT*t,int key)功能:在二分检索树t 中插入关键字为key 的元素,成功时返回1,否则返回 0.int TSearch1(BT*t,int key,BT f,BT*p)功能:用递归算法在二分检索树t 中查找关键字为key 的元素,成功时返回1,p 指向该元素节点,否则 p 指向查找路径上最后一个节点并返

35、回0,f 指向 t 的双亲,其初始调用值为NULL.名师资料总结-精品资料欢迎下载-名师精心整理-第 21 页，共 44 页 -int TSearch2(BT*t,int key,BT f,BT*p)功能:用迭代算法在二分检索树t 中查找关键字为key 的元素,成功时返回1,p 指向该元素节点,否则 p 指向查找路径上最后一个节点并返回0,f 指向 t 的双亲,其初始调用值为NULL.实验步骤 1.调试线性结构表示下的快速分类与二分检索递归程序,直至正确为止;2.调试线性结构表示下的快速分类与二分检索迭代程序,直至正确为止;3.待各功能子程序调试完毕,去掉测试程序,将程序整理成功能模块存盘备用

36、.实验报告要求 1.阐述实验目的和实验内容;2.提交实验程序的功能模块;3.阐述将递归算法改写成迭代算法的一般方法;4.用类 C 语言阐述分治法递归与迭代实现抽象控制策略.思考与练习 1.怎样优化由递归程序改写的迭代程序?2.设计二分检索树的构造与检索递归程序,并将其改写成相应的迭代算法.名师资料总结-精品资料欢迎下载-名师精心整理-第 22 页，共 44 页 -实验十二多段图问题的动态规划算法设计实验目的 1.掌握有向网的成本邻接矩阵表示法;2.能用程序设计语言实现多段图问题的动态规划递推算法;3.基本掌握动态规划法的原理方法.预习要求 1.认真阅读数据结构教材和算法设计教材,熟习有向网的成

37、本邻接矩阵表示法和动态规划求解多段图问题的递推原理;2.设计用动态规划算法求解多段图问题的数据结构和递推程序.参考数据类型或变量 typedef NodeNumber int;/*节点编号*/typedef CostType int;/*成本值类型*/CostType costnn=;/*成本邻接矩阵,n 为顶点数*/NodeNumber pathk;/*k 段图最短路径上的节点编号数组*/NodeNumber cur=-1;/*当前邻接节点*/参考子程序接口与功能描述 int FindForward(CostType*costn,NodeNumber i,NodeNumber cur)功能:

38、根据邻接矩阵查找节点i 的下一个前向邻接节点,成功时返回节点编号,否则返回-1;cur 为当前的前向邻接节点,第一次调用时其值为-1.int FindBackward(CostType*costn,NodeNumber i,NodeNumber cur)功能:根据邻接矩阵查找节点i 的下一个后向邻接节点,成功时返回节点编号,否则返回-1;cur 为当前的后向邻接节点,第一次调用时其值为-1.void FPath(CostType*costn,int k,int n,NodeNumber*path)功能:n 个节点的k 段图前向递推算法,path 存储最短路径节点序列.void BPath(Co

39、stType*costn,int k,int n,NodeNumber*path)功能:n 个节点的k 段图后向递推算法,path 存储最短路径节点序列.void OutPath(int k,NodeNumber*path)功能:输出 k 段图的最短路径序列,path存储最短路径节点序列.实验步骤 1.设计程序和测试数据,修改并调试程序,直至正确为止;2.应用设计的算法和程序输出给定多段图问题的最短路径序列;3.去掉测试程序,将你的程序整理成功能模块存盘备用.实验报告要求 1.阐述实验目的和实验内容;2.阐述求解多段图问题的动态规划递推原理;3.提交实验程序的功能模块;4.记录最终测试数据和测

40、试结果。名师资料总结-精品资料欢迎下载-名师精心整理-第 23 页，共 44 页 -思考与练习 1.试用 C 语言实现求有向网每对节点之间最短路径的数据结构和动态规划递推算法,要求算法能输出每条最短路径节点序列.试用动态规划法求解最长公共子序列问题：2.若给定序列X=x1,x2,xm，则另一序列Z=z1,z2,zk，是 X的子序列是指存在一个严格递增下标序列i1,i2,ik使得对于所有j=1,2,k 有：zj=xij。例如，序列Z=B，C，D，B是序列 X=A，B，C，B，D，A，B的子序列，相应的递增下标序列为2，3，5，7。给定 2 个序列 X和 Y，当另一序列Z 既是 X的子序列又是Y

41、的子序列时，称Z 是序列 X和 Y的公共子序列。给定2 个序列 X=x1,x2,xm 和 Y=y1,y2,yn，找出 X和 Y的最长公共子序列。名师资料总结-精品资料欢迎下载-名师精心整理-第 24 页，共 44 页 -实验十三作业调度问题 实验目的 1.熟悉多机调度问题的算法；2.进一步掌握贪心算法3.提高分析与解决问题的能力。预习要求 1.认真阅读教材或参考书,掌握贪心算法的基本思想；2.写出求解“作业调度”的程序；3.设计好测试用例。实验题 要求给出一种作业调度方案，使所给的n 个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中

42、断处理。作业不能拆分成更小的子作业。实验提示 1.把作业按加工所用的时间从大到小排序；2.如果作业数目比机器的数目少或相等，则直接把作业分配下去；3.如果作业数目比机器的数目多，则每台机器上先分配一个作业，如下的作业分配时，是选那个表头上s 最小的链表加入新作业。typedef struct Job int ID;/作业号 int time;/作业所花费的时间Job;typedef struct JobNode/作业链表的节点 int ID;int time;JobNode*next;JobNode,*pJobNode;typedef struct Header/链表的表头 int s;pJo

43、bNode next;Header,pHeader;int SelectMin(Header*M,int m)int k=0;for(int i=1;im;i+)if(Mi.smk.s)k=i;return k;名师资料总结-精品资料欢迎下载-名师精心整理-第 25 页，共 44 页 -实验步骤 1 先用贪心算法求解该问题，并测试你的程序，直至正确为止；2 针对问题实例，实录运行时的输入、输出文件；3 将你的程序和实录的界面存盘备用。实验报告要求 阐述实验目的和实验内容；1 提交模块化的实验程序源代码；2 简述程序的测试过程，提交实录的输入、输出文件；3 鼓励对实验内容展开讨论，鼓励提交思考与

44、练习题的代码和测试结果。思考与练习 试用贪心算法求解“01 背包”问题，并分析求解时存在的问题。名师资料总结-精品资料欢迎下载-名师精心整理-第 26 页，共 44 页 -实验十四搜索顺序的选择 实验目的 1熟悉搜索类问题的基本求解方法；2了解选择搜索顺序的基本原则；3了解启发式搜索的优点和局限性。预习要求 1认真阅读教材或参考书,掌握静态优化搜索顺序和动态调整搜索顺序的基本思想；2写出求解问题的程序；3设计好测试用例。实验题 质数方阵 在一个 55 的方阵中填入数字，使得沿行，沿列及两个对角线的5 个数字都能构成一个5 位质数（5 位质数的首位不为0）。所有质数的各位数字之和必须等于一个常数

45、。这个常数和方阵左上角中的数字预先给出。请求出其中的一个解。实验提示 (1)选择搜索顺序的基本原则1取值范围小的搜索元素先搜索。2 一个搜索元素确定以后对其它搜索元素取值范围的影响称为制约力。制约力较大的搜索元素先搜索。3先搜索对解影响较大的元素可以使剪枝时的估价函数更准确，使剪枝更加有效。（1）搜索元素的性质1.最后一行和最后一列：可以填的数字只有1，3，7，9。2.两条对角线：与方阵中的所有五位素数有关。3.其他行列：特殊性取决于行列中已经确定的格子个数。(2)根据元素取值范围和制约力确定搜索顺序1.最后一行和最后一列是取值范围最小的搜索元素，而且它们对其他所有的元素都有一定的制约力，因此

46、要放在搜索序列的最前面。2.两条对角线同样影响到其他所有的搜索元素，制约力在剩下的格子中是最大的，因此也应当优先搜索。3.剩下的行列依据它们取值范围的大小确定搜索顺序。实验步骤 1先用程序求解该问题，并测试你的程序，直至正确为止；2针对问题实例，实录运行时的输入、输出文件；3修改搜索方式，比较程序的执行效率，并分析实验结果；如：普通搜索算法剪枝(求一组解）动态调整搜索顺序(求一组解）普通搜索算法剪枝(求所有解）动态调整搜索顺序(求所有解）耗时2.09 sec 0.00 sec 12.97 sec 0.11 sec 实验报告要求 1 阐述实验目的和实验内容；2 提交模块化的实验程序源代码；3 简

47、述程序的测试过程，提交实录的输入、输出文件；4 鼓励对实验内容展开讨论，鼓励提交思考与练习题的代码和测试结果。名师资料总结-精品资料欢迎下载-名师精心整理-第 27 页，共 44 页 -思考与练习 1 古 梅 算 符 由 小 写 字 母a到m 组 成，分 别 对 应 于 现 代 算 符 中 的0,1,2,3,4,5,6,7,8,9,+,*,=中的一个。给出一组古梅算符表示的等式，若存在满足等式的对应关系，则输出所有能够确定的古梅算符和现代算符的对应关系；否则输出,noway?。本题中有三个算符最特殊：,=?、,*?、,+?，它们要满足以下条件：（1）这三个算符不能出现在等式的最左端和最右端。（

48、2）这三个算符两两不能相邻。（3）,?，这是最特殊的算符，它在任何一个等式中必须出现且仅出现一次。从取值范围方面考虑，,?，,?，,*?的取值范围在所有算符中是最小的；从制约力方面考虑，,?和,?，,*?的制约力无疑都强于,0?到,9?这十个数字；从对剪枝有利的角度考虑，这三个算符对解的影响最大，因此,?，,?，,*?这三个算符应当放在搜索序列的前面。对于这三个算符，由于,?受到的限制更多，取值范围更小，所以应当优先搜索。2求质数方阵的全部解。名师资料总结-精品资料欢迎下载-名师精心整理-第 28 页，共 44 页 -实验十五蛇和梯子 实验目的 1.掌握深度优先和广度优先搜索算法的基本思想和设

49、计方法；2.理解贪心算法的局限性；3.提高分析与解决问题的能力。预习要求 1 认真阅读教材或参考书,掌握贪心算法、深度优先和广度优先搜索算法的基本思想；2 写出求解“蛇和梯子”的程序；3 设计好测试用例。实验题 “蛇和梯子”是一个在NN（0N=20)的方格棋盘上进行的游戏。（见下图）方格从 1 到 N的平方编号。除了第 1 号和最后编号的方格，其它的格子都有可能有蛇或梯子存在（蛇和梯子的数量及具体位置由输入确定，它们的数量都在100 之内并且蛇和梯子不能临近放置，也就是在任何了放置两者首尾的方格之间至少还有一个未放置任何东西的格子）。开始的时候玩家把他们的标志物放在1 号格子中。玩家轮流以扔骰

50、子的方式移动他们的指示物。如果一个指示物到达了一条蛇的嘴部，则把它移回蛇的尾部。如果一个指示物到达了一个梯子的底部则将它移动到梯子的顶部。如果你是一个可以自由控制骰子的高手，现在请求出你至少需要扔几次骰子才能到达标为N2的格子。（比如在上图所示例一中，你的方案应该是走4 步到达 5 并由梯子上升到16，再走 4 步到达 20 并由梯子上升到33，然后走3 步。这样，你一共需要扔3 次骰子。而在例二中，你的方案应该是连扔4 个 6。）实验提示 从上面的实验题中很容易看出，这个问题是不能用贪心算法解决的，因为你不能保证在这步到达一个数码比较大的格子就意味着最好的效率（即使是通过梯子到达了一个这步所