35 lines
964 B
Plaintext
35 lines
964 B
Plaintext
local fmt = require "fmt"
|
|
|
|
local function josephus(n, k, m)
|
|
if k <= 0 or m <= 0 or n <= k or n <= m then
|
|
error("one or more parameters are invalid")
|
|
end
|
|
local killed = {}
|
|
local survived = {}
|
|
for i = 1, n do survived[i] = i - 1 end
|
|
local start = k
|
|
while true do
|
|
local finish = #survived
|
|
local i = start
|
|
local deleted = 0
|
|
while i <= finish do
|
|
killed:insert(survived:remove(i - deleted))
|
|
if #survived == m then return {survived, killed} end
|
|
++deleted
|
|
i += k
|
|
end
|
|
start = i - finish
|
|
end
|
|
return {survived, killed}
|
|
end
|
|
|
|
local triples = { {5, 2, 1}, {41, 3, 1}, {41, 3, 3} }
|
|
for triples as triple do
|
|
local [n, k, m] = triple
|
|
print($"Prisoners = {n}, Step = {k}, Survivors = {m}")
|
|
local sk = josephus(n, k, m)
|
|
print($"Survived : {fmt.swrite(sk[1])}")
|
|
print($"Kill order : {fmt.swrite(sk[2])}")
|
|
print()
|
|
end
|