数据结构之顺序表应用-----《约瑟夫问题》
1.问题描述:
2.算法思路:
3.算法描述:
{ /*求解约瑟夫问题的出列元素序列的入口参数:已经存放数据的顺序表josephus_seq,起始序号s,计数值m*/
/*出口参数:1表示成功,0表示表中无元素*/
if(!josephus_seq->length)
{
printf("表中无元素!\n");
return 0;
}
s1=s-1;/*--------------------------------------------------data数组中的下标从0开始*/
printf("输出约瑟夫序列:\n");
for(i=josephus_seq->length;i>0;i--)
{
s1=(s1+m)%i;/*----------------------------------------找到出列元素的下标*/
w=josephus_seq->data[s1];
printf("%d\t",w);
Delete_SeqList(josephus_seq,s1+1);/*-----------删除出列元素*/
}
return 1;/*---------------------------------------------------返回成功*/-
4.具体程序实现:
#include<cstdio>
#include<cstdlib>
#define MAXSIZE 100
typedef struct node
{
int data[MAXSIZE];
int length;
}SeqList,*PSeqList;
PSeqList Init_SeqList(void)
{
PSeqList PL;
PL=(PSeqList)malloc(sizeof(SeqList));
if(PL)
PL->length=0;
return PL;
}
/*
int Location_SeqList(PSeqList L,int x)
{
int i=0;
while(i<L->length&&L->data[i]!=x)
{
i++;
}
if(i>=L->length)
return 0;
else
return i;
}
int Insert_SeqList(PSeqList PL,int i,int x)
{
int j;
if(!PL)
{
printf("表不存在!\n");
}
if(PL->length>=MAXSIZE)
{
printf("表溢出!\n");
}
if(i<1||i>PL->length+1)
{
printf("表插入的位置不合法!\n");
}
for(j=PL->length-1;j>=i-1;j--)
{
PL->data[j+1]=PL->data[j];
}
PL->data[i-1]=x;
PL->length++;
}*/
int Delete_SeqList(PSeqList PL,int i)
{
int j;
if(!PL)
{
printf("表不存在!\n");
}
if(i<1||i>PL->length)
{
printf("表删除的位置不合法!\n");
}
for(j=i;j<PL->length;j++)
{
PL->data[j-1]=PL->data[j];
}
PL->length--;
return (1);
}
int josephus_SeqList(PSeqList josephus_seq,int s,int m)
{
int s1,i,w;
if(!josephus_seq->length)
{
printf("表中无元素!\n");
return 0;
}
s1=s-1;
printf("输出约瑟夫序列:\n");
for(i=josephus_seq->length;i>0;i--)
{
s1=(s1+m)%i;
w=josephus_seq->data[s1];
printf("%d\t",w);
Delete_SeqList(josephus_seq,s1+1);
}
return 1;
}
void main()
{
int s,m,n,i;
PSeqList josephus_seq;
josephus_seq=Init_SeqList();
printf("输入约瑟夫问题中的人数: n= ");
scanf("%d",&n);
josephus_seq->length=n;
putchar('\n');
printf("输入约瑟夫问题中的编号: \n");
for(i=0;i<josephus_seq->length;i++)
{
scanf("%d",&josephus_seq->data[i]);
}
printf("输入起始序号: s= ");
scanf("%d",&s);
putchar('\n');
printf("输入计数值: m= ");
scanf("%d",&m);
putchar('\n');
josephus_SeqList(josephus_seq,s,m);
putchar('\n');
}
5.运行结果截图:
6.算法评价:
该算法运行的主要时间耗费在求出列元素(总共需要出n个元素),每求出一个出列元素调出Delete_SeqList()函数一次,所以时间复杂度O(n^2)。