用C++實現(xiàn)約瑟夫環(huán)的問題
來源：程序員人生 發(fā)布時間：2014-11-13 08:45:55 閱讀次數(shù)：2098次
約瑟夫問題是個著名的問題：N個人圍成1圈，從第1個開始報數(shù)，第M個將被殺掉，最后剩下1個，其余人都將被殺掉。例如N=6，M=5，被殺掉的人的序號為5，4，6，2，3。最后剩下1號。
假定在圈子里前K個為好人，后K個為壞人，你的任務(wù)是肯定這樣的最少M，使得所有的壞人在第1個好人之前被殺掉。
//----數(shù)學(xué)中有乘法口訣。。那只是工具。我們都很熟習(xí)。
//----C++中有1些基本的程序。也只是工具。我們必須像熟習(xí)乘法口訣1樣去熟習(xí)這些程序。
//----很基礎(chǔ)的1些東西，必須熟練。。。
#include<iostream>
class link;
using namespace std;
class node{
friend class link;
public:
node():next(NULL){}
node(int value):data(value),next(NULL){}
private:
int data;
node *next;
};
class link{
public:
link(int x,int y,int z):n(x),s(y),m(z){}
node *createlink()
{
node *p,*r;
node *q;
r=p=new node;
for(int i=1;i<=n;++i)
{
q=new node;
q->data=i;
r->next=q;
r=q;
}
r->next=p->next;
return p;
}
node *jusefu(node *startnode)
{
node *p=startnode->next;
node *q;
for(int i=1;i<s;++i)
p=p->next;//讓p指向開始數(shù)數(shù)的位置，讓q指向需要刪除結(jié)點的位置的前1個位置
q=p->next;
while(q->next!=p)
{
q=q->next;
}
while(p->next!=p)
{
for(int j=1;j<m;++j)
{
//node *tmp;
q=p;
p=p->next;
}
q->next=p->next;
cout<<"將要刪除的號碼是"<<p->data<<endl;
delete p;
p=q->next;
}
cout<<"留下來的人數(shù)的號碼為"<<p->data<<endl;
return p;
}
private:
int n;
int s;
int m;
};
int main()
{ int i,j,k;
cout<<"輸入總數(shù)，開始位置；每次循環(huán)人數(shù)"<<endl;
cin>>i>>j>>k;
link linklist(i,j,k);
node *head=linklist.createlink();
node *lastnode=linklist.jusefu(head);
system("pause");
return 0;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈
