Creative Commons License
本Blog采用 知识共享署名-非商业性使用-禁止演绎 3.0 Unported许可协议 进行许可。 —— Fox <游戏人生>

游戏人生

游戏人生 != ( 人生 == 游戏 )
站点迁移至:http://www.yulefox.com。请订阅本博的朋友将RSS修改为http://feeds.feedburner.com/yulefox
posts - 62, comments - 508, trackbacks - 0, articles - 7

编程之美:中国象棋将帅问题

Posted on 2008-04-18 00:26 Fox 阅读(3932) 评论(8)  编辑 收藏 引用 所属分类: T技术碎语

Author: Fox

晚上没有加班,打游戏打到9点过,后面就又看了一道《编程之美》的题目《中国象棋将帅问题》。

题目:下过中国象棋的朋友都知道,双方的“将”和“帅”相隔遥远,并且它们不能照面。在象棋残局中,许多高手能利用这一规则走出精妙的杀招。假设棋盘上只有“将”和“帅”二子(如图1-3所示)(为了下面叙述方便,我们约定用A表示“将”,B表示“帅”):

1-3副本

AB二子被限制在己方3×3的格子里运动。例如,在如上的表格里,A被正方形{d10, f10, d8, f8}包围,而B被正方形{d3, f3, d1, f1}包围。每一步,AB分别可以横向或纵向移动一格,但不能沿对角线移动。另外,A不能面对B,也就是说,AB不能处于同一纵向直线上(比如Ad10的位置,那么B就不能在d1d2以及d3)。

请写出一个程序,输出AB所有合法位置。要求在代码中只能使用一个变量。

在纸上画了半天,Soft从台湾给带的长寿都让我抽完了,总算对得起这会儿工夫……

我的思路大致如下:

1) 只能使用一个变量nNum ==> 只能使用一个循环,nNum只能用来表示A、B位置的组合,nNum最大为9×9-1=80;

2) 如何用nNum表示一个A、B位置的组合?

下图表示A(红色)B(蓝色)所在位置:

6 7 8
3 4 5
0 1 2
6 7 8
3 4 5
0 1 2

nNum%9表示A的位置nNum/9表示B的位置,如nNum==15,A==6B==1

3) 如何确定A、B位置的合法性?

规则都指定了,合法性的确定也就很简单了:A%3 != B%3。

OK,剩下的输出就很简单了,为了好看一点,这里希望直接按题目给的图表示出A、B的位置,如:“A:d10, B:e3”,还有颜色:D。

A的行号:A/3+8;

A的列号:A%3+d;

B的行号:B/3+1;

B的列号:B%3+d;

代码如下(注释掉的部分只是为了输出更“漂亮”一点):

 

 1 #include <stdio.h>
 2 //#include <windows.h>
 3 
 4 //HANDLE hStdout;
 5 //CONSOLE_SCREEN_BUFFER_INFO csbiInfo;
 6 //WORD wOldColorAttrs;
 7 
 8 int _tmain(int argc, _TCHAR* argv[])
 9 {
10     //hStdout = GetStdHandle(STD_OUTPUT_HANDLE);
11     //GetConsoleScreenBufferInfo(hStdout, &csbiInfo);
12     //wOldColorAttrs = csbiInfo.wAttributes;
13 
14     int nNum = 81;    // nNum表示所有位置(含非法),故nNum = 3 * 3 * 3 * 3
15     while( nNum-- )
16     {
17         if( nNum%9%3 != nNum/9%3 )
18         {
19             //SetConsoleTextAttribute(hStdout, FOREGROUND_RED | FOREGROUND_INTENSITY);
20             printf("A:%x%02d ", nNum%9%3+0xd, nNum%9/3+8);
21             //SetConsoleTextAttribute(hStdout, FOREGROUND_BLUE | FOREGROUND_INTENSITY);
22             printf("B:%x%02d  ", nNum/9%3+0xd, nNum/9/3+1);
23         }
24         if!(nNum%9) )
25             printf("\n");
26     };
27     printf("\n");
28     //SetConsoleTextAttribute(hStdout, wOldColorAttrs);
29     return 0;
30 }

输出:

点击查看更清晰原图:D

PS: 刚写完,没有来得及总结更多,急着向LP炫耀。但上面的思路应该比较清晰了,也不管书上的答案了,反正我感觉我这点代码效率应该也不会低到哪儿吧:-)?

Feedback

# re: 编程之美:中国象棋将帅问题[未登录]  回复  更多评论   

2008-04-18 10:52 by cppexplore
最简单的方法是先写个效率低下的程序,把所有结果打印出来。
然后写个程序,把结果存在一个表里,用查表法,扫描整个表,挨个打印出来。

当然也可以一个变量不用,直接把上个程序的输入结果,打印下。不过这样就没意义了。实际的应用一定是需要其中的结果,而查表是最实用的。

# re: 编程之美:中国象棋将帅问题  回复  更多评论   

2008-04-18 11:01 by Fox
我还是中规中矩的按照题目的要求去考虑如何只用一个变量、一个循环实现。写完了,贴上来才看到书上的几种方案,本来想写N>=3的一个统一算法,后面考虑了一下,有点麻烦,也未必能实现,就算了。

另一个就是本来想加一个宏的实现,效率又高,而且一个变量都不用。就一个OUTPUT。

#define OUTPUT CALC(3)
#define CALC(N) ....
#define ...

本质上还不如上面的代码。后面觉得有点偷奸耍滑的味道,算了。

楼上说的方法也是些“奇技淫巧”了,后来看了下书上的,居然还有用结构体变量的,我心想:成员变量就不是变量了?

# re: 编程之美:中国象棋将帅问题  回复  更多评论   

2008-04-18 11:05 by Xin
好像还不太合题意哪,
题目不是要输出A、B所有合法位置。
当A:e10时 B的位置有好几个的 B:d1 B:d2 B:d3 B:f1 B:f2 B:f3
这六个位置。

# re: 编程之美:中国象棋将帅问题  回复  更多评论   

2008-04-18 11:15 by Fox
@Xin
输出的都有啊:-),总共81-3×3×3=54种合法位置。
给的图也很清楚啊,看不清的话,直接查看原图吧:D。

# re: 编程之美:中国象棋将帅问题[未登录]  回复  更多评论   

2008-04-18 11:48 by cppexplore
@Fox
呵呵,不同的经验能得出不同的看法。
我觉得这种题目,查表法不仅不是“奇技淫巧”,反而是最完美的方法。

就像经常见的面试题:给定一个unsigned char类型变量,输出按位反转后的值,比如0x2A=00101010 反转后就是01010100=0x54

猜猜这个题目的标准答案是什么啊,呵呵,查表法。如果反对,请给出一个比这个还高效的算法。

# re: 编程之美:中国象棋将帅问题  回复  更多评论   

2008-04-19 15:05 by Fox
@cppexplore
你看看这个吧:http://book.csdn.net/bookfiles/656/10065620784.shtml
看看“标准”答案里有没有:D

# re: 编程之美:中国象棋将帅问题[未登录]  回复  更多评论   

2008-04-19 17:55 by CppExplore
那里没有我心目中的标准答案 遗憾啊 呵呵

# re: 编程之美:中国象棋将帅问题  回复  更多评论   

2008-07-02 13:48 by holly
博文视点为《编程之美》建立官方qq读者讨论群,号码是64955253,欢迎读者在群内进行分享、交流、讨论。

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理