约瑟夫问题的解决方法

有n只猴子,按顺时针方向围成一圈选大王(编号从1到n),从第1号开始报数,一直数到m,数到m的猴子退出圈外,剩下的猴子再接着从 1 开始报数。就这样,直到圈内只剩下一只猴子时,这个猴子就是猴王。
现在告诉你 n 和 m,请帮忙求出哪一只猴子能当大王。

这种问题如果模拟链表或数组很容易会让问题的超时复杂度O(m,n),所以还是有一种数学的方法降低复杂度到O(n)

递推公式
f[1]=0;
f=(f+m) mod i; (i>1);
问题解法
QQ截图20160907093024

发表评论

电子邮件地址不会被公开。 必填项已用*标注