go语言约瑟夫问题 约瑟夫问题数据结构与算法

什么是约瑟夫问题

约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的人的序号为5，4，6，2，3。最后剩下1号。

网站建设哪家好，找成都创新互联公司！专注于网页设计、网站建设、微信开发、小程序开发、集团企业网站建设等服务项目。为回馈新老客户创新互联还提供了湘阴免费建站欢迎大家使用！

假定在圈子里前K个为好人，后K个为坏人，你的任务是确定这样的最少M，使得所有的坏人在第一个好人之前被杀掉。

什么是约瑟夫斯问题？

这是一个古老的传说：有６４名战士被敌人俘虏了，敌人命令他们排成一个圆圈，编上号码１，２，３，…，６４，敌人把１号杀了，又把３号杀了，他们是隔一个杀一个这样转着圈杀，最后剩下一个人，这个人就是约瑟夫斯，请问约瑟夫斯是多少号？这就是“约瑟夫斯问题”。

这个问题是比较容易解答的：敌人从１号开始，隔一个杀一个，第一圈把奇数号码的战士全杀死了。剩下的３２名战士需要重新编号，而敌人在第二圈杀死的是重新编排的奇数号码。

由于第一圈剩下的全部是偶数号２，４，６，８，…，６４。把它们全部用２除，得１，２，３，４，…，３２，这是第二圈重新编的号码，第二圈杀过之后，又把奇数号码都杀掉了，还剩下１６个人，如此下去，可以想到最后剩下的必然是６４号。

６４＝２６，它可以连续被２整除６次，是从１到６４中能被２整除次数最多的数，因此，最后必然把６４号剩下，从６４＝２６还可以看到，是转这６圈之后，把约瑟夫斯剩下来的。

如果有６５名战士被俘，敌人还是按上述方法残杀战士，最后剩下的还是６４号约瑟夫斯吗？

不是了，因为第一个人被杀后，也就是１号被杀后，第二个被杀的必然是３号，如果把１号排除在外，那么剩下的仍是６４个人，对于剩下这６４个人，新１号就应该是原来的３号，这样原来的２号就变成新的６４号了，所以剩下的必然是原来的２号。

对于一般情况来说，如果原来有２ｋ个人，最后剩下的必然是２ｋ号；如果原来有２ｋ＋１个人，最后剩下的是２号；如果原来有２ｋ＋２个人，最后剩下的是４号……如果原来有２ｋ＋ｍ个人，最后剩下的是２ｍ号。

比如，原来有１００人，由于１００＝６４＋３６＝２６＋３６，所以最后剩下的是２×３６＝７２号；又比如，原来有１１１人，由于１１１＝６４＋４７＝２６＋４７，所以最后剩下的是２×４７＝９４号。

下面把问题改一下：不让被俘的战士站成圆圈，而排成一条直线，然后编上号码，从１号开始，隔一个杀一个，杀过一遍之后，然后再重新编号，从新１号开始，再隔一个杀一个，问最后还是约瑟夫斯吗!

答案是肯定的，最后剩下的仍然是约瑟夫斯。

如果战俘人数是６５人呢？剩下的还是约瑟夫斯，只要人数不超过１２８人，也就是人数小于２７，那么最后剩下的总是约瑟夫斯，因为从１到１２８中间，能被２整除次数最多的就是６４，而敌人每次都是杀奇数号留偶数号，所以６４号总是最后被留下的人。

约瑟夫问题描述： 编号为1，2，……，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始

#includestdio.h

#includemalloc.h

//1.元素类型，结点类型和指针类型

typedef struct LNode         //定义结构体，

{

int number,password;                 //num用来存储人的序号，pwd用来存储人的密码

struct LNode *next;

}SLX;

struct LNode *head,*p,*pt;    //定义结点

//2 、创建循环链表函数

int CreatLinkListFunction(int n)      //参数n传递人数，

{

int i;

head=(struct LNode*)malloc(sizeof(SLX));   //创建一个带头结点的链表

p=head;

for(i=1;in;i++)

{

pt=(struct LNode*)malloc(sizeof(SLX));

p-next=pt;

p=pt;

}

p-next=head; //构成循环链表

pt=head;

return 0;

}

//3.创建输入密码函数

int EnterPassword(int n)        //参数n传递人数

{

int i,k;

printf("\n请输入密码: \n");

for( i=1;i=n;i++)

{

scanf("%d",k);

pt-number=i;        //num存储人的序号

pt-password=k;         //pwd存储人的密码

pt=pt-next;

}

pt=p;//创建循环链表  此时P是头结点head  这个函数存入密码 之后再一次返回密码

return 0;

}

//4、创建输出函数

int OutListFunction(int m,int n)    //参数m、n传递报数上限值和人数

{

int i,a;

for(i=1;i=n;i++)         //用一个for循环搜索循环链表

{

for(a=1;am;a++)      //删除结点

{

pt=pt-next;

}

p=pt-next;

m=p-password;

printf("%d ",p-number);    //输出人的序号

pt-next=p-next;

free(p);          //释放动态申请的结点空间

}

return 0;

}

//主函数

void main()

{   int m,n;   //m为报数上限值，n为人数

printf("\n参数m、n传递报数上限值和人数;\n");

printf("\n请输入 m 和n: \n");

scanf("%d %d",m,n);

CreatLinkListFunction( n);  //调用创建链表函数

EnterPassword( n);       //调用输入密码函数

printf("\n出队的人依次是:\n");

OutListFunction( m,n);      //调用输出链表函数

}