本帖最后由 shicuf 于 2015-1-7 10:11 编辑
班级群有人发了一个约瑟夫环的经典算法,超级简单,没人能给出解释,经过几小时熬战,整理出解题思路,现将问题分析如下,若有错误请指正!
问题描述:耶稣有15个门徒,其中有一个就是出卖耶稣的叛徒,请用排除法找出这位叛 徒:15人围坐一圈,从第一个开始报号:1,2,3,1,2,3......,凡是报到“3”就 退出圈子,最后留在圈内的人就是出卖耶稣的叛徒,请找出它原来的序号。
解析:为了方便推理,现把题目改为编号为1,2,3...n的n个人,报数到m则出列。
(1).从编号为1的人开始报数,第一个要出列的编号应该是m,考虑到环无越界,所以第一个出列的准确表达应该是m%n,令k = m%n(此处无任何逻辑意义,只是为了方便描述)。
(2).接下来是问题的关键,m出列之后,从编号为m+1的人开始重新组成了一个新的约瑟夫环,编号为m+1,m+2,…,n,0,1,…,m-1,此时的总人数变为n-1。因为当前问题变为n-1个人报数,报数为m的人出列。
(3).假设原始问题的叛徒编号为x’,第二步的叛徒编号为x,则第(2)步中所得到的n-1个人的叛徒编号与那个人的叛徒编号的对应关系应是x’ = x+k,考虑到环无越界的问题,所以准确表达应该为(x+k)%n。
(4).由第一步的k = m%n,带入第三步的结果,可得x’ = (x + m%n)%n = (x + m)%n。
综上四步分析,得到递推关系,如想知道那个人时的叛徒编号,需要知道n-1个人时的叛徒编号,以此类推,需要知道2个人时的叛徒编号(为什么从2开始,应该不用解释了吧。),两个人的情况即为初始条。加入初始条件,重新整合递推公式为x = (x + m - 1) % n + 1。倒推,即可得到最终答案。
代码如下:
- (NSInteger)traitorIndex: (NSInteger)totalNum with: (NSInteger)maxValue
{
// totalNum和maxValue必须是正整数
NSAssert((totalNum > 0 && maxValue > 0), @"输入参数必须为正整数!")
int i = 0;
NSInteger traitorIndex = 1;
for (i = 2; i <= totalNum; i++) {
traitorIndex = (traitorIndex + maxValue - 1) % i + 1;
}
return traitorIndex;
} |
|