约瑟夫问题

Posted on 2009-11-30 11:17 王之昊 阅读(207) 评论(0)  编辑 收藏 引用 所属分类: 数学
约瑟夫的两个经典问题：
  1. 最后活下来的人是谁？
  2. 杀人序列如何？
对于问题一，有递推式可以做到O(n)， 具体数学上也提供了一种基于上下界知识的O(logn)的算法。不过对数的底比较小。
对于问题二，比较常见的方法是O(n^2)，用树状数组+二分的思想可以做到O(n*logn*logn)


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


posts - 26, comments - 7, trackbacks - 0, articles - 17

Copyright © 王之昊