【題目】
假設在中國象棋中只剩下將帥兩個棋子，國人都知道基本規則：將帥不能出九宮格，只能上下左右移動，不能斜向移動，同時將帥不能照面。問在這樣條件下，所有可能將帥位置。要求在代碼中只能使用一個字節存儲變量。
【分析】
3種方案：
1）位運算實現1個byte存入和讀取2個變量。
2）使用位域把幾個不同的對象用一個字節的二進制位域來表示。比如
C++ Code
1
2
3
4
5
struct
{
unsigned char a: 4;
unsigned char b: 4;
} i;
3）使用1個變量表達2重循環。後面將會重點討論該方案。（思考：如何用1個變量實現N重循環?）
【位運算】
C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/*
version: 1.0
author: hellogiser
blog: http://www.cnblogs.com/hellogiser
date: 2014/6/24
*/
#include<stdio.h>
#define HALF_BITS_LENGTH 4
#define FULLMASK 255
#define LMASK (FULLMASK << HALF_BITS_LENGTH)
#define RMASK (FULLMASK >> HALF_BITS_LENGTH)
#define RSET(b,n) (b = (b & LMASK) | (n))
#define LSET(b,n) (b = ((b & RMASK) | ((n) << HALF_BITS_LENGTH)))
#define RGET(b) (b & RMASK)
#define LGET(b) ((b & LMASK)>>HALF_BITS_LENGTH)
#define GRIDW 3
void Solution1()
{
unsigned char b;
for(LSET(b, 1); LGET(b) <= GRIDW * GRIDW; LSET(b, (LGET(b) + 1)))
{
for(RSET(b, 1); RGET(b) <= GRIDW * GRIDW; RSET(b, (RGET(b)) + 1))
{
if(LGET(b) % GRIDW != RGET(b) % GRIDW)
{
printf("A=%d,B=%d\n", LGET(b), RGET(b));
}
}
}
}
【位域】
C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
version: 1.0
author: hellogiser
blog: http://www.cnblogs.com/hellogiser
date: 2014/6/24
*/
struct
{
unsigned char a: 4;
unsigned char b: 4;
} i;
void Solution2()
{
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) // column not equal
printf("%d,%d\n", i.a, i.b);
}
【單個變量】
C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
version: 1.0
author: hellogiser
blog: http://www.cnblogs.com/hellogiser
date: 2014/6/24
*/
void Solution3()
{
unsigned char i = 81;
while(i--)
{
// i = 9*a+b, a = i/9, b = i%9
if (i / 9 % 3 == i % 9 % 3)
continue;
printf("%d,%d\n", i / 9, i % 9);
}
}
“將”和“帥”各在自己的3*3的格子間裡面走動，我們共需要驗證9*9=81種位置關系，這也是i=81的由來。此外我們要明白 i/9和i%9的含義。我們知道，整數i可以由部兩分組成，即i=(i/9)*9+i%9 。我們注意到，在i從81到0變化的過程中，i%9的變化相當於內層循環，i/9的變化相對於外層循環。
【擴展】
如何用1個變量實現N重循環？
先看個簡單例子，1個變量實現2重循環。
C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
version: 1.0
author: hellogiser
blog: http://www.cnblogs.com/hellogiser
date: 2014/6/24
*/
void LoopWith2Variables()
{
unsigned char i, j;
for(i = 0; i < 5; i++)
for(j = 0; j < 4; j++)
printf("%d,%d", i, j);
}
void LoopWith1Variable()
{
unsigned char val = 4 * 5;
while(val--)
{
printf("%d,%d", (val / 4) % 5, val % 4);
}
}
【總結】
對於 a*b = i ，我們可以用如下公式展開：
loop1=i%b;
loop2=(i/b)%a
其中loop1是內層循環，loop2是外層循環。
由此可以得出N重時的公式,假設 an * a(n-1) * ....... * a3 * a2 * a1 = N
loop1=N%a1
loop2=(N/(a1))%a2
loop3=(N/(a1a2))%a3
.....
loopN=(N/(a1a2.....a(n-1)))%an
【參考】
http://blog.csdn.net/kabini/article/details/2256421
http://blog.csdn.net/silenceburn/article/details/6133222
http://blog.csdn.net/zhongkeli/article/details/8779168
http://www.cnblogs.com/python27/archive/2012/04/10/2441114.html
【本文鏈接】
http://www.cnblogs.com/hellogiser/p/chinese-chess.html
