数七小游戏（C++）

小游戏（C++）"/>

数七小游戏（C++）

数七小游戏

【问题描述】
由n人围成一个圈，编号从1～n，从第1号开始报数，报到7的倍数的人离开，一直这样循环数下去，直到最后只剩下1个人，求此人的编号。

【解题】
方法1：数组
进行每一轮游戏，被淘汰的人的编号被记录在一个数组中，在进行接下来的m轮游戏数数时跳过记录数组中所记录的元素编号，直到剩下最后一个元素。（但效率较低）

#include<iostream>
using namespace std;
int panduan(int p[],int,int);
int main()
{int n;cin>>n;int a[n+1];for(int i=1;i<=n;i++){a[i]=i;}int sum=0,t=0;int b[500]={0};for(int i=1;i<=n;i++){if(panduan(b,i,n)==1) {sum++;}if(sum%7==0){if(panduan(b,i,n)==1){b[t++]=a[i];}}if(sum==7*(n-1)+1) {cout<<a[i]<<endl;break;}if(i==n) {i=0;}}return 0;
}
int panduan(int p[],int c,int n)
{int f=1;for(int i=0;i<n;i++){if(c==p[i]) {f=0;break;}}return f;
}

方法2
原理：n阶约瑟夫环问题的求解

#include<iostream>
using namespace std;
int main()
{int n;cin>>n;int s=0;for(int i=2;i<=n;i++){s=(s+7)%i;}cout<<s+1<<endl;return 0;
}

方法3：单向链表
创建一个以n个人为游戏成员的圈（约瑟夫环），每个游戏成员都有一个指向下一个成员的指针，游戏从编号为1的成员开始，当某个成员被踢除时，则将它的上一个成员指向下一个成员的指针指向它的下一个成员，因而形成新的游戏圈。（也可尝试双向链表方法）

#include <iostream>
using namespace std;
class player
{
private:int num;player* next;
public:player(int n){num=n;}int getnum(){return num;}void setnext(player* p){next=p;}player* getnext(){return next;}
};
class cycle
{
private:int quantity;player *start;
public:cycle(int q){quantity=q;player* first=NULL;player* m=NULL;for(int i=1;i<=quantity;i++){player* p;p=new player(i);if(i==1){first=p;start=p;}if(i>1){m->setnext(p);}m=p;        //指针获取地址}m->setnext(first);}player* getstart(){return start;}int getquantity(){return quantity;}void out(){player* p;p=getstart();int n=1;while(n!=6){p=p->getnext();n++;}player* q;q=(p->getnext());p->setnext(q->getnext());   //删除该成员的关键步骤：将p的next指针跳过被提出的成员直接指向下一个start=q->getnext();quantity--;}~cycle(){delete start;}
};
int main()
{int n;cin>>n;cycle* p=new cycle(n);while(p->getquantity()>0){p->out();}player* winner=p->getstart();cout<<winner->getnum()<<endl;return 0;
}

可对比以下两篇文章游戏（约瑟夫问题）和约瑟夫问题（单向链表解法&队列法）
若有错误，望各位大神指出！共同进步。