プログラミングの美読書ノート1.2——中国将棋将帥問題
5510 ワード
http://blog.csdn.net/pipisorry/article/details/36380669
質問:中国将棋を打ったことがある友达はすべて知っていて、双方の“将”と“帥”は遠く離れていて、しかもそれらは顔を合わせることができません.将棋の残局では、多くの達人がこのルールを利用してすばらしい殺技を出すことができる.将棋盤には「将」と「帥」の二子(図1-3に示す)しかないと仮定する(以下の説明の便宜上、Aで「将」、Bで「帥」を表すことを約束する):
A、B二子は味方3に制限されている×3の格子の中で運動します.例えば、上記のような表では、Aは正方形{d 10、 f10, d8, f 8}に囲まれ、Bは正方形{d 3, f3, d1, f 1}包囲.各ステップでは、A、Bはそれぞれ横方向または縦方向に1マス移動できますが、対角線に沿って移動することはできません.また、AはBに直面することができず、すなわち、AとBが同じ長手方向直線上にあることができない(例えば、Aがd 10の位置にあると、Bはd 1、d 2、d 3にあることができない).
A、Bのすべての合法的な位置を出力するプログラムを書いてください.コードには1つの変数しか使用できないことが要求されます.
分析:
タイトルでは、イケメンと顔を合わせるかどうかを判断するだけで、イケメンとはそれぞれ9つの位置でしか移動できないので、1~9という9つの数字を形式化するだけです.
この問題の解法1における従来の解決手段,すなわちビット操作である.一般に、マクロで定義したり、列挙タイプで定義したりする一連のマスク(masks)を定義します.
参照コード:
説明:
1.chessTest 1を見ると、printfだけで正解を出力でき、ABが異なる列であれば3*3*2*3=54の場合
2.chessTest 2は考えにくいので、AB番号が同じ(if判定文中)でABが異なる列であることに注意して出力すればよい
質問:中国将棋を打ったことがある友达はすべて知っていて、双方の“将”と“帥”は遠く離れていて、しかもそれらは顔を合わせることができません.将棋の残局では、多くの達人がこのルールを利用してすばらしい殺技を出すことができる.将棋盤には「将」と「帥」の二子(図1-3に示す)しかないと仮定する(以下の説明の便宜上、Aで「将」、Bで「帥」を表すことを約束する):
A、B二子は味方3に制限されている×3の格子の中で運動します.例えば、上記のような表では、Aは正方形{d 10、 f10, d8, f 8}に囲まれ、Bは正方形{d 3, f3, d1, f 1}包囲.各ステップでは、A、Bはそれぞれ横方向または縦方向に1マス移動できますが、対角線に沿って移動することはできません.また、AはBに直面することができず、すなわち、AとBが同じ長手方向直線上にあることができない(例えば、Aがd 10の位置にあると、Bはd 1、d 2、d 3にあることができない).
A、Bのすべての合法的な位置を出力するプログラムを書いてください.コードには1つの変数しか使用できないことが要求されます.
分析:
タイトルでは、イケメンと顔を合わせるかどうかを判断するだけで、イケメンとはそれぞれ9つの位置でしか移動できないので、1~9という9つの数字を形式化するだけです.
この問題の解法1における従来の解決手段,すなわちビット操作である.一般に、マクロで定義したり、列挙タイプで定義したりする一連のマスク(masks)を定義します.
参照コード:
/****************************************************************************/
/* 1.2 2014-7-1 */
/****************************************************************************/
#include <stdio.h>
typedef struct bitField{
unsigned char a:4;
unsigned char b:4;
}bit;
void chessTest1(){
char column = 1;
for(; column <=3 ; column ++){ //A
for(; column <= 9; column += 3){ //A( B)
printf("A = %d, B = %d
", column, column%3 + 1);
printf("A = %d, B = %d
", column, column%3 + 1 + 3);
printf("A = %d, B = %d
", column, column%3 + 1 + 6);
printf("A = %d, B = %d
", column, (column + 1)%3 + 1);
printf("A = %d, B = %d
", column, (column + 1)%3 + 1 + 3);
printf("A = %d, B = %d
", column, (column + 1)%3 + 1 + 6);
}
column -= 9;
}
}
void chessTest2(){
char i = 81;
while(i--){
if(i/9 % 3 == i % 9 %3) //i/9(A -1[0~8]) % 3(A ); i%9(B -1[8~0]) %3
continue; // continue
printf("A = %d, B = %d
",i/9 + 1, i%9 + 1);
}
}
void chessTest3(){
bit i;
for(i.a = 1; i.a <= 9; i.a++)
for(i.b = 1; i.b <= 9; i.b ++)
if(i.a%3 != i.b%3) //A B
printf("A = %d, B = %d
", i.a, i.b);
}
void main(){<span style="font-family: Arial, Helvetica, sans-serif;"> chessTest3();</span><span style="font-family: Arial, Helvetica, sans-serif;">}</span>
説明:
1.chessTest 1を見ると、printfだけで正解を出力でき、ABが異なる列であれば3*3*2*3=54の場合
2.chessTest 2は考えにくいので、AB番号が同じ(if判定文中)でABが異なる列であることに注意して出力すればよい
<span style="font-size:14px;">3.chessTest3 , :http://blog.csdn.net/pipisorry/article/details/36220851</span>
位域的概念《C程序设计语言》用了一页纸介绍,说明了应用场合主要是为了节省空间或直接访问位,应用场景如编译器的符号表以及一些硬件的驱动程序。网络开发、信息编码压缩解压缩、位图等方面可能还会用到,其余的场景多半会去讨论怎么节省时间开销,让程序运行的更加高效。此外还有一种位读写方式是STL库中提供的泛型类bitset,它支持对位赋值的操作,也支持整体的位运算,最方便的是输入输出流被重载,很容易查看对应的位是否被置正确。相比于位域,bitset不能支持局部几个比特位的访问,而这正是位域的优势。不过对将与帅的问题,要求一个字节,而bitset基本的对齐是4个字节,所以可能不符合题目要求,不过对于其它的位操作场合却是一种很好的选择。
位域的概念《C程序设计语言》用了一页纸介绍,说明了应用场合主要是为了节省空间或直接访问位,应用场景如编译器的符号表以及一些硬件的驱动程序。我想做网络开发、信息编码压缩解压缩、位图等方面可能还会用到,其余的场景多半会去讨论怎么节省时间开销,让程序运行的更加高效。另解:要将一个变量i拆成两个,可以根据它的二进制表示分别取出连续几位,比如第0-3位和第4-7位,读变量时,取出变量i相应的几位,存变量时,再更新变量i的对应几位。另外,利用位置的对称性,可以一次输出两个,减少循环次数。
下面的代码和解法一类似,但是一次输出两个,减少了循环次数,并且没有用到除法(不考虑C++ IO效率的影响)
// b i 4-7 , 1, 8。 // a i 0-3 , b+1, 9。 for (unsigned i = 0x10; i < 0x90; i += 0x10) for (i= (i & 0xF0) | (i >> 4); (++i & 0xF) < 10; ) if (((i & 0xF) - (i >> 4)) != 3 && ((i & 0xF) - (i >> 4)) != 6) std::cout << "A=" << (i >> 4) << ", B="<< (i & 0xF) << "
" << "A=" << (i & 0xF) << ", B="<< (i >> 4) << "
";
from:
http://blog.csdn.net/pipisorry/article/details/36380669
ref:http://www.cnblogs.com/flyinghearts/archive/2010/09/08/1821042.html