关于这个算法的由来
今天是在公司写麻将算法的第四天,在第二天的时候已基本实现带N个癞子的麻将判胡算法,
但是,性能太垃圾了,运行1万次就需要大概3秒左右,也就是我上一篇文章提及的算法,想一下如果全国1000万人同时玩麻将,有100服务器,那么每秒需要判断1000万次是否胡牌,每台服务器每秒需要判断10万次,那么每个人需要在0-30秒后才能得到结果,虽然这个只是大概数据,但是显然不符合实际,所以算法要从根本思路去颠覆
新算法 -- 类二叉递归法
废话不多说(如果要让我用文字去描述这个算法,那不如让我去死)
为了让人更容易看懂,我使用了一个特例去画思维导图,结合代码运行,应该大家就可以慢慢理解到里面的神奇精妙之处
这个案例没有讲解带N个癞子的情况,但是我相信理解了这个图和代码之后,带N个癞子的情况也能慢慢理解~
好了,真的不废话了,上干货!
麻将算法核心思路xmind图解.png
再结合代码:
-- @曾帅 2018/7/6
---------------------思路(伪代码)-------------
--[=[
检查胡牌：
local 对子 = 找对子
if 对子 then
移除对子(对子)
result
if count == 0 then return result end
检查胡牌()
加回对子(对子)
end
lcoal 顺子= 找顺子()
if 顺子 then
移除顺子(顺子)
result
if count == 0 then return result end
检查胡牌()
加回顺子(顺子)
end
lcoal 刻子= 找刻子()
if 刻子 then
移除刻子(刻子)
检查胡牌()
加回刻子(刻子)
end
]=]
-- 定义胡牌成功的牌组数据结构
local result = {
dui_zi = nil,
ke_zi_array = {},
shun_zi_array = {},
}
-- 辅助函数，递归打印表，以便观察结果和测试查错等
function PrintTable(tbl, level) -- level 为递归深度，默认为1
if tbl == nil then return end
local msg = ""
level = level or 1
local indent_str = "" -- 缩进
for i = 1, level do
indent_str = indent_str .. " "
end
if level == 1 then
print(indent_str .. "{")
end
for k, v in pairs(tbl) do
local k_str = ""
if type(k) == "string" then -- 键值为字符串，则["xxx"]
k_str = string.format("[\"%s\"]", k)
else
k_str = string.format("[%s]", k)
end
if type(v) == "table" then
local item_str = string.format("%s%s = {", indent_str .. " ", k_str)
print(item_str)
PrintTable(v, level + 1)
elseif type(v) == "number" then
local item_str = string.format("%s%s = %s,", indent_str .. " ", k_str, tostring(v))
print(item_str)
else
local item_str = string.format("%s%s = \"%s\",", indent_str .. " ", k_str, tostring(v))
print(item_str)
end
end
if level == 1 then
print(indent_str .. "}")
else
print(indent_str .. "},")
end
end
-- 在有序牌中找到第一个非个数为0的牌,最多需要遍历十次
function GetFirstNotZeroKey(t, index)
for i = 1, 10 do
if t[i] and t[i] > 0 then
return i + index - 1
end
if i == 10 then
if t[99] and t[99] > 0 then
return 99
end
end
end
end
-- 查找到ABC,记录ABC牌组
-- 查找到AB,癞子足够,记录牌组和一个癞子
-- 查找到AC,癞子足够,记录牌组和一个癞子
-- 没查找到 返回false
-- 优化的地方:这里的查找并不是真的查找
-- 先拿到牌组中第一个个数不为0的牌(first_k)
-- 再去找顺子,都是在一个table中找一个key对应的value
-- 在lua中,这种操作时间复杂度都是O(1)
-- 所以这个方法的时间复杂度为O(1),比之前的O(N^2)优化了许多
function CheckAbc(t)
local first_k = GetFirstNotZeroKey(t, 1)
local zu_he = {first_k}
local lai_zi_count = t[99]
for k, v in ipairs({first_k + 1, first_k + 2, 99, 99}) do
if t[v] and t[v] > 0 then
if v == 99 and lai_zi_count == 0 then
break
end
table.insert(zu_he, v)
if v == 99 then lai_zi_count = lai_zi_count - 1 end
if #zu_he == 3 then break end
end
end
return #zu_he == 3 and zu_he or false
end
-- 查找到AAA,记录AAA牌组
-- 查找到AA,癞子足够,记录牌组和一个癞子
-- 查找到A,癞子足够,记录牌组和两个癞子(特殊情况,癞子少的时候较少,癞子多的时候起优化作用)
-- 原理和上面一致
function Check3n(t)
for k, v in pairs(t) do
if v >= 3 then
return {k, k, k}
end
if t[99] and t[99] >= 1 and v == 2 then
return {k, k, 99}
end
if t[99] and t[99] >= 2 and v == 1 then
return {k, 99, 99}
end
if t[99] and t[99] >= 3 and v == 0 then
return {99, 99, 99}
end
end
end
-- 原理和上面一致
function Check2n(t)
for k, v in pairs(t) do
if v >= 2 then
return {k, k}
end
if t[99] and t[99] >= 1 then
return {GetFirstNotZeroKey(t, 1), 99}
end
if t[99] and t[99] >= 2 then
return {99, 99}
end
end
end
-- 把t2的元素加到t中,只是单纯把对应key的value加1,时间复杂度为O(1)
function Insert(t, t1)
for i, v in ipairs(t1) do
t[v] = t[v] + 1
end
return t
end
-- 把t2的元素从t中移除,原理同上
function Remove(t, t1)
for i, v in ipairs(t1) do
t[v] = t[v] - 1
end
return t
end
-- 递归去除(看简书上面的图解~),这里的删除添加操作与上面原理一样,时间复杂度为O(1)
function Check(t)
local res_2n = Check2n(t) -- 返回找到的对子
if not result.dui_zi and res_2n then -- 如果找到对子，并且之前没有对子在记录中
---[[
print("-------------find_2n-------------")
PrintTable(res_2n)
print("-------------删除前的t表-------------")
PrintTable(t)
--]]
Remove(t, res_2n) -- 从牌组中移除对子
---[[
print("-------------removed_2n-------------")
PrintTable(t)
--]]
result.dui_zi = res_2n -- 记录好对子
if not GetFirstNotZeroKey(t, 1) then return result end -- 如果移除完之后没有牌了，那么就返回结果
if Check(t) then return result end -- 否则继续递归
result.dui_zi = nil -- 清除对子
Insert(t, res_2n) -- 还原对子到表中
---[[
print("-------------insert_2n-------------")
PrintTable(res_2n)
print("-------------插入回去的t表-------------")
PrintTable(t)
--]]
end
-- 同上
local res_abc = CheckAbc(t)
if res_abc then
---[[
print("-------------find_abc-------------")
PrintTable(res_abc)
print("-------------删除前的t表-------------")
PrintTable(t)
--]]
Remove(t, res_abc)
---[[
print("-------------removed_abc-------------")
PrintTable(t)
--]]
table.insert(result.shun_zi_array, res_abc)
if not GetFirstNotZeroKey(t, 1) then return result end
if Check(t) then return result end
table.remove(result.shun_zi_array)
Insert(t, res_abc)
---[[
print("-------------insert_abc-------------")
PrintTable(res_abc)
print("-------------插入回去t表-------------")
PrintTable(t)
--]]
end
-- 同上
local res_3n = Check3n(t)
if res_3n then
---[[
print("-------------find_3n-------------")
PrintTable(res_3n)
print("-------------删除前的t表-------------")
PrintTable(t)
--]]
Remove(t, res_3n)
---[[
print("-------------removed_3n-------------")
PrintTable(t)
--]]
table.insert(result.ke_zi_array, res_3n)
if not GetFirstNotZeroKey(t, 1) then return result end
if Check(t) then return result end
table.remove(result.ke_zi_array)
Insert(t, res_3n)
---[[
print("-------------insert_3n-------------")
PrintTable(res_3n)
print("-------------插入回去的t表-------------")
PrintTable(t)
--]]
end
return false
end
-- 数出牌组中每个牌对应的个数,如牌是{1,1,1,3},则形成类似下面的表
--[[
{
[1] = 3,
[3] = 1,
}
--]]
function TTT(tab)
local tabT = {}
table.sort(tab, function(a, b)
return a < b
end)
for key, v in pairs(tab) do
if tabT[tab[key]] == nil then
tabT[tab[key]] = 1
else
tabT[tab[key]] = tabT[tab[key]] + 1
end
end
return tabT
end
-- 判断是否能胡牌
function CheckIsHu(t)
if #t % 3 == 2 then -- 不符合基础规则(剔除大部分情况)
-- 输出每张牌有多少个
local count_t = {}
count_t = TTT(t) -- 数表
print("-------------------最开始的t表-----------------")
PrintTable(count_t)
local can_hu = Check(count_t) -- 递归验证
if can_hu then
print("-------------------最终胡牌组合-----------------")
PrintTable(can_hu)
return true
end
return false
else
return false
end
end
print("--------------带N个赖子的胡牌算法-------------")
-- 提供测试的数据
-- local pai = {1, 99}
-- local pai = {1, 1, 99}
-- local pai = {1, 1, 2, 3, 99, 99, 99, 99}
-- local pai = {1, 3, 5, 8, 8, 99, 99, 99}
-- local pai = {1, 2, 3, 6, 8, 8, 8, 2, 3, 5, 5, 7, 7, 9, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99}
-- local pai = {1, 1, 1, 9, 4, 4, 5, 5, 6, 7, 7, 99, 99, 99} -- 复杂测试
-- local pai = {1, 3, 3, 3, 5, 7, 7, 99, 99, 99, 99}
-- local pai = {1, 2, 3, 5, 4, 99, 99, 99}
-- local pai = {1, 2, 3, 5, 4, 5, 5, 6}
-- local pai = {2, 3, 7, 9, 99, 99, 99, 99}
-- local pai = {1,1,2,3,99,99,99,99}
local pai = {1, 1, 2, 3, 4, 6, 6, 8}
-- 测试运行时间
local start_time = os.clock()
local res
res = CheckIsHu(pai)
local end_time = os.clock()
print(string.format("start_time : %.6f", start_time))
print(string.format("end_time : %.6f", end_time))
print(string.format("cost_time : %.6f", end_time - start_time))
-- 结果
print("能否胡牌：" .. tostring(res))
好了,希望即将要去面试棋牌游戏公司的童鞋们用这个算法去征服你们的HR吧~
希望有更好的算法,愿意的话可以随时联系我 _
注 : 未经允许,请不要随意转载
有任何疑问或者是优化请联系我:
邮箱 511793781@qq.com
网友评论