百科问答小站 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进行压缩编码。再用另一个二进制序列来标注出现在指定顺序位置的棋子是黑还是白。

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


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




  

相关话题

  C语言中,write(1,buf,N)与write(0,buf,N)在底层存在什么样的区别? 
  作为非计算机专业的学生,觉得 C 语言远比其他语言易于上手,正常吗? 
  C语言中整型输出(%d)有什么用? 
  p是char类型指针,p[1]不是指向p[0]的下一个字节吗?为什么会到0x11? 
  现代C/C++编译器有多智能?能做出什么厉害的优化? 
  一条C语言语句不一定是原子操作,但是一个汇编指令是原子操作吗? 
  Objective-C 的一些函数名为什么都这么长? 
  为什么不建议一个对象在多处存储引用? 
  C++的CRTP所带来的静态多态功能具体有什么用? 
  请问#define PI 3.1416比float pi=3.1416有什么优势呢? 

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





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