约瑟夫环数学解法,约瑟夫环 数学

约瑟夫环

约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

链表方法：这个就是约瑟夫环问题的实际场景，有一种是要通过输入n,m,k三个正整数，来求出列的序列。这个问题采用的是典型的循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。 p-link=head 解决问题的核心步骤：（程序的基本算法） 1.建立一个具有n个链结点，无头结点的循环链表； 2.确定第1个报数人的位置； 3.不断地从链表中删除链结点，直到链表为空。 void JOSEPHUS(int n,int k,int m) //n为总人数，k为第一个开始报数的人，m为出列者喊到的数 { /* p为当前结点 r为辅助结点，指向p的前驱结点 list为头节点*/ LinkList p,r,list; /*建立循环链表*/ for(int i=0；in；i++) { p=(LinkList)malloc(sizeof(LNode)); p-data=i; if(list==NULL) list=p; else r-link=p; r=p; } p-link=list; /*使链表循环起来*/ p=list;　/*使p指向头节点*/ /*把当前指针移动到第一个报数的人*/ for(i=0;ik;i++) { r=p； p=p-link; } /*循环地删除队列结点*/ while(p-link!=p) { for(i=0;im-1;i++) { r=p; p=p-link; } r-link=p-link; printf("被删除的元素：%4d ",p-data); free(p); p=r-link; } printf("\n最后被删除的元素是：%4d",P-data); }

约瑟夫环问题的数学解

下午和朋友聊天的时候，有朋友提到了约瑟夫环问题。你和另外 n-1 个人围成一个圈，按 1，2，...，n 依次编号。第一个人从 1 开始报数，数到 k 的人会被杀掉，然后下一个人重新从 1 开始报数。如此往复，直到最后只剩下一个人。问题是，你应该如何选择自己的初始位置，才能保证最后不被杀掉呢？

速度越快的算法当然越好，毕竟这是一个生死攸关的问题。下面你将会看到，我们如何通过一些基本的数学推导最终得到这个问题的递推解。

考虑这样一种相对简单的情况：总共有 5 个人，数到 3 的人被杀掉。那么，死亡过程如下图所示：

经过一番模拟之后，我们已经对约瑟夫环问题有了一个大概的直观理解。下面，尝试使用数学语言来描述这个问题。

哦对了，假如圆圈里只有你自己，那么你肯定就是最后的幸存者，这是一个极其有用的特殊情况。

这些是我们的 已知条件 ：

这个是我们的 未知数 ：

现在考虑一种泛化情形：总共有 n 个人，数到 k 的人被杀掉，其中 n = k。幸存者的位置为 p n 。

显而易见，初始位置为 k 的人将会第一个被杀掉。此时，经过重新排序之后，问题变成了 n-1 个人的情形。幸存者的位置为 p n-1 。如果能够找到从 p n-1 到 p n 的递推关系，那么问题就解决了。

重新排序之后，每个人的位置发生了下面这些变化：

很容易我们能得到这样一个关系式：p n = (p n-1 + k) % n 。再加上刚才讨论的特例，只有一个人的情况时，p 1 = 1 。递推式就已经很明显了。

当然上文只讨论了 n=k 的情形，实际上对于 nk 的情形，刚才所得到的递推式依然适用，我们就不展开讨论了。

既然递推式这么简洁明确，那么编码实现就不用写了吧？

【生活处处皆算法】巧用约瑟夫环

约瑟夫环 （约瑟夫问题）是一个数学的应用问题：

已知n个人（以编号1，2，3....n分别表示）围坐在一张圆桌周围。

从编号为k的人开始报数，数到m的那个人出圈；他的下一个人又从1开始报数，数到m的那个人又出圈；依次规律重复下去，直到剩余最后一个胜利者。

例如：有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号为胜利者

? ? ? ? 用数组求解的基本思想就是用一个数组去标识这n个人的状态，默认全为1，也就是都在圈子内。

? ? ? ? 当数到m的人出圈之后，标识置为0（就是出圈了），同时报数器清0，下一个要从1开始。

? ? ? ? 在每次报数之前要判断他是否在圈子内（也就是他的标识是否为1），如果在圈子里面才会继续报数。定义一个变量记录出圈的人数，出圈? ? ? ? ? ? 的人数等于n-1时，则游戏结束。