[转]用单向循环链表解决约瑟夫环问题

时间:2022-05-11 08:33:53

设有n个人围坐一圈,现以某个人开始报数,数到m的人出列,接着从出列的下一个人开始重新报数,数到m的人又出列,如此下去,直到所有人都出列为止.按出列顺序输出. 

这段代码是从网上找来的,在此特别说明!!!!!

C代码
  1. #include   "stdlib.h"  
  2. struct ele {  
  3.     int no;  
  4.     struct ele *link;  
  5. } main() {   
  6.   
  7.     struct ele *h, *u, *p;  
  8.     int n, m, i;  
  9.     printf("Please   input   n&m:/n");  
  10.     scanf("%d%d", &n, &m);/*输入n和m*/  
  11.     h = u = (struct ele *) malloc(sizeof(struct ele));/*形成首表元*/  
  12.     h->no = 1;  
  13.     for (i = 2; i <= n; i++)/*形成其余的n-1个表元*/  
  14.     {  
  15.         u->link = (struct ele *) malloc(sizeof(struct ele));  
  16.         u = u->link;  
  17.         u->no = i;/*第i个表元置编号i*/  
  18.     }  
  19.     u->link = h;/*末表元后继首表元,形成环*/  
  20.     puts(  
  21.             "/nThe   numbers   of   who   will   quit   the   cycle   in   turn   are:");  
  22.     while (n) {  
  23.         for (i = 1; i < m; i++)  
  24.             /*掠过m-1个表元*/  
  25.             u = u->link;  
  26.         p = u->link;/*p指向第m个表元*/  
  27.         u->link = p->link;/*第m个表元从环中脱钩*/  
  28.         printf("%4d", p->no);  
  29.         free(p);/*释放第m个表元占用的空间*/  
  30.         n--;  
  31.     }  
  32.     printf("/n/n   Press   any   key   to   quit.../n");  
  33.     getchar();  
  34. }   

     当碰到问题,首先考虑这个问题是怎样的类型,第二从解决列表中选择中最合适的方案.以这个问题为例:问题中是一个循环性质,关键点“有n个人围坐一圈”。可选数据结构与算法中的可选方案:队列,栈,线性表,串。队列,栈和串都不大合适。以线性表中的单向循环链表最合适。