数据结构实验报告_实验一1
需积分: 0 36 浏览量
2022-08-03
16:39:10
上传
评论
收藏 553KB PDF 举报
数据结构实验报告
姓名： 杨家玺 学号：U201717007 班级：软工 1703 班
实验一 求整数和、切 pizza 和 Hanoi 塔等问题的求解
一、实验描述
用 C 语言编程实现求整数和，切 pizza 以及 Hanoi 塔等问题的求解，在程序中加入
clock ()来计算求解时间，使用不同的输入值得到对应的时间值。分析算法的时间复
杂度并与测量结果进行比较，如果存在差异，解释原因。
二、实验之前!
1. 程序计时方法：在算法执行前于执行结束后分别执行 clock()，获取算法的运行
ticks，不除以 CLOCK_PER_SECOND，因为个人认为使用 ticks 会更加准确。
2. 设计了三个宏指令以简化程序
#define _TIME_INIT clock_t tic = 0;
#define _TIME_START tic = clock();
#define _TIME_END printf("%lu", clock() - tic);
3. 计时原则：同一规模多次试验取平均，规模渐进增长
4. 算法复杂度绘图：绘制规模-ticks 图，绘制 f(规模)-ticks 图，f 为关系函数。
5. 使用 Python 程序辅助统计并进行画图，部分代码如下：
def run_test(cmd, size, method):
res = {}
for mth in method:
res[mth] = {"size": [], "ticks": []}
for sz in tqdm(size):
cmd_s = cmd + " " + str(sz) + " " + str(mth)
tmp = 0
times = 5
for _ in range(times):
tmp += int(subprocess.check_output(cmd_s.split(" ")).decode("utf-8"))
res[mth]["size"].append(sz)
res[mth]["ticks"].append(tmp / times) # 5 次取平均
res[mth]["size"] = np.array(res[mth]["size"])
res[mth]["ticks"] = np.array(res[mth]["ticks"])
return res
# 参数 cmd2 为命令行中执行“可执行文件”的命令，例如./a.out
res = run_test(cmd2, np.arange(500, 100000, 100), [0])
show(res[0]["size"], res[0]["ticks"], "Integer Sum Problem", lambda t: t)
# t -> f(t)为 size 的变换关系，这个变换使 f(size)与 ticks 呈现线性关系
# e.g. 三次方 : lambda t : t**3
对数 : lambda t : np.log(t)
nlogn : lambda t : t * np.log(t)
三、实验设计
1. 整数求和问题：计算小于等于 n 的整数的和，n 取 500~100000 每隔 100 取一个。
2. 切 pizza 问题：利用递归算法计算一块 pizza 在切 n 刀后最多可产生多少块小 pizza。
3. 河内塔问题：利用递归算法计算规模为 n 的汉诺塔需要的步数。
4. 使用上一步定义的三个宏获取核心算法执行所需的 ticks
5. 利用 Python 自动完成程序的调用与绘图输出
评论0