失踪的文物

来自计算思维百科
跳转至: 导航搜索
失踪的文物.png

某市博物馆的艺术品类文物共有16件,它们是从0开始的二进制数编码的即(0000~1111)。今天管理员在清点文物的时候发现少了一件文物,但不知道是哪个编号的文物不见了。此时馆内现存的文物编码有:0111、0010、0101、1010、0001、1111、0110、1000、0100、0011、1110、1011、1100、0000、1101。你有什么好的办法能够帮助管理员尽快的找出失踪的那件文物吗?

解决方案

方案一:蛮力法

我们能想到比较直接的办法就是将每个文物的二进制编码转换为十进制,即将15个二进制编码转换为0~15之前的十进制数,然后用0~15之间的数去一一匹配检查,可以把丢失的那件文物编码找到。那我们可以得到馆内现有的文物编号分别为7、2、5、10、1、15、6、8、4、3、14、11、12、0、13.检查过程:

完整编号

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

馆内编号

0

1

2

3

4

5

6

7

8

 

10

11

12

13

14

15

所以9号文物即1001号文物失踪了。

运用的计算思维

方案一利用全遍历比较去寻找比较,这是计算机里最简单的方式,但当数据量较大时,显然效率较低,这也是机械化思维方式不可避免的一个缺点。

方案二:分治法

我们可以知道从0000~1111之间的所有数,各个位置上为1的数和为0的数,总的个数是相等的,即最低位为1的数和最低位为0的数个数相等即都为8个,对于其他位也是同样的道理。所以我们先考察最低位的情况:

 

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

最低位

1

0

1

0

1

1

0

0

0

1

0

1

0

0

1

我们发现最低位为1的只有7个,说明丢失的文物编号末尾是1;此时我们可以排除8种可能性,范围缩小了一半,现在我们查询倒数第二位;

 

1

3

5

6

10

12

15

倒数第二位

1

0

0

1

1

1

0

倒数第二位为0的本该有4个,此时只有一个,说明丢失的文物编号的倒数第二位应为0,范围再次缩小一半,考察倒数第三位;

 

3

5

6

倒数第二位

1

0

1

显然,倒数第三位数为0,此时就只剩下5号对应的数,最高位为1;所以丢失的文物编码为1001。

运用的计算思维

方案二通过分治法,一步步的缩小比较范围,提高了效率,这是规约思维方式的优点体现!

参考文献

[1] 《算法艺术与信息学竞赛》 清华大学出版社