算法12---约瑟夫环问题

算法12---约瑟夫环问题

1 首先我们来解决一个约瑟夫环的问题，再慢慢的深入。

 

问题描述：

罗马人攻占了桥塔帕克，41个人躲在一个山洞中，逃过了这场浩劫。这41人中，包括历史学家约瑟夫和他的一个朋友。剩余的39人为了表示不想屈服罗马人，决定集体自杀。大家想到了一个自杀方案，这41个人围城一个圆圈，由第一个人开始顺时针报数，每报数为3的人就立刻自杀。然后再由下一个人重新开始报数，仍然是每报数为3的人自杀，。。。。，直到所有的人都自杀身亡；

约瑟夫和他的朋友不想自杀，于是约瑟夫想到了一个计策，他们两个同样的参与到自杀方案中，但是最后却躲过了自杀，请问，他是怎么做到的？

 

#include <String.h>
#include <stdio.h>
#include <malloc.h>


#define Num 41
#define killman 3

void josephus(int alive)
{
    int man[Num]={0};
    int count=1;
    int i=0;
    int pos=-1;
    while(count<=Num)
    {
        do
        {
            pos=(pos+1)%Num;//环处理
            if (man[pos]==0)
            {
                i++;
            }
            if (i==killman)
            {
                i=0;
                break;
            }   
        }while(1);
        man[pos]=count;
        printf("the %2d people die! the number of josephus is %2d
",pos+1,man[pos]);

        count++;
    }
    printf("the %d man who want to live should be in the number of :
",alive );
    alive=Num-alive;
    for (int i = 0; i < Num; i++)
    {
        if (man[i]>alive)
        {
            printf("init number:%d.josephus number:%d
",i+1,man[i]);
        }
    }
    printf("
");
}


int  main()
{
    int alive;
    printf("the solve of josephus!
");
    printf("the number fo people want to live:");
    scanf("%d",&alive);
    josephus(alive);
    return 0;
}

 

 

2 我们就上面的问题引出josephus排序问题；

就是对任意输入的人数，决定自杀的个数，输出自杀的顺序；

 

#include <String.h>
#include <stdio.h>
#include <malloc.h>


#define Num 41
#define killman 4

void josephus_sort()
{
    int man[Num]={0};
    int count=1;
    int i=0;
    int pos=-1;
    while(count<=Num)
    {
        do
        {
            pos=(pos+1)%Num;//环处理
            if (man[pos]==0)
            {
                i++;
            }
            if (i==killman)
            {
                i=0;
                break;
            }   
        }while(1);
        man[pos]=count;
        printf("the %2d people die! the number of josephus is %2d
",pos+1,man[pos]);

        count++;
    }
}



int  main(void)
{

    printf("the solve of josephus sort!
");

    josephus_sort();
    return 0;
}

 

3 现在接着上面的问题，升级一下：n个人坐成一个圈，现在每个人都拿一个随机写有数字的字条，游戏开始，任选一个数字m。从第一个人开始进行，按照编号重新开始报数，报道m的人出列，并且将其手中的数字作为新的出列数字。然后从下一个人开始重新从1开始报数，如此循环下去，问最后剩下来哪个人？

/*
由于在这里下一个决定出列的数字随机生成的，而且总的个数是可以自己定义的；
在这里我们采用链表的方式来解答。
*/


#include <string.h>
#include <stdio.h>
#include <malloc.h>
#include <time.h>

#define random_len 10

typedef struct node 
{
    int number;  //游戏者编号
    int psw;    //出列数字
    struct node *next;        //指针域，指向下一个节点
}Lnode,*linklist; 



void circleFun(linklist *list,int m)
{
    linklist p,q;
    q=p=*list;
    while(q->next!=p)
    {
        q=q->next;
    }
    printf("the gamer out the list in this order!
");
    while(p->next!=p)
    {
        for (int i = 0; i < m-1; i++)
        {
            q=p;
            p=p->next;
        }
        q->next=p->next;
        printf("the %d people pop,the number in his hand is %d
",p->number,p->psw );
        m=p->psw;
        free(p);
        p=q->next;
    }

    printf("the last one is %d,the number in his hand is %d 
",p->number,p->psw );
}

void insertlist(linklist *list,linklist q,int number ,int psw)
{
    linklist p;
    p=(linklist)malloc(sizeof(Lnode));

    p->number=number;
    p->psw=psw;
    if (!*list)
    {
        *list=p;
        p->next=NULL;
    }
    else
    {
        p->next=q->next;
        q->next=p;
    }
}


int  main()
{
    linklist list1=NULL,q=NULL,list;
    int num,m_number; //m_number为第一个决定出列的数字；
    int e;
    printf("the solve of complex josephus problem
");
    printf("please input the number of people who join the game:");
    scanf("%d",&num);
    srand(time(NULL));
    for (int i = 0; i < num; i++)
    {
        e=rand()%10;
        printf("the number in %d people's hand %d 
",i+1,e);
        insertlist(&list1,q,i+1,e);
        if (i==0)
        {
            q=list1;
        }
        else
            q=q->next;
    }
    q->next=list1;
    list=list1;//循环链表

    printf("please input the number first input:
");
    scanf("%d",&m_number);
    circleFun(&list,m_number);
    printf("
");
    return 0;
}