百科问答小站 logo
百科问答小站 font logo



如何用最简短的二进制代码表示一张19*19的围棋棋盘的情况? 第1页

  

user avatar   Ivony 网友的相关建议: 
      

题目是:如何用最简短的二进制代码表示一张19*19的围棋棋盘的情况?

然后问题描述中给出了一种最蠢的办法……


这真是让人哭笑不得………………


好吧,还是回归问题,如何用最简短的代码标识一个围棋棋盘情况?

事实上,稍加分析就能看出来:围棋的棋盘分为三个阶段:

布局、中盘、官子。

布局阶段棋盘上的棋子非常少,空位非常多。此时,采用坐标描述棋子是最合适的,且布局阶段黑白棋子数量相等(布局阶段几乎不可能吃子),所以可以直接按顺序储存黑白棋子坐标,譬如说:

黑子坐标,白子坐标,黑子坐标,白子坐标。

也就是说第一个坐标一定是黑子,第二个一定是白子,第三个一定是黑子,类推。

如果真的出现了吃子的情况,再采用空子坐标来修正,譬如说白子被吃掉了一个:

黑子坐标,白子坐标,黑子坐标,空子坐标、黑子坐标。

当然,我们也可以约定只要出现吃子,就不判定局面为布局,局面怎么判定以后再聊。


又由于布局阶段几乎不可能在中腹落子和顶边落子,所以可以采用变长编码。其中2、3、4和16、17、18采用短编码,即:000=2,001=3,010=4,100=16,101=17,110=18。

注意到011和111没有用,这是因为它们用于长编码:

然后:

01100=1,01101=5,01110=6,0111100=7,0111101=8,0111110=9,0111111=10

11100=19,11101=15,11110=14,1111100=13,1111101=12,1111110=11,

1111111=空子坐标

或者我们可以采用另一种长编码:

011000=1,011001=5,011010=6,011100=7,011101=8,011110=9,011111=10

111000=19,111001=15,111010=14,111100=13,111101=12,111110=11,

其实效果会差不多。


所以,如果黑子第一着在左上点三三,白子紧接着在右下点三三,记录下来就是:

001001101101

是不是很简短?

这种方式记录的一个子坐标长度平均会在8位左右,大约二十着或者更早的时候的时候编码变得不实用,因为长度已经太长,此时更换为下面的方式:

先把整个棋盘映射成一个二进制空间,规模是19*19=361位。接下来把棋子出现的位置置为1,其余为0。然后再将连续的0进行压缩编码。再用另一个二进制序列来标注出现在指定顺序位置的棋子是黑还是白。

在棋子远少于空位的中盘易得这种方式比纯粹的三进制要省空间。


先这样,有空再补充官子的记录方式……




  

相关话题

  如何把一个文件快速分发到 100w 个服务器? 
  如何通俗地解释 C、C++、C#、Java、JavaScript、HTML、Python的用处? 
  请问有什么好的C语言面向对象的扩展的方式?最好是有比较好的项目的源码参考。 
  我试图用 C 语言的共用体来实现 Base64 编码,为什么失败了? 
  memcpy比循环赋值快吗?为什么? 
  c/c++怎么把一个bool数组(刚好8个元素)转换成char? 
  C语言中指针与数组都可以用a[3]表示,那它们是不是相同? 
  内存为啥要分堆栈在编程里,要是全部只用堆或者全部只用栈,行不行? 
  无码编程的思想是否值得推行? 
  如何看待枚举类型与基本类型的关系? 

前一个讨论
为什么出版社后面都有个京东自营?
下一个讨论
为什么有些女生现在就过上了普通人望尘莫及的生活?





© 2025-04-03 - tinynew.org. All Rights Reserved.
© 2025-04-03 - tinynew.org. 保留所有权利