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); //调用输出链表函数
}
网页题目：go语言约瑟夫问题 约瑟夫问题数据结构与算法
网页地址：http://cdiso.cn/article/dohiiii.html
