小孩报数问题（循环链表）

TimeLimit:1000MS  MemoryLimit:65536K

64-bit integer IO format:

%lld

Problem Description

有N个小孩围成一圈，给他们从1开始依次编号，现指定从第W个开始报数，报到第S个时，该小孩出列，然后从下一个小孩开始报数，仍是报到S个出列，如此重复下去，直到所有的小孩都出列（总人数不足S个时将循环报数），求小孩出列的顺序。

Input

第一行输入小孩的人数N（N<=64） 

接下来每行输入一个小孩的名字(人名不超过15个字符) 

最后一行输入W,S (W < N)，用逗号","间隔

Output

按人名输出小孩按顺序出列的顺序，每行输出一个人名

SampleInput

5XiaomingXiaohuaXiaowangZhangsanLisi2,3

SampleOutput

ZhangsanXiaohuaXiaomingXiaowangLisi 用 模拟 循环链表的 代码 AC：

#include 
        
         using namespace std;typedef struct node Node;const int all = 18;struct node{    char name[all];    Node *pre;    Node *next;};void make( Node *head, int a, int b, int n );Node* Create( int n );int main(void){    int n, a, b;    scanf( "%d", &n );    Node *head = Create( n );    scanf( "%d,%d", &a, &b );    Node *tmp = head->next;    make( head, a, b, n );    return 0;}Node* Create( int n ){    Node *head=NULL, *tmp=NULL, *tmp2;    if( n ){        head = tmp = new Node;        scanf( "%s", tmp->name );        tmp->next = head;        head->pre == tmp;        -- n;        while( n -- ){            tmp2 = tmp;            tmp->next = new Node;            tmp = tmp->next;            tmp->pre = tmp2;            scanf( "%s", tmp->name );            tmp->next = head;            head->pre = tmp;        }    }    return head;}void make( Node *head, int a, int b, int n ){    Node *tmp = head, *tmp2;    int num;    -- a;    while( a -- ){        tmp = tmp->next;    }    -- b;    while( n -- ){        num = b;        while( num -- && tmp->pre != tmp->next ){            tmp = tmp->next;        }        puts( tmp->name );        tmp2 = tmp->next;        tmp->pre->next = tmp->next;        tmp->next->pre = tmp->pre;        delete tmp;        tmp = tmp2;    }}
        

 

 

用 约瑟夫 问题 解决办法：

即用 递推 方式， 

比如 给 一个 数列：

 1 2 3 4 5 6 7 8 9 10；

每 隔 3 个 去掉 一个：

如下变化：

1 2 4 5 6 7 8 9 10； <-- @1;

1 2 4 5 7 8 9 10；　<-- @2;

1 2 4 5 7 8 10；　　<--@3;

...

 

@1数列， 尝试转换成 1 2 3 4 5 6 7 8 9， 即 减去 3.

即 所求的数 n = （ 0 + 3 -1 ） % n + 1；

@2数列， 尝试转换成 1 2 3 4 5 6 7 8， 即 减去 3.

令 m = （ 0 + 3 - 1 ） % ( n - 1 ) + 1；

所 求得 的数 n = （ m + 3 - 1 ) % n + 1;

 

code：

// 应用 约瑟夫 问题的解决 方法#include 
        
         using namespace std;const int all = 64;char con[ all ][ 64/4 ];int calc( int n, int m, int p );int main(void){    int n, m, w;    scanf( "%d", &n );    for( int i=1; i <= n; ++ i ){        scanf( "%s", con[i] );    }    scanf( "%d,%d", &w, &m );    for( int i=1; i <= n; ++ i ){        puts( con[ ( calc( n, m, i ) + w - 2 ) % n + 1 ] );    }    return 0;}int calc( int n, int m, int p ){    int f = 0;    for( int i=n-p+1; i<=n; ++ i ){        f = (f+m-1)%i+1;    }    return f;}