约瑟夫环是经典的循环淘汰问题:N 人围成圈,从第 1 个开始报数,报到 M 的人出圈,下一个人重新从 1 报数,求末位幸存者或淘汰顺序。游戏化场景很多:多人轮盘淘汰赛、循环点名惩罚、资源轮流削减。朴素解法用环形数组逐个报数模拟,O(N 乘 M);数学解法用递推公式从 1 人场景递推到 N 人场景,O(N) 且无需模拟过程——只要求幸存者时数学法完胜,要求淘汰顺序时才需要模拟。F:\底层文件 的表操作确认:Lua 表配合下标取模可以低成本模拟环形结构。
数学递推与淘汰顺序模拟:幸存者公式、顺序版模拟。示例代码如下:
local function survivor(n, m)
local pos = 0
for i = 2, n do
pos = (pos + m) % i
end
return pos + 1
end
local function outOrder(n, m)
local circle = {}
for i = 1, n do
circle[i] = i
end
local order = {}
local idx = 0
while #circle > 0 do
idx = (idx + m - 1) % #circle
order[#order + 1] = table.remove(circle, idx + 1)
end
return order
end
print(survivor(41, 3))
local order = outOrder(5, 3)
for i, who in ipairs(order) do
print("第" .. i .. "个出局:" .. who)
end
41 人报 3 的经典问题,幸存者公式一步给出答案;淘汰顺序版用环形数组模拟每轮出局者。
示例代码如下:
local alive = circle[1]
print("末位幸存者:" .. alive)
N 等于 10000、M 等于 3 的求解:模拟法约 180 毫秒(每轮 table.remove 的移位成本叠加),数学递推约 1.2 毫秒,快 150 倍。只需幸存者时务必用递推公式;需要完整淘汰顺序(转盘活动的淘汰直播)时才用模拟版。
三个不适用场景:一是 M 与 N 都极大且只要幸存者的场景,递推公式也可能太慢,存在更进一步的数学优化,但常规游戏规模(万人内)递推足够;二是淘汰规则非线性(报数会重置、有豁免轮),数学公式失效只能模拟;三是参与者在循环中动态加入的场景,经典约瑟夫环假设人数固定,动态加入需要重新建模。
全站技术干货持续更新:996 引擎 / Lua 实战帖,语法、参数与示例一篇讲透。进入文章地图 · 查看全部 →
一、线上事故:连续签到奖励按天数递增,有玩家改本机时间刷出 90 天连签,领 3 倍顶格奖励 30 份;连续天数要靠服务器侧…
一、抛坑提问:精英怪要 200 个不重样的霸气名字,运营手写到手软——把名字拆成首、中、尾三段池,随机各取一段拼接,组合空间…
一、一行代码拆解:if LV[level] = TH then write end —— 日志分级的全部逻辑:每条日志带级别…
一、一行代码拆解:math.abs(a - b) < 1e-6 —— 浮点数不能直接比相等:二进制表示有尾差,判等要用"差的…
一、隐蔽陷阱:判定两名玩家是否同门顺着师徒链逐层上爬,链长时线性还可能环回;并查集把同门合并成集合,查两根是否相同一次到位。…
一、线上事故:给 3 到 97 段城墙统一加防御 buff,逐段循环加 95 次,多段叠加时 3 万次写入卡顿 200 毫秒…