卡诺图与“只出现一次的数字”问题

宋正兵 on 2020-12-11

只出现一次的数字问题

只出现一次的数字 II

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。

题目来源:LeetCode

卡诺图解法

如果不理解卡诺图,可以看下面的卡诺图章节

根据题目,我们需要找到一个能表达一个模 3 含义的状态转移过程,需要设置两个状态位来描述 00->01->10->00 的状态转移过程。

状态转移矩阵,其中 ab 代表状态位的低位和高位,每一个状态由 ab 和到来的 bit 位 x 决定。

9365eb6b82ff445789f100c8cbba982a.png

此时并没有办法直接通过观察看出我们所需要执行操作的具体形式,此时可以祭出卡诺图来解决问题。

下面是关于 b 的卡诺图,表中的数位对应状态的下一个状态中 b 的值。

Snipaste_2020-12-11_18-01-55.png

使用卡诺图化简法,不难写出如下转移方程:
$$
b = \overline{x}\overline{a}b + x\overline{a}\overline{b} = \overline{a}(\overline{x}b + x\overline{b})
$$
又由于 $\overline{x}b + x\overline{b} = x \bigoplus b $ ,所以有 b = ~a & (b ^ x)

下面是关于 a 的卡诺图,表中的数位对应状态的下一个状态中 a 的值。

Snipaste_2020-12-11_18-01-45.png

使用卡诺图化简法,不难写出如下转移方程:
$$
a = \overline{x}a + xb
$$
所以有 a = (~x & a) | (x & b)

把所有数依次输入,然后不断更新状态.最终,出现 3 次的位都成 0(也就是00),出现 1 次的位都成了 1(也就是 01)。我们最后直接返回状态 Y 就是要的答案。(另外辅助验证,最后 X 应该为全 0 ,因为最后所有位的状态要么是 00 ,即出现 3 次的数的位,要么是 01,即出现 1 次的数的位)

可以写出代码为:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public int singleNumber(int[] nums) {
int a = 0, b = 0;
int tmp;
for (int x : nums) {
tmp = b;
b = ~a & (x ^ b);
a = (~x & a) | (x & tmp);
}
return b;
}
}

由于代码中是先计算 b 再计算 a 的,所以可以通过画一个关于 anew_bx 的卡诺图来利用先生成的 new_b

Snipaste_2020-12-11_18-30-34.png

有 $a = x\overline{a}\overline{b} + \overline{x}a\overline{b} = (x\overline{a} + \overline{x}a)\overline{b}$ ,很明显的异或操作,于是有 a = ~b & (x ^ a)

1
2
3
4
5
6
7
8
9
10
class Solution {
public int singleNumber(int[] nums) {
int a = 0, b = 0;
for (int x : nums) {
b = ~a & (x ^ b);
a = ~b & (x ^ a);
}
return b;
}
}

逻辑真值表达式解法

同样的是需要找到一种逻辑操作,可以满足 1 * 1 * 1 = 00 * 1 = 1 * 0 = 1,其中 * 是这种新逻辑操作符。设当前状态为 XY,输入为 Z,那么我们可以为XY 列出真值表。

XY Z x$_{NEW}$ y$_{NEW}$
00 0 0 0
01 0 0 1
10 0 1 0
00 1 0 1
01 1 1 0
10 1 0 0

对于 Y,转化为逻辑表达式就是(取所有 $Y_{NEW} = 1$ 的行的 XYZ 的最小项,然后 $OR$ 起来)。

$$
Y_{NEW} = \overline{X}Y\overline{Z} + \overline{X}\overline{Y}Z
$$
化简:
$$
Y_{NEW} = \overline{X}(Y \bigoplus Z)
$$
同理可以求得 X 的逻辑表达式,此处有一个可以取巧的地方,不用再去求新的表达式。我们更新完 Y 之后,把 $Y_{NEW}$ 放到逻辑表达式中替换原来的 Y 的值形成新的逻辑表,这个新的逻辑表(Z、$X_{NEW}$、$XY_{NEW}$)对于 X 来说是跟求 Y 的时候的逻辑表是同构的。

Xy Z x$_{NEW}$ y$_{NEW}$ Xy$_{NEW}$
00 0 0 0 00
01 0 0 1 01
10 0 1 0 10
00 1 0 1 00
01 1 1 0 01
10 1 0 0 10

所以 $X_{NEW} = \overline{Y_{NEW}}(X \bigoplus Z)$

把所有数依次输入,然后不断更新状态.最终,出现 3 次的位都成 0(也就是00),出现 1 次的位都成了 1(也就是 01)。我们最后直接返回状态 Y 就是要的答案。(另外辅助验证,最后 X 应该为全 0 ,因为最后所有位的状态要么是 00 ,即出现 3 次的数的位,要么是 01,即出现 1 次的数的位)

代码

1
2
3
4
5
6
7
8
9
10
class Solution {
public int singleNumber(int[] nums) {
int a = 0, b = 0;
for (int x : nums) {
b = ~a & (x ^ b);
a = ~b & (x ^ a);
}
return b;
}
}

卡诺图

关于“最小项”

(1)最小项的定义

如果一个函数的某个乘积项包含了函数的全部变量,其中每个变量都以原变量或反变量的形式出现,且仅出现一次,则这个乘积项称为该函数的一个标准积项,通常成为最小项

例如 3 个变量 A、B 、C 可组成 8 个 最小项:
$$
\overline{A}\overline{B}\overline{C}、\overline{A}\overline{B}C、\overline{A}B\overline{C}、A\overline{B}\overline{C}、\overline{A}BC、A\overline{B}C、AB\overline{C}、ABC
$$

(2)最小项的表示方法

通常用符号 $m_{i}$ 来表示最小项。下标 i 的确定:把最小项中的原变量标记为 1,反变量标记为 0,当变量顺序确定后,可以按顺序排列成一个二进制数,则与这个二进制数相对应的十进制数,就是这个最小项的下标 i

3 个变量 A、B、C 的 8 个最小项可以分别表示为:
$$
m_{0}=\overline{A}\overline{B}\overline{C}、m_{1}=\overline{A}\overline{B}C、m_{2}=\overline{A}B\overline{C}、m_{3}=\overline{A}BC、m_{4}=A\overline{B}\overline{C}、m_{5}=A\overline{B}C、m_{6}=AB\overline{C}、m_{7}=ABC
$$

(3)最小项的性质

image-20201211110655988.png

  • 性质1:任意一个最小项,只有一组变量取值使其值为 1,而在变量取其他各组值时这个最小项的值都是 0
  • 性质2:不同的最小项,使它的值为 1 的那一组变量取值也不同;
  • 性质3:任意两个不同的最小项的乘积必为 0
  • 性质4:全部最小项的和必为 1

(4)逻辑函数的最小项表达式

任何一个逻辑函数都可以表示成唯一的一组最小项之和,称为标准与或表达式,也称为最小项表达式。

对于不是最小项表达式的与或表达式,可以利用公式进行化简。

(5)公式和定理

交换律:$A B = B A \ A + B = B + A$

结合律:$(A B)C = A (B C) \ (A+B)+C = A+(B+C)$
分配律:$A(B+C) = AB + AC \ A + BC = (A+B)(A+C)$

同一律:$AA=A \ A+A=A$

德·摩根定律:$\overline{AB} = \overline{A} + \overline{B} \ \overline{A+B}=\overline{A} \cdot \overline{B}$

还原律:$\overline{\overline{A}} = A$

(6)最小项的相邻性

任何两个最小项如果他们只有一个因子不同,其余因子都相同,则称这两个最小项为相邻最小项。

显然,$m_{0}(\overline{A}\overline{B}\overline{C})$ 与 $m_{1}(\overline{A}\overline{B}C)$ 具有相邻性,而 $m_{1}(\overline{A}\overline{B}C)$ 与 $m_{2}(\overline{A}B\overline{C})$ 不相邻。

相邻的两个最小项之和可以合并成一项,并消去一个变量。如:
$$
m_{0} + m_{2} = \overline{A}\overline{B}\overline{C} + \overline{A}B\overline{C} = \overline{A}(\overline{AB})m_{0} + m_{2} = \overline{A}\overline{B}\overline{C} + \overline{A}B\overline{C} = \overline{A}(\overline{B}+B)\overline{C} = \overline{A}\overline{C}
$$

卡诺图的构成

把所有最小项按一定顺序排列起来,每一个小方格由一个最小项占有。设变量数为 n,则最小项的数目为 $2^{n}$。两个变量的卡诺图:

Snipaste_2020-12-11_16-02-21.png

上图还显示这些小方格与变量 A 和变量 B 之间的关系。每行、列都被表上 01 代表变量值。

Snipaste_2020-12-11_16-14-20.png

如上图,其中有三个小方格被标上 1,这些方格就代表了函数的最小项:
$$
m_{1} + m_{2} + m_{3} = \overline{A}B + A\overline{B} + AB = A + B
$$
注意:

最小项并不是按照自然二进制顺序排列,而是按照类似于格雷码的顺序排列,这种排列方式相邻两列只有一位发生变化。

逻辑函数的卡诺图化简法

卡诺图相邻性的特点保证了几何相邻两方格所代表的最小项只有一个变量不同。因此,若相邻的方格都为 1 时,则对应的最小项就可以合并。合并的结果是消去这个不同的变量,只保留相同的变量。这是图形化简法的依据。

性质:在 n 个变量的卡诺图中,若有 2k1 格相邻(即圈内的 1 格数必须为 1,2,4,8 等,它们可以圈在一起加以合并,合并时可消去 k 个不同的变量,简化为一个具有 (n-k) 个变量的与项。若 k=n,则合并时可消去全部变量,结果为 1

用卡诺图化简法求最简与或表达式的步骤:

  1. 画出函数的卡诺图;
  2. 合并最小项;
  3. 写出最简与或表达式。

Snipaste_2020-12-11_16-21-57.png
Snipaste_2020-12-11_16-22-49.png

提示:

  • 圈的个数应尽可能少。即保证 1 格一个也不漏圈的前提下,圈的个数越少越好。
  • 按照 2k 个方格来组合,即圈内的 1 格数必须为 1,2,4,8 等,圈的面积越大越好。
  • 每个圈应至少包含一个新的 1 格,否则这个图是多余的。
  • 用卡诺图化简得到的最简与或式不是唯一的。

至此,我们已经明白了卡诺图的用法。