用递归解决排列问题

引用

一根很细的竹竿27cm，在3cm,7cm,11cm,17cm,23cm 处各有一只蚂蚁，蚂蚁每秒钟走1cm，不能停，可以向左走也可以向右走，当两只蚂蚁碰头后都掉头往回走，蚂蚁不能相互超越，问全部走完竹竿的最长时间和最短时间。 写出程序设计思路

对蚂蚁建模：
属性：速度，在竹竿上的位置，是否向右移动，是否走完
方法：是否向右移动，移动时间后改变状态，是否会和另一只蚂蚁相遇，是否和另一只蚂蚁移动方向相同，改变移动方向，会和另一只蚂蚁相遇的时间。

public class Ant {
    // minus: left; positive: right
    private int speed = 1;

    private float position;

    private boolean over;

    public Ant(float position) {
        this.position = position;
    }

    /**
     * 移动时间后改变状态
     * @param time
     *            the time to set
     */
    public void setTime(float time) {
        if (over) {
            return;
        }
        position = position + speed * time;
        if (position <= 0) {
            over = true;
            position = 0;
        }
        if (position >= 27) {
            over = true;
            position = 27;
        }
    }

    /**
     * @return the loc
     */
    public float getPosition() {
        return position;
    }

    /**
     * @param direction
     *            the direction to set
     */
    public void changeDirection() {
        this.speed *= -1;
    }

    /**
     * @return the right
     */
    public boolean isRight() {
        return this.speed > 0 ? true : false;
    }

    /**
     * @return the over
     */
    public boolean isOver() {
        return over;
    }

    public boolean isSameDirection(Ant ant) {
        return ant.isRight() == isRight();
    }

    public boolean willConflict(Ant ant) {
        return (!ant.isRight()) && isRight();
    }
    
    public float conflict(Ant ant) {
        float f = getPosition();
        float s = ant.getPosition();
        return Math.abs((f - s) / 2);
    }

    public Ant copy() {
        Ant ant = new Ant(this.position);
        ant.over = this.over;
        ant.speed = this.speed;
        return ant;
    }
}

把这个问题它分解成3部分：
  1. 5只蚂蚁初始的移动方向
  2. 根据初始的移动方向，5只蚂蚁走完竹竿的时间
  3. 求出最短和最长时间

第1部分是排列问题，5只蚂蚁初始移动方向共有32种方式，对于排列问题的解决方法我个人认为使用递归比较好，至少是“优雅的”代码，而不是嵌套5个for循环。

/**
     * 
     * @param stack 剩余未被加入排列的元素
     * @param pops 每一个元素是一个排列
     * @author luyang
     */
    private static void permutation(List<Ant> stack, List<List<Ant>> pops) {
        if (stack.isEmpty()) {
            return;
        }
        Ant pop = stack.remove(0);
        if (pops.isEmpty()) {
            List<Ant> pops1 = new ArrayList<Ant>();
            pops1.add(pop);
            pops.add(pops1);

            List<Ant> pops2 = new ArrayList<Ant>();
            Ant clone = pop.copy();
            clone.changeDirection();
            pops2.add(clone);
            pops.add(pops2);
            permutation(stack, pops);
            return;
        }
        List<List<Ant>> copyList = new ArrayList<List<Ant>>();
        for (List<Ant> list : pops) {
            List<Ant> copy = new ArrayList<Ant>();
            copyList.add(copy);
            for (Ant ant : list) {
                Ant clone = ant.copy();
                copy.add(clone);
            }
            list.add(pop.copy());
            Ant clone = pop.copy();
            clone.changeDirection();
            copy.add(clone);
        }
        pops.addAll(copyList);
        permutation(stack, pops);
    }

对于第2部分解决它的算法也是使用递归。
1. 求出2只相邻蚂蚁相遇的最短的时间，这段时间是所有蚂蚁共同的移动时间，也是所有蚂蚁状态保持不变的时间。
2. 2只相邻蚂蚁相遇后，改变他们的状态，累加时间。
3. 重复第1，2步，直到所有蚂蚁走完竹竿。

private static float calculate(List<Ant> ants) {
        float min_time = 13.5F;
        float sum = 0;
        int min_index = 0;
        int same_index = -1;
        for (int i = 0; i < ants.size() - 1; i++) {
            Ant ant = ants.get(i);
            boolean same = ant.isSameDirection(ants.get(i + 1));
            if (!same) {
                same_index = i;
            }
            boolean conflict = ant.willConflict(ants.get(i + 1));
            if (!conflict) {
                continue;
            }
            float time = ant.conflict(ants.get(i+1));
            if (min_time > time) {
                min_time = time;
                min_index = i;
            }
        }
        if (min_time == 13.5F) {
            if (same_index == -1) {
                // same direction
                if (ants.get(0).isRight()) {
                    return 27 - ants.get(0).getPosition() + sum;
                } else {
                    return ants.get(ants.size() - 1).getPosition() + sum;
                }
            } else {
                Ant ant1 = ants.get(same_index);
                Ant ant2 = ants.get(same_index + 1);
                if (ant1.isRight()) {
                    float f1 = 27 - ant1.getPosition();
                    float f2 = ant2.getPosition();
                    return f1 > f2 ? f1 + sum : f2 + sum;
                } else {
                    float f1 = ant1.getPosition();
                    float f2 = 27 - ant2.getPosition();
                    return f1 > f2 ? f1 + sum : f2 + sum;
                }
            }

        }
        sum += min_time;
        for (int i = ants.size() - 1; i >= 0; i--) {
            Ant ant = ants.get(i);
            ant.setTime(min_time);
        }
        ants.get(min_index).changeDirection();
        ants.get(min_index + 1).changeDirection();
        for (int i = ants.size() - 1; i >= 0; i--) {
            Ant ant = ants.get(i);
            boolean over = ant.isOver();
            if (over) {
                ants.remove(i);
            }
        }

        if (!ants.isEmpty()) {
            sum += calculate(ants);
        }
        return sum;
    }

评论

3 楼 bill.end 2009-02-26  

bill.end 写道

mumuxinfei 写道

最长24s, 最短11s,
可以把蚂蚁碰撞, 理解为蚂蚁彼此穿越, 不影响结果, 这样的话
程序, 只有两个for循环了, 更加简介了

啊，我没想到，这样问题就简单多了，而且，也证明了我的时间的计算是有问题的。

不是时间的计算是有问题，而是Ant类的right属性是多余的，已经被修改了

2 楼 bill.end 2009-02-26  

mumuxinfei 写道

最长24s, 最短11s,
可以把蚂蚁碰撞, 理解为蚂蚁彼此穿越, 不影响结果, 这样的话
程序, 只有两个for循环了, 更加简介了

啊，我没想到，这样问题就简单多了，而且，也证明了我的时间的计算是有问题的。

1 楼 mumuxinfei 2009-02-25  

最长24s, 最短11s,
可以把蚂蚁碰撞, 理解为蚂蚁彼此穿越, 不影响结果, 这样的话
程序, 只有两个for循环了, 更加简介了