seg*_*way 3 algorithm hashtable data-structures
我正在研究一种算法，以确定井字游戏模型是否有赢家。不过有一点曲折-函数has_won？被多次调用。因此，我正在阅读的书（破解编码面试）中算法问题的作者建议生成2 ^ 9个可能的表中的每一个并将它们散列到一个表中。
为了为每个排列生成唯一的键，她将每个板表示为整数（板最初是一个char数组）。这样生成整数：（3 ^ 0）v0 +（3 ^ 1）v1 +（3 ^ 2）v2 + ... +（3 ^ 8）v8其中，如果空格为空，则v为0；如果空格为v，则为1它是X，如果是O，则为2。
这是我不关注的内容。我了解她为什么要这样做。但是，如何保证在大约20,000个可能的板中不会有另一个板不会以该表示形式共享相同的整数键值？她没有提供证明，而且我无法直观地理解为什么这是唯一的数字。
让我们尝试通过一个简单的示例查看其工作方式。假设板上只有两个空格。我知道这不是一个好游戏，但作为第一步，请使用它来演示数字代码的工作原理。在这种情况下，整数是您的符号
(3^0)v0 + (3^1)v1
其中v0和v1告诉我们两个空格是空的（0）是X（1）还是O（2）。现在列举案例：
_ _ (3^0) 0 + (3^1) 0 = 0
X _ (3^0) 1 + (3^1) 0 = 1
O _ (3^0) 2 + (3^1) 0 = 2
请注意，填满左侧空间只会产生小于3的数字。现在填满右侧空间。
_ X (3^0) 0 + (3^1) 1 = 3
_ O (3^0) 0 + (3^1) 2 = 6
请注意，在填充右侧空间时，我们只会得到3的倍数。现在休息。
X X (3^0) 1 + (3^1) 1 = 4
O X (3^0) 2 + (3^1) 1 = 5
X O (3^0) 1 + (3^1) 2 = 7
O O (3^0) 2 + (3^1) 2 = 8
现在我们可以看到每个配置都只对应一个整数。此外，我们可以通过整数除法从整数中获取配置。倒数第二种情况为7。将其除以3得到2，其余数为1。2是右手正方形的配置，而1是左手正方形的配置。这适用于以上所有示例。
如果您尝试使用两个以上的正方形，则会得到相同的结果。我知道这是事实的原因，以及在帖子中获得所要证明的方式是，要意识到以三为基的数字系统会将每个正方形的状态保留为一个数字。这就是您描述的编码的工作方式，这就是为什么整数编码中的每一项具有3的幂的原因。我认为这足以表明生成的整数是唯一的。
还有一种可能的澄清方法是想象可以处于十个状态中的任何一个状态的正方形。调用这些0到9。然后使用任何普通的以10为底的数字
234
保持每个数字只有一个平方的状态，并且每个平方的配置都为您提供一个且只有一个十进制数。用您在帖子中输入的符号写下这个数字
(10^0) 4 + (10^1) 3 + (10^2) 2 = 234
我们有v0 = 4，v1 = 3和v2 = 2。