王不見王的問題

/*
題目說明 : 請用一個變數 ( 32 bits 以內), 來解決將棋之中"將"與"帥"不能碰面的問題(王不見王的問題) , 印出所有非"王不見王"的可能位置..
解題策略 : 把"將"."帥"這兩個棋子可以走的位置分成9宮格並且依序標上號碼 :
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
  代表王見王的可能位置[由上往下看]為 (1 , 4 , 7) Or (2 , 5 , 8) Or (3 , 6 , 9) ,
  再根據數字排列的性質可觀察出 , 1 % 3 = 1 , 4 % 3 = 1 , 7 % 3 = 1 OR 2 % 3 = 2 , 5 % 3 = 2 , 8 % 3 = 2 ...依此類推
  最後由上面的運算式可得出一個結論 , 只要"將"位置編號 % 3 == "帥"位置編號 % 3 , 就表示"將"."帥"王見王的情況發生
解題方法 : (1) 由一個struct存兩個變數 , 分別代表為 "將" . "帥"的變數 ( unsigned char = 8bits , 2個 = 16 bits ) , 再由策略所提及的邏輯就可以完成
(2) 由一個unsigned char 變數存 8個bits , 其實位置資料只要 4個bits( 0 ~ 15 )就可以儲存( 1~9 ) , 把一個unsigned char 切成一半
分別儲存"將" . "帥" 的變數值.以下為此方法的實作程式:
*/
#include "stdio.h"  //引用標準輸出輸入的函式庫裡面有printf() . scanf() 之類的副程式可以達到輸入/出的目的
#include "stdlib.h"  //引用標準函式庫,裡面有system()這個可以直接呼叫系統的命令提示自元的函式
int main() {
unsigned char a = 0x00 ;  //初始化這個變數左邊4個digit表示"將"(A) 右邊4個digit表示"帥"(B)

printf("print the result: \n") ;
printf("----------------------------------\n") ;
for ( ; ((a & 0xF0 ) >> 4 ) < 9 ; a = (((a & 0xF0) >> 4) + 1 ) << 4 ) //clear the right value and increase the left value
{
printf("Pos(將) = %d\nPos(帥)  = " , ((a & 0xF0 ) >> 4 ) + 1) ;

for (  ; (a & 0x0F) < 9 ; a = a + 1  ) { //increase the right value
if ( (((a & 0xF0 ) >> 4 ) % 3)  != ((a & 0x0F) % 3) ) {
printf("%d\t" , (a & 0x0F) + 1 ) ;
}
}
printf("\n----------------------------------\n") ;
}
system("pause") ;
return 0 ;
}

後記: 這題的重點應該是如何避免造成不必要的資源浪費,也就是說我們已知這個變數值可能跑的數值範圍,如果我們給的變數大小遠遠大過於程式必要的,這樣在run程式的時候就會造成不必要的浪費.

以上面的程式例子來說,我們如果要一個unsigned char變數的左邊4個digit,可以使用 "&"這個operator,根據And ( & )的運算規則 , 任何數字 & 0都會為 0 , 如果 & 1就數字就保持不變,所以在上面的例子來講,我們可以把變數 & 0xF0 ( 2進制表示法: 11110000 ),就可以把右邊不必要的數字給遮避掉,最後再將這個數字往"右"位移4個bit ( 以0/1的資料來講 ) 即可得到想要的變數值,舉個例子來講 : 如果我們要左邊4個digit儲存2( 10進制 ) , 右邊4個digit儲存3( 10進制 ) , 那麼只要這個變數儲存 00100011 , 要取出左邊4個digit的話 , 可以把其與 0xF0 &起來 , 這樣就可以得到 00100000 , 再往右位移4個digit , 可以得到00000010 , 最後就可以得知這個數值為2 ( 10進制 ) ; 然而我們如果要取出右邊4個digit的值 3( 10進制 ) , 只要把 00100011 & 0x0F , 可得 00000011 = 3 ( 10進制 ) , 如果要把左邊那個數值 + 1存回去的話 , 就只要先取得左邊的數值(根據上述的方法) + 1 , 再往"左"位移4個digit , 最後再 | ( or ) 右邊4個digit即可達成 , 這樣做的話不僅僅可以保持右邊的變數值 , 還可以把想要的值存進去..

最後,雖然這樣可以達到節省資源的目的,可是隨這個衍生的問題就是要做這麼多operator,那倒不如直接另定另外一個新的變數值來儲存這樣會來得比較直接 , 我覺得這個就是方法取捨的問題 , 如果在可以能省則省的情況下 , 那多一點operator那倒也無訪 , 儲存起來成本節省也是相當可觀的...

題目引用於 : http://edisonx.pixnet.net/blog/post/60197123