维奇图编程求助

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实现的代码，只需要将十六进制数值输入即可获得相应的布尔表达式：

1. # 定义每个分组的规则
   
2. patterns = {
   
3.     # 相邻的 4 个 X 组成一组，最高优先级
   
4.     (0, 1, 4, 5): ['(~A)', '(A)'],
   
5.     (1, 2, 5, 6): ['(B)', '(~B)'],
   
6.     (3, 4, 7, 8): ['(C)', '(~C)'],
   
7.     (4, 5, 8, 9): ['(D)', '(~D)'],
   
8.     # 在两端列上的 4 个 X 组成一组，次高优先级
   
9.     (0, 1, 2, 3, 12, 13, 14, 15): ['(~C)'],
   
10.     # 相邻的 2 个 X 组成一组，按顺序加入项中，第三优先级
    
11.     (0, 1): ['(~A&B)', '(A&~B)'],
    
12.     (1, 2): ['(A&B)', '(~A&~B)'],
    
13.     (4, 5): ['(~B&C)', '(B&~C)'],
    
14.     (5, 6): ['(B&C)', '(~B&~C)'],
    
15.     (8, 9): ['(~C&D)', '(C&~D)'],
    
16.     (9, 10): ['(C&D)', '(~C&~D)'],
    
17.     (12, 13): ['(~A&D)', '(A&~D)'],
    
18.     (13, 14): ['(A&D)', '(~A&~D)'],
    
19.     # 同行最左列和最右列的 2 个 X 组成一组，次优先级
    
20.     (0, 4): ['(B&~C)'],
    
21.     (1, 5): ['(~A&~C)'],
    
22.     (3, 7): ['(A&C)'],
    
23.     (4, 8): ['(A&~B)'],
    
24.     # 最后一种情况，单独一个 X，最低优先级
    
25.     (0,): ['(~A&~B&C)', '(A&B&~C)','(~A&~C&D)', '(A&C&~D)'],  # 最左边的一列
    
26.     (4,): ['(B&~C&D)', '(~B&C&~D)'],  # 中间的两列
    
27.     (8,): ['(~C&D&A)', '(C&~D&~A)']  # 最右边的一列
    
28. }
    
29. 
    
30. def get_bool_expression(pattern, x_values):
    
31.     """根据分组规则和变量值生成该分组对应的布尔表达式"""
    
32.     expressions = patterns[pattern]  # 获取该分组规则下的全部表达式
    
33.     result = []
    
34.     for exp in expressions:
    
35.         for i in range(len(x_values)):
    
36.             if exp.find(chr(65 + i)) != -1:
    
37.                 # 将表达式中的字母替换为变量的值
    
38.                 if x_values[i] == '0':
    
39.                     exp = exp.replace(chr(65 + i), '~' + chr(97 + i))
    
40.                 else:
    
41.                     exp = exp.replace(chr(65 + i), chr(97 + i))
    
42.         result.append(exp)
    
43.     return result
    
44. 
    
45. def veitch_to_bool(inputs):
    
46.     """将 Veitch 图转换为布尔表达式"""
    
47.     # 将十六进制字符串转换为二进制字符串
    
48.     binary_values = [bin(int(x, 16))[2:].zfill(4) for x in inputs]
    
49.     patterns_list = list(patterns.keys())[::-1]  # 将分组规则按优先级的高低排序并倒序
    
50.     results = []
    
51.     for pattern in patterns_list:
    
52.         for i in range(0, 16, 4):
    
53.             if all(binary_values[j][i+j%4] == '1' for j in pattern):  # 判断该分组是否可用
    
54.                 results += get_bool_expression(pattern, [x[i+j%4] for j, x in enumerate(binary_values)])
    
55.                 break
    
56.     # 合并生成的项及删除重复项
    
57.     return ' + '.join(list(set(results)))
    
58. 
    
59. 
    
60. # 测试
    
61. inputs = ["33", "3C", "94", "77", "95"]
    
62. print(veitch_to_bool(inputs))
    

复制代码

运行结果为：

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

复制代码