没有合适的资源？快使用搜索试试~ 我知道了~

文库首页课程资源C/C++算法设计与分析实验报告.pdf

算法设计与分析实验报告.pdf

实验报告

TYUT

算法设计与分析

需积分: 15 18 下载量 43 浏览量 2021-07-22 21:47:12 上传评论 1 收藏 990KB PDF 举报

温馨提示

试读

19页

以太原理工大学为蓝本的算法实验报告供需要的小伙伴参考。目录：1.分治-求解n位格雷码 2.贪心-最小延迟调度 3.动态规划-图像压缩 4.回溯与分支限界-排兵布阵

资源推荐

资源详情

资源评论

实验一减治、分治和变治策略的算法设计、实现与分析

1.1 实验目的

(1) 掌握分治法、减治法和变治法的设计思想；

(2) 掌握分治法的求解步骤；

(3) 掌握分治法解题的算法框架。

1.2 实验设备和编程环境

(1) 硬件环境：1 台 DELL 笔记本

(a) 处理器：Intel(R) Core(TM) i5-9300H CPU @ 2.40GHz

(b) 内存：海力士 HMA81GS6DJR8N-VK @ 2666MHz

(2) 软件环境

(a) 操作系统：Windows 10 LTCS

(b) IDE：Visual Studio 2019

1.3 格雷码构造问题

1.3.1 问题描述

Gray 玛是一个长度为 2

的序列。序列无相同元素，每个元素都是长度

为 n 的串，相邻元素恰好只有一位不同。试设计一个算法对任意 n 构造相应

的 Gray 码。（分治、减治、变治皆可）

格雷码是反射码，例子可以参见表 1–1。我们可以利用递归的如下规则来

构造：

n 位的格雷码可以由 n − 1 位的格雷码得到，将每一个 n − 1 位的格雷码

左侧加一位

′

，便可以得到前 2

n−1

个 n 位的格雷码。

之后将 n − 1 位的格雷码的排列顺序逆序，将每一个 n − 1 位的格雷码左

侧加一位

′

，便可得到后 2

n−1

个 n 位的格雷码，由此全部的 n 位的格雷码

已求出。

递归边界为 1 位的格雷码只有

′

，直接返回即可。

1.3.2 问题的形式化

n 位格雷码 [i] =’0’+n − 1 位格雷码 [i]

n 位格雷码 [2

− i − 1] =’1’+n − 1 位格雷码 [i]

2 实验一：减治、分治和变治策略的算法设计、实现与分析

表 1–1 格雷码示例

2 位格雷码 3 位格雷码 4 位格雷码 4 位自然二进制码

0000 0000

0001 0001

0011 0010

0010 0011

000 0110 0100

001 0111 0101

00 011 0101 0110

01 010 0100 0111

11 110 1100 1000

10 111 1101 1001

101 1111 1010

100 1110 1011

1010 1100

1011 1101

1001 1110

1000 1111

1.4 算法设计

1.4.1 算法的伪代码描述

[算法] Algorithm 1 求解格雷码问题的分治算法

输入: graycode 数组，待求格雷码的长度 n

输出: 格雷码

1: function getGray(n)

2: if n = 0 then

3: return

4: end if

5: if n = 1 then

6: graycode[0] ← 0

7: graycode[1] ← 1

8: else

9: getGray(n − 1)

10: len ← graycode.size

11: for i = 0 → len do

12: graycode[i] ← 0 + graycode[i]

13: end for

14: for i = len − 1 → 0 do

15: graycode[i] ← 1 + graycode[i]

16: end for

17: end if

18: end function

1.5 编码实现 3

1.4.2 时间复杂度分析

T (n) = T (n − 1) + n = T (n − 2) + T (n − 1) + n...

T (n) = T (0) + 1 + 2 + 3 + ... + (n − 2) + (n − 1) + n

T (n) =

n(n + 1) = O(n

)

1.5 编码实现

1 #include<iostream>

2 #include<vector>

3 #include<string>

4 #include<cmath>

6 using namespace std;

8 vector<string> graycode;

10 void getGray(int n) {

11 if (n == 0)//不合法输入

12 return;

13 if (n == 1) {//递归边界

14 graycode.push_back(”0”);

15 graycode.push_back(”1”);

16 }

17 else {

18 getGray(n - 1);//递归：求n位Gray码，应先知道n-1位Gray码（减治）

19 int len = graycode.size();//n-1位Gray码序列长度

20 for (int i = 0; i < len; i++) {

21 graycode.push_back(”0” + graycode[i]);//n-1位Gray码顺序书写，加前缀0

22 }

23 for (int i = len - 1; i >= 0; i--) {

24 graycode.push_back(”1” + graycode[i]);//n-1位Gray码逆序书写，加前缀1

25 }

26 graycode.erase(graycode.begin(), graycode.begin() + len);//删除n-1位Gray码序列

27 }

28 }

30 int main() {

31 cout << ”输入Gray码长度：”;

32 int n;

33 cin >> n;

34 getGray(n);

35 cout << n << ”位Gray码：” << endl;

36 int index1 = 0, index2 = graycode.size()/2;

37 while (index1 < graycode.size()/2)

38 {

39 cout << graycode[index1] << ” ” << graycode[index2] << endl;

40 index1++;

41 index2++;

42 }

43 cout << ”共” << pow(2, n) << ”个。” << endl;

44 return 0;

45 }

4 实验一：减治、分治和变治策略的算法设计、实现与分析

1.6 程序调试与结果展示

样例结果图如图 1–1所示

(a) 算法实例 1 (b) 算法实例 2

图 1–1 算法实例的结果

1.7 实验总结

递归和分治往往一同出现。

递归算法是一种通过将重复问题分解为同类的子问题的方法，其思想很

简单，但是计算量大，计算效率低。

分治算法则是将一个规模为 N 的问题分解为 k 个子问题，这些子问题相

互独立且原问题性质相同，求出问题的解，就可以得到原问题的解了。

剩余18页未读，继续阅读

评论收藏

内容反馈

资源评论

资源反馈

评论星级较低，若资源使用遇到问题可联系上传者，3个工作日内问题未解决可申请退款~

Mymel_晗

粉丝: 2941
资源: 3

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

算法设计与分析实验报告.pdf

算法设计与分析实验报告统计数字问题.pdf

《动态规划算法实验》实验报告.docx

实验三 决策树算法实验实验报告.pdf

算法设计与分析实验报告

算法分析与设计实验报告

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

计算机算法设计与分析实验报告.pdf

算法实验报告.pdf

算法设计与分析实验

算法设计与分析实验报告完整版

大学算法设计与分析实验报告

最短路径算法实验报告

排序算法实验报告

SVM分类算法实验报告+C语言程序 加强版

操作系统算法实验报告

算法实验报告

分治法实现归并排序算法算法设计与分析实验报告.pdf

算法与数据结构实验报告.pdf

算法分析与设计实验报告一.docx

C++数据结构与算法实验报告及代码

算法实验报告（包括源代码，调试过程，运行结果截图）

动态规划法（算法）华北电力大学

算法设计与分析（Python）程振波编著 实验报告

《算法设计与分析》实验报告：实验一（分治策略）

太原理工大学算法分析与设计

最新资源

实验三决策树算法实验实验报告.pdf

SVM分类算法实验报告+C语言程序加强版

算法设计与分析（Python）程振波编著实验报告