首页 > 代码库 > 约瑟夫环问题求解
约瑟夫环问题求解
问题描述:已知n个人,分别以编号1,2,3,...n表示,围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列,求最后一个出列人的编号。
一般性递归算法思考:n个人围成一圈,从k开始以m为步长报数,第(k+m)-1个人出列;于是转化为n-1个人围成一圈,从(k+m-1)+1开始以m为步长报数,第(k+m)+m-1个人出列;再转化为求n-2个人围成一圈,从(k+2m-1)+1开始以m为步长报数,第(k+2m)+m-1个人出列;依次类推,直至只剩1个人围成一圈,该人出列即为问题的解。另外,在经过多轮数数出列之后,起始报数人编号和出列人编号一直在递增,它们的取值最终都可能大于n;如果此过程不中断,必然出现同一个人多次出列的情况。
算法实现:Josephus(n, m, k)
/** * 约瑟夫环胜利者求值,同时也打印出圈顺序至console以便于调试观察 * * @para int n 总人数 * @para int m 数数步长 * @para int k 起始数数者 * @return int 最后胜利者 */ function Josephus(n, m, k) { let list = ‘‘; if (n < 1) { return 0; } else if (n == 1) { list = ‘1‘; console.log(list); return 1; } else { return dequeue(n, m, k - 1); } function dequeue(n, m, out, i = n) { //n为总人数,m为数数步长,out为前一个出列者,i为迭代控制变量 if (i < 1) { list = list.slice(0,-1); console.log(list); return out; //返回最后胜利者 } else { out = (out + m - 1) % n + 1; //先减1后加1以避免(out + m) % n = 0,即当前出圈者为n时,模的取值却为0,而非n;同样又保证了当前out的取值始终落在[1, n]这个区间上,而如果令out = (out + m) % (n + 1),虽能保证当前out取值合法,却存在无效的情况,比如当(out + m) % (n + 1) = 0时,当前out取值1才是有效的 list += out + ‘,‘; i = i - 1; return dequeue(n, m, out, i); } } }
约瑟夫环问题求解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。