小游戏(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;
}
可对比以下两篇文章游戏(约瑟夫问题)和约瑟夫问题(单向链表解法&队列法)
若有错误,望各位大神指出!共同进步。
更多推荐
数七小游戏(C++)
发布评论