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

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

一、实验描述

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.通过算法分析和实验结果，均证明排好序的多项式乘法更优。