今天講的一道習題是很經典的約瑟夫環問題，其實lz對于鏈表的某些操作還不是太懂，所以在程序中有些地方還不太看得懂，這里借鑒的網上的做法，還請大牛能夠解答我的疑惑，謝謝！
標題：約瑟夫環
說明：約瑟夫環是這么一個問題：已知n個人（編號1,2，。。。n）圍坐在圓桌周圍。從編號為k的人開始報數，數到m的人出列，他的下一個人又從1開始報數，數到m的人出列，直到所有人都出列。
struct node{
? ? int num;
? ? node *next;
};
node *creat(int n)//構建一個鏈表，即head-》1-》2-》。。。-》n，最后n又回到head
{
? ? node *p,*q,*head=NULL;
? ? for(int i=0;i<=n;i++)
? ? {
? ? ?p=new node;
? ? ?p->num=i;
? ? ?if(head==NULL)
? ? ? {
? ? ? ? head=p; //head用0來表示
? ? ? }
? ? ?else
? ? ?{
? ? ? ? q->next=p;
? ? ?}
? ? ?q=p;
? ? }
? ? p->next=head; ?//p變為最后一個節點
? ? return p;
}
int main()
{
? ?int n,k,m;//n為總人數，k為開始報數的人的序號，m為報到的需要出列的數
? ?cin>>n>>k>>m;
? ?node *l,*q;
? ?l=creat(n);//l即為生成的鏈表
? ?q=l;l=l->next;
? ?for(int i=1;i<k;i++)//這步其實不太理解是什么意思
? ? {
? ? ? ?q=l;
? ? ? ? l=l->next;
? ? }
? ?while(l->next!=l)//l->next==l表示只剩下最后一個人了
? ?{
? ? ? for(int i=1;i<m;i++)//如果還沒有報到則依次遍歷
? ? ? ?{
? ? ? ? ? ?q=l;
? ? ? ? ? ? l=l->next;
? ? ? ? }
? ? ? cout<<l->num<<"->";//輸出出列的人的序號
? ? ? q->next=l->next;//將這個人的位置刪去
? ? ? delete l;
? ? ? l=q->next;//用出列的下一個人來代替出列的人
? ?}
? ?cout<<l->num;
? ?delete l;
}
)
)
