约瑟夫环问题

• 2021 年 2 月 17 日
• 筆記
• 数据结构与算法

C语言代码实现：

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

/**
   循环链表实现约瑟夫环
   41个人排成一个圆圈，然后从1-3报数，报到3的人自杀，依次类推，直到剩下最后两个人可以存活下来，这两个人分别是第16个位置和第31个位置
*/

/*
定义node节点
*/
typedef struct node{
      int data;
      node * next;
}node, *Node;

/*
初始化单链表
*/
node * init_list(int n){
      // 声明头指针
      Node head;
      // 声明尾指针
      Node tail;
      head = (Node)malloc(sizeof(node));
      // 让当前尾指针指向头节点
      tail = head;
      int i = 1;
      while (i <= n) {
      	  Node newNode = (Node)malloc(sizeof(node));
      	  if (newNode == NULL){
      	      exit(0);
      	  }
	  newNode->data = i++;
          tail->next = newNode;
          tail = newNode;
      }

      // 让尾节点的指针域指向第一个节点
      tail->next = head->next;
      // 删除头节点，释放内存
      free(head);
      // 返回第一个节点的指针
      return tail->next;
}


int main(){
      Node ysfh;
      int people;
      int num;

      printf("请输入参与约瑟夫环游戏的人数：");
      scanf("%d", &people);
      printf("请输入报数的终点（1-n）：");
      scanf("%d", &num);

      // 初始化约瑟夫环
      ysfh = init_list(people);
      // 定义一个临时指针变量
      Node p = ysfh;

      while (p != p->next){
      	  int count = 1;
      	  for (; p != p->next && count < num - 1; p = p->next) {
      	      count++;	
	  }		
	  Node temp = p->next;
	  printf("%d\n", temp->data);
	  p->next = temp->next;		
	  free(temp);
          p = p->next;
      }

      // 打印最后一个
      printf("%d\n", p->data);
      return 0;
}