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

【参考】

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

上一篇:HOJ 1096 Divided Product (DFS)


下一篇:四轴飞行器1.6 emwin与ucgui的移植,汉字外挂字库移植和DEMO效果对比