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

课程名称： 算法分析与设计 学 号： 姓 名： 王 洪 朋 专业班级： （非师范）计算机科学与技术081 学 院： 数理与信息工程学院 指导老师： 宋 炯 数理与信息工程学院 实验一 递归与分治策略 一、实验目的 1、熟练掌握递归与分治策略的思想并应用其解决实际问题。 2、利用递归与分治策略的思想解决Gray码问题。 二、实验要求 Gray码是一个长度为2n的序列。序列中无相同元素，每个元素都是长度为n 位的串，相邻元素恰好只有1位相同。用分治策略设计一个算法对任意的n构造相应的Gray码。 三、算法实现 #include iostream using namespace std; void print(int a[], int length); void gray(int n, int a[], int length); int main(void) {int n; coutPlease input n:; cinn; int a[n]; for (int i = 0; i n; i ++) { a[i] = 0; } print(a, n); gray(n - 1, a, n); return 0; } void print(int a[], int length) { for(int i = length - 1; i = 0; i--) { couta[i]; } coutendl; } void gray(int n, int a[], int length) { if(n == 0) { a[n] = 1 - a[n]; print(a, length); } else { gray(n - 1, a, length); a[n] = 1 - a[n]; print(a, length); gray(n - 1, a, length); } } 实验运行结果： 四、实验总结 按照分治策略设计，利用递归方法构造Grey码。长度为n的Grey码字符串，前半部分只要在长度为n-1的Grey码前添0就可；后半部分令第二位为1，后几位为前半部分的逆顺序就可。 实验二动态规划 一、实验目的 1、掌握动态规划的基本思想并应用其解决实际问题。 2、利用动态规划的基本思想解决N堆石子合并问题。 二、实验要求 在一个圆形操场的四周摆放N堆石子，现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分，并分析算法的计算复杂性。 三、算法实现 #include iostream #include string #define N 500 #define oo 2000000000 #define MIN(a, b) (a)(b)?(a):(b) #define 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]; // f[i][j]存储最优解，同时存储合并线索 int sum[N][N]; // sum[i][j] 表示从第 i 堆起，顺时针数j堆的石子总数 // 递归打印子序列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 coutv[k] ; } coutendl; v[i] = v[i] + v[x]; v[x] = -v[x]; // 置为- 类似于删除 } } // flag = 0求最小