1.2 中国象棋将帅问题进一步讨论与扩展：如何用1个变量实现N重循环?[chinese chess]

【题目】

假设在中国象棋中只剩下将帅两个棋子，国人都知道基本规则：将帅不能出九宫格，只能上下左右移动，不能斜向移动，同时将帅不能照面。问在这样条件下，所有可能将帅位置。要求在代码中只能使用一个字节存储变量。

【分析】

3种方案：

1）位运算实现1个byte存入和读取2个变量。

2）使用位域把几个不同的对象用一个字节的二进制位域来表示。比如

C++ Code

1
2
3
4
5

struct
{
;
;
} 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 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)

void Solution1()
{
    unsigned char b;
    )))
    {
        ))
        {
            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
{
    ;
    ;
} i;

void Solution2()
{
    ; i.a++)
        ; i.b++)
            ) // 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()
{
    ;
    while(i--)
    {
        // i = 9*a+b, a = i/9, b = i%9
)
            continue;
        printf();
    }
}

“将”和“帅”各在自己的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;
    ; i++)
        ; j++)
            printf("%d,%d", i, j);
}

void LoopWith1Variable()
{
    ;
    while(val--)
    {
        printf();
    }
}

【总结】

对于 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