| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 1719 人关注过本帖
标题:微软2015校招题
只看楼主 加入收藏
诸葛欧阳
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:流年
等 级:贵宾
威 望:82
帖 子:2786
专家分:14619
注 册:2014-10-16
  得分:0 
有人弄出来吗?

一片落叶掉进了回忆的流年。
2015-10-08 20:02
yangfrancis
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:141
帖 子:1510
专家分:7661
注 册:2014-5-19
  得分:0 
谈何容易,如果用递归的话,最后又怎么还原成一个大的矩阵,这是最蛋疼的。
2015-10-08 21:12
wmf2014
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:185
帖 子:1799
专家分:10092
注 册:2014-12-6
  得分:13 
从输入说明里没看到翻转系数k的输入。

能编个毛线衣吗?
2015-10-09 10:12
linan03
Rank: 4
等 级:业余侠客
威 望:5
帖 子:76
专家分:204
注 册:2012-10-27
  得分:13 
k固定范围 在代码里四种数值情况都要试过去来验证的吧。

那个示例输入没看明白,第一行是边长的话,为 3 ?
2015-10-10 11:49
yangfrancis
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:141
帖 子:1510
专家分:7661
注 册:2014-5-19
  得分:0 
回复 14楼 linan03
那个3是输入的测试案例个数,以下三个案例连长分别是2,2,4
2015-10-10 17:02
yangfrancis
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:141
帖 子:1510
专家分:7661
注 册:2014-5-19
  得分:0 
以下代码已经测试
#include<iostream>
#include<stdlib.h>
using namespace std;
class Matrix
{
public:
    char ** x;
    short width;
    Matrix(){x=0;
    };
    void Init(short w)
    {
        x = new char*[w];
        for(short i=0;i<w;i++)
           x[i]=new char[w];
        width=w;
    }
    friend bool operator==(Matrix mx1,Matrix mx2);
    friend bool operator!=(Matrix mx1,Matrix mx2);
};
bool operator==(Matrix mx1,Matrix mx2)
{
    short n;n=mx1.width;
    if(n!=mx2.width) return false;
    short row,col;
    for(row=0;row<n;row++)
    {
        for(col=0;col<n;col++)
            if(mx1.x[row][col]!=mx2.x[row][col])
                return false;
    }
    return true;
}
bool operator!=(Matrix mx1,Matrix mx2){return !(mx1==mx2);}
Matrix Roll90(Matrix mx)/*旋转90度*/
{
    short width;width=mx.width;
    Matrix temp;temp.Init(width);
    for(short row=0;row<width;row++)
    {
        for(short col=0;col<width;col++)
            temp.x[row][col]=mx.x[width-1-col][row];
    }
    return temp;
}
Matrix Roll180(Matrix mx)/*旋转180度*/
{
    short width;width=mx.width;
    Matrix temp;temp.Init(width);
    for(short row=0;row<width;row++)
    {
        for(short col=0;col<width;col++)
            temp.x[row][col]=mx.x[width-1-row][width-1-col];
    }
    return temp;
}
Matrix Roll270(Matrix mx)/*旋转270度*/
{
    short width;width=mx.width;
    Matrix temp;temp.Init(width);
    for(short row=0;row<width;row++)
    {
        for(short col=0;col<width;col++)
            temp.x[row][col]=mx.x[col][width-1-row];
    }
    return temp;
}
bool Split1(const Matrix mx,Matrix &submx)/*分裂出左上方的小矩阵*/
{
    short n;
    n=mx.width;
    if(n%2==1) return false;
    submx.Init(n/2);
    short row,col;
    for(row=0;row<submx.width;row++)
    {
        for(col=0;col<submx.width;col++)
        {
            submx.x[row][col]=mx.x[row][col];
        }
    }
    return true;
}
bool Split2(const Matrix mx,Matrix &submx)/*分裂出右上方的小矩阵*/
{
    short n;
    n=mx.width;
    if(n%2==1) return false;
    submx.Init(n/2);
    short row,col;
    for(row=0;row<submx.width;row++)
    {
        for(col=0;col<submx.width;col++)
        {
            submx.x[row][col]=mx.x[row][col+submx.width];
        }
    }
    return true;
}
bool Split3(const Matrix mx,Matrix &submx)/*分裂出左下方的小矩阵*/
{
    short n;
    n=mx.width;
    if(n%2==1) return false;
    submx.Init(n/2);
    short row,col;
    for(row=0;row<submx.width;row++)
    {
        for(col=0;col<submx.width;col++)
        {
            submx.x[row][col]=mx.x[row+submx.width][col];
        }
    }
    return true;
}
bool Split4(const Matrix mx,Matrix &submx)/*分裂出右下方的小矩阵*/
{
    short n;
    n=mx.width;
    if(n%2==1) return false;
    submx.Init(n/2);
    short row,col;
    for(row=0;row<submx.width;row++)
    {
        for(col=0;col<submx.width;col++)
        {
            submx.x[row][col]=mx.x[row+submx.width][col+submx.width];
        }
    }
    return true;
}
bool FillValue(Matrix &mx,char *str)//用字符串为矩阵赋值
{
    short size;
    size=mx.width*mx.width;
    if(size!=strlen(str)) return false;
    short row,col;
    for(row=0;row<mx.width;row++)
       for(col=0;col<mx.width;col++)
           mx.x[row][col]=str[row*mx.width+col];
    return true;
}
bool Compare(const Matrix mxSource,const Matrix mxTarget)
{
    if(mxSource.width!=mxTarget.width) return false;
    Matrix mxRolled;
    if(mxSource.width%2!=0)//不可再分割的情况
    {
        mxRolled=mxSource;//旋转0度
        if(mxRolled==mxTarget) return true;
        mxRolled=Roll90(mxSource);//旋转90度的情况
        if(mxRolled==mxTarget) return true;
        mxRolled=Roll180(mxSource);//旋转180度的情况
        if(mxRolled==mxTarget) return true;
        mxRolled=Roll270(mxSource);//旋转270度的情况
        if(mxRolled==mxTarget) return true;
        return false;//四种状况均不与目标方阵吻合
    }
    bool OK1=true,OK2=true,OK3=true,OK4=true;//用布尔变量记录四种转角递归后是否与目标区域一致
    Matrix submx1,submx2,submx3,submx4;
    Matrix subTg1,subTg2,subTg3,subTg4;
    Split1(mxTarget,subTg1);Split2(mxTarget,subTg2);Split3(mxTarget,subTg3);Split4(mxTarget,subTg4);
    /*获得目标矩形比较区域*/
    mxRolled=mxSource;//旋转0度
    Split1(mxRolled,submx1);Split2(mxRolled,submx2);Split3(mxRolled,submx3);Split4(mxRolled,submx4);
    /*获得源矩形比较区域*/
    if(!Compare(submx1,subTg1)) OK1=false;//左上角小方阵递归加密不与目标方阵相应区域吻合
    if(!Compare(submx2,subTg2)) OK1=false;//右上角小方阵递归加密不与目标方阵相应区域吻合
    if(!Compare(submx3,subTg3)) OK1=false;//左下角小方阵递归加密不与目标方阵相应区域吻合
    if(!Compare(submx4,subTg4)) OK1=false;//右下角小方阵递归加密不与目标方阵相应区域吻合
    /*---------------------------------------------------------------------------------*/
    mxRolled=Roll90(mxSource);//旋转90度
    Split1(mxRolled,submx1);Split2(mxRolled,submx2);Split3(mxRolled,submx3);Split4(mxRolled,submx4);
    /*获得源矩形比较区域*/
    if(!Compare(submx1,subTg1)) OK2=false;//左上角小方阵递归加密不与目标方阵相应区域吻合
    if(!Compare(submx2,subTg2)) OK2=false;//右上角小方阵递归加密不与目标方阵相应区域吻合
    if(!Compare(submx3,subTg3)) OK2=false;//左下角小方阵递归加密不与目标方阵相应区域吻合
    if(!Compare(submx4,subTg4)) OK2=false;//右下角小方阵递归加密不与目标方阵相应区域吻合
    /*---------------------------------------------------------------------------------*/
    mxRolled=Roll180(mxSource);//旋转180度
    Split1(mxRolled,submx1);Split2(mxRolled,submx2);Split3(mxRolled,submx3);Split4(mxRolled,submx4);
    /*获得源矩形比较区域*/
    if(!Compare(submx1,subTg1)) OK3=false;//左上角小方阵递归加密不与目标方阵相应区域吻合
    if(!Compare(submx2,subTg2)) OK3=false;//右上角小方阵递归加密不与目标方阵相应区域吻合
    if(!Compare(submx3,subTg3)) OK3=false;//左下角小方阵递归加密不与目标方阵相应区域吻合
    if(!Compare(submx4,subTg4)) OK3=false;//右下角小方阵递归加密不与目标方阵相应区域吻合
    /*---------------------------------------------------------------------------------*/
    mxRolled=Roll270(mxSource);//旋转270度
    Split1(mxRolled,submx1);Split2(mxRolled,submx2);Split3(mxRolled,submx3);Split4(mxRolled,submx4);
    /*获得源矩形比较区域*/
    if(!Compare(submx1,subTg1)) OK4=false;//左上角小方阵递归加密不与目标方阵相应区域吻合
    if(!Compare(submx2,subTg2)) OK4=false;//右上角小方阵递归加密不与目标方阵相应区域吻合
    if(!Compare(submx3,subTg3)) OK4=false;//左下角小方阵递归加密不与目标方阵相应区域吻合
    if(!Compare(submx4,subTg4)) OK4=false;//右下角小方阵递归加密不与目标方阵相应区域吻合
    if(OK1||OK2||OK3||OK4)
       return true;
    else
       return false;
}
int main()
{
    Matrix A,B;
    short number;/*测试次数*/short w;/*边长变量*/
    char str1[101],str2[101];/*为源矩阵和目标矩阵赋值的字符串*/
    cout<<"请输入想要测试的次数:";
    cin>>number;
    short row,col;//用于循环遍历赋值
    for(short i=0;i<number;i++)
    {
        cout<<"请输入边长:";
        cin>>w;A.Init(w);B.Init(w);
        cout<<"请输入含"<<w*w<<"个字符的字符串,为源矩阵赋值:";
        cin>>str1;
        cout<<"请输入含"<<w*w<<"个字符的字符串,为目标矩阵赋值:";
        cin>>str2;
        if(!FillValue(A,str1)){cout<<"非法输入,按任意键退出。\n";system("pause");return 0;}
        if(!FillValue(B,str2)){cout<<"非法输入,按任意键退出。\n";system("pause");return 0;}
        for(row=0;row<w;row++)
        {
           for(col=0;col<w;col++)
              cout<<'\t'<<A.x[row][col];
           cout<<endl;
        }
        cout<<endl;
        for(row=0;row<w;row++)
        {
           for(col=0;col<w;col++)
              cout<<'\t'<<B.x[row][col];
           cout<<endl;
        }
        if(Compare(A,B)) cout<<"YES!";
        else cout<<"NO!";
    }
    system("pause");
    return 0;
}
2015-10-10 18:23
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
  得分:0 
练练手,果然c++忘的差不多了,查资料就用了不少时间。

程序代码:
#include <vector>
#include <fstream>
#include <iostream>

using namespace std;
typedef vector<unsigned> linear_array;
typedef vector<linear_array> dyadic_array;

class Matrix {
private:
    char flag;
    dyadic_array data;
    size_t length, angle;

    void rotate90(size_t x_pos, size_t y_pos, size_t range);

    void rotate(size_t range, size_t x_pos, size_t y_pos);

public:
    Matrix(size_t length, char flag) : length(length), flag(flag), angle(0) {}

    void rotate();

    bool operator ==(const Matrix &matrix) const;

    friend istream &operator >>(istream &is, Matrix &matrix);

    friend ostream &operator <<(ostream &os, const Matrix &matrix);
};

void Matrix::rotate90(size_t x_pos, size_t y_pos, size_t range) {
    dyadic_array array(range, linear_array(range));
    for (size_t x = 0; x != range; ++x) {
        for (size_t y = 0; y != range; ++y) {
            array[x][y] = this->data[x_pos + range - 1 - y][y_pos + x];
        }
    }
    for (size_t x = 0; x != array.size(); ++x) {
        for (size_t y = 0; y != array[x].size(); ++y) {
            this->data[x_pos + x][y_pos + y] = array[x][y];
        }
    }
}

void Matrix::rotate(size_t range, size_t x_pos, size_t y_pos) {
    rotate90(x_pos, y_pos, range);

    if (range % 2 || range <= 2) return;
    size_t length = range / 2;

    rotate(length, x_pos, y_pos);
    rotate(length, x_pos, y_pos + length);
    rotate(length, x_pos + length, y_pos);
    rotate(length, x_pos + length, y_pos + length);
}

void Matrix::rotate() {
    this->angle += 90;
    rotate(this->length, 0, 0);
}

bool Matrix::operator ==(const Matrix &matrix) const {
    return this->length == matrix.length && this->data == matrix.data;
}

istream &operator >>(istream &is, Matrix &matrix) {
    for (size_t i = 0; i != matrix.length; ++i) {
        matrix.data.push_back(linear_array(matrix.length));
        for (size_t j = 0; j != matrix.length; ++j) {
            is >> matrix.data[i][j];
        }
    }
    return is;
}

ostream &operator <<(ostream &os, const Matrix &matrix) {
    os << "Matrix(" << matrix.flag << ", " << matrix.angle << ") :" << endl;
    for (size_t i = 0; i != matrix.length; ++i) {
        for (size_t j = 0; j != matrix.length; ++j) {
            os << matrix.data[i][j] << ' ';
        }
        os << endl;
    }
    return os;
}

int main(void) {
    bool flag;
    size_t T, N;

    ifstream in("stdin");
    if (in.fail()) return -1;

    in >> T;
    while (T--) {
        in >> N;

        Matrix A(N, 'A'), B(N, 'B');
        in >> A >> B;

        flag = A == B;
        for (int i = 0; i < 3; ++i) {
            A.rotate();
            if (A == B) flag = true;
        }

        if (flag) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    in.close();

    return 0;
}


[此贴子已经被作者于2016-11-17 14:45编辑过]



[fly]存在即是合理[/fly]
2016-11-17 14:40
快速回复:微软2015校招题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.055876 second(s), 8 queries.
Copyright©2004-2019, BCCN.NET, All Rights Reserved