当前位置:首页 >> IT/计算机 >>

算法分析与设计——实验报告


课程名称: 课程名称: 学 姓 学 号: 名: 院:

算法分析与设计 08220429 王 洪 朋 数理与信息工程学院 宋 炯

专业班级: 非师范) 专业班级: (非师范)计算机科学与技术 081 指导老师: 指导老师:

数理与信息工程学院

实验一 递归与分治策略
一、实验目的 1、熟练掌握递归与分治策略的思想并应用其解决实际问题。 2、利用递归与分治策略的思想解决 Gray 码问题。 二、实验要求 Gray 码是一个长度为 2n 的序列。序列中无相同元素,每个元素都是长度为 n 位的串, 相邻元素恰好只有 1 位相同。用分治策略设计一个算法对任意的 n 构造相应的 Gray 码。 三、算法实现 #include <iostream> { using namespace std; cout<<a[i]; void print(int a[], int length); } void gray(int n, int a[], int length); cout<<endl; int main(void) } {int n; void gray(int n, int a[], int length) cout<<"Please input n:"; { cin>>n; if(n == 0) int a[n]; { for (int i = 0; i < n; i ++) a[n] = 1 - a[n]; { print(a, length); a[i] = 0; } } else print(a, n); { gray(n - 1, a, n); gray(n - 1, a, length); return 0; a[n] = 1 - a[n]; } print(a, length); void print(int a[], int length) gray(n - 1, a, length); { } for(int i = length - 1; i >= 0; i--) } 实验运行结果:

四、实验总结 按照分治策略设计,利用递归方法构造 Grey 码。长度为 n 的 Grey 码字符串,前半部分 只要在长度为 n-1 的 Grey 码前添 0 就可;后半部分令第二位为 1,后几位为前半部分的逆 顺序就可。

实验二动态规划
一、实验目的 1、掌握动态规划的基本思想并应用其解决实际问题。 2、利用动态规划的基本思想解决 N 堆石子合并问题。 二、实验要求 在一个圆形操场的四周摆放 N 堆石子,现要将石子有次序地合并成一堆。规定每次只 能选相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。试设计一 个算法,计算出将 n 堆石子合并成一堆的最小得分和最大得分,并分析算法的计算复杂性。 三、算法实现
#include <iostream> #include <string> #define N 500 2000000000 cout<<endl; v[i] = v[i] + v[x]; v[x] = -v[x]; } } // flag = 0 求最小得分, flag = 1 求最大得分 void Solve(int flag) { int i, j, k, x, t, result; // 每堆石头的个数 // 输出最优解的具 for(i = 1; i <= n; i++) 在合并 f[i][1].c = f[i][1].d = 0; for(j = 2; j <= n; j++) { // 顺 推含 2 堆,3 堆...n 堆石子的各子序列的合并方案 for(i = 1; i <= n; i++) { // sum[i][j] 表示从 t = sum[i][j]; if(flag == 0) f[i][j].c = oo; 分,那么需要初始化为 oo // 递归打印子序列 f[i][j]的合并过程 void Print(int i, int j) { int k, x; if(j != 1) { Print(i, f[i][j].d); x = (i + f[i][j].d - 1)%n + 1; Print(x, j - f[i][j].d); for(k = 1; k <= n; k++) if(v[k] > 0) { if(i == k || x == k) cout<<"*"<<v[k]<<" "; 示这次操作合并该堆 else cout<<v[k]<<" "; } // *号表 else f[i][j].c = 0; // 求最大得分, 那么需要初始化为 0 for(k = 1; k <= j-1; k++) { x = (i + k - 1)%n + 1; if((flag == 0 && f[i][k].c + f[x][j-k].c + t < f[i][j].c) ||(flag != 0 && f[i][k].c + f[x][j-k].c + t > f[i][j].c)) { f[i][j].c = f[i][k].c + f[x][j-k].c + t; f[i][j].d = k; } } } } result = f[1][n].c; k = 1; for(i = 2; i <= n; i++) if((flag == 0 && f[i][n].c < result) || (flag != 0 && // 求最小得 // 仅含一堆石子的序列不存 // 置为"-" 类似于删除

#define oo #define #define

MIN(a, b) (a)<(b)?(a):(b) MAX(a, b) (a)>(b)?(a):(b)

using namespace std; typedef struct { int c, d; } Node; int n; int v[N]; int save[N];

体合并需要随时改变 v 的值,所以为了同时输出 最小,最大的合并,在完成一个任务之后需要回溯 Node f[N][N]; 解,同时存储合并线索 int sum[N][N]; 第 i 堆起,顺时针数 j 堆的石子总数 // f[i][j]存储最优

f[i][n].c > result)) { result = f[i][n].c; k = i; } cout<<(flag == 0 ? "最小" : "最大")<<"得分是 "<<result<<endl; cout<<"合并过程如下:"<<endl; Print(k, n); cout<<sum[1][n]<<endl; } int main() { int i, j;

cout<<"输入石子堆数:"<<endl; cin>>n; cout<<"输入每堆石子数:"<<endl; for(i = 1; i <= n; i++) cin>>v[i]; memcpy(save+1, v+1, n*sizeof(v[1])); for(i = 1; i <= n; i++) sum[i][1] = v[i]; for(j = 2; j <= n; j++) for(i = 1; i <= n; i++) sum[i][j] = v[i] + sum[i%n+1][j-1]; Solve(0); memcpy(v+1, save+1, n*sizeof(v[1])); Solve(1); return 0; }

实验运行结果:

四、实验总结 动态规划算法与分治法类似, 其基本思想也是将待求解问题分解成若干个子问题, 但是 经分解得到的子问题往往不是互相独立的。 不同子问题的数目常常只有多项式量级。 在用分 治法求解时,有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案,而在 需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。

实验三回溯法 实验三回溯法
一、实验目的 1、了解回溯法的基本思想。 2、运用回溯法解决最小重量机器设计问题。

二、实验要求 最小重量机器设计问题。设某一机器由 n 个部件组成,每一种部件可以从 m 个不同的供应 商处购得。设 wij 是从供应商 j 处购得的部件 i 的重量,cij 是相应的价格。 试设计一个算法,给出总价格不超过 c 的最小重量机器设计。 三、算法实现
#include<iostream> using namespace std; #define N 50 class MinWmechine { int n; //部件个数 int m; //供应商个数 int COST; //题目中的 C int cw; //当前的重量 int cc; //当前花费 int bestw; //当前最小重量 int bestx[N]; int savex[N]; int w[N][N]; int c[N][N]; public: MinWmechine(); void machine_plan(int i); void prinout(); }; MinWmechine::MinWmechine() { cw=0; //当前的重量 cc=0; //当前花费 bestw=-1; //当前最小重量 bestx[N]; savex[N]; cout<<"请输入部件个数:"; cin>>n; cout<<"请输入供应商个数:"; cin>>m; cout<<"请输入总价格不超过:"; cin>>COST; for(int j=0;j<m;j++) { for(int i=0;i<n;i++) { } for(int j=0; j<m; j++) //依次递归尝试每个供 应商 { if(cc+c[i][j]<COST) { cc+=c[i][j]; cw+=w[i][j]; bestx[i]=j; machine_plan(i+1); bestx[i]=-1; } return; } } void MinWmechine::machine_plan(int i) { if(i>=n) { if(cw <bestw || bestw==-1) { bestw=cw; for(int j=0;j<n; j++) //把当前搜过的路径 记下来 savex[j]=bestx[j]; } } cout<<"请输入第 "<<j+1<<" 个供应商的第 "<<i+1<<" 个部件的重量:"; cin>>w[i][j]; cout<<"请输入第 "<<j+1<<" 个供应商的第 "<<i+1<<" 个部件的价格:"; cin>>c[i][j]; if(w[i][j]<0 || c[i][j]<0) { cout<<"重量或价钱不能为负数!\n"; i=i-1;

cc-=c[i][j]; cw-=w[i][j]; } } } void MinWmechine::prinout() { int i,j,ccc=0; for(j=0;j<m;j++) { for(i=0;i<n;i++) { cout<<"第 "<<j+1<<" 供应商的第 "<<i+1<<" 部件重量:"<<w[i][j]<<" "<<c[i][j]<<"\n"; } } for(j=0; j<n; j++) { bestx[j]=-1; 价格:

} machine_plan(0); cout<<"\n 最小重量机器的重量是: "<<bestw<<endl; for(int k=0; k<n; k++) { cout<<" 第 "<<k+1<<" 部件来自供应商 "<<savex[k]+1<<"\n"; ccc+=c[k][savex[k]]; } cout<<"\n 该机器的总价钱是: "<<ccc<<endl; cout<<endl; } int main(void) { MinWmechine Y; Y.prinout(); return 0; }

实验运行结果:

四、实验总结 实验总结 回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。算法搜索 至解空间树的任意一点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对该 结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略 搜索。


相关文章:
算法分析与设计实验报告.doc
算法分析与设计实验报告 - 算法分析与设计 实验报告 专业班级: 姓学名: 号:
算法分析与设计实验报告.doc
算法分析与设计实验报告 - 算法 二分查找,归并排序,快速排序 回溯算法: 0
算法设计与分析实验报告.doc
算法设计与分析实验报告 - 算法设计与分析 实验报告 教师: 学号: 姓名: 实验一:串匹配问题 实验目的: (1) 深刻理解并掌握蛮力法的设计思想; (2) 提高应用...
算法分析与设计实验报告.doc
算法分析与设计实验报告 - 算法分析与设计 实验报告 班级: 学号: 姓名: 实
算法设计与分析实验报告.doc
算法设计与分析实验报告 - 算法设计与分析实验报告 20162017 学年第二
算法设计与分析实验报告.doc
算法设计与分析实验报告 - 算法设计与分析 报告 学生姓名 学号 专业班级 指导
算法分析实验报告.doc
算法分析实验报告 - 西安邮电大学计算机学院,算法分析实验报告... 西安邮电大学 (计算机学院) 算法设计与分析课内实验报告实验名称: 递归与分治法 专业名称: 班级: ...
算法分析与设计实验报告.doc
算法分析与设计实验报告 - 安徽工业大学专业: 班级: 姓名: 学号: 实验一:
算法分析与设计实验报告.doc
算法分析与设计 实验报告 实验一 1、 实验目的与要求 熟悉 C/C++语言的集
算法设计与分析实验报告.doc
算法设计与分析实验报告 - 算法设计与分析实验报告项目 1)实验项目名称:迭代与蛮力策略实例编程 实验目的与要求:1、加深对迭代与蛮力算法基本思想的理解; 2、 深入...
算法分析与设计实验报告(二)-20131344102-蒋刘燃.doc
南京信息工程大学算法设计与分析 实验报告课程 学号 计算机算法设计与分析 201
算法设计与分析实验报告.doc
算法设计与分析实验报告 - 分治法 第一章. 第一章.实验要求 1. 了解用分治
四川师范大学《算法设计与分析》实验报告.pdf
四川师范大学《算法设计与分析实验报告_工学_高等教育_教育专区。四川师范大学《算法设计与分析实验报告,适合软件工程专业,仅供学习参考。 ...
算法设计与分析实验报告3.doc
算法设计与分析实验报告3 - 信息工程学院实验报告 算法分析与设计(地点:磨弘文
算法分析与设计实验报告-最大子段和、0-1背包问题.doc
实验报告课程 学号 计算机算法设计与分析 姓名 实验名称 最大子段和、0-1 背
算法设计与分析实验报告 统计数字问题.doc
算法设计与分析实验报告 统计数字问题_IT/计算机_专业资料。算法设计与分析实验报告实验名称 实验日期 姓名 年 统计数字问题 月 专业班级 日 指导教师 学号 评分 ...
《算法设计与分析》实验三_实验报告模板.doc
学号《算法设计与分析实验报告三 学专指成 生业导、 姓班教 名级师绩 唐国峰 计算机与信息工程学院软件工程系 2014 年 9 月 28 日 实验三:贪心算法...
算法实验报告.doc
算法实验报告 - 院专年 系: 业: 级: 计算机科学学院 08 级 课程名称: 算法设计与分析基础 班组号: 号: 5 6 指导教师: 2010 年 12 月 日 学...
算法分析与设计 实验报告 动态规划:智能数值计算.doc
武夷学院实验报告课程名称: 算法分析与设计 项目名称: 动态规划:智能数值计算
算法分析实验报告--分治策略.doc
算法分析实验报告--分治策略 - 《算法设计与分析》实验报告 分治策略 姓 名:
更多相关标签: