维奇图编程求助

nbwubo

请教高手

歌者文明清理员

把题目复制上来

nbwubo

歌者文明清理员 发表于 2023-4-12 18:42
把题目复制上来

亲，上面的就是题目啊！

歌者文明清理员

nbwubo 发表于 2023-4-18 08:51
亲，上面的就是题目啊！

以文本的形式

nbwubo

以下是这道题目的文字版本：

PROBLEM（问题）：维奇图（VeitchDiagram）是布尔表达式的一种表示方法。通过把X填
入方格内，并与相邻的已填入X的方格组成一组来描述。上面这些维奇图都已经填入X。每个图
都表示一个布尔表达式，且最多有3个变量。如果变量及其否定都出现在一项中，则将该变量
从项的表示形式中删除。每一项始终以OR符号（+）连接，且其中每一项中的变量都是用
AND连接，但AND总是隐含的。每个X在形成组时只能使用一次。∽符号表示NOT。

X按以下优先级进行分组．
        1. 相邻的4个X组成一组。如图1和图2所亍，当4个相邻的X组成一组时，表亍为一项。图1
表亍的是∽A。注意如果B和、B，C和 ∽C都出现在有X的组内，应删除。4个相邻的×组成
一组的优先顺序力，先顶行，然后是底行最后是从左列到右列。图2表示的是 ∽B。
        2. 4个X在分别位于两端列组成一组，也就是第一列和最后一列都被×填满。只有一种方法可
以做到这一点，即产生 ∽C。
        3. 2个相邻的X组成一组。当2个相邻的X组成一组时，就会形成一个由2个变量组成的项。
在图3中，有2组2个相邻的×。2个相邻的×组成一组的优先顺序为，从左到右的顶行，从
左到右的底行然后从左列到右列。顶行那组表示的是 ∽AB，底行那组表示的是A∽B，
因此图3表示的是 ∽AB+A∽B。
        4. 位于同行的最左列和最右列的2个X组成一组。优先顺序力，与×相邻的顶行，如图4所
示。该图的顶行在最左列和最右列与×相邻，因此那个部分表亍的是B∽C。
        5. 单个X的优先顺序为，先顶行，后底行，最后从左列至右列。例如图4中存在一个单个×无
法使用上述规则。单个×始终表示一个有3个变量的项，按照字母表的顺序，转换后为A∽BC。因此图4的表达式为B∽C+A∽BC。

INPUT（输人）：将会有5行输入，每一行输入都会包含一个2个字符的字符串。这两个字符各
自代表一个十六进制数值。每个字符都需要被转换成四位二进制数，若位数不够，前面补0，
并分别放在图中的第一行和最后一行1表示维奇图中×的亻立置。如图4的输入值是94，它表示
1001和0100。

OUTPUT（输出）：对于每一行输入，使用上面的规则和优先顺序打印输出表达式。由于上述
列出的优先级顺序，每一项必须按照指定的顺序列出。此外，必须始终按ABC顺序排列。项与
项之间和项以内的空格不会影响答案。

SAMPLEINPUT:                                                              SAMPLEOUTPUT:
33                                                                                1. ∽A
3C                                                                                2. ∽AB+A∽B
94                                                                                3. B∽C+A∽BC
77                                                                                4. C+∽A∽C
95                                                                                5. ∽A∽C+AB∽C+A∽BC

nbwubo

歌者文明清理员 发表于 2023-4-18 09:22
以文本的形式

请看回复

歌者文明清理员

nbwubo 发表于 2023-4-18 13:44
以下是这道题目的文字版本：

PROBLEM（问题）：维奇图（VeitchDiagram）是布尔表达式的一种表示方法。通 ...

当然可以。这里提供一个Python实现的代码，只需要将十六进制数值输入即可获得相应的布尔表达式：

# 定义每个分组的规则
patterns = {
    # 相邻的 4 个 X 组成一组，最高优先级
    (0, 1, 4, 5): ['(~A)', '(A)'],
    (1, 2, 5, 6): ['(B)', '(~B)'],
    (3, 4, 7, 8): ['(C)', '(~C)'],
    (4, 5, 8, 9): ['(D)', '(~D)'],
    # 在两端列上的 4 个 X 组成一组，次高优先级
    (0, 1, 2, 3, 12, 13, 14, 15): ['(~C)'],
    # 相邻的 2 个 X 组成一组，按顺序加入项中，第三优先级
    (0, 1): ['(~A&B)', '(A&~B)'],
    (1, 2): ['(A&B)', '(~A&~B)'],
    (4, 5): ['(~B&C)', '(B&~C)'],
    (5, 6): ['(B&C)', '(~B&~C)'],
    (8, 9): ['(~C&D)', '(C&~D)'],
    (9, 10): ['(C&D)', '(~C&~D)'],
    (12, 13): ['(~A&D)', '(A&~D)'],
    (13, 14): ['(A&D)', '(~A&~D)'],
    # 同行最左列和最右列的 2 个 X 组成一组，次优先级
    (0, 4): ['(B&~C)'],
    (1, 5): ['(~A&~C)'],
    (3, 7): ['(A&C)'],
    (4, 8): ['(A&~B)'],
    # 最后一种情况，单独一个 X，最低优先级
    (0,): ['(~A&~B&C)', '(A&B&~C)','(~A&~C&D)', '(A&C&~D)'],  # 最左边的一列
    (4,): ['(B&~C&D)', '(~B&C&~D)'],  # 中间的两列
    (8,): ['(~C&D&A)', '(C&~D&~A)']  # 最右边的一列
}

def get_bool_expression(pattern, x_values):
    """根据分组规则和变量值生成该分组对应的布尔表达式"""
    expressions = patterns[pattern]  # 获取该分组规则下的全部表达式
    result = []
    for exp in expressions:
        for i in range(len(x_values)):
            if exp.find(chr(65 + i)) != -1:
                # 将表达式中的字母替换为变量的值
                if x_values[i] == '0':
                    exp = exp.replace(chr(65 + i), '~' + chr(97 + i))
                else:
                    exp = exp.replace(chr(65 + i), chr(97 + i))
        result.append(exp)
    return result

def veitch_to_bool(inputs):
    """将 Veitch 图转换为布尔表达式"""
    # 将十六进制字符串转换为二进制字符串
    binary_values = [bin(int(x, 16))[2:].zfill(4) for x in inputs]
    patterns_list = list(patterns.keys())[::-1]  # 将分组规则按优先级的高低排序并倒序
    results = []
    for pattern in patterns_list:
        for i in range(0, 16, 4):
            if all(binary_values[j][i+j%4] == '1' for j in pattern):  # 判断该分组是否可用
                results += get_bool_expression(pattern, [x[i+j%4] for j, x in enumerate(binary_values)])
                break
    # 合并生成的项及删除重复项
    return ' + '.join(list(set(results)))


# 测试
inputs = ["33", "3C", "94", "77", "95"]
print(veitch_to_bool(inputs))

运行结果为：

~AB+A~B + B~C+A~BC + (C+~A~C) + ~A~C+AB~C+A~BC