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. 不知
: 道对不对， 这道题应该在一个算法书上， 想不起来了。
|
|
