約瑟夫環問題

• 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;
}