rambo

约瑟夫问题

问题一:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。

n个数字(0,1,…,n-1)形成一个圆圈,从数字0开始,每次从这个圆圈中删除第m个数字(第一个为当前数字本身,第二个为当前数字的下一个数字)。当一个数字删除后,从被删除数字的下一个继续删除第m个数字。

我们要确定每次删除的数字在所有数字(TOTAL)的Index,那么每次删除一个数字后再下一个需要删除的数字在当前数字总数(TOTAL-1)中的相对Index。

解题思路:

回溯法:  int arr[n] = {0,1,2,3,4,5,6,7,8,…,n-1};

假设要找n个数字中的第m个,即删除a[m-1]这个元素,然后从a[m]这个数字为起始删除第m个。

0    1    ...  m-2    m-1  m  ...     n-1

0    1    ...   m-2    m   m+1   ...  n -1

以第m个元素为起始,重新排列,并从0开始计数

m   m+1   ...  n -1   0    1    ...   m-2    数组一 (编号m到n-1中有n-1-m+1=n-m个数)

0     1     ....  n-m-1 n-m  n-m+1  ...  n-2     数组二      n-2=m-2+n-m

如果这时候数组二和数组一是一一对应的,例如数组二的第n-m+1元素就是数组一的 1元素所以如果数组二的元素位置记为x,在数组一的元素位置记为x',

则有  数组二----->  数组一      x' = (x+m)%n   表示删除一个元素后,在当前总数中的相对Index对应在前一次总数中的相对index位置

那同理,数组三 ---->数组二      x' = (x+m)%(n-1)

显然,当知道最后一个数组(只有一个元素,index为0),可以推得其在前一次总数中(即有两个元素时)的Index位置。然后再回溯,以此类推可以知道其在原始总数的Index

f(i)=\begin{cases}<br />
0 ;& \text{if $i==1$ }\\<br />
(f(i-1)+m)\% i ;& \text{$if i>1$}<br />
\end{cases}

也就说最后被删除的数字在最初的数列中的编号是2。

问题二:让n个人围成一圈,并将他们从1到n编号,从编号为1的那个开始残酷的计数,每次消去第二个人直到只留下一个幸存者。

如果n是6,那么2,4,6在通过圆圈的第一轮就将被消去;而初始位置为1和3的那些人将在第二轮被消去,留下一个初始位置为5的幸存者。J(6)=5。如果n为7,那么2,4,6,1位置上的人在通过圆圈的第一轮就将被消去;而初始位置为5和3的那些人将在第二轮被消去。J(7)=7。

QQ截图20150614212042

解题思路:考虑奇数n和偶数n的情况。

当n为偶数(n=2k),那么对圆圈处理第一遍后,规模减半,一个初始位置为3的人在第二轮会处在2号位置上。也就是说J(2k)=2J(k)-1。

当n为奇数(n=2k+1),第一轮消去所有偶数位置上的人,把紧接着消去的位置1上的人也加进来,留下一个规模为k的实例。J(2k+1)=2J(k)+1。

一种做法是将n的二进制表示向左循环移动一位来得到J(n)。J(6)=J(110_{2})=101_{2}=5J(7)=J(111_{2})=111_{2}=7

对于所有为2的乘方的n来说,它的约瑟夫斯问题的解是1。

 

问题3:参考自http://blog.csdn.net/csf111/article/details/6846095

http://blog.csdn.net/xiaowei_cqu/article/details/8585888

1) 问题描述

约瑟夫斯(Josephus)问题的一种描述是:编号为1,2,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向下一个人开始重新从1报数,如此下去,直至所有的人全部出列为止。试设计一个程序,按出列顺序印出各人编号。

2)基本要求

利用单向循环链表存储结构模拟此过程,按照出列的顺序印出各人的编号。

3)测试数据

n=7,7个人的密码依次为:3,1,7,2,4,8,4。m初值为6(正确的出列顺序应为6,1,4,7,2,3,5)。

4)提示

程序运行后,首先要求用户指定初始报数上限m,然后读取个人的密码。可设n≤30。注意链表中空表和非空表的界限。

QQ截图20150614221415