论坛首页 Java企业应用论坛

用递归解决排列问题

浏览 2230 次
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2009-02-25   最后修改:2009-02-26
引用
一根很细的竹竿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;
    }


   发表时间:2009-02-25  
最长24s, 最短11s,
可以把蚂蚁碰撞, 理解为蚂蚁彼此穿越, 不影响结果, 这样的话
程序, 只有两个for循环了, 更加简介了
0 请登录后投票
   发表时间:2009-02-26   最后修改:2009-02-26
mumuxinfei 写道
最长24s, 最短11s,
可以把蚂蚁碰撞, 理解为蚂蚁彼此穿越, 不影响结果, 这样的话
程序, 只有两个for循环了, 更加简介了

啊,我没想到,这样问题就简单多了,而且,也证明了我的时间的计算是有问题的。
0 请登录后投票
   发表时间:2009-02-26  
bill.end 写道
mumuxinfei 写道
最长24s, 最短11s,
可以把蚂蚁碰撞, 理解为蚂蚁彼此穿越, 不影响结果, 这样的话
程序, 只有两个for循环了, 更加简介了

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

不是时间的计算是有问题,而是Ant类的right属性是多余的,已经被修改了
0 请登录后投票
论坛首页 Java企业应用版

跳转论坛:
Global site tag (gtag.js) - Google Analytics