约瑟夫环问题详解

约瑟夫环

故事背景：

据说著名犹太历史学家 Josephus 有过以下的故事：在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人 开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止，然而 Josephus 和他的朋友并不想遵从，Josephus 要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

问题描述：

有n个人围成一个环，然后给从某个人开始顺时针从1开始报数，每报到m时，将此人出环杀死，然后从下一个人继续从1报数，直到最后只剩下一个人，求这个唯一剩下的存活的人是谁？并求出环的顺序。

内圈是排列顺序，外圈是出环的顺序，也就是自杀的顺序。
41个人而报数3的约琴夫排列如下所示：
14 36 1 38 15 2 24 30 3 16 34 4 25 17 5 40 31 6 18 26 7 37 19 8 35 27 9 20 32 10 41 21 11 28 39 12 22 33 13 29 23
追后两个剩下的便是 Josephus 和他的朋友。。

循环链表模拟：

有序循环链表（无头尾节点）：

#include<stdio.h>
#include<stdlib.h>
typedef struct node{
    int data;
    struct node *next;
}Lnode,*Linklist;

void Printlist(Linklist L ){
    Linklist p;
    p=L;
    if(L->next!=NULL){
    printf("%d ",p->data);
    p=p->next;
    while(p!=L && p->next!=p){
        printf("%d ",p->data);
        p=p->next;
    }//while
    printf("\n");
}   //if
} //Printlist
void Createlist(Linklist *L, int n){
    Linklist head,r,s;
    int i;
    (*L)=(Linklist)malloc(sizeof(Lnode));
    (*L)->next=NULL;
    (*L)->data=1;
    head=(*L);
    r=(*L);                 //使用一个中间结点再循环中让指向后移，实现尾插 
    for(i=2; i<=n; i++){
        s=(Linklist)malloc(sizeof(Lnode));
        s->data=i;
        r->next=s;
        r=s;
    }
    r->next=head;
}

void Outlist(Linklist *L, int m, int n){
    Linklist pre,p;
    int j,i=1;
    p=(*L);
//  p=pre->next;
    while(i<m){ //找到从传来的m位开始的地方 
        pre=p;
        p=p->next;
        i++;
    }
    while(p->next != p){   //历编这个链表直到剩下最后一个
         for(j=1; j<n; j++){
            pre=p;
            p=p->next;
         }
         printf("%d ",p->data);
         pre->next=p->next;
         free(p);
         p=pre->next;

    }
    printf("%d ",p->data);
    (*L)->next=NULL;
}

int main()
{
    Linklist L;
    int x,m,n;
    printf("输入要输入的环的组成数: ");
    scanf("%d", &x);
    Createlist(&L, x);
    Printlist(L);
    printf("输入要从第几个数数到第几个数: "); 
    scanf("%d%d",&m,&n);
    Outlist(&L, m, n);
    printf("\n最后输出表中剩下的数: ");
    Printlist(L);
    printf("\n");
    return 0;

}

代码分析：需要模拟游戏过程时间复杂度达到了O(m*n)

数组模拟

    //约瑟夫环，数组模拟
#include<stdio.h>
int main()
{
    int i, n,m,a[10001],dead=0,num=0;
    scanf("%d%d",&m,&n);
    for(i=1 ;i<=n; i++)
        a[i]=i;
    for(i=1; ; i++){
        if( i>n )   
            i=i%n; //数到大于人数的时候从头在开始
        if( a[i] > 0){ //活着就报数 
            num++;
        } 
        if(m==num && dead != n-1){//数到第 M 个数时，下个一重新开始计数，数组设置为0
            num=0;
            printf("%d ",a[i]);
            dead++;
            a[i]=0;
        } 
        else if(m==num && dead == n-1 ){
            printf("%d ",a[i]);
            break;
        }
    }
    return 0;
 } 

代码分析：需要模拟整个游戏流程时间复杂度为O(m*(n-1))

递归

如果不模拟游戏过程，把问题改变成1~n的人报数，报到m就要退出，那么这时还剩下n-1个人，退出的人不理他再把这n-1个人看成一个新的环，(开始从m mod n)再进行报数到m个人退出。
环变成了 k k+1 k+2 … 1 2 3 ….k-3 k-2

新的环	重新编号
k	1
k+1	2
k+2	3
…	..
k-3	n-2
k-2	n-1

把规模为n的问题变成规模为n-1的子问题 。类推直到1，使用递归
递归边界是n=1时 f[1]=0；
递归方程为 f[i]=(f[i-1]+m) mod i; (i>1）

//约瑟夫环， 递归


#include<stdio.h>

int f(int n, int m){
    if(n==1)    return 0;
    else return (f(n-1,m)+m)%n;
} 


int main()
{
    int m, n;
    scanf("%d %d",&n,&m);
    printf("%d\n", f(n,m)+1);
    return 0;
}