《算法设计与分析》实验二09770106刘东辉.doc

学 号 09770106算法设计与分析实验报告二学生姓名 刘东辉专业、班级软件一班指导教师唐国峰成绩电子与信息工程系2011 年 11 月 17 日实验二：典型算法的理解与应用一、实验目的本次实验是针对书上各章节所阐述的算法的相关应用练习，旨在加深学生对该部分知识的理解，提高学生运用该算法解决问题的能力。二、实验步骤与要求1实验前复习课程所学知识以及阅读和理解指定的课外阅读材料；2学生独自完成实验指定内容；3实验结束后，用统一的实验报告模板编写实验报告。4提交说明： （1）电子版提交说明：a 需要提交Winrar压缩包，文件名为“算法设计与分析实验二_学号_姓名”，如“算法设计与分析实验二_07770101_张三”。 b 压缩包内为一个“算法设计与分析实验二_学号_姓名”命名的顶层文件夹，其下为两个文件夹，一个文件夹命名为“源程序”，另一个文件夹命名为“实验报告电子版”。其下分别放置对应实验成果物。 （2）打印版提交说明：a 不可随意更改模板样式。 b 字体：中文为宋体，大小为10号字，英文为Time New Roman，大小为10号字。 c 行间距：单倍行距。（3）提交截止时间：2011年11月17日16:00。三、 实验项目【分治策略】1 采用分治策略算法实现棋盘覆盖问题的求解；2 运用冒泡排序算法、合并排序算法、快速排序算法实现对给定数字序列的排序。【动态规划】1 运用动态规划算法求解矩阵连乘问题；2 运用动态规划算法求解最长公共子序列问题；3 运用动态规划算法求解最大子段和问题；4运用动态规划算法求解0-1背包问题。【贪心算法】1 运用贪心算法求解找零钱问题。【回溯算法】1 运用回溯算法求解0-1背包问题；2 运用回溯算法求解4城市旅行商问题；3 运用回溯算法求解N后问题。【分支限界算法】1 运用分支限界算法求解0-1背包问题；2 运用分支限界算法求解4城市旅行商问题。【其他搜索算法】1 运用深度优先搜索算法求解马走棋盘问题；2 运用A*算法求解九宫问题。四、 实验过程【分治策略】1题目分析和算法构造在此论证算法设计中的一些必要的设计依据。将棋盘平分四部分，一直分，知道含有特殊方格，看特殊方格在那一部分中，在延边用L型骨牌覆盖。2算法实现程序源代码（请写入必要的注释）。棋盘#include #include using namespace std; /* * 参数含义：* tr-当前棋盘左上角的行号* tc-当前棋盘左上角的列号* dr-当前特殊方格所在的行号* dc-当前特殊方格所在的列号*/ int Board100100;/用来存放棋盘元素的数组int tile=1; /L型骨牌的投放序号void ChessBoard(int tr, int tc, int dr, int dc, int size) if(size=1) /棋盘方格大小为,说明递归到最里层 return; int t=tile+; /每次递增 int s=size/2; /分割棋盘 if(drtr+s & dctc+s) /检查特殊方块是否在左上角子棋盘中 ChessBoard(tr, tc, dr, dc, s); else /不在，将该子棋盘右下角的方块视为特殊方块 Boardtr+s-1tc+s-1=t; ChessBoard(tr, tc, tr+s-1, tc+s-1, s); if(dr=tc+s) /检查特殊方块是否在右上角子棋盘中 ChessBoard(tr, tc+s, dr, dc, s); else /不在，将该子棋盘左下角的方块视为特殊方块 Boardtr+s-1tc+s=t; ChessBoard(tr, tc+s, tr+s-1, tc+s, s); if(dr=tr+s & dc=tr+s & dc=tc+s) /检查特殊方块是否在右下角子棋盘中 ChessBoard(tr+s, tc+s, dr, dc, s); else /不在，将该子棋盘左上角的方块视为特殊方块 Boardtr+stc+s=t; ChessBoard(tr+s, tc+s, tr+s, tc+s, s); void main() int n; int size;/棋盘大小 coutn; int x,y; size=(int)pow(2.0,(int)n); cout x; cout y; cout endl; ChessBoard(0,0,x,y,size); cout 程序运行结果如下所示： endl endl; for(int i=0;isize;i+) for(int j=0;jsize;j+) cout Boardij t; cout endl; cout endl; system(pause);3.运行结果4经验归纳棋盘覆盖的是基本思想基于分治策略，即是将棋盘平分四部分1. 题目分析和算法构造在此论证算法设计中的一些必要的设计依据。N个数字来排队；两两相比小靠前；外层n-1；内层n-i-1。2. 算法实现程序源代码（请写入必要的注释）。冒泡#include using namespace std;int main()int a10;int i, b=0;for( i=0;iai;for( i=0;i10;i+)for(int j=0;jaj+1)b=aj;aj=aj+1;aj+1=b;for( i=0;i10;i+)coutai ; return 0; 3. 运行结果4. 经验归纳 冒泡排序的基本思想就是利用双重for循环。1题目分析和算法构造在此论证算法设计中的一些必要的设计依据。 将一组数从中间分成两部分，左侧的都小于中间数，右侧的都大于中间数。然后在两部分重复上述过程，直到完成排序。2算法实现程序源代码（请写入必要的注释）。快速排序#includeusing namespace std;void kuaisu(int *p,int left,int right) int i(left),j(right),middle(0),iTemp(0); middle=p(left+right)/2;/求中间值 do while(pimiddle)&(imiddle) & (jleft)/从右扫描小于中值的数 j-; /找到了一对值,交换 if(i=j) iTemp=pj; pj=pi; pi=iTemp; i+; j-; while(i=j);/如果两边扫描的下标交错，就停止（完成一次） /当左边部分有值(leftj)，递归左半边 if(lefti)，递归右半边 if(righti) kuaisu(p,i,right); int main() int data=10,9,8,7,6,5,4,3,2,1; kuaisu(data,0,10); for(int i=0;i10;i+) coutdatai ; coutendl; return 0; 3.运行结果4经验归纳递归左右部分。1题目分析和算法构造在此论证算法设计中的一些必要的设计依据。 分成若干小区间内进行排序，相邻区间两两合一，在进行排序，最后完成排序。2算法实现程序源代码（请写入必要的注释）。合并#include using namespace std;#define n 9templatevoid MergeSort(Type a, int left, int right) if(leftright) /保证至少有两个元素 Type *b=new Typeright-left; /临时存储数据int i=(left+right)/2; /取中点 MergeSort(a,left,i); MergeSort(a,i+1,right); Merge(a,b,left,i,right); /合并到数组b Copy(a,b,left,right); /复制回数组atemplatevoid Copy(Type a,Type b, int left, int right) for (int i = left; i = right; i+) ai=bi; templatevoid Merge(Type c,Type d,int l,int m,int r) int i=l;int j=m+1; int k=l; while(i=m)&(j=r) if(cim) for(int q=j;q=r;q+) dk+=cq; else for(int q=i;q=m;q+) dk+=cq; void main() int datan; int i,j; cout请依次输入数组的元素：endl; for(i=0;idatai; MergeSort(data, 0, n-1); /用递归实现的合并排序算法 for(j=0;jn;j+) /打印输出结果 cout dataj ; cout endl ;3.运行结果4经验归纳合并排序法的基本思想是基于分治策略【动态规划】运用动态规划算法求解最大子段和问题1题目分析和算法构造在此论证算法设计中的一些必要的设计依据。给出一段序列，找到这个序列的子序列的最大和。用一维数组来存储这段序列，调用求子段和的动态规划算法。2算法实现程序源代码（请写入必要的注释）。#include using namespace std; #define m 7int maxSubSum(int* a, int n) int sum= an -1; int s = an-1; int i; for( i = n-2; i=0; i-) if(s sum) /若当前子数组之和大于sum，则更新sum sum = s; return sum; void main() int datam; cout请依次输入数组的元素：endl; for(int i=0;idatai; int maxSub = maxSubSum(data,m); /递归 coutmaxSubendl; 3.运行结果4经验归纳当前子数组之和大于sum，则更新sum 【贪心算法】找零钱1题目分析和算法构造在此论证算法设计中的一些必要的设计依据。希望用数目最少的硬币找零钱。2算法实现程序源代码（请写入必要的注释）。#includeusing namespace std;void main() int a,b25,b10,b5,b2,b1; cout请输入要找的零钱:a; b25=(a/25); b10=(a%25)/10; b5=(a%25)%10/5; b2=(a%25)%10%5/2; b1=(a%25)%10%5%2; cout需要以下几枚零钱:endl; if(b25!=0) cout25分的b25枚endl; if(b10!=0) cout10分的b10枚endl; if(b5!=0) cout5分的b5枚endl; if(b2!=0) cout2分的b2枚endl; if(b1!=0) cout1分的b1枚endl; 3.运行结果4经验归纳贪心算法的基本思想：从问题的一个初始解逼近给定的目标，以尽可能快的求得更好的解。【回溯算法】01背包1题目分析和算法构造在此论证算法设计中的一些必要的设计依据。0-1背包问题的解空间可用子集树表示。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。当右子树有可能包含最优解时才进入右子树搜索。否则将右子树剪去。设r是当前剩余物品价值总和；cp是当前价值；bestp是当前最优价值。当cp+rbestp时，可剪去右 子树。计算右子树中解的上界的更好方法是将剩余物品依其单位重量价值排序，然后 依次装入物品，直至装不下时，再装入该物品的一部分而装满背包。由此得到的价值是 右子树中解的上界。2算法实现程序源代码（请写入必要的注释）。#include using namespace std; /类knap的数据成员记录解空间树的结点信息class Knap friend int Knapsack(int p,int w,int c,int n ); public: void print() for(int m=1;m=n;m+) coutbestxm ; coutendl; ; private: int Bound(int i); void Backtrack(int i); int c;/背包容量 int n; /物品数 int *w;/物品重量数组 int *p;/物品价值数组 int cw;/当前重量 int cp;/当前价值 int bestp;/当前最优值 int *bestx;/当前最优解 int *x;/当前解 ; int Knap:Bound(int i) /计算上界 int cleft=c-cw;/剩余容量 int b=cp; /以物品单位重量价值递减序装入物品 while(i=n&wi=cleft) cleft-=wi; b+=pi; i+; /装满背包 if(in) if(bestpcp) for(int j=1;j=n;j+) bestxj=xj; bestp=cp; return; if(cw+wibestp)/搜索右子树 xi=0; Backtrack(i+1); class Object friend int Knapsack(int p,int w,int c,int n); public: int operator=a.d); private: int ID; float d; ; int Knapsack(int p,int w,int c,int n) /为Knap:Backtrack初始化 int W=0; int P=0; int i=1; Object *Q=new Objectn; for(i=1;i=n;i+) Qi-1.ID=i; Qi-1.d=1.0*pi/wi; P+=pi; W+=wi; if(W=c) return P;/装入所有物品 /依物品单位重量排序 float f; for( i=0;in;i+) for(int j=i;jn;j+) if(Qi.dQj.d) f=Qi.d; Qi.d=Qj.d; Qj.d=f; Knap K; K.p = new intn+1; K.w = new intn+1; K.x = new intn+1; K.bestx = new i