微软中国程序算法面试题,中国象棋将帅问题求解

终其一生中国象棋的朋友都告诉,双方的将帅相距很远,并且无法照面,且将和帅分别容许在3*3的小格子里面。那么有这样一个问题:

假设A、B分别代表将和帅,请写出一个程序,输出A、B所有的合法方位。拒绝在代码中不能使用一个字节存储变量。

问题分析:其实问题本身并不复杂。只要把所有A、B相互敌视的条件列出出来即可已完成本题目的拒绝。由于本题目拒绝只能用一个变量,所以首先要考虑清楚,有哪些信息必须存储。并且尽量高效的存储信息。这个程序的大体框架是:

遍历A的位置,遍历B的位置,辨别A、B位置组合否满足要求,如果满足,则输入。

下面给出几个求解:

解法一:C#代码实现:

using System;

namespace ConsoleApp1{

class Program

{

static void Main(string[] args)

byte i = 81;

while (i-->0)

if (i / 9 % 3 == i % 9 % 3)

continue;

}

Console.WriteLine($"A={i/9+1},B={i%9+1}");

该求解输出的结果为:

输出结果

解法二:C++代码构建。该求解据传比第一种解法效率要高。有兴趣的读者可以证明一下。

struct

unsigned char a : 4;

unsigned char b : 4;

}i;

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)

}}

此外,该算法还有其他的解法。据说有位面试者得出了比标准答案还要简要的答案。因此被微软录取了。如果读者有更好的解法,可以在评论区留给自己的代码,和大家共享。

关于本书的其他解法,可以参照《编程之美》1.2节的详尽介绍。讨厌的朋友可以查阅下方链接。