`
guispor7
  • 浏览: 26010 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

EMC笔试题(最后一道编程题)

阅读更多
昨天去EMC面试,有个题没写出来,只写了个思路,想和大家讨论下
题目是这样的:7*8的一个棋盘,即有56个格子。格子上随机放上小球。小球只可以做水平或者垂直方向运动。
小球相互可以碰撞,碰撞的情况为:
如果两个小球相邻,比如Ball(1, 3)和Ball (1, 4),这时远处的小球Ball(1, 1)移动过来撞到Ball(1, 3),Ball(1, 1)应该停止在(1, 2)位置,同时Ball(1, 3)把碰撞传递给Ball(1, 4)后,Ball(1,3)仍然不动, Ball(1, 4)被撞开,以此类推。



Ball(1, 1) => Ball(1, 3), Ball(1, 4)

如果一个方向上没有其他的小球存在,那么不允许直接将小球沿着这个方向直接移出棋盘。

例如下图中,G表示小球,那么(2,2)位置上的小球只能向右或向下移动,因为(2, 2)位置的小球的上方和左方都没有小球,规则不允许把(2, 2)位置的小球沿上、左方移动从而直接移出棋盘。同理,(4, 2)位置的小球只允许向左移动。

### # # # #
#G # G # # #
# # #  # # # #
# G #  # # # #
# # #  # # # #
# # #  # # # #
# # #  # # # #
# # #  # # # #
两个球相邻是不能动的。中间一定要有至少一个的空格。
当碰撞过后,只有一个球在棋盘上为有解。否则无解。
每次选择任意一个球开始运动,碰撞完成后,可以选择任意剩下小球开始运动。
请写出一个程序,任意初始化棋盘上的小球,然后判断是否有解,有解打印出球移动步骤,否则输入无解。
分享到:
评论
10 楼 zhizhuodeyu 2010-12-01  

没有看懂题目。

为何没有两个小球碰撞情况。

此题可否如此理解,三个小球只要横坐标或纵坐标相同,此题误解。或是两个小球碰撞后横坐标或纵坐标相邻此题无解
其他情况均为有解。
9 楼 suntao19830709 2010-11-30  
正面做这个问题可以,但是比较麻烦。例如需要递归,每一步还需要记住当前棋盘小球的位置。而且由于递归的需要,可能要创建大量的这样的位置信息。

但是这个题目并没有限定死,任意初始化棋盘上的小球,然后判断是否有解,有解打印出球移动步骤,否则输入无解。
关键这个任意并不是要输出全部的。我们完全可以模拟一种“伪任意”,可以按照下面偷个巧。

按下面步骤:
1:一开始随机生成一个任意位置的小球
2:假想这个小球是x,是另一个随机的小球y撞过来的。
3:把第二步的y当成x,再新建一个随机的小球y,假想它撞了当前的x(第二步里的y)
4:重复若干次步骤3
5:把最终各个小球的位置当成初始位置,然后逆向打出上面的结果。

如果要无解的那种有点类似上面有人提到的,生成一个类似8皇后的即可。

这样其实比较容易。以前看到有的游戏不会创建无解的初始位置,相信通过这种方式比较容易实现。

8 楼 tomorrow009 2010-11-30  
疑惑:小球是只有从“远处”移动过来才可以碰撞么?
即: 假如最后剩下两个相邻小球, b1(1,2) , b2(2,2), 那么是否可以使用b1撞走b2,而b1位置不变,并认定为有解呢?
7 楼 guispor7 2010-11-30  
junlas 写道
LZ,题目我看不懂,有个疑惑:

不允许直接将小球沿着这个方向直接移出棋盘,碰撞过后,"有解"怎么就一个球在棋盘上呢??其它球呢?不懂~~


就是有球撞才能动,球要是被别的球撞出去的。不能自己跑出棋盘。
6 楼 junlas 2010-11-30  
LZ,题目我看不懂,有个疑惑:

不允许直接将小球沿着这个方向直接移出棋盘,碰撞过后,"有解"怎么就一个球在棋盘上呢??其它球呢?不懂~~
5 楼 guispor7 2010-11-30  
CnXiaowei 写道
我觉得是不是这个思路:
从任意一个小球开始,先找一个有其他小球的方向移动,移动到其他小球的时候,和那个小球合并,再继续找另一个小球的方向进行移动,以此类推,直到四个方向都没有任何小球的时候,回溯到上一步,继续上一步找其他方向的小球移动,直到棋盘上只剩下一个小球,为找到的解,或者回溯到了最开始并且没有任何可移动的方向,则这个小球的位置开始无解,继续下一个小球的位置继续找。
其实就是回溯算法


不是替代原球,是在这个球的前方停下。
您的思路和我当时写得一样的。就是状态太多,不知道用什么来存储老的状态。
4 楼 CnXiaowei 2010-11-30  
我觉得是不是这个思路:
从任意一个小球开始,先找一个有其他小球的方向移动,移动到其他小球的时候,和那个小球合并,再继续找另一个小球的方向进行移动,以此类推,直到四个方向都没有任何小球的时候,回溯到上一步,继续上一步找其他方向的小球移动,直到棋盘上只剩下一个小球,为找到的解,或者回溯到了最开始并且没有任何可移动的方向,则这个小球的位置开始无解,继续下一个小球的位置继续找。
其实就是回溯算法
3 楼 lyw985 2010-11-30  
regular 写道
变种八皇后问题。

显然不是八皇后问题的变种,拜托看清题目再回答
2 楼 EldonReturn 2010-11-29  
除了推演+剪枝,暂时没想到更好的办法
1 楼 regular 2010-11-29  
变种八皇后问题。

相关推荐

    EMC笔试题面经整理

    EMC笔试题面经整理EMC笔试题面经整理EMC笔试题面经整理

    EMC笔试题和面试题

    笔试部分主要包括选择题、编程题和写作题三个部分。选择题有30多道,答对得分,答错需要倒扣分数,每道题都很有难度,考察了算法、C/C++基础、面向对象、逻辑等多方面的知识。编程题有4个,2个容易,2个困难,题目...

    2007年emc笔试题

    此次笔试共分为四个部分:信息收集、多项选择题、编程题以及开放性问题。考试时间限定为3小时,不允许使用任何电子设备辅助答题。 #### 信息收集部分解析 这一部分主要是为了收集应聘者的个人偏好信息,包括工作...

    EMC笔试题答案(c++)

    EMC2009校园招聘笔试题答案,c++实现,可编译运行

    EMC 面试笔试必备

    EMC面试笔试必备的知识点涵盖了多个方面,包括但不限于以下几个关键领域: 1. 存储基础: - 存储层次结构:理解主存、辅助存储和外部存储之间的区别,以及它们如何协同工作以提高数据访问效率。 - 存储类型:了解...

    北京华为经典笔试题(附答案)

    【压缩包子文件的文件名称列表】:"华为笔试"可能是包含所有笔试题目的文档,可能是一个PDF文件或者一系列的文本文件,涵盖了不同类型的题目,如选择题、填空题、编程题等。文件中可能还包含了详细的解题步骤和解释...

    EMC 面试题 笔试题 面试经验 知识树

    同时,还有对应聘者提供的招聘流程、笔试题、面试经验、面试题目和面试感受等信息。这些内容对于想要了解EMC招聘流程和面试技巧的求职者非常有价值。 通过上述知识点,我们可以看出EMC是一个在存储技术领域具有深厚...

    EMC2007笔试题

    【EMC2007笔试题】涉及到的是EMC公司2007年针对软件质量工程师一职的招聘笔试环节。EMC是一家知名的全球信息技术公司,主要提供数据存储、信息安全、云计算等解决方案。在这样的笔试中,考生可以期待遇到与软件测试...

    EMC2010年校园招聘笔试题

    【EMC2010年校园招聘笔试题】是一份极具价值的历史资料,它记录了全球知名存储解决方案提供商EMC在2010年面向校园招聘时所使用的测试题目。对于那些希望进入EMC工作的求职者,这份资料具有很高的参考价值,能够帮助...

    emc 2007 应届生 笔试题

    根据给定的EMC 2007应届生笔试题的内容,我们可以从中提取出一些重要的知识点,并对其进行详细的解析。 ### 一、考试说明与规则 #### 1. 考试时间 - 考生需在**3小时内**完成整个考试。 #### 2. 考试结构 - **总...

    EMC 笔试资料精华

    1. **编程题限制**: 在提供的代码示例中,题目要求编写一个函数`p(int i, int N)`,该函数要在一行内完成输出i到N以及N到i的数字,并且每个数字占一行。此外,还有一些特殊的限制条件: - 只允许有一个语句,即一...

Global site tag (gtag.js) - Google Analytics