c++设计方案大作业指导与要求.docVIP

C++大作业题目 一、约瑟夫环问题 1. 问题描述 ????? 设有编号为 1 ， 2 ， ……， n 的 n ( n 0 ) 个人围成一个圈，每个人持有一个密码 m ，从第 1 个人开始报数，报到 m 时停止报数，报 m 的人出圈，再从他的下一个人起重新报数，报到 m 时停止报数，报 m 的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定 n 和 m 后，设计算法求 n 个人出圈的次序。 2. 基本要求 ????? ⑴ 建立模型，确定存储结构； ⑵ 对任意 n 个人，密码为 m ，实现约瑟夫环问题； ? ⑶ 出圈的顺序可以依次输出，也可以用一个数组存储。 3. 设计思想 ????? 首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。?? 其次，建立一个不带头结点的循环链表并由头指针 first 指示。 最后，设计约瑟夫环问题的算法。下面给出伪代码描述，操作示意图如图 2-1 所示。 ? 二、一元多项式相加 1. 问题描述 ????? 已知 A ( x ) = a 0 + a 1 x + a 2 x 2 + …… + a n x n 和 B ( x ) = b 0 + b 1 x + b 2 x 2 + …… + b m x m ，并且在 A ( x ) 和 B ( x ) 中指数相差很多，求 A ( x ) = A ( x ) + B ( x ) 。 2. 基本要求 ????? ⑴ 设计存储结构表示一元多项式； ⑵ 设计算法实现一元多项式相加； ⑶ 分析算法的时间复杂度和空间复杂度。 3. 设计思想 ????? 一元多项式求和 实质上是合并同类项的过程，其运算规则为： ⑴ 若两项的指数相等，则系数相加； ⑵ 若两项的指数不等，则将两项加在结果中。 ????? 一元多项式 A ( x ) =a 0 +a 1 x+a 2 x 2 + …… +a n x n 由 n +1 个系数唯一确定，因此，可以用一个线性表 ( a 0 ， a 1 ， a 2 ，……， a n ) 来表示，每一项的指数 i 隐含在其系数 a i 的序号里。但是，当多项式的指数很高且变化很大时，在表示多项式的线性表中就会存在很多零元素。一个较好的存储方法是只存非零元素，但是需要在存储非零元素系数的同时存储相应的指数。这样，一个一元多项式的每一个非零项可由系数和指数唯一表示。 ????? 由于两个一元多项式相加后，会改变多项式的系数和指数，因此采用顺序表不合适。 采用单链表存储，则每一个非零项对应单链表中的一个结点，且单链表应按指数递增有序排列。 结点结构如图 2 - 2 所示。 ? ? 其中， coef ：系数域，存放非零项的系数； exp ：指数域，存放非零项的指数； next ：指针域，存放指向下一结点的指针。 将两个一元多项式用两个单链表存储后，如何实现二者相加呢？ 设两个工作指针 p 和 q ，分别指向两个单链表的开始结点。通过对结点 p 的指数域和结点 q 的指数域进行比较进行同类项合并，则出现下列三种情况： ⑴ 若 p - exp q-exp ，则结点 p 应为结果中的一个结点； ? ⑵ 若 p - expq - exp ，则结点 q 应为结果中的一个结点，将 q 插入到第一个链表中结点 p 之前； ⑶ 若 p - exp=q - exp ，则结点 p 与结点 q 为同类项，将 q 的系数加到 p 的系数上。若相加结果不为 0 ，则结点 p 应为结果中的一个结点，同时删除结点 q ；若相加结果为 0 ，则表明结果中无此项，删除结点 p 和结点 q ； ????? 算法用伪代码描述如下： ? 三、 信号放大器 1. 问题描述 ????? 天然气经过管道网络从其生产基地输送到消耗地，在传输过程中，其性能的某一个或几个方面可能会有所衰减（例如气压）。为了保证信号衰减不超过容忍值，应在网络中的合适位置放置放大器以增加信号（例如电压）使其与源端相同。设计算法确定把信号放大器放在何处，能使所用的放大器数目最少并且保证信号衰减不超过给定的容忍值。 2. 基本要求 　　⑴ 建立模型，设计数据结构；⑵ 设计算法完成放大器的放置；⑶ 分析算法的时间复杂度。 3. 设计思想 ????? 为了简化问题，假设分布网络是二叉树结构，源端是树的根结点，信号从一个结点流向其孩子结点，树中的每一结点（除了根）表示一个可以用来放置放大器的位置。图5-3是一个网络示意图，边上标出的是从父结点到子结点的信号衰减量。 ????????????????????? ??? ????? 对于网络中任一结点i，设d(i)表示结点i与其父结点间的衰减