有这么一道题目, 看下面的图, 假设有一条直线, 每个叉叉上有一只蚂蚁, 它们会随机选择一个方向, 向前或者向后移动, 每次走一格, 前进中当两只蚂蚁相遇, 它们会掉头, 问: 全部蚂蚁都走出去的最长和最短步数;
最短步数很明显...只要方向对了, 就是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;elsem_pos -= x;}void turnBack() {m_direction *= -1;}int m_pos;int m_d