首页 > 代码库 > [Puzzle] 蚂蚁路线碰撞问题
[Puzzle] 蚂蚁路线碰撞问题
有这么一道题目, 看下面的图, 假设有一条直线, 每个叉叉上有一只蚂蚁, 它们会随机选择一个方向, 向前或者向后移动, 前进中当两只蚂蚁相遇, 它们会掉头, 问: 全部蚂蚁都走出去的最长和最短步数;
最短步数很明显...只要方向对了, 就是11;
最长呢...在看到问题时脑子里第一个反应是: 没有储存对这类问题的算法, 然后开始模拟蚂蚁行进路线, 发现可能性太多, 简直就是一个分子碰撞大混乱的情形...比如 3向右, 7向左, 11向左, 那样3和7碰撞, 7调头, 会和11碰撞, 然后在调头...脑子内存不够模拟...
然后我准备写一下代码:
// 蚂蚁路线问题: 一条直线上多只蚂蚁, 相遇则反转方向, 计算最长爬行距离int pts[] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15, 16,17,18,19,20,21,22,23,24,25};class Ant {public: Ant(int p, int d): m_pos(p),m_direction(d) {} void move(int x) { if(m_direction > 0) m_pos += x; else m_pos -= x; } void turnBack() { m_direction *= -1; } int m_pos; int m_direction;};Ant firstMeet(const QList <Ant>& list) { // all the ants always ascending order Ant a = list.first(); for (int i = 1; i < list.size(); i++) { if(a.m_pos == list[i].m_pos) return a; }}void path() { QList <Ant> aList; Ant a1(3, 1); aList.append(a1); Ant a2(7, 1); aList.append(a2); Ant a3(11, 1); aList.append(a3); Ant a4(16, -1); aList.append(a4); Ant a5(20, -1); aList.append(a5); bool antsLeave = false; while (antsLeave) { }}
花了几分钟写到这里的时候, 停下来考虑要给Ant id, 给各种方向做所有的情况遍历...考虑有不只一对蚂蚁同时相遇的情况等等等等...我突然醒悟了....这不是程序题目, 如果你脑洞大一些, 就能明白, 最大值就是那个离开目标最远的蚂蚁要走的步数, 这里是22, 不劳烦计算机把所有case尝试一遍了;
[Puzzle] 蚂蚁路线碰撞问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。