下过中国中国象棋将帅问题的朋伖都知道双方的“将”和“帅”相隔遥远,并且不能照面在中国象棋将帅问题残局中,许多高手能利用这一规则走出许多精妙的杀招假设棋盘上只有“将”和“帅”二子。(下面为了叙述方面我们约定用A表示“将”,B表示“帅”)
A和B分别被限制在自己的九宫格内,不能走出九宫格不能走斜线,只能走横竖线上的一步
请写出一个程序,输出A、B所有合法位置要求代码中只能使用一个字节存储变量。
问题本身并不复杂只要把所有A、B互相排斥的条件列举出来就可以完成本题的要求。由于本题要求只能存储使用一个变量所有首先必须想清楚在写代码的时候,有哪些信息需要存储并且尽量高效地存储信息。稍微思考一下可以知道这个程序的大体框架是:
因此,需要存储的是A、B的位置信息并且每次循环都要更新,首先创建一个逻辑坐标系统一个可行的办法是用1-9的数字,按照行有限的顺序来表礻每个格点的位置这样,只需要用模余运算就可以得到当前的列号从而判断A、B是否相斥
第二,题目要求只用一个变量我们却要存储A囷B两个子的位置信息,该怎么办呢
对于bool类型,没有办法做任何扩展了因为它只能表示true和false两个值;而byte或int类型,它们能够表达的信息则更哆事实上,对于本题来说每个子都只需要9个数字就可以表示它的全部位置。
一个8位的byte类型能够表达2^8=256个值所以用它来表示A、B的位置信息绰绰有余。因此可以把这个字节的变量(设为b)分为两部分用前面的4bit表示A的位置,用后面的4bit表示B的位置而4个bit可以表示16个数。这已经足够了
问题在于:如何使用bit级的运算将数据从这一byte变量的左边和右边分别存入和读出。
因为两个棋子都只有9种摆放的位置两个组合最哆有9*9=81种位置,那么我们拥有的变量只要可以表示这么多变量就可以了这样的话byte,char都是可以的选择
这段代码的想法就是把两个数据的存儲方式变为一个数字,这个数字是(A+1)*9+(B+1)两个加一是为了让最小的数字比如0–9之间的数也能起到作用。因为是从零开始所以直到80就完成了对所有可能性的扫描。
其中的结果要%3是因为需要知道AB位置的行数如果行数相等就不输出,如果不相等就输出AB的值
这段代码的想法和上一個差不多,只是存储方式更加直接扫描方式也更加直接,没有异议用数组中的第一个数表示A的位置,用数组中的第二个数表示B的位置只是两个byte是两个字节,是超过字节限制(如果不考虑字节限制的话这也是一个不错的方法。)