《算法设计与分析》实验二09770106刘东辉
学 号 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(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 else /不在，将该子棋盘左上角的方块视为特殊方块Boardtr+stc+s=t;ChessBoard(tr+s, tc+s, tr+s, tc+s, s);void main()int n;int size;/棋盘大小 cout>n; int x,y;size=(int)pow(2.0,(int)n);cout > x;cout > y;cout using namespace std;int main()int a10;int i, b=0;for( i=0;i>ai;for( i=0;iaj+1)b=aj;aj=aj+1;aj+1=b;for( i=0;iusing namespace std;void kuaisu(int *p,int left,int right)int i(left),j(right),middle(0),iTemp(0);middle=p(left+right)/2;/求中间值 dowhile(pimiddle) /找到了一对值,交换 if(ii)，递归右半边 if(right>i)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;iusing namespace std;#define n 9templatevoid MergeSort(Type a, int left, int right) if(leftvoid Copy(Type a,Type b, int left, int right) for (int i = left; i void Merge(Type c,Type d,int l,int m,int r)int i=l;int j=m+1;int k=l;while(im)for(int q=j;q>datai;MergeSort(data, 0, n-1); /用递归实现的合并排序算法for(j=0;j 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>datai;int maxSub = maxSubSum(data,m); /递归coutusing 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 using namespace std; /类 knap 的数据成员记录解空间树的结点信息class Knap friend int Knapsack(int p,int w,int c,int n ); public: void print() for(int m=1;mn) if(bestpbestp)/搜索右子树 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>c; cout>n; p=new intn+1; w=new intn+1; p0=0; w0=0; cout>pi; cout>wi; cout<<“最优解为(bestx)：“<<endl; cout<<“最优值为(bestp)：“<<endl; cout<<Knapsack(p,w,c,n)<<endl; 3 运行结果4 经验归纳0-1 背包问题的解空间可用子集树表示。1 题目分析和算法构造在此论证算法设计中的一些必要的设计依据。2 算法实现程序源代码（请写入必要的注释） 。3 运行结果4 经验归纳1 题目分析和算法构造在此论证算法设计中的一些必要的设计依据。2 算法实现程序源代码（请写入必要的注释） 。3 运行结果4 经验归纳请仿照此步骤写实验过程。五、实验总结五、实验总结
