编程之美-将帅问题

基本是基于编程之美的将帅问题原本以为这是个降低循环嵌套的游戏，比如以前做过的一个单循环打印菱形的题目，但后来发现还是有很多不同的（也有很多相同的地方，比如书上给的那个令很多人称奇的算法其实和单循环打印菱形的其中一个解法是相同的），值得玩味，学习

题目：根据中国象棋的基本原则，在只有双的将帅棋盘上，找出所有双方可以落子的位置（将帅不能碰面），但只能使用一个变量。：

1、基本思想是肯定是遍历了，难点在于单变量咋遍历二维循环呢，这就和打印菱形一样了，单变量是肯定可以遍历单层循环的，那么我们把二层循环降为单层循环就可以了

解法一：

//

#include "stdafx.h"
#include "stdio.h"
#include "windows.h"

int _tmain(int argc, _TCHAR* argv[])
{
  int var = 81;
   while( var-- )
   {
  if( var / 9 % 3 == var % 9 % 3 )//发生冲突 
   continue;
  else
   printf("将:(%d,%d) 帅:(%d,%d)\n",var/9/3+1,var/9%3+1,var%9/3+1,var%9%3+1);
   }
   system("pause");
 return 0;
}

2、然后是书上的第一个解法，将一个Byte变量前四位当做9个数，后四位当做9个数，其实我感觉，我或我这个水平的人（算是个大学的ACM菜鸟？），应该首先想到的是第一种解法（降循环）吧，看来出题老师的思维高屋建瓴迥异常人啊

解法二：

#include <stdio.h>
#include "windows.h"
void lset(unsigned int& c,int n) {c=(c & 0x0F) | (n << 4);}
void rset(unsigned int& c,int n) {c=(c & 0xF0) | n;}
int lget(unsigned int c) {return (c >> 4);}
int rget(unsigned int c) {return (c & 0x0F);}
int main()
{
    unsigned int c;
    for(lset(c,1);lget(c)<=9;lset(c,(lget(c)+1)))
        for(rset(c,1);rget(c)<=9;rset(c,(rget(c)+1)))
            if(lget(c)%3 != rget(c)%3)
                printf("将:(%d,%d) 帅:(%d,%d)\n",(lget(c)+2)/3,(lget(c)-1)%3+1,(rget(c)+2)/3,(rget(c)-1)%3+1);
    system("pause");
    return 0;
}

3、方法三是可以用一个double的整数部分表示“将”的位置，用其小数部分表示“帅”的位置，与方法二有异曲同工之妙，在一个博客上看到了这种解法不过那个博客上的解法有错误，因为这里有一个小陷阱，就是虽然从1.1到9.9，整数表示“将”，小数表示“帅”，看起来很完美，但实际上，整数部分是一个9层的循环，而小数部分却是一个10层的循环，这与我们期望是不符的，所以改进如下

解法三：

#include <iostream>
using namespace std;
#define GETA(i) (int)(i)
#define GETB(i) (int)((i-GETA(i))*10)

int main(void)
{
    for(double j = 1.1;j<10.0;j+=0.1)
    {
        if(GETB(j)==0)
            j+=0.1;
        if((GETB(j)%3)!=(GETA(j)%3))
            cout << "A=" << GETA(j) << "," << "B=" <<GETB(j)<<endl;
    }
    return 0;
}

4、当然，打表更简单

解法四：

#include <iostream>
using namespace std;
#define a(a,i) (a+i)%9+1
int main(void)
{
    for(int i=0;i<9;++i)
    {
        cout<<i+1<<","<<a(i,1)<<endl;
        cout<<i+1<<","<<a(i,2)<<endl;
        cout<<i+1<<","<<a(i,4)<<endl;
        cout<<i+1<<","<<a(i,5)<<endl;
        cout<<i+1<<","<<a(i,7)<<endl;
        cout<<i+1<<","<<a(i,8)<<endl;
    }
    return 0;
}

5、原书最后给出了一个应用位域的解决方法，虽然很多人认为（包括我）这种解法违背了题目的趣味性（打表的方法其实也是违背了的），但是从另一个角度讲，按这个题目的规则，这种应用位域的解法无疑是符合规则中最优的（这就好比你有打火机来打火了，你为什么还要钻木取火呢？即使钻木取火远比拿个打火机打火更有技术含量），而且还要反省，自己之所以没有用这种方法，其实很大程度上也是因为自己的知识储备还不足以想出用位域的方法来解决这个问题吧，反思，反思，学习，学习

解法五：

#include<stdio.h>
 struct {
     unsigned char a:4;
     unsigned char b:4;
 } i;
 int main()
 {
     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)
                 printf("A=%d,B=%d\n",i.a,i.b);
     return 0;
 }

参考

http://blog.csdn.net/gnuhpc/article/details/6284125
http://blog.csdn.net/silenceburn/article/details/6133222
http://blog.csdn.net/kabini/article/details/2256421
http://www.cppblog.com/Fox/archive/2008/04/18/chinese_chess_one_param.html
http://my.oschina.net/cashlang/blog/57813