hiho一下第261周《一人麻将》题目分析

4
0

《一人麻将》

本题是一道搜索题目。

要判断最早什么时候可能胡牌,我们可以当作只摸进牌不打出牌,什么时候手里的牌能凑出2种胡牌牌型之一,就是最早可能胡牌的时候。

我们估计一下整个搜索的大致计算量:

首先每摸进一张牌就要多判断一次,最多摸进94张牌,所以最多判断95次。

对于每次判断,我们要枚举缺的花色是哪一种,一共要枚举3种情况。

然后我们分别判断是胡哪一种牌型,显然2x7的牌型可以直接统计+判断,计算量大概是手牌总张数,远低于后一种牌型判断。

对于3+3+3+3+2这种牌型。我们要搜索判断。每一层递归我们枚举一种可能的坎(3张牌),递归4层之后判断余下手牌是否能凑出1对。

每一层的坎可能是3张相同的牌,考虑到只有2种花色,一共有18种可能;

坎也可能是同一花色连续3张牌,一共有14种可能。

所以每一层的枚举量大约是32种可能。4层递归总计计算量大约32^4。

所以整道题目的计算量上限大约是95x3x32^4 约等于 3 x 10^8。

不过实际的计算量远低于上述上限。

1 answer(s)

0

一个花色内的坎的数量可用动态规划来统计出来的,然后可以先枚举眼,然后再重新计算这个花色的坎的数量,这样运算复杂度可以下降非常多

write answer 切换为英文 切换为中文


转发分享