数据结构实验报告-实验三-约瑟夫问题、多项式乘法问题的求解

冷不防 2023-06-17 03:58 2阅读 0赞

# **实验三 约瑟夫问题、多项式乘法问题的求解** #

## 问题一：约瑟夫问题的求解 ##

### 一、实验描述 ###

N人围成一个圈，每经过K个人就消灭一个人，谁将是最后的幸存者？

### 二、实验分析 ###

（1）将人的顺序简单编号，从1到N；

（2）构造一个循环链表，可以解决首位相连的问题，同时如果将人的编号改为人名或者其他比较方便

（3）将人的编号插入到结构体的Data域；

（4）遍历人的编号，输出参与的人的编号；

（5）开始报数，从头报数，报到k的人出局（删除次结点），（输出出局的人更人性化）避免浪费，可释放次结点。直到人数只有一个人时，退出循环。输出获胜的人。

（6）在写删除删除结点的函数时都是针对K>=2的情况处理，所以要考虑k=1的情况，要是出局的密码为1时则最后一个获胜。

### 三、实验设计 ###

1.基本思想：

(1)确定需要删除的位置，

(2)设置并删除该位置。

已知报数间隔m，我们可以把当前位置加上m获得需要删除的位置，如果获得的位置超过顺序表中实际元素的总长度，则可以通过减去数组的实际长度来修正（即模拟环状计数）。然后把顺序表中的当前指向位置设置为该位置，继而删掉该位置。

反复进行上述确定位置和删除位置的操作，直到顺序表为空。

2.主程序的流程：

程序由三个模块组成：

①输入模块：无提示语句，直接输入总人数n和报数次数m，中间用逗号隔开。

②处理模块：将元素储存于顺序表中。在主函数中根据报数间隔确定需要删除的元素的位置，在顺序表中设置该位置并删除该位置，同时输出该位置的值。反复设置并删除直到表空。

③输出模块：分别在DOS下和文件中，按移除元素的顺序依次显示其位置。

各程序模块之间的层次（调用）关系：

主函数会按设计的方法调用顺序表中“获取实际长度”、“设置需要删除元素的位置”、“移除该位置元素”和“判断是否为空表”四种方法方法，使元素依次出列，并正确结束程序

约瑟夫问题的代码实现：

#include<stdio.h>  
    #include<malloc.h>  
    #include<stdlib.h>  
    /*宏定义和单链表类型定义*/  
    #define ListSize 100  
    typedef int DataType;  
    typedef struct Node  
    {  
        DataType data;  
        struct Node *next;  
    } ListNode,*LinkList;  
    /*函数声明*/  
    LinkList  CreateCycList(int n);/*创建一个长度为n的循环单链表的函数声明*/  
    void Josephus(LinkList head,int n,int m,int k); /*在长度为n的循环单链表中，报数为编号为m的出列*/  
    void DisplayCycList(LinkList head);/*输出循环单链表*/  
    void main()  
    {  
        LinkList h;  
        int n,k,m;  
        printf("输入环中人的个数n=");  
        scanf("%d",&n);  
        printf("输入开始报数的序号m=");  
        scanf("%d",&k);  
        printf("输出结果为：");  
        scanf("%d",&k);  
        h=CreateCycList(n);  
        Josephus(h,n,m,k);  
    }  
      
    void Josephus(LinkList head,int n,int m,int k)  
    /*在长度为n的循环单链表中，从第k个人开始报数，数到m的人出列*/  
    {  
        ListNode *p,*q;  
        int i;  
        p=head;  
        for(i=1; i<k; i++) /*从第k个人开始报数*/  
        {  
            q=p;  
            p=p->next;  
        }  
        while(p->next!=p)  
        {  
            for(i=1; i<m; i++) /*数到m的人出列*/  
            {  
                q=p;  
                p=p->next;  
            }  
            q->next=p->next; /*将p指向的结点删除，即报数为m的人出列*/  
            printf("%4d",p->data)；  
            free(p);  
            p=q->next; /*p指向下一个结点，重新开始报数*/  
        }  
        printf("%4d\n",p->data);  
    }  
      
    LinkList CreateCycList(int n)  
    /*宏定义和单链表类型定义*/  
    {  
        LinkList head=NULL;  
        ListNode *s,*r;  
        int i;  
        for(i=1; i<=n; i++)  
        {  
            s=(ListNode*)malloc(sizeof(ListNode));  
            s->data=i;  
            s->next=NULL;  
            if(head==NULL)  
                head=s;  
            else  
                r->next=s;  
            r=s;  
        }  
        r->next=head;  
        return head;  
    }  
      
    void DisplayCycList(LinkList head)  
    /*输出循环链表的每一个元素*/  
    {  
        ListNode *p;  
        p=head;  
        if(p==NULL)  
        {  
            printf("该链表是空表");  
            return;  
        }  
        while(p->next!=head)  
            /*如果不是最后一个结点，输出该结点*/  
        {  
            printf("%4d",p->data);  
            p=p->next;  
        }  
        printf("%4d\n",p->data);/*输出最后一个结点*/  
    }

运行输出结果：

输入环中人的个数n=7

请输入每个人的密码：3 1 7 2 4 8 4

输入开始报数的序号m=20

输出结果为：6 1 4 7 2 3 5

### 四、实验结论 ###

1.初始化部分为循环赋值，时间复杂度为O(n)。

2.处理部分，我为了提高效率没有采用循环寻找的方法，直接利用数学关系通过当前位置获得下一位置，因此对于长度为n的约瑟夫环，只做了n次定位，每次定位的复杂度为O(1)，所以时间复杂度为O(n)。

但是用顺序表实现时，每次其移除的方法是时间复杂度为O(k)的(k与实际长度有关)，化简后时间复杂度仍然为O(n^2)。

综上，该算法的时间代价为O(n^2)。

（如果是用循环查找，在n次定位中每次都使用了m次的循环，至少是O(n\*m)，然后再用顺序表的移除方法，总的复杂度应该是O(m\*n^2)的）

## 问题二：多项式乘法问题的求解 ##

### 一、实验描述 ###

用链表表示多项式，分别在对指数排序和不排序的情况下，写出两个给定多项式的乘法的函数，并计算其复杂程度。

### 二、实验分析 ###

1.分别设置两个求多项式乘法结果的函数，一个为排好序的多项式乘法，另一个为无序的多项式，其对应的函数名分别为：顺序 MultPolynomial\_inorder 无序 MultPolynomial

2.比较两个算法的复杂程度和时间，多项式从1一直到1+x+x2+…+xn，比较从1到n的数据。对标准的多项式乘法的算法可以使用任意多项式进行乘法计算。

3.对于排序好的序列，每次查找多项式只需从上一项之后查找，与幂数相等的系数。而对于无序多项式的乘法，则需要遍历所有的多项式，找到与此幂数相等的系数，再做加法。

4.定义两个时间类型变量，分别用于记录一个函数执行前后的时间，将两个时间相减并除以一个常数，便可以得到该函数的运行时间。

5.通过分析获取的时间，比较两种算法的时间复杂度。

### 三、实验设计 ###

1.定义clock\_t 变量 start\_time，end\_time来存放函数开始执行的时间和停止执行的时间。

2.使用(double) (end\_time - start\_time) 即可得到double类型的数值用来记录运行时间。

3.定义方法：

两个多项式的乘法

void MultPolynomial\_inorder( PtroToNode Poly1, PtroToNode Poly2,PtroToNode PolyProd) 顺序的多项式乘法 （参数为两个多项式的指针）

void MultPolynomial( PtroToNode Poly1, PtroToNode Poly2,PtroToNode PolyProd)

4.合并同类项

PtroToNode insert(PtroToNode list,PtroToNode p)

//并返回当前插入位置的指针（这个返回值，可以体现排序多项式的优越性）

5.构造多项式

void Input\_1(PtroToNode Poly1, PtroToNode Poly2, int n)

void Input\_2(PtroToNode Poly1, PtroToNode Poly2,int n)

幂数从1开始，直到n

6.主函数

分别调用

void Input\_1(PtroToNode Poly1, PtroToNode Poly2, int n)

void Input\_2(PtroToNode Poly1, PtroToNode Poly2,int n)

构造多项式

计算幂数数从100-1000依次递增100的多项式乘积所用的时间

7.对n的各个取值，分别用两个算法计算其多项式的值，每个函数均执行1,000,000次。在函数执行前，加上代码：start\_time = clock (); 函数执行后，加上代码：end\_time = clock (); ,得到函数执行前的时间和执行后的时间。

8.(double) ((end\_time - start\_time) / (double)CLOCKS\_PER\_SEC),得到运行时间，单位为秒，类型为double.

9.重复5次实验，得到平均数据。

10.将执行时间的平均数据输入到Excel中，生成坐标图，多项式项数n，纵坐标为函数执行1,000,000次所需的时间。

### 四、实验结论 ###

1.实验结果很明显，排序的乘法用时远远小于未排序的时间

2.设运行时间为T(n)，未排序时，有T(1) = 1，f(x, n) = Cx^n+f(n-1)，所以f(x, n)\*f(x, n) = C\*C\*x^2n+2Cx^n\*f(x, n-1)+f(x, n-1)\*f(x, n-1)，在多项式中寻找与此项幂数相同的项进行合并同类项，由于之前的式子未排序，所以指数分布没有规律，必须从第一项开始寻找，直到找到幂数相同的项

T( n ) = T( n – 1 ) + n ^ 2 + 1,

则T( n ) =O ( 1 / 6 \* n \* ( n + 1 ) ( 2 n + 1 ) ) = O ( n ^ 3 )。与实验结果相符。

3.设运行时间为T(n)，对排序时，有T(1) = 1，f(x, n) = Cx^n+f(n-1)，所以f(x, n)\*f(x, n) = C\*C\*x^2n+2Cx^n\*f(x, n-1)+f(x, n-1)\*f(x, n-1)，在多项式中寻找与此项幂数相同的项进行合并同类项，由于之前的式子已排序，所以指数分布由高到低，查找只需从上一项指针之后查找即可，直到找到幂数相同的项

可知T(n) = T(n – 1) + n + 1，T(n) = O(n^2)时间复杂程度为O(n^2),与实验结果相符

4. n较小时，数据呈现不规则的情况，这是因为程序运行速度较快，系统噪声对执行时间有所影响。当n较大的时候，时间的增长便有规律了。

5.通过算法分析和实验结果，均证明排好序的多项式乘法更优。