【精品】c++课程设计大作业指导与要求

《【精品】c++课程设计大作业指导与要求》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、C++大作业题目一、约瑟夫环问题1.问题描述设有编号为1,2,门的n{n>Q)个人围成一个圈，每个人持有一个密码〃，从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，..…，如此下去，直到所有人全部出圈为止。当任意给定门和刃后，设计算法求n个人出圈的次序。2.基本要求(1)建立模型，确定存储结构；⑵对任意/7个人，密码为m,实现约瑟夫环问题；⑶出圈的顺序可以依次输出，也可以用一个数组存储。3.设计思想首先，设计实现约瑟夫环问题的存储结构。由丁•约瑟夫环问题本身具冇循环性质，考虑采用循环链表,为了统一对表中任意结点的操

2、作，循坏链表不带头结点。其次，建立一个不带头结点的循坏链表并山头指针first指示。最后，设计约瑟夫环问题的算法。下面给出伪代码描述，操作示意图如图2-1所示。1.工作指针pre和p初始化，计数器count初始化；2.循环直到P=prepreF=first;p=first->next;count=2;〃为便于删除操作‘从2开始计数2.1如果count=m,则2.1.1输出结点p；2.1.2删除结点p；2.1.3计数器coiM蓿零，重新开始计埶2.2否则,执行2.2.1工作指针pr已和p后移；2.2.2计数器増b3.退出循环，琏表中只剩下一个结点p,输出结点p后将结点卩刪除;c

3、ount=2(a)-般情况(b)只剩下一个结点的特殊情况E2-1约瑟夫环问题存储示意图二.一元多项式相加1•问题描述已知A{x)=aO+a1x+a2x2++anxn和B(x)=bO+b1x+b2x2七+bmxm，并且在A(x)和8(x)中指数相差很多，求A(x)=A(x)+8(x)。1.基本要求(1)设计存储结构衣示一元多项式；(2)设计算法实现一元多项式相加；⑶分析算法的时间复杂度和空间复杂度。2.设计思想一元多项式求和实质上是介并同类项的过程，其运算规则为：(1)若两项的指数相等，则系数相加；⑵若两项的指数不等，则将两项加在结果中。一元多项式力(x)=曰0+日1卅•日2+

4、+anxn由门+1个系数唯一确定，因此，可以用一个线性表(日0,自1,a2,..…，an)来表示，毎-•项的指数/隐含在其系数日/•的序号里。但是，当多项式的指数很高且变化很大时，在表示多项式的线性表中就会存在很多零元素。一个较好的存储方法是只存非零元索，但是需要在存储非零元索系数的同时存储相应的指数。这样，一个一元多项式的每一个非零项可由系数和指数唯一衣示。山于两个一元多项式相加后，会改变多项式的系数和指数，因此采用顺序表不合适。采用单链表存储,则每一个非零项对应单链表中的一个结点，且单链表应按指数递増冇序排列。结点结构如图2-2所示。coefescpnextB2-2一元多

5、项式单犍表的结点结构其中,coef:系数域,存放非零项的系数;exp:指数域,存放非零项的指数;next:指针域,存放指向下一结点的指针。将两个一元多项式用两个单链表存储后，如何实现二者相加呢？设两个工作指针p和q,分别指向两个单链表的开始结点。通过对结点p的指数域和结点q的指数域进行比较进行同类项合并，则出现F列三种情况：⑴若p->expexp,则结点p应为结果屮的一个结点；⑵若p->exp>q->exp,则结点q应为结果中的一个结点，将q插入到笫一个链表屮结点p之前；⑶若p->exp=q->exp，则结点p与结点q为同类项，将q的系数加到p的系数上。若相加结果不为

6、0,则结点p应为结果中的一个结点，同时删除结点q；若相加结果为0,则表明结果中无此项，删除结点p和结点q；算法用伪代码描述如下：戲/l.工作扌雜十p、q初始化；憾/2.while（p存在且q存在）执行下列三种情形之一y2.1如果p->expexp,则指针p后移；22如果p->exp>q->expJ则2.2.1将结点q插入到结点p之前；2.2.2指针q指向原指结点的下一个结点；23如果p->exp=q->expJ则2.3.1p->coef=p->coefi-q->coef；2.3.2如果p->coef=0,则执行下列操作，否则，指针p后移;2321刪除结点p；2322指

7、向它原指结点的下一个结点；2.3.3刪除结点q；2.3.4使指针q指向它原指结点的下一个结点；3.如果q不为空，将结点q链接在第一个单链表的后面；三、信号放大器1.问题描述天然气经过管道网络从其生产基地输送到消耗地，在传输过程中，其性能的某一个或儿个方面可能会有所哀减（例如气压）。为了保证信号衰减不超过容忍值，应在网络中的合适位置放置放大器以増加信号（例如电压）使其与源端相同。设计算法确定把信号放大器放在何处，能使所用的放大器数目最少并H保证信号衰减不超过给定的容忍值。2.基本要求（1）建立模熨，设计数