博客

问题描述

约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知 n 个人（以编号1，2，3 … n 分别表示）围坐在一张圆桌周围。从编号为 k 的人开始报数，数到 m 的那个人出圈；他的下一个人又从 1 开始报数，数到 m 的那个人又出圈；依次规律重复下去，知道剩余最后一个胜利者。

一、 k==1 的约瑟夫问题

例如：有10个人围成一圈进行此游戏，每个人编号为 1-10 。若规定数到 3 的人出圈。则游戏过程如下。
（1）开始报数，第一个数到 3 的人为 3 号，3 号出圈。
  1， 2， 【3】， 4， 5， 6， 7， 8， 9， 10。
（2）从 4 号重新从1开始计数，则接下来数到 3 的人为 6 号，6 号出圈。
  1， 2， 【3】， 4， 5， 【6】， 7， 8， 9， 10。
（3）从 7 号重新从 1 开始计数，则接下来数到 3 的人为 9 号，9 号出圈。
  1， 2， 【3】， 4， 5， 【6】， 7， 8， 【9】， 10。
（4）从 10 号重新从 1 开始计数，由于 10 个人称环形结构，则接下来数到 3 的人为 2 号，2 号出圈。
  1， 【2】， 【3】， 4， 5， 【6】， 7， 8， 【9】， 10。
（5）从 4 号重新从 1 开始计数，则接下来数到 3 的人为 7 号，7 号出圈。
  1， 【2】， 【3】， 4， 5， 【6】， 【7】， 8， 【9】， 10。
（6）从 8 号重新从 1 开始计数，则接下来数到 3 的人为 1 号，1 号出圈。
  【1】， 【2】， 【3】， 4， 5， 【6】， 【7】， 8， 【9】， 10。
（7）从 4 号重新从 1 开始计数，则接下来数到 3 的人为 8 号，8 号出圈。
  【1】， 【2】， 【3】， 4， 5， 【6】， 【7】， 【8】， 【9】， 10。
（8）从 10 号重新从 1 开始计数，则接下来数到 3 的人为 5 号，5 号出圈。
  【1】， 【2】， 【3】， 4， 【5】， 【6】， 【7】， 【8】， 【9】， 10。
（9）从 10 号重新从 1 开始计数，则接下来数到 3 的人为 10 号，10 号出圈。
  【1】， 【2】， 【3】， 4， 【5】， 【6】， 【7】， 【8】， 【9】， 【10】。
（10）最终剩余 4 号，4 号为胜利者。

1. 数组法：

  用数组求解的基本思想就是用一个一维数组去标识这 n 个人的状态，默认全为 1 ，也就是都在圈子内，当数到 m 的人出圈之后，标识置为 0（就是出圈了），同时报数器清 0，下一个人要从 1 开始。在每次报数之前要判断他是否在圈子内（也就是他的标识是否为 1 ），如果在圈子里面才会继续报数。定义一个变量记录出圈的人数， 出圈的人数等于 n-1 时，则游戏结束。
  时间复杂度：O(nm)，空间复杂度：O(n)
一般会TL

const int maxn = 10010;
int a[maxn];
int main(void)
{
    int n,m,fp,num;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        a[i] = 1;
    num = fp = 0;
    while(fp<n-1){
        for(int i=1;i<=n;i++){
            if(a[i]==1){
                num++;
                if(num==m){
                    printf("%d ",i);
                    a[i] = 0;
                    num = 0;
                    fp++;
                }
                if(fp==n-1) break;
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(a[i]==1){
            printf("%d\n",i);
            break;
        }
    }
    return 0;
}

2.循环链表

  约瑟夫环问题可以转化为循环链表的数据结构来求解。可以将每个人看做链表的单个节点，每个节点之间通过链表的 next 指针连接起来，并且将链表末尾节点指向头节点就形成的环，由链表构成的环形结构在数据结构中称为循环链表。
  时间复杂度：O(nm)，空间复杂度：O(n)
一般会TL

struct node{
    int num;
    node *next;
};
node* CreatNode(int x)
{
    node *p;
    p = (node *)malloc(sizeof(node));
    p->num = x;
    p->next = NULL;
    return p;
}
node* CreatJoseph(int n)
{
    node *head,*p,*q;
    for(int i=1;i<=n;i++){
        p = CreatNode(i);
        if(i==1)    head = p;
        else    q->next = p;
        q = p;
    }
    q->next = head;
    return head;
}
void Runjoseph(int n,int m)
{
    node *p,*q;
    p = CreatJoseph(n);
    while(p->next!=p){
        for(int i=1;i<m-1;i++)
            p = p->next;
        q = p->next;
        p->next = q->next;
        p = p->next;
        printf("%d--",q->num);
        free(q);
    }
    printf("%d\n",p->num);
}
int main(void)
{
    int n,m;
    scanf("%d%d",&n,&m);
    Runjoseph(n,m);

    return 0;
}

3. 递推公式求解

  约瑟夫环中，每当有一个人出圈，出圈的人的下一个人成为新的环的头，相当于把数组向前移动 m 位。若已知 n-1 个人时，胜利者的下标位置位 f(n−1,m) ，则 n 个人的时候，就是往后移动 m 位，(因为有可能数组越界，超过的部分会被接到头上，所以还要模 n )，根据此推导过程得到的计算公式为：
  f(n,m) = (f(n−1,m) + m) % n。
其中，f(n,m) 表示 n 个人进行报数时，每报到 m 时杀掉那个人，最终的编号，f(n−1,m) 表示，n-1 个人报数，每报到 m 时杀掉那个人，最终胜利者的编号。有了递推公式后即可使用递归的方式实现。
  时间复杂度是 O(n)，空间复杂度是O(n)
http://www.51nod.com/Challenge/Problem.html#problemId=1073
递归写法：

int f(int n,int m)
{
    return n==1 ? 0 : (f(n-1,m)+m)%n;
}
int main(void)
{
    int n,m;
    scanf("%d%d",&n,&m);
    printf("%d",f(n,m)+1);

    return 0;
}

递推写法：

int main(void)
{
    int n,m;
    scanf("%d%d",&n,&m);
    int ans = 0;
    for(int i=2;i<=n;i++){
        ans = (ans + m)%i;
    }
    printf("%d\n",ans+1);
    
    return 0;
}

==当n>>m时，简单的递推O(n)会TL，就优化一下：
我们可以跳着删t个以至于不用模i，找一找关系改一下递推即可。
http://www.51nod.com/Challenge/Problem.html#problemId=1074

int main(void){
    ll n,m;
    scanf("%lld%lld",&n,&m);
    ll ans = 0,t;
    for(ll i=2;i<=n;i+=t){
        t = min((i-ans-1)/m,n-i);
        if(!t){
            ans = (ans + m)%i;
            t = 1;
        }
        else{
            ans = (ans + m*t);	//删除t个
        }
    }
    printf("%lld\n",ans+1);
}