i******t 发帖数: 158 | 1 看到过好多次, 但一直不知道答案.求解.
n个人站成circle, 从某人开始1-m报数, 报到m的人退出, 继续,直到只剩一个人. 求最
后那个人的序号
先谢了! | b******4 发帖数: 1873 | | m**q 发帖数: 189 | 3 如果m可以认为是常数,直接算就行;如果不能认为是常数,
用顺序统计树可以算。复杂度O(n)
算法导论某一章的习题
【在 i******t 的大作中提到】 : 看到过好多次, 但一直不知道答案.求解. : n个人站成circle, 从某人开始1-m报数, 报到m的人退出, 继续,直到只剩一个人. 求最 : 后那个人的序号 : 先谢了!
| P**********c 发帖数: 3417 | 4 这个就是Josephus problem吧。
http://en.wikipedia.org/wiki/Josephus_problem
【在 i******t 的大作中提到】 : 看到过好多次, 但一直不知道答案.求解. : n个人站成circle, 从某人开始1-m报数, 报到m的人退出, 继续,直到只剩一个人. 求最 : 后那个人的序号 : 先谢了!
| s**x 发帖数: 7506 | 5 偶很早以前考过别人这个题, 当时偶希望的答案是用 single linked list create
one circle, just go through circle , remove element until the last one. 不知
道对不对, 这道题应该在一个算法书上, 想不起来了。 | i******t 发帖数: 158 | 6 多谢,多谢.果然有O(n)的算法:)
【在 P**********c 的大作中提到】 : 这个就是Josephus problem吧。 : http://en.wikipedia.org/wiki/Josephus_problem
| i******t 发帖数: 158 | 7 我想到的也是这样,用linklist直接走, 复杂度是O(nk).
【在 s**x 的大作中提到】 : 偶很早以前考过别人这个题, 当时偶希望的答案是用 single linked list create : one circle, just go through circle , remove element until the last one. 不知 : 道对不对, 这道题应该在一个算法书上, 想不起来了。
|
|