Question

Josephus问题 C++编程

Josephus问题是说， n 个小孩围成一圈做游戏，游戏将决出一个胜利者。从第 s 个小孩起，顺时针计数，每数到第 m 个小孩时，该小孩离开。接着又从下一个小孩开始数数，数到第 m 个小孩时，该小孩离开，如此不断反复进行，最后剩下的小孩就是胜利者。在这里,我们扩展为求 w 个胜利者。n、s、m和w在应用程序里输入。提示：作为一个要处理的Josephus问题，可以把它定义为一个类， 属性有小孩数 n 、数数开始位置 s 和计数间隔m，求获胜者作为操作。求获胜者需要操作代表一圈小孩的环链表，可以把它定义为一个类，包括数m个小孩、小孩离开、返回离开小孩编号等操作。

Answer 1

#include <iostream>
#include <assert.h>using namespace std;class LinkedListNode
{
private:
int m_intNoOfChild;
LinkedListNode *m_pNextNode;
public:
LinkedListNode(int intNoOfChild)
{
m_intNoOfChild = intNoOfChild;
m_pNextNode = NULL;
}
int GetNo()
{
return m_intNoOfChild;
}
void SetNextNode(LinkedListNode *pNextNode)
{
m_pNextNode = pNextNode;
}
LinkedListNode *GetNextNode()
{
return m_pNextNode;
}
}class CirLinkedList
{
private:
int m_intNumChildren;
LinkedListNode *m_pHeadNode;
LinkedListNode *m_pCurrNode;
LinkedListNode *m_pPrevNode;
public:
CirLinkedList(int intNumChildren);
~CirLinkedList();
void Count(int intInterval);
int GetNoOfCurrentChild();
int Dequeue();
int NumOfRestChildren() { return m_intNumChildren; }
}
CirLinkedList::~CirLinkedList()
{
if (m_intNumChildren==0)
return;
LinkedListNode *pTmpNode;
for (int i=0; i<m_intNumChildren; ++i)
{
pTmpNode = m_pCurrNode->GetNextNode();
delete m_pCurrNode;
m_pCurrNode = pTmpNode ;
}
}
CirLinkedList::CirLinkedList(int intNumChildren)
{

m_intNumChildren = intNumChildren;

m_pCurrNode = new ListedListNode(1);
m_pHeadNode = m_pCurrNode;
//m_pPrevNode = NULL;
for(int i=2; i<=intNumChildren; ++i)
{
m_pPrevNode = pCurrNode;
m_pCurrNode = new LinkedListNode(i);
m_pPrevNode->SetNextNode(pCurrNode);
}
m_pCurrentNode->SetNextNode(pHeadNode);
m_pPrevNode = m_pCurrNode;
m_pCurrNode = m_pHeadNode;
}
void CirLinkedList::Count(int intInterval)
{
for (;intInterval>0; intInterval--)
{
m_pPrevNode = m_pCurrNode;
m_pCurrNode = m_pCurrNode->GetNextNode();
}
}
int CirLinkedList::GetNoOfCurrentChild()
{
return m_pCurrNode->GetNo();
}
int CirLinkedList::Dequeue()
{
if (0==m_intNumChildren)
return -1; imt intCurrNo ;
intCurrNo = m_pCurrNode->GetNo();
if (m_intNumChildren>1)
{
m_pPrevNode->SetNextNode(m_pCurrNode->GetNextNode());
delete m_pCurrNode;
m_pCurrNode = m_pPrevNode->GetNextNode();
}
else
{
delete m_pCurrNode;
m_pPrevNode = NULL;
m_pCurrentNode = NULL;
m_pHeadNode = NULL;
}
m_intNumChildren--;
return intCurrNo;
}class Josephus
{
private:
int *m_pWinners;
int *m_pDequeueOrder;
public:
int intNumChildren;
int intBegin;
int intInterval;
int intNumOfWinners; Josephus() { m_pWinners=NULL; m_pDequeueOrder=NULL; intNumChildren=0; intBegin=0; intInterval=0;} ~Josephus()
{
if (m_pWinners!=NULL)
delete m_pWinners;
if (m_pDequeueOrder!=NULL)
delete m_pDequeueOrder;
} void Resolve();
void OutputDequeueOrder();
void OutputWinners();
}void Josephus::Resolve()
{
assert(intNumChildren>0);
assert(intBegin>0 && intBegin<=intNumChildren);
assert(intInterval>0);
assert(intNumOfWinners>0);
m_pWinners = new int[intNumOfWinners];
m_pDequeueOrder = new int[intNumChildren-intNumOfWinners]; CirLinkedList OneJosephus(intNumChildren); OneJosephus.Count(intBegin-1); int Counter = 0;
while(OneJosephus.NumOfRestChildren()>intNumOfWinners)
{
OneJosephus.Count(intInterval);
m_pDequeueOrder[i] = OneJosephus.GetNoOfCurrentChild();
OneJosephus.Dequeue();
Counter ++;
}

for (int i=0; i<intNumOfWinners; ++i)
{
m_pWinners[i] = OneJosephus.GetNoOfCurrentChild();
OneJosephus.Count(1);
}
}
void Josephus::OutputDequeueOrder()
{
for(int i=0; i<intNumChildren-intNumOfWinners; ++i)
{
cout << "第" << i+1 << "个离开的孩子是号码为:"<< m_pDequeueOrder[i] << "的孩子" << endl;
}
}
void Josephus::OutputWinners()
{
cout << "获胜的孩子为:" << endl;
for (int i=1; i<=intNumOfWinners; ++i)
{
cout << m_pWinners[i-1];
if (i%5 == 0)
count << endl;
else if (i != intNumOfWinners)
count << ", ";
}
}
void main()
{
int n,s,m,w;
cout << "请输入小孩子数 : ";
cin >> n;
cout << endl << "从第几个小孩子数起:";
cin >> s;
cout << endl << "计数间隔为:";
cin >> m;
cout << endl << "有几个胜利者:";
cin >> w;
Josephus OneGame();
OneGame.intNumChildren = n;
OneGame.intBegin = s;
OneGame.intInterval = m;
OneGame.intNumOfWinners = w;
OneGame.Resolve();
OneGame.OutputDequeueOrder();
cout << endl;
OneGame.OutputWinners();
}

Answer 2

哥给你做出来了,挺好玩的，调了N久。跟提示有点不一样，我的函数不是在类里写的，是在MAIN里直接写的。那几个参数可以调的，在那个初始化设置里，代码很简单。play.cpp:#include "play.h"
#include "iostream.h"void main()
{
int n=0;
int s=0;
int m=0;
int j=0; int i=0;
int c=0;
int x=0;
int y=0;
//游戏初始设置
SHURUN:
cout<<"请输入玩家数目n(0-20):"<<endl;
cin>>n;
if (n>20||n<1)
{
cout<<"请输入一个0到20之间的n"<<endl;
goto SHURUN;
}
SHURUS:
cout<<"请输入开始位置s(小于等于n):"<<endl;
cin>>s;
if (s>n||s<1)
{
cout<<"请输入一个小于等于n的s"<<endl;
goto SHURUS;
}
SHURUM:
cout<<"请输入剩余胜利者数目m(1-n):"<<endl;
cin>>m;
if (m>n||m<2)
{
cout<<"请输入一个1到n之间的m"<<endl;
goto SHURUM;
}
SHURUJ:
cout<<"请输入计数周期j(0-100):"<<endl;
cin>>j;
if (j>100||j<1)
{
cout<<"请输入一个0到100之间的j"<<endl;
goto SHURUJ;
}
//实例化玩家对象
player pla[20];
for(i=1;i<=n;i++)
{
pla[i].playerid=i;
pla[i].playvalue=1;
}
//开始游戏
x=s;
c=0;
for(i=0;i<n-m;i++)
{
y=0;
for(c=c;c<j;c=c)
{
BEGIN:
if (x>n)
{
x=1;
}

if(pla[x].playvalue>0)
{
c++;
if(c>(j-1))
{
if ((x+1)>n)
{
x=0;
}
if (pla[x+1].playvalue<1)
{
c--;
x++;
y=1;
goto BEGIN;
}
else
{
if(x<1)
{
x=1;
}
x++;
x-=y;
goto LAST;
}
}
}
x++;
}
LAST:
pla[x].playvalue=0;
cout<<"玩家"<<x<<"离开"<<endl;
c=1;
}
//输出胜利玩家信息
cout<<"胜利的玩家："<<endl;

for(i=1;i<=n;i++)
{
if(pla[i].playvalue>0)
{
cout<<"玩家"<<i<<endl;
}
}
}
play.h:#ifndef _play_H_
#define _play_Hclass player
{
public:
int playvalue;
int playerid;
};
#endif