数据结构实验报告_实验三1
需积分: 0 89 浏览量
2022-08-03
16:11:33
上传
评论
收藏 82KB PDF 举报
数据结构实验报告
姓名： 杨家玺 学号：U201717007 班级：软工 1703 班
2018．12．03
实验三
约瑟夫问题和多项式相乘问题的求解
一、实验描述
1.约瑟夫问题：用游标方式的循环链表实现 Josephus(n, m)问题的求解。
2. 多项式乘法：用链表表示多项式，分别在对指数排序和不排序的情况下，写
出求两个给定多项式的乘法的函数。其计算复杂度分别是多少？
二、实验环境
1. 开发环境： OS X
2. IDE： CLion
3. 编译器： Clang 9.1.0 Apple LLVM
4. C 标准： C11
三、问题分析
1. 约瑟夫问题
这是一个历史悠久的问题，解决这个问题的方法也层出不穷，本次实验我采
用了 1. 基于游标的循环链表方法与 2. 基于数学推导的递归/迭代方法。
在代码中，规定了人的编号从 0 开始，报数从 1 开始，这样做使得三个算法
的结果输出形式保持一致。
a. 对于基于游标的链表，首要解决的问题是 malloc 与 free 函数的数组模
拟，此部分利用书中代码实现。
b. 对于基于数学推导的递归/迭代方法，推导如下：
a) 对于一给定数列[0,1,2,3,4...n-1]与每轮划去的元素 m-1（从 1
开始报数，所以对应从 0 开始的 m-1）
b) 假设 n>m，第一轮后：[0,1...m-2,m,m+1,...n-1]
c) 将 m 置 0，也就是[-m,-m+1,...-2,0,1,...n-1-m]
d) 由于出现负数，根据环状报数规则重新映射序列
e) -> [n-m,n-m+1,...n-2,0,1,...n-1-m] (list+n)%n
f) 对于这 n-1 个数组成的新序列使用同样的方法，构成递归
g) 将上述过程转换为自底向上的搜索，可得到转移方程与边界条件：
h) f(k, m)=(f(k-1, m)+m)%k, 1<=k<=n
i) f(1, m)=0
2. 多项式乘法
利用链表实现多项式乘法，可以避免非稀疏情况下的内存浪费问题。
a. 对于没有进行指数排序的多项式：
评论0
最新资源