Python入门习题（87）——OpenJudge百练习题：判断游戏胜者

题目描述

来源
OpenJudge网站 —— 百练习题集-第4111号习题

要求
总时间限制: 3000ms 单个测试点时间限制: 1000ms 内存限制: 65536kB

描述

Alice和Bob在玩一个游戏，每一局中他们每人获得一个16进制数串，计算它对应的二进制数串中有多少个连续的1序列块(单个的1也算作序列块)。块数多者胜利，请判断游戏的胜者并输出，若平局则输出Tie，比如样例中的第一组数据为Alice: 0xfa425 Bob: 0xab3672。Alice的数据转换为2进制串后为11111010010000100101， 其中有6个连续的1序列块。Bob的数据转换为2进制串后为 101010110011011001110010 其中有8个序列块，故胜者为Bob。

输入
第一行为游戏局数正整数n，接下来n行每行由两部分组成，前者是Alice获得的16进制数串，后者是Bob获得的16进制数串，中间用空格隔开。
输出
每一行输出一局的胜者。
样例输入
2
0xfa425 0xab3672
0x52c6 0xf429
样例输出
Bob
Tie

解题思路

1. 关键问题是求出16进制串换成二进制串后，二进制串中1序列块的数目。
2. Python语言中，16进制串串换成二进制串的做法是，先调用int(hex, 16)把16进制串hex换成整数number，而后调用bin(number)换成二进制串。
3. 求出二进制串1序列块的数目的做法是，从左到右扫描每一位，遇到打头的1字符，则把1序列块的数目加1，接着跳过连续的1；遇到0字符，跳过。下面的代码中，sub1_num函数求出二进制串中1序列块的数目。jump_to_0函数跳过连续的1字符。

参考答案

#跳过连续的1字符，求出二进制字符串bin_str内索引index位置后第一个0字符的位置，或者是字符串结尾
def jump_to_0(bin_str, index):
    while index < len(bin_str):
        if bin_str[index] == '1':
            index += 1
        else:
            return index
    return index

#求二进制字符串中1序列块的数量
#bin_str是二进制字符串，以0b打头。
def sub1_num(bin_str):
    count = 0
    index = 2
    while index < len(bin_str):
        if bin_str[index] == '1':  #遇到打头的1字符
            count += 1
            index = jump_to_0(bin_str, index)   #跳过连续的1字符
        else:
            index += 1  #遇到0字符，索引增1
    return count

# assert sub1_num('0b0') == 0
# assert sub1_num('0b1') == 1
# assert sub1_num('0b101') == 2
# assert sub1_num('0b1010') == 2
# assert sub1_num('0b11110001100110') == 3
# assert sub1_num('0b1111111111') == 1

n = int(input())
for i in range(n):
    Alice, Bob = input().split()
    Alice = bin(int(Alice, 16))  #先把十六进制串转换为整数，然后转换为二进制串
    Bob = bin(int(Bob, 16))  #int函数的第二个参数16，表明Bob字符串是16进制的
    # print(Alice, Bob)
    sub1_num_Alice = sub1_num(Alice)  #求出Alice拿到的串的1序列块的数目
    sub1_num_Bob = sub1_num(Bob)
    if sub1_num_Alice > sub1_num_Bob:
        print("Alice")
    elif sub1_num_Alice == sub1_num_Bob:
        print("Tie")
    else:
        print("Bob")

测试用例

1. 题目描述给出的测试用例有两组测试数据。第一组测试数据覆盖了数目不等的情形。第二组测试数据覆盖了1序列块数目相等的情形。
2. 上一节给出的代码中的assert语句，验证了sub1_num函数的正确性。有了这个，无需更多测试用例。因为我相信，除开sub1_num函数封装的求二进制串中1序列块数目的逻辑，其他代码是简单直接的，不会出错。
3. 不放心的话，令n=1，Alice拿到全0的，Bob拿到全1的。
   样例输入
   1
   0x0 0xff
   样例输出
   Bob

小结

1. Python语言提供了从16进制字符串转换为整数的函数和把整数转换为二进制串的函数。
2. 用函数来封装一个子步骤，能够绕开两重循环。本例中，jump_to_0函数起到了这个作用。如果没有使用该函数，那么代码逻辑的复杂度将显著上升。有了该函数，代码变得清晰简洁。