2

这是一道面试题：

8x8 棋盘上两个位置的最小位表示是多少？

我找到了答案http://www.careercup.com/question?id=4981467352399872

但我无法理解作者在说：

您可以用 n 位表示 2^n 个值。但是，您可以用最多n 位表示 2^n + 2^(n-1) + 2^(n-2) + ... 1 = 2^(n+1) - 1 个值。因此，您可以仅使用 10 位来表示 2^11 - 1 = 2047 个不同的值。

我并不是要解释作者在他的回答中的建议，但我对解决问题本身更感兴趣。据我所知，既然有64C2 = 2016办法在一块板上表示两块8x8，所需的最小位数应该是 11。但有人建议可以只用 10 位来表示板。如何？

4

2 回答 2

2

作者说您可以使用 5、6、7、8、9 和 10 位值来表示位置。

二进制 2016 是 11111100000 (1024 + 512+ 256 + 128 + 64 + 32)

5 bits  (00000 -      11111) represent 32 positions
6 bits  (000000 -     111111) represent 64 positions
7 bits  (0000000 -    1111111) represent 128 positions
8 bits  (00000000 -   11111111) represent 256 positions
9 bits  (000000000 -  111111111) represent 512 positions
10 bits (0000000000 - 1111111111) represent 1024 positions

共 2016 个职位。

这可以在具有位集合的语言中实现，例如 C++ bitset，它具有获取长度的大小函数。

这是一个 2x2 板的示例，希望能更好地解释这一点。

对于 2x2 板，有 4C2 (6) 个位置

.x  x.  ..  xx  .x  x.
.x  x.  xx  ..  x.  .x

所以你可以使用 3 位 000、001、010、011、100、101 和 110

但是 6 是二进制 110 (4+2)，因此您可以将 1 位 (0-1) 用于 2 个位置，将 2 位 (00, 01, 10, 11) 用于其余 4。因此位置是：

0、1、00、01、10、11。

于 2013-09-02T13:18:07.337 回答
0

要回答问题并获得整数解，您必须评估以下等式：

bits = ceil(log2(combination(64,2)));
bits = ceil(log2(64!/(62!*2!)));
bits = ceil(log2(64*63/2));
bits = ceil(log2(32*63));
bits = ceil(log2(32)+log2(63));
bits = ceil(5+log2(63));
bits = ceil(5+5.97728);
bits = 11;

推导方程需要组合学的工作知识。

combination(64,2)表示选择可能的唯一空间2的方法的数量。64

于 2013-10-13T19:43:39.160 回答