【循环链表】约瑟夫问题

描述约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。输入8 1 3 (n=8 k=1 m=3 )输出7 (剩下的那个)

样例输入

8 1 3

样例输出

7

 

#include <cstdio>
#include <iostream>
using namespace std; 
struct Node
{
  int data;
  Node *next;
};
int main() 
{
  int n, k, m;
  cin >> n >> k >> m;//n个人,第k出列,第m开始。
  if (m == 1)
  {
    int left = k - 1;
    if (left == 0)
      left = n;
    cout << left;
    return 0;
  }
  Node *first = new Node();
  first->data = 1;
  Node *p=first, *q;
  for (int i = 2; i <= n; i++)
  {
    q = new Node();
    q->data = i;
    p->next = q;
    p = p->next;
  }
  p->next = first;
  p = first;
  for (int i = 1; i <= k - 1; i++)
  {
    p = p->next;
  }

  while (p!=p->next)
  {
    for (int i = 1; i < m - 1; i++)
    {
      p = p->next;
    }
    q = p->next;
    p->next = q->next;
    delete q;
    p = p->next;
  }
  cout << p->data << endl;
  return 0;
}

 

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注

13 + 15 =