春假扭腰Bloomberg一游

whuwangyi 发表于 2014-3-19 02:51
我觉得python这种语言虽然也很流行，但和c/c++/java这些主流编程语言还是很不一样的，建议再至少学一门其 ...

目前正打算自学java

whuwangyi 发表于 2014-3-19 00:12
我也觉得这题应该有更好的解法，我解得太直接了。当时我说想弄出个更好解法的时候，面试官的确让我想了下 ...

以下引自链接：http://baike.baidu.com/link?url= ... zyjN5I-jZZ8LUhXAaC_

为了讨论方便，先把问题稍微改变一下，并不影响原意：
问题描述：n个人（编号0~(n-1）），从0开始报数，报到（m-1）的退出，剩下的人继续从0开始报数。求胜利者的编号。
我们知道第一个人（编号一定是（m-1） mod n) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m mod n的人开始）：
k k+1 k+2 ... n-2,n-1,0,1,2,... k-2
并且从k开始报0。
我们把他们的编号做一下转换：
k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2
变换后就完完全全成为了（n-1）个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x'=(x+k) mod n
如何知道（n-1）个人报数的问题的解？对，只要知道（n-2）个人的解就行了。（n-2）个人的解呢？当然是先求（n-3）的情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：
令f表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]
递推公式
f[1]=0;
f[i]=(f[i-1]+m) mod i; (i>1）

whuwangyi 发表于 2014-3-19 10:53
多谢指教！这个方法还挺好理解的~

网上搜了下约瑟夫问题，的确是个经典问题。发现除了线性解法之外还有 ...

lgn的解法相当于进制转化，还挺酷的。
欢迎交流~

whuwangyi 发表于 2014-3-19 00:06
有正装就最好穿上吧。我当时没穿，属于另类。。。

好样的！下周同当另类！
我实在是没有正装，别家也都不用正装，为这一家intern置办一身有点不情愿啊～

看完lz之后只能膜拜啊，希望明天这家轻虐我。