【算法竞赛】实现约瑟夫问题的四种方法（附手绘图详解）

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
struct node
{
  int data;
  node* next;//单向链表，一个next指针
};
int main()
{
  int m, n;
  scanf("%d%d", &n, &m);
  node* head, * p, * now, * prev;
  head = new node; head->data = 1; head->next = NULL;//分配第一个节点,数据置为1
  now = head;
  for (int i = 2; i <= n; i++)
  {
  p = new node; p->data = i; p->next = NULL;//把申请的新节点链接到前面的链表上
  now->next = p;
  now = p;
  }
  now->next = head;
  //上面是建立链表。
  now = head, prev = head;
  while ((n--) > 1)
  {
  for (int i = 1; i < m; i++)//数到m为止
  {
    prev = now;//类似于单链表的元素删除，记录前一个位置，用于下面跳过第m个节点
    now = now->next;
  }
  printf(" %d ", now->data);
  prev->next = now->next;
  delete now;
  now = prev->next;
  }
  printf(" %d", now->data);//最后一个节点的打印
  delete now;//释放掉最后一个节点
  return 0;
}

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
const int N = 100;//定义静态链表的空间大小
struct node
{
  int id, nextid;
}nodes[N];
int main()
{
  int n, m;
  scanf("%d%d", &n, &m);
  nodes[0].nextid = 1;
  for (int i = 1; i <= n; i++)
  {
  nodes[i].id = i, nodes[i].nextid = i + 1;
  }
  nodes[n].nextid = 1;
  int now = 1, prev = 1;
  while ((n--) > 1)
  {
  for (int i = 1; i < m; i++)
  {
    prev = now;
    now = nodes[now].nextid;
  }
  printf(" %d ", nodes[now].id);
  now = nodes[prev].nextid;
  }
  printf(" %d", nodes[now].nextid);
  return 0;
}

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
const int N = 100;
struct node
{
  int id;
  int preid, nextid;//前后节点
}nodes[N];
int main()
{
  int n, m;
  scanf("%d%d", &n, &m);
  nodes[0].nextid = 1;
  for (int i = 1; i <= n; i++)
  {
  nodes[i].id = i;
  nodes[i].preid = i - 1;
  nodes[i].nextid = i + 1;
  }
  nodes[n].nextid = 1;//循环链表，尾指向头
  nodes[1].preid = n;//循环链表，头指向尾
  int now = 1;//从第一个节点开始
  while ((n--) > 1)
  {
  for (int i = 1; i < m; i++)
  {
    now = nodes[now].nextid;
  }
  printf(" %d ", nodes[now].id);
  int prev = nodes[now].preid, next = nodes[now].nextid;
  nodes[prev].nextid = nodes[now].nextid;
  nodes[next].preid = nodes[now].preid;
  now = next;//新的开始
  }
  printf(" %d", nodes[now].nextid);
  return 0;
}

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
int nodes[150];
int main()
{
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n - 1; i++)
  {
  nodes[i] = i + 1;//nodes[i]的值就是下一个节点
  }
  nodes[n] = 1;
  int now = 1, prev = 1;
  while ((n--) > 1)
  {
  for (int i = 1; i < m; i++)
  {
    prev = now; now = nodes[now];
  }
  printf(" %d ", now);
  nodes[prev] = nodes[now];//跳过now节点
  now = nodes[prev];//新的now节点
  }
  printf(" %d", now);
  return 0;
}