欢迎吹毛求疵 QQ ：1423173783 邮箱：1423173783@qq.com
/*问题描述：有length个人坐在圆桌吃饭编号从1到length，买单的人只能是一个人，他们争着买单。为了决定谁买单
他们制订了一套规则：从编号为start的人开始报数，按编号递增的顺序报数从1报到standard，下一个人又开始报1.
当一个人第hittimes次报数为standard此人便丧失买单的权利即出局，以后也不参与报数。*/
/*输出描述： 屏幕会输出编号1到length两遍，每行输出10个编号，这个输出的目的是检查循环单链表的create是否
成功，当length 后紧跟1表示循环单链表create成功。 接着输出出局顺序，出局人按先后顺序保存到向量trace中
trace存储的是出局人的编号。*/
/*程序用C描述，在VC2010编译运行得到预期值，没有经过大量测试。测试数据为 length=12，start=1
standard=14642，hittimes从1取到10，相应的买单者编号为9,1,11,11,11,5,5,5,1,1*/
/*优缺点分析：优点是思路清晰，容易理解，变量名称可读性强，缺点是当问题规模很大时，时空复杂度有待改进*/
/*极限测试 10000 23 14642 78运行分时长4分钟
100000 23 14642 78 运行时长38分钟*/
#include <iostream>
#include<iomanip>
#include <vector>
using namespace std;
typedef struct linknode
{
int number;
bool sign;
int times;
struct linknode *next;
} node;
node* create(int length)
{
node *head ,*p,*s;
int i=1;
head=(node*)malloc(sizeof(node));
p=head;
while(i<=length)
{
s=(node*)malloc(sizeof(node));
s->number=i;
s->sign=true;
s->times=0;
p->next=s;
p=s;
i++;
}
p->next=head->next;
p=head;
head=head->next;
free(p);
return(head);
}
int main()
{
int length,start,standard,hittimes,statistics=0,person=0,see;
/*变量说明：length：人形成的圆环的长度 ；start：从第几个人开始报数；standard：报到哪个数停止
hittimes：有几次被打击顾名思义就是同一个人有几次报到standard这个数；
statistics：统计值就是报数时不断累加的信号值，累加到standard又重设为0；
person：即作为死亡顺序向量的下标，又用作while循环的跳出条件
see：仅为了看终端屏幕的输出结果*/
vector<int> trace;
node* cycle;
node* head;
cin>>length>>start>>standard>>hittimes;
/*接口描述：从屏幕上输入您要解决的问题的相关参数
参数顺序为：length start standard hittimes 建议参数之间输入空格standard可以远远大于
length，以上参数皆为正整数*/
head=create(length);
cycle=head;
for(int i=0;i<2*length;i++)
{ cout<<setw(6)<<cycle->number<<" ";
if(i%10==9) cout<<endl;
cycle=cycle->next;
}
cout<<endl;
for(int i=0;i<start-1;i++)
head=head->next;
while(person<length)
{
if(head->sign==true)
{
statistics++;
if(statistics==standard)
{
head->times++;
if(head->times==hittimes)
{
trace.push_back(head->number);
person++;
head->sign=false;
statistics=0;
}
else statistics=0;
}
}
head=head->next;
}
for( int i=0;i<person;i++)
{
cout<<setw(6)<<trace[i];
if(i%10==9) cout<<endl;
}
cout<<endl;
cin>>see;
}