微软MSRA电话面试(第二天)

今天中午就接到MSRA的第二个电话面试,有点奇怪,因为前面几个电话都是晚上,我一直以为微软的前辈们都按照美国时间工作…结果今天在我午睡正香的时候打来了电话,开始问了几个项目的事情,我晕晕乎乎答得语无伦次,我明白他想知道关于开发中遇到的难题,然后我是怎么克服的,无奈实在不清醒…都想不起来了,结果我想他没有得到太多想得到的吧。之后,给我出了一个简单的算法题目要求写出来,听工程院实习的同学讲,当面面试的时候都会直接写在白板上,然后由微软的人录入编译的,这样放给我自己做,我觉得还算是降低难度了吧。

题目是这样的:有一个矩阵,每个元素是一个数,要求,从左上角出发到达右下角,每次只能向右或向下,要求全路线经过的元素和最小,求出路径及这个和的值。要求分别用递归和非递归方法实现之。
结果图:
matrix1.jpg
我花了一下午,写出了这个程序,幸运的是,两种方法的结果竟然相同…
哈哈~~玩笑话,放出代码:

[code=’c#’]
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[MATRIX_X, MATRIX_Y];
//初始化一个方向矩阵
string[,] direction = new string[MATRIX_X, MATRIX_Y];
//随机生成目标矩阵的元素
Generate(ref matrix, MATRIX_X, MATRIX_Y);
Console.WriteLine(“Target Matrix is:”);
//打印矩阵
PrintMatrix(matrix, MATRIX_X, MATRIX_Y);

//递归法
Console.Write(“\r\nMethod No.1 Result\r\nMinCost=” + Step(direction, matrix, MATRIX_X, MATRIX_Y, MATRIX_X – 1, MATRIX_Y – 1));
//打印结果
PrintDirection(direction, MATRIX_X, MATRIX_Y);

//清空方向矩阵
direction = new string[MATRIX_X, MATRIX_Y];
//非递归法
PrintMinCostRoute(direction, matrix, MATRIX_X, MATRIX_Y);
}

///

随机生成目标矩阵

/// 目标矩阵的引用 /// 矩阵宽度 ///矩阵高度 static private void Generate(ref int[,] matrix, int x, int y)
{
//如果未初始化,先初始化之
if (matrix == null)
{
matrix = new int[x, y];
}
//随机生成元素
Random random = new Random();
for (int i = 0; i < x; i++) { for (int j = 0; j < y; j++) { matrix[i, j] = random.Next(MAX_ELEMENT - 1) + 1; } } } ///

非递归寻找最小值及路径

///路径矩阵 ///目标矩阵 ///矩阵宽度 ///矩阵高度 static private void PrintMinCostRoute(string[,] direction, int[,] matrix, int x, int y)
{
//动态规划备忘录矩阵
int[,] cost = new int[x, y];
//初始化各节点为整型变量最大值
for (int i = 0; i < x; i++) { for (int j = 0; j < y; j++) { cost[i, j] = int.MaxValue; } } //从左上角逐次扩大矩阵 for (int i = 0; i < (x >= y ? x : y); i++)
{
//左上角
if (i == 0)
{
//就是本身
direction[0, 0] = “S”;
cost[0, 0] = matrix[0, 0];
}
else
{
//顺次检查当前方阵周围的元素
for (int k = 0; k < i + 1; k++) { //如果范围合法 if (i < x && k < y) { //检查比较当前的最小值和从上面过来的值 if (cost[i, k] >= (cost[i – 1, k] + matrix[i, k]))
{
//上面更小则更新
cost[i, k] = cost[i – 1, k] + matrix[i, k];
direction[i, k] = “U”;
}
if (k >= 1)
{
//检查比较当前的最小值和从左面过来的值
if (cost[i, k] >= (cost[i, k – 1] + matrix[i, k]))
{
//左面更小则更新
cost[i, k] = cost[i, k – 1] + matrix[i, k];
direction[i, k] = “L”;
}
}
}
//如果范围合法
if (i < y && k < x) { //检查比较当前的最小值和从上面过来的值 if (cost[k, i] >= (cost[k, i – 1] + matrix[k, i]))
{
//上面更小则更新
cost[k, i] = cost[k, i – 1] + matrix[k, i];
direction[k, i] = “L”;
}
if (k >= 1)
{
//检查比较当前的最小值和从上面过来的值
if (cost[k, i] >= (cost[k – 1, i] + matrix[k, i]))
{
//左面更小则更新
cost[k, i] = cost[k – 1, i] + matrix[k, i];
direction[k, i] = “U”;
}
}
}
}
}
}
Console.Write(“\r\n\r\nMethod No.2 Result\r\nMinCost=” + cost[x – 1, y – 1]);
PrintDirection(direction, x, y);
}

///

一步递归求某位置的最小值

///路径矩阵 ///目标矩阵 ///矩阵宽度 ///矩阵高度 ///位置x坐标 ///位置y坐标 /// 这个位置的最小值
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[pos_x, pos_y] = “S”;
//返回本身的值
return matrix[pos_x, pos_y];
}
//第一行非第一个,必然从左边走过来
else
{
//路径指向Left=”L”
direction[pos_x, pos_y] = “L”;
//左边一个的最优值加上本身得到最优值
return Step(direction, matrix, x, y, pos_x, pos_y – 1) + matrix[pos_x, pos_y];
}
}
//第一列的元素,必然从上边走过来
if (pos_y == 0)
{
//路径指向Up=”U”
direction[pos_x, pos_y] = “U”;
//上边一个的最优值加上本身得到最优值
return Step(direction, matrix, x, y, pos_x – 1, pos_y) + matrix[pos_x, pos_y];
}
//避免重复计算,先取到上面一个和左边一个的最优值
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[pos_x, pos_y] = "U"; //上边一个的最优值加上本身得到最优值 return up + matrix[pos_x, pos_y]; } //如果从左面走合算 else { //路径指向Left="L" direction[pos_x, pos_y] = "L"; //左边一个的最优值加上本身得到最优值 return left + matrix[pos_x, pos_y]; } } ///

打印矩阵

/// ///矩阵宽度///
///矩阵高度
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[i, j].ToString() + " "); } Console.Write("\r\n"); } } ///

打印所走的路径矩阵及走法

///路径矩阵 ///路径矩阵宽度 ///路径矩阵高度 static private void PrintDirection(string[,] matrix, int x, int y)
{
//打印路径矩阵
Console.WriteLine(“\r\nThe Direction Matrix:”);
for (int i = 0; i < x; i++) { for (int j = 0; j < y; j++) { Console.Write(matrix[i, j] + " "); } Console.Write("\r\n"); } //打印走法 Console.Write("The Route is:"); //走法的逆序存放数组 string[] Reverse = new string[x + y - 2]; int pos_x = x - 1; int pos_y = y - 1; //从终点开始向路径矩阵指示的方向回溯走法 for (int i = 0; i < (x + y - 2); i++) { //从左边来的 if (matrix[pos_x, pos_y].Equals("L")) { pos_y--; Reverse[i] = "right"; } //从上边来的 else { pos_x--; Reverse[i] = "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(","); } } } } } [/code]

推荐文章

5条评论

  1. //看了下题目 用c写了一个递归 不用递归的话就是动态规划 思想都一样
    //就用了你给的数据测试 结果一样

    #include “stdio.h”
    #include “stdlib.h”

    #define MAX 65535
    #define H 4
    #define W 15

    int a[H][W]={
    {1,2,7,9,7,1,1,1,7,9,1,4,1,5,5},
    {6,4,4,8,9,1,6,9,6,9,5,8,8,8,2},
    {2,7,9,2,4,2,8,6,3,6,2,6,7,2,7},
    {8,9,2,9,7,2,7,3,2,4,4,3,1,9,2}
    };

    int route[H][W]={0};
    int i=0;

    int f(int m ,int n)
    {
    int x,y,t1,t2;
    if(m==0&&n==0) //原始点
    return a[m][n];
    else if(m0||n>0)
    {
    if(route[m][n]==7)
    {
    a[k++]=0;
    n–;
    }
    else
    {
    a[k++]=1;
    m–;
    }
    }

    for(l=k-1;l>=0;l–)
    if(a[l]==0) printf(“right “);
    else printf(“down “);

    printf(“\nthe min value : %d”,total);
    system(“PAUSE”);
    return 0;
    }

  2. #include “stdio.h”
    #include “stdlib.h”

    #define MAX 65535
    #define H 4
    #define W 15

    int a[H][W]={
    {1,2,7,9,7,1,1,1,7,9,1,4,1,5,5},
    {6,4,4,8,9,1,6,9,6,9,5,8,8,8,2},
    {2,7,9,2,4,2,8,6,3,6,2,6,7,2,7},
    {8,9,2,9,7,2,7,3,2,4,4,3,1,9,2}
    };

    int route[H][W]={0}; //路径
    int i=0;

    int f(int m ,int n)
    {
    int x,y,t1,t2;
    if(m==0&&n==0) //原始点
    return a[m][n];
    else if(m0||n>0)
    {
    if(route[m][n]==7)
    {
    a[k++]=0;
    n–;
    }
    else
    {
    a[k++]=1;
    m–;
    }
    }

    for(l=k-1;l>=0;l–)
    if(a[l]==0) printf(“right “);
    else printf(“down “);

    printf(“\nthe min value : %d”,total);
    system(“PAUSE”);
    return 0;
    }

  3. 这个博客有问题啊
    代码提交怎么会自动裁掉一段
    是不是什么过滤了

  4. 博客有问题啊
    怎么提交内容会自动裁掉一段
    过滤掉了?

  5. Hi,xy:
    Can u give a copy of your coding to me?
    I want to have a look at your coding.
    Would u please send it to my Email: cms_914@163.com

发表评论