微软MSRA电话面试（第二天）
今天中午就接到MSRA的第二个电话面试，有点奇怪，因为前面几个电话都是晚上，我一直以为微软的前辈们都按照美国时间工作...结果今天在我午睡正香的时候打来了电话，开始问了几个项目的事情，我晕晕乎乎答得语无伦次，我明白他想知道关于开发中遇到的难题，然后我是怎么克服的，无奈实在不清醒...都想不起来了，结果我想他没有得到太多想得到的吧。之后，给我出了一个简单的算法题目要求写出来，听工程院实习的同学讲，当面面试的时候都会直接写在白板上，然后由微软的人录入编译的，这样放给我自己做，我觉得还算是降低难度了吧。
题目是这样的：有一个矩阵，每个元素是一个数，要求，从左上角出发到达右下角，每次只能向右或向下，要求全路线经过的元素和最小，求出路径及这个和的值。要求分别用递归和非递归方法实现之。
结果图：
!
!!
!
我花了一下午，写出了这个程序，幸运的是，两种方法的结果竟然相同...
哈哈~~玩笑话，放出代码：
using System; using System.Collections.Generic; using System.Text;
namespace Matrix { class Program { /// /// 矩阵元素的最大值，用于生成随机矩阵 /// private static int MAX_ELEMENT = 10; /// /// 矩阵的高度 /// private static int MATRIX_X = 4; /// /// 矩阵的宽度 /// private static int MATRIX_Y = 15;
/// 主函数
/// 命令行参数
static void Main(string[] args)
{
//初始化一个目标矩阵
int[,] matrix = new int;
//初始化一个方向矩阵
string[,] direction = new string;
//随机生成目标矩阵的元素
Generate(ref matrix, MATRIX_X, MATRIX_Y);
Console.WriteLine("Target Matrix is:");
//打印矩阵
PrintMatrix(matrix, MATRIX_X, MATRIX_Y);
//递归法
Console.Write("\
Method No.1 Result
MinCost=" + Step(direction, matrix, MATRIX_X, MATRIX_Y, MATRIX_X - 1, MATRIX_Y - 1));
//打印结果
PrintDirection(direction, MATRIX_X, MATRIX_Y);
//清空方向矩阵
direction = new string;
//非递归法
PrintMinCostRoute(direction, matrix, MATRIX_X, MATRIX_Y);
}
/// 随机生成目标矩阵
/// 目标矩阵的引用
/// 矩阵宽度
///矩阵高度
static private void Generate(ref int[,] matrix, int x, int y)
{
//如果未初始化，先初始化之
if (matrix == null)
{
matrix = new int;
}
//随机生成元素
Random random = new Random();
for (int i = 0; i < x; i++)
{
for (int j = 0; j < y; j++)
{
matrix = random.Next(MAX_ELEMENT - 1) + 1;
}
}
}
/// 非递归寻找最小值及路径
///路径矩阵
///目标矩阵
///矩阵宽度
///矩阵高度
static private void PrintMinCostRoute(string[,] direction, int[,] matrix, int x, int y)
{
//动态规划备忘录矩阵
int[,] cost = new int;
//初始化各节点为整型变量最大值
for (int i = 0; i < x; i++)
{
for (int j = 0; j < y; j++)
{
cost = int.MaxValue;
}
}
//从左上角逐次扩大矩阵
for (int i = 0; i < (x >= y ? x : y); i++)
{
//左上角
if (i == 0)
{
//就是本身
direction = "S";
cost = matrix;
}
else
{
//顺次检查当前方阵周围的元素
for (int k = 0; k < i + 1; k++)
{
//如果范围合法
if (i < x && k < y)
{
//检查比较当前的最小值和从上面过来的值
if (cost >= (cost + matrix))
{
//上面更小则更新
cost = cost + matrix;
direction = "U";
}
if (k >= 1)
{
//检查比较当前的最小值和从左面过来的值
if (cost >= (cost + matrix))
{
//左面更小则更新
cost = cost + matrix;
direction = "L";
}
}
}
//如果范围合法
if (i < y && k < x)
{
//检查比较当前的最小值和从上面过来的值
if (cost >= (cost + matrix))
{
//上面更小则更新
cost = cost + matrix;
direction = "L";
}
if (k >= 1)
{
//检查比较当前的最小值和从上面过来的值
if (cost >= (cost + matrix))
{
//左面更小则更新
cost = cost + matrix;
direction = "U";
}
}
}
}
}
}
Console.Write("\
Method No.2 Result
MinCost=" + cost);
PrintDirection(direction, x, y);
}
/// 一步递归求某位置的最小值
///路径矩阵
///目标矩阵
///矩阵宽度
///矩阵高度
///位置x坐标
///位置y坐标
/// <returns>这个位置的最小值</returns>
static private int Step(string[,] direction, int[,] matrix, int x, int y, int pos_x, int pos_y)
{
//Debug用
//Console.WriteLine("pos_x=" + pos_x + ",pos_y=" + pos_y);
//第一行的元素
if (pos_x == 0)
{
//第一个元素，递归结束，返回本身的值
if (pos_y == 0)
{
//特殊位置，路径指向Self="S"
direction = "S";
//返回本身的值
return matrix;
}
//第一行非第一个，必然从左边走过来
else
{
//路径指向Left="L"
direction = "L";
//左边一个的最优值加上本身得到最优值
return Step(direction, matrix, x, y, pos_x, pos_y - 1) + matrix;
}
}
//第一列的元素，必然从上边走过来
if (pos_y == 0)
{
//路径指向Up="U"
direction = "U";
//上边一个的最优值加上本身得到最优值
return Step(direction, matrix, x, y, pos_x - 1, pos_y) + matrix;
}
//避免重复计算，先取到上面一个和左边一个的最优值
int up = Step(direction, matrix, x, y, pos_x - 1, pos_y);
int left = Step(direction, matrix, x, y, pos_x, pos_y - 1);
//如果从上面走合算
if (up <= left)
{
//路径指向Up="U"
direction = "U";
//上边一个的最优值加上本身得到最优值
return up + matrix;
}
//如果从左面走合算
else
{
//路径指向Left="L"
direction = "L";
//左边一个的最优值加上本身得到最优值
return left + matrix;
}
}
/// 打印矩阵
///
///矩阵宽度///
///矩阵高度
static private void PrintMatrix(int[,] matrix, int x, int y)
{
for (int i = 0; i < x; i++)
{
for (int j = 0; j < y; j++)
{
Console.Write(matrix.ToString() + " ");
}
Console.Write("\
");
}
}
/// 打印所走的路径矩阵及走法
///路径矩阵
///路径矩阵宽度
///路径矩阵高度
static private void PrintDirection(string[,] matrix, int x, int y)
{
//打印路径矩阵
Console.WriteLine("\
The Direction Matrix:");
for (int i = 0; i < x; i++)
{
for (int j = 0; j < y; j++)
{
Console.Write(matrix + " ");
}
Console.Write("
");
}
//打印走法
Console.Write("The Route is:");
//走法的逆序存放数组
string[] Reverse = new string;
int pos_x = x - 1;
int pos_y = y - 1;
//从终点开始向路径矩阵指示的方向回溯走法
for (int i = 0; i < (x + y - 2); i++)
{
//从左边来的
if (matrix.Equals("L"))
{
pos_y--;
Reverse = "right";
}
//从上边来的
else
{
pos_x--;
Reverse = "down";
}
}
//倒序打印走法的逆序存放数组，得到真正的从起点出发的走法
for (int i = 0; i < (x + y - 2); i++)
{
//倒序打印
Console.Write(Reverse[(x + y - 2) - i - 1]);
if (i < (x + y - 3))
{
//不是最后一个的时候打一个分隔号
Console.Write(",");
}
}
}
}}