《一人麻将》
本题是一道搜索题目。
要判断最早什么时候可能胡牌,我们可以当作只摸进牌不打出牌,什么时候手里的牌能凑出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。
不过实际的计算量远低于上述上限。
麻将真好玩