Life Is A Boat

好久没更新了，其实最近写的代码跟多，学到的内容也很多，有时间把实验报告贴上来好了
昨天在网上看到个问题，没事就做了一下，还费了点时间，后来问同学才知道那就是约瑟夫问题~~~~~~~~~
问题是这样的：有n个人，轮流从1到3报数，凡是报到3的人退出，问最后剩下的是最开始的几号？
我用递归的办法解决的，最后是O(n)的时间复杂度，是这样解决的：
首先是3个人的情况：
1 2 3
显然最后是第2个人留下来了
那么看4个人的情况：
1 2 3 4
首先是第3个人退出了，然后开始下一轮报数，此时的情况是这样的：  1 2 3 4 ----- 4 1 2 
回到了3个人的情况，我们知道是第2个人，实际编号为1的人最后剩下来了
此时有规律可找了，因为3个人的时候是第2个人留下来，那4个人的时候就是当第3个人退出后再往下的第2个人留下来
令n=3,k=2（k是退出的那个人的位置）
那么，当n=4时 k = (3+k) % n = 1
然后n = 5
        n = 6
        ……
的时候类推，问题解决了，用C写是这样的：
如果用n个人，则
for (i = 3,k = 2; i < n; i++)
     k = (3+k)%(i+1);


当然，伟大的Kunth，对，就是他，给出了这个问题的解公式，把这个问题变成常数复杂度了。。。。不过那个公式有点复杂就不写上来了，Kunth果然是牛人