1009: josephus问题

Time Limit: 1 Sec Memory Limit: 64 MB
Submit: 549 Solved: 227

Description

josephus问题其实就是一个游戏，一群小孩围成一个圈，设置一个数，这个数是个小于小孩总数大于0的一个整数,从第一个小孩开始报数，当其中一个小孩报到你设置的那个数的时候离开那个圈，这样一来反复报下去，直到只剩下最后一个小孩的时候那个小孩就是胜利者。现在的问题是设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，……，如此反复直到所有的人全部出局为止。下面要解决的Josephus问题是：对于任意给定的n, s和m，求出这n个人的出局序列。请以n = 9, s = 1, m = 5为例，人工模拟Josephus的求解过程以求得问题的解。出局人的顺序为5, 1, 7, 4, 3, 6, 9, 2, 8。本题可以对多个测试案例进行测试。

Input

第一行输入测试案例数T 以下T行,每一行是一个测试案例，分别输入n,s,m,以一个或多个空格隔开

Output

每个测试案例输出2行，第一行输出出局顺序第2行输出"** win.",其中**是胜利者编号，即最后出局者

Sample Input

1
9 1 5

Sample Output

5 1 7 4 3 6 9 2 8
8 win.

开学初看得别人用链表来写这道题是云里雾里，而如今已经自己可以写了。（o。o虽然又出现了一堆云雾）

总之是进步了，嘿嘿。

对了，这道题还有纯数学的做法。

  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<stdlib.h>
  4 typedef struct Link
  5 {
  6     int num;
  7     struct Link *next;
  8 }IA;
  9 
 10 int n,s,m;
 11 
 12 IA *Create();
 13 void *Delete(IA *head);
 14 
 15 int main()
 16 {
 17     //freopen("a.txt","r",stdin);
 18     IA *head=NULL,*tail=NULL;
 19     int T;
 20     scanf("%d",&T);
 21     while(T--)
 22     {
 23         scanf("%d%d%d",&n,&s,&m);
 24         tail=Create();
 25         Delete(tail);
 26     }
 27     return 0;
 28 }
 29 
 30 IA *Create()
 31 {
 32     IA *head=NULL,*q,*tail;
 33     tail=head;
 34     int i=1;
 35     while(i<=n)
 36     {
 37         q=(IA*)malloc(sizeof(IA));
 38         q->num=i;
 39         if(head==NULL)
 40         {
 41             head=q;
 42             tail=q;
 43             tail->next=NULL;
 44         }
 45         else
 46         {
 47             tail->next=q;
 48             q->next=NULL;
 49             tail=q;
 50         }
 51         i++;
 52     }
 53     tail->next=head;
 54  //   Print(head);
 55     return tail;
 56 }
 57 
 58 void *Delete(IA *tail)
 59 {
 60     int cnt=0,hui=0,i=1;//cnt记数，数到m就让此时的人出局；hui记录出局人数
 61     IA *ptr1,*ptr2;
 62     if(tail->next==NULL)
 63         return;
 64     ptr1=tail;
 65     ptr2=tail->next;
 66     while(i!=s)
 67     {
 68         ptr1=ptr2;
 69         ptr2=ptr2->next;
 70         i++;
 71     }
 72     while(hui!=n-1)
 73     {
 74         ++cnt;
 75         if(cnt==m)
 76         {
 77             printf("%d ",ptr2->num);
 78             ptr1->next=ptr2->next;
 79             free(ptr2);
 80             cnt=0;
 81             hui++;
 82         }
 83         else
 84             ptr1=ptr2;
 85         ptr2=ptr1->next;
 86     }
 87     printf("%d
%d win.
",ptr1->num,ptr1->num);
 88 }
 89 
 90 /*void Print(IA *head)
 91 {
 92     IA *p;
 93     if(head==NULL)
 94         return;
 95 
 96     printf("%d ",head->num);
 97     for(p=head->next;p!=head;p=p->next)
 98     {
 99         printf("%d ",p->num);
100     }
101     printf("

");
102 }*/

循环链表