【编程的乐趣-用python解算法谜题系列】谜题一 保持一致

2019/04/10 10:10
阅读数 36

谜题一 保持一致

谜题

假设有一大群人排队等待观看棒球比赛。他们都是主场球迷,每个人都戴着队帽,但不是所有人都用同一种戴法,有些人正着戴,有些人反着戴。

假定你是保安,只有在全组球迷帽子戴法一致时才能让他们进入球场,要么全部正着戴,要么全部反着戴。因为每个人对正戴和反戴的定义并不相同。因此你不能对他们说把帽子正着戴或反着戴,只能告诉他们转一下帽子。

举个栗子(我们用 F 表示正戴,B 表示反戴)

F F B B B F B B B F F B F

上面是一个13人的队伍,位置从0 ~ 12。你可以发出以下指令:

请 0 号位置的人转一下帽子,

请 1 号位置的人转一下帽子,

......

然后分别对5,9,10,12号位置的人发出同样的指令,总共要发出六次指令。

我们也可以发出这样的指令:

请 2~4 号位置的人转一下帽子,

请 6~8号位置的人转一下帽子,

请 11 号位置的人转一下帽子。

只需要 3 次指令。

我们的要求是让保安生成的命令数最少。难度更大的问题是:能否第一次沿着队伍就得正确答案呢?

算法

算法一 寻找想法相同的连续人员

计算正戴区间和反戴区间的个数, 区间数更少的即是我们要反转的帽子区间。

def pleaseconform(caps):
    section = [] # 统计各区间的列表
    start = 0
    Fnum = 0 # 正戴区间数
    Bnum = 0 # 反戴区间数
    for i in range(1,len(caps)):
        if caps[start] != caps[i]: # 标志着新区间的产生
            section.append([start , i-1 ,caps[start]])
            if caps[start]=='F':
                 Fnum += 1
            else:
                Bnum += 1
            start = i
    section.append([start,len(caps)-1,caps[start]]) # 6~13行代码未添加最后一个区间,这行代码用于添加最后一个区间
    if caps[start]=='F':
        Fnum += 1
    else: 
        Bnum +=1
    if Fnum>Bnum :
        flag = 'B'
    else:
        flag = 'F'
    for t in section:
        if t[2]==flag:
            if(t[0] == t[1]):
                print("请"+str(t[0])+"号位置的人反转帽子")
            else:
                print("请"+str(t[0])+"到"+str(t[1])+"的人反转帽子")
   
caps = ['F','F','B','B','B','F','B','B','B','F','F','B','F']    
pleaseconform(caps)

"""
Output:
		请2到4的人反转帽子                               
		请6到8的人反转帽子                                   
		请11号位置的人反转帽子
"""
  • 我们注意到算法一的核心代码 6~13 行未添加最后一个区间,因此我们要再添加代码来完善算法,显得过于繁琐。实际上,我们只需要在 caps 列表添加一个其他元素如'M',就可以消除掉这种情况。
# 代码优化
def pleaseconform(caps):
    caps.append('M')
    section = []
    start = 0
    Fnum = 0
    Bnum = 0
    for i in range(1,len(caps)):
        if caps[start] != caps[i]:
            section.append([start , i-1 ,caps[start]])
            if caps[start]=='F':
                 Fnum += 1
            else:
                Bnum += 1
            start = i
    if Fnum>Bnum :
        flag = 'B'
    else:
        flag = 'F'
    for t in section:
        if t[2]==flag:
            if(t[0] == t[1]):
                print("请"+str(t[0])+"号位置的人反转帽子")
            else:
                print("请"+str(t[0])+"到"+str(t[1])+"的人反转帽子")
 
caps = ['F','F','B','B','B','F','B','B','B','F','F','B','F']    
pleaseconform(caps)

"""
Output:
		请2到4的人反转帽子                               
		请6到8的人反转帽子                                   
		请11号位置的人反转帽子
"""
算法二 单遍算法one pass

通过观察,实际上我们只需要通过 caps 列表中第一只帽子的方向,就可以得出我们需要反转的是正戴区间还是反戴区间。因为第一只帽子方向区间的个数一定大于等于另一方向的区间数。基于这一观察,能够实现一个one pass 算法。

# one pass 
def pleaseconformonepass(caps):
    caps.append(caps[0])
    for i in range(1,len(caps)):
        if(caps[i] != caps[i-1]):
            if(caps[i] != caps[0]):
                print("请"+str(i)+"号位置到")
            else:
                print(str(i-1)+"号位置的人反转帽子")
            
pleaseconformonepass(caps)

"""
Output:
		请2号位置到                                           
		4号位置的人反转帽子                                     
		请6号位置到                                         
		8号位置的人反转帽子                                    
		请11号位置到                                      
		11号位置的人反转帽子    
"""

谜题背后

这道谜题背后的出发点是数据压缩。向同一方向的人发出的命令信息是相同的,可以被压缩为一组较少的命令,其中每一条命令指挥一组连续的人。

谜题拓展

数据压缩有多种实现方式,在思路上接近于这道习题的一种算法叫做游程编码。举一个最简单的例子最容易描述,假设有以下字符串:

WWWWWWWWWWWWWBBWWWWWWWWWWWWBBBBB

使用游程编码算法,我们可以把上述字符串压缩为一个由数字和字符构成的字符串:

13W2B12W5B

游程解码算法就是把' 13W2B12W5B '解压为原始字符串的过程。

现代计算机的压缩工具,便是利用了这种思想相关的算法。

以下是游程编码解码的具体实现:

def youcengbianma(string):
    start=0
    newstring = ''
    for i in range(1,len(string)):
        if(string[start]!=string[i]):
            newstring += str(i-start)
            newstring += string[start]
            start=i
    newstring += str(i-start+1)
    newstring += string[start]
    return newstring

print(youcengbianma("wwweeewwwweeffeee"))

"""
Output:
		3w3e4w2e2f3e
"""

def youcengjiema(string):
    num = ''
    newstring = ''
    for i in range(0,len(string)):
        if(not string[i].isalpha()): # isalpha() 如果是字母字符,返回true
            num += string[i]
        else:
            for j in range(0,int(num)):
                newstring += string[i]
            num = ''
    return newstring

print(youcengjiema("3w3e4w2e2f3e")

"""
Output:
		wwweeewwwweeffeee
"""

原文出处:https://www.cnblogs.com/sang-bit/p/12285331.html

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部