维奇图编程求助
请教高手 把题目复制上来 歌者文明清理员 发表于 2023-4-12 18:42把题目复制上来
亲，上面的就是题目啊！ nbwubo 发表于 2023-4-18 08:51
亲，上面的就是题目啊！
以文本的形式 以下是这道题目的文字版本：
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
歌者文明清理员 发表于 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# 获取该分组规则下的全部表达式
result = []
for exp in expressions:
for i in range(len(x_values)):
if exp.find(chr(65 + i)) != -1:
# 将表达式中的字母替换为变量的值
if x_values == '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 = .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 == '1' for j in pattern):# 判断该分组是否可用
results += get_bool_expression(pattern, 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
页:
[1]