数据结构实验报告三：教材3.10Josephus（约瑟夫环）问题、多项式乘法问题的求解

蔚落 2022-05-31 10:58 56阅读 0赞

# **实验三：教材3.10Josephus（约瑟夫环）问题、多项式乘法问题的求解** #

## 问题一·教材3.10Josephus问题 ##

### 1、实验描述 ###

N个人从1到N编号，围坐成一个圆圈。从1号开始传递一个热土豆。经过M次传递后拿着热土豆的人被清楚离座，围坐的圆圈缩紧。由坐在被清楚的人后面的人拿起热土豆继续进行游戏。最后剩下的人取胜。

### 2、问题分析与算法设计 ###

使用游标法，创建结构体数组，结构体元素中包括编号、上一个未被清除元素的索引（上游标）、下一个未被清除元素的索引（下游标）。通过迭代法进行循环，当p节点被删除时，更改p前节点的下游标和p后节点的上游标。每一重循环删除一个节点，并更新当前节点的索引。当当前节点的索引和当前节点的下游标相同时，意味着数组中只剩下一个元素，即为留下的最后一个元素。

### 3、实验实现过程 ###

代码：

#include<stdio.h>
    
    #defineN (5)
    
    #defineM (2)
    
     
    
    //define a list using cursors
    
    typedefstruct
    
    {
    
        int number;
    
        int lastIndex;//上游标
    
        int nextIndex;//下游标
    
    }listNode;
    
     
    
    staticlistNode list[]=
    
    {
    
        {1,4,1},
    
        {2,0,2},
    
        {3,1,3},
    
        {4,2,4},
    
        {5,3,0},
    
    };
    
     
    
    staticint Josephus(intn,intm)
    
    {
    
        int curIndex=m;
    
        while(curIndex!=list[curIndex].nextIndex)
    
        {
    
           if(list[curIndex].number>0)
    
            {
    
               printf("%d->",list[curIndex].number);//打印当前游标的编号
    
               list[curIndex].number=-1;//删除当前节点
    
               intlast=list[curIndex].lastIndex;
    
               intnext=list[curIndex].nextIndex;
    
               list[last].nextIndex=(next)%n;//更新前一个节点的游标
    
               list[next].lastIndex=(last)%n;//更新后一个节点的游标
    
               for(int i=0;i<m;i++)
    
               {
    
                    if(list[curIndex].number>0)//当前节点未被删除，寻找m内的下一个节点
    
                      curIndex=(list[curIndex].nextIndex)%n;
    
                  else//当前节点已被删除，寻找m内的下一个节点
    
                  {
    
                      curIndex=(curIndex+1)%n;
    
                      i--;
    
                  }
    
               }  
    
           }
    
           else
    
               curIndex=list[curIndex].nextIndex;
    
        }
    
        returnlist[curIndex].number;  
    
    }
    
    int main()
    
    {
    
        printf("the alive one:%d",Josephus(N,M));
    
    }

### 4、实验结果分析 ###

测试用例：N=5，M=0时：

![70][]

N=5，M=1时：

![70 1][]

N=5，M=2时：

![70 2][]

实验结果正确。

很明显，该算法主要有两重循环，外循环遍历整个结构体数组T(N)=O(N)，内循环寻找后m个存活的节点T(N)=O(M)。总体时间复杂度为T(N)=O(N\*M)。

### 5、算法改进： ###

问题重述：n个人编号0~(n-1)，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。  
    第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环，以编号为k=m%n的人开始:即k，k+1，k+2，...，n-2, n-1, 0, 1, 2, ... k-2并且从k开始报0。  
现在我们把他们的编号做一下转换：  
     k   --> 0  
     k+1  --> 1  
     k+2  --> 2  
     ...  
     k-2  --> n-2  
   变换后就成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去就是n个人情况的解。变回去的公式为x'=(x+k)%n。

令f\[i\]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f\[n\]。  
   递推公式  
    f\[1\]=0;  
    f\[i\]=(f\[i-1\]+m)%i;  (i>1)

代码：

#include<stdio.h>
    
    int main()
    
    {
    
        int n, m, i, s = 0;
    
        printf("N M = ");
    
        scanf("%d%d", &n, &m);
    
        for (i = 2; i <= n;i++)
    
        {
    
           s= (s + m) % i;
    
        }
    
        printf("\nThe winner is %d\n", s + 1);
    
    }

此时的时间复杂度为T(N)=O(N)。

## 问题二·多项式乘法问题 ##

### 1、实验描述 ###

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

### 2、问题分析与算法设计 ###

构造两个链表p1、p2，每个链表节点中存放多项式其中一项的系数和次数，以及下一节点的地址。再构造一个总链表p，代表p1、p2相乘后得到的多项式。总链表每一项的系数为对应p1、p2节点系数之积，每一项的次数为对应p1、p2节点次数之和。用两重循环遍历p1、p2,按照规定的计算方法将相乘所得的指数和次数存入总链表p中。更新总链表时先遍历以及建立的总链表p，看看其中是否以及存在同次项，若存在，更改同次项的系数；若不存在重新开辟一个节点表示该项。

### 3、实验实现过程 ###

代码：

#include<stdio.h>
    
    #include<malloc.h>
    
    #include<stdlib.h>
    
    #defineSUCCESS 1;
    
    #defineFAILURE 0;
    
     
    
    typedefstructnode
    
    {
    
        int coefficient;
    
        int degree;
    
        node* next;
    
    }Polynomial;
    
     
    
    Polynomial *head, *p1, *p2;;
    
     
    
    Polynomial* createPoly()
    
    {
    
        Polynomial *p1, *p2, *head;
    
        p1= p2 = (Polynomial *)malloc(sizeof(Polynomial));
    
        head= p1;
    
        for (int i = 0;i < 5;i++)
    
        {
    
           if (i < 4)
    
               p1= (Polynomial *)malloc(sizeof(Polynomial));
    
           p2->coefficient= i + 1;
    
           p2->degree= 2 * i;
    
           p2->next= p1;
    
           p2= p1;
    
        }
    
        p1->next= NULL;
    
        return head;
    
    }
    
     
    
    Polynomial* search(intpDegree, Polynomial *head)
    
    {
    
        while (head != NULL)
    
        {
    
           if (head->degree == pDegree)
    
               returnhead;
    
           head = head->next;
    
        }
    
        returnNULL;
    
    }
    
     
    
    int polyMult(Polynomial *p1, Polynomial *p2)
    
    {
    
        if (p1 == NULL || p2 == NULL)
    
        {
    
           returnFAILURE;
    
        }
    
        Polynomial *p0 = p2;
    
        Polynomial *temP1 = NULL;
    
        Polynomial *temP2 = NULL;
    
        Polynomial *pSearch = NULL;
    
        int pCoefficient = 0;
    
        int pDegree = 0;
    
        head= temP1 = temP2 = (Polynomial *)malloc(sizeof(Polynomial));
    
        head->next= NULL;
    
        //遍历链表
    
        while (p1 != NULL) {
    
           while (p2 != NULL)
    
           {
    
               //找是否存在同次项
    
               pCoefficient= p1->coefficient*p2->coefficient;
    
               pDegree= p1->degree + p2->degree;
    
               pSearch= search(pDegree, head);
    
               if (pSearch != NULL)
    
                  pSearch->coefficient+= pCoefficient;
    
               else
    
                  //新插入节点
    
               {
    
                  temP1= (Polynomial *)malloc(sizeof(Polynomial));
    
                  temP1->next= NULL;
    
                  temP2->coefficient= pCoefficient;
    
                  temP2->degree= pDegree;
    
                  temP2->next= temP1;
    
                  temP2= temP1;
    
               }
    
               p2 = p2->next;
    
           }
    
           p1 = p1->next;
    
           //从头开始
    
           p2 = p0;
    
        }
    
        temP2->next= NULL;
    
        returnSUCCESS;
    
    }
    
    int main()
    
    {
    
        //创建两个多项式
    
        p1= createPoly();
    
        p2= createPoly();
    
     
    
        polyMult(p1,p2);
    
        {
    
           if (NULL != head)
    
           {
    
               while (head != NULL)
    
               {
    
                  printf("%dx^%d + ", head->coefficient, head->degree);
    
                  head= head->next;
    
               }
    
           }
    
        }
    
        system("PAUSE");
    
        return 0;
    
    }

### 4、实验结果分析 ###

测试用例：p1=p2=2x^2+3x^4+4x^6+5x^8。

输出：

![70 3][]

结果正确。

### 5、时间复杂度分析 ###

遍历p1、p2的两重循环需要O(N2)的时间复杂度，插入和输出均为线性时间复杂度。所以总的时间复杂度T(N)=O(N2)。若采取排序，则减少了检查插入的步骤，但遍历p1、p2的两重循环依然存在，总的时间复杂度仍为T(N)=O(N2)。

[70]: /images/20220531/6810ae634cac4ec8bccc8b52f7a1b289.png
[70 1]: /images/20220531/086d34d7d5f140d49f0b56b2ab076f2e.png
[70 2]: /images/20220531/4cc3d4da31ea4680812bc19cc2cf3b97.png
[70 3]: /images/20220531/cb96c8060a3b48da8d054a037732757f.png