| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2608 人关注过本帖, 1 人收藏
标题:几道中南大学考研机试题
只看楼主 加入收藏
x275012749
Rank: 2
等 级:论坛游民
帖 子:9
专家分:10
注 册:2017-4-26
结帖率:0
收藏(1)
 问题点数:0 回复次数:3 
几道中南大学考研机试题
几道中南大学考研机试题
哪位老哥大神能告诉我每道题考得什么算法
要是能求解,上代码就更好了。谢谢帮助
题目 B(20 分)
问题描述:
有一个愚蠢的机器人走进了一个 w*h 的迷宫,迷宫里有空地和陷阱。它想要走遍每一个方格,但是它很笨,只会按照指令方向走。当下一步是边界或者是陷阱时,它会向右旋转 90 度。请问这个机器人最多可以经过多少个方格?


数据输入:
对于每组数据,第一行两个数 w 和 h,分别表示迷宫的行和列(1≤w,h≤10)
接下来 w 行,每行有 h 个字符用于描述这个迷宫。迷宫中的‘.’表示空地,即可以走的地方;‘*’表示陷阱,即不能走的地方;迷宫中有一个英文字母,表示机器人的出发点。字母只可能是‘U’、‘D’、‘L’、‘R’,分别表示机器人初始指令方向是向上、向下、向左、向右。

结果输出:
对于每组数据,输出一个整数,表示机器人一共经过了多少个方格

输入示例:
2 3
U..
.*.
4 4
R...
.**.
.**.
....

输出示例:
4
12



题目 C(15 分)
问题描述:
在一片 n*m 的土地上,每一块 1*1 的区域里都有一定数量的金子。这一天,你来到这里淘金。然而当地人告诉你,如果你要挖(x,y)区域的金子,那么你就不能挖(x-1,y)、(x+1,y)以及纵坐标为 y-1 和 y+1 的金子(也就是说你挖某一区域的金子,左边、右边、上一行、下一行的金子你都不被允许挖了)。那么问题来了,你最多能淘多少金?


数据输入:
对于每组数据,第一行两个数 n 和 m,分别表示土地的长度和宽度(1≤n,m≤200)
接下来 n 行,每行有 m 个数表示每个区域金子的数量,每个区域金子数量不超过 1000


结果输出:
对于每组数据,输出最多能得到的金子数量

输入示例:
4 6

11 0 7 5 13 9

78 4 81 6 22 4

1 40 9 34 16 10

11 22 0 33 39 6

输出示例:
242



题目 D(20 分)
问题描述:
巨人国的小学生放学了,老师要给小朋友们排队了。可是这个老师有强迫症,一定要让路队上的小朋友按身高从高到矮排序。小朋友们呢也很调皮,一旦老师给他排好了队就不愿意动了。这时候小朋友们一个一个从教室里出来了,每个小朋友一出来老师就要给小朋友安排好位置。请问老师最少要给小朋友们排几条路队?

数据输入:
对于每组数据,第一行一个整数 n,表示小朋友的总数(1≤n≤10000)第二行 n 个整数,表示每个小朋友的身高,身高不超过 30000

结果输出:
对于每组数据,输出一个整数,表示最少的路队数

输入示例:
8

389 207 155 300 299 170 158 65

输出示例

2

样例解释:
最少要排两条路队,其中一种方案是:389-207-155-65 和 300-299-170-158



题目 E(15 分)
问题描述:
你收到通知被中南大学录取了,高兴地来到长沙。很快你就来到了麓山南路上,已知你的位置是 N,中南大学的位置是 K。为了去中南大学,你有两种移动方式:走路或者坐公交车。走路:你可以从位置 X 移动到 X+1 或者 X-1 搭公交:你可以从位置 X 移动到 2X;
每次走路和搭公交所需的时间都是一分钟,你现在想尽快到中南大学,所需的时间是多少呢?

数据输入:
对于每组数据,输入一行,分别是 N 和 K(1≤N,K≤100,000)

结果输出:
对于每组数据,输出一个整数,表示所需时间

输入示例:
5 17

输出示例:
4

样例解释:
其中的一种方案是:5-10-9-18-17 所需时间是 4 分钟。
搜索更多相关主题的帖子: 机器人 下一步 中南大学 
2017-04-26 21:56
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9007
专家分:53942
注 册:2011-1-18
收藏
得分:0 
程序代码:
#include <stdio.h>

int main( void )
{
    for( unsigned w,h; scanf("%u%u",&w,&h)==2; )
    {
        enum { B=1, U=2, D=4, L=8, R=16 }; // 障碍物、上、下、左、右
        unsigned char m[10][10] = { 0 }; // 地图

        // 读入地图
        unsigned start_r=-1, start_c=-1; // 起点
        unsigned direction; // 当前行走方向
        unsigned count = 0; // 踏过的方格数量
        for( unsigned r=0; r!=w; ++r )
        for( unsigned c=0; c!=h; ++c )
        {
            char ch;
            scanf( " %c", &ch );
            switch( ch )
            {
            case '.': m[r][c]=0; break;
            case '*': m[r][c]=B; break;
            case 'U': m[r][c]=0; start_r=r, start_c=c; direction=U; break;
            case 'D': m[r][c]=0; start_r=r, start_c=c; direction=D; break;
            case 'L': m[r][c]=0; start_r=r, start_c=c; direction=L; break;
            case 'R': m[r][c]=0; start_r=r, start_c=c; direction=R; break;
            }
        }

        // 遍历
        for( ; start_r!=-1; )
        {
            if( (m[start_r][start_c]&direction) != 0 ) // 之前以相同方向走过此格
                break;
            if( (m[start_r][start_c]&(U|D|L|R)) == 0 ) // 之前未曾走过此格
                ++count;
            m[start_r][start_c] |= direction;

            // next
            switch( direction )
            {
            case U: if( start_r==0   || m[start_r-1][start_c]==B ) direction=R; else --start_r; break;
            case D: if( start_r==w-1 || m[start_r+1][start_c]==B ) direction=L; else ++start_r; break;
            case L: if( start_c==0   || m[start_r][start_c-1]==B ) direction=U; else --start_c; break;
            case R: if( start_c==h-1 || m[start_r][start_c+1]==B ) direction=D; else ++start_c; break;
            }
        }
        printf( "%u\n", count );
    }

    return 0;
}


授人以鱼,不如授人以渔,下面不写代码了,只是分析算法

题目 C(15 分)
行和列方法相同,以行为例:
每一行都有“挖”和“不挖”两种可能
如果是“挖”,那么其结果是 上上一行 的最大结果 + 本行最大结果
如果是“不挖”,那么其结果是 上一行 的最大结果
本行的结果是 “挖”和“不挖”两种情况下的最大值

举例(简化到每行只有一个数字)
第0行 4
第1行 1
第2行 2
第3行 5

第-2行,结果是0
第-1行,结果是0
第0行,结果是 max(0+4,0) = 4
第1行,结果是 max(0+1,4) = 4
第2行,结果是 max(4+2,4) = 6
第3行,结果是 max(4+5,6) = 9

题目 D(20 分)
从第一个数开始,比其尾部小的就加入到尾部,直到结束
重复上述过程,一共重复了几次就输出几次
(没看出有什么特殊的地方,分值反而比“题目 C”还高?!那或许是我想简单了)

题目 E(15 分)
效率低但胜在简单的方法是递归
unsigned foo( n, k )
{
    if( n == k ) return 0;
    return 1 + min( 如果k>=一个半的n有foo(2*n,k), 如果n>1有foo(n-1,k), 如果n<k有foo(n+1,k) );
}


假设一共乘车m次
n*2^m + a*2^A + b*2^B + c*2^C + …… = k (abs(a、b、c)==1)
还是蛮复杂的
2017-04-27 11:11
x275012749
Rank: 2
等 级:论坛游民
帖 子:9
专家分:10
注 册:2017-4-26
收藏
得分:0 
回复 2楼 rjsp
第一次发帖,这么详细的回复!
老哥 谢谢你哦!
2017-04-27 12:05
yangfrancis
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:贵宾
威 望:141
帖 子:1510
专家分:7661
注 册:2014-5-19
收藏
得分:0 
题目C

#include<iostream>
#include<time.h>
#include<vector>
#include<math.h>
#include<conio.h>
using namespace std;
template<typename T>
class MyVector:public vector<T>
{
public:
    bool find(T elem)
    {
        if(empty()) return false;
        iterator itr;
        for(itr=begin();itr!=end();itr++)
            if(*itr==elem) return true;
        return false;
    }
};
int w,h;
class  cell
{
public:
    int value;
    int x;
    int y;
    bool operator==(const cell&compare)
    {
        if(x==compare.x&&y==compare.y) return true;
        return abs(x-compare.x)+abs(y-compare.y)==1;
    }
};
ostream&operator<<(ostream&os,cell&c)
{
    os<<c.value;
    return os;
};
cell**arr;
int main()
{
    cout<<"输入宽:";cin>>w;
    cout<<"高:";cin>>h;
    srand((unsigned int)time(0));
    arr=new cell*[h];
    for(int i=0;i<h;i++)
        arr[i]=new cell[w];
    /*赋值*/
    for(i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
        {
            arr[i][j].value=(unsigned int)rand()%20;
            arr[i][j].x=j;arr[i][j].y=i;
            cout<<arr[i][j].value<<'\t';
        }
        cout<<endl;
    }
    MyVector<cell> vt,max_vt;int max=0;int sum=0;
    cell tmp=arr[0][0];
    do
    {
        do
        {
            if(vt.find(tmp))
            {
                if(tmp.x==w-1&&tmp.y==h-1) break;
                tmp=arr[tmp.y+(tmp.x+1)/w][(tmp.x+1)%w];//定位到下一元素
            }
            else
            {
                vt.push_back(tmp);sum+=tmp.value;
            }
        }while(tmp.x<w-1||tmp.y<h-1);
        /*求和*/
        if(sum>max)
        {
            max=sum;
            max_vt=vt;
        }
        /******************/
        while(vt.back().x==w-1&&vt.back().y==h-1)
        {
            sum-=vt.back().value;vt.pop_back();
        }
        if(vt.empty()) break;
        tmp=vt.back();sum-=tmp.value;vt.pop_back();//回退
        tmp=arr[tmp.y+(tmp.x+1)/w][(tmp.x+1)%w];
    }while(1);
    cout<<"最终极大值:"<<max<<"\n具体相加项:"<<endl;
    MyVector<cell>::iterator itr;
    for(itr=max_vt.begin();itr!=max_vt.end();itr++)
        cout<<*itr<<" ";
    cout<<endl;
    /*释放*/
    for(i=0;i<h;i++)
        delete []arr[i];
    delete []arr;
    return 0;
}
2017-04-29 22:35
快速回复:几道中南大学考研机试题
数据加载中...
 
   



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

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