九连环游戏由某一状态到另一状态需要多少步,以及如何进行的问题。
玩九连环的习惯是第一环在左边,第九环在右边。因此仅第一环和第三环在上的状态用数字表示是101000000。但二进制数与格雷码都是是个位数在右边,因此九连环的状态要翻转写出,才是相应的格雷码。例如状态101000000的格雷码是000000101。再把格雷码转换为二进制数,这要算一下,讲到九连环数学原理的书都会介绍二进制数与格雷码的互化的方法。至于二进制数转换为十进制数就大家都很熟悉。
例如,考虑由状态A:000111100到状态B:111000011需要多少步。状态A的格雷码是001111000,相应二进制数是 001010000 ,十进制数是 80 。状态B的格雷码是 110000111 ,对应二进制数是 100000101 ,十进制数是 261 。故需要261-80=181步。而且状态A的十进制数小于状态B的十进制数,因此方向是由000000000到100000000的方向。
至于第一步如何操作,可以看到从80到261的过程中,下一个是81,二进制数001010001,相应格雷码是001111001,状态是100111100,与原来状态A对比,可看出,第一步应当上第一环。
|