蚂蚁和木杆的问题<2>其中的简单排列问题_夏虫语冰

http://blog.sina.com.cn/u/1590057661

首页博文目录关于我

个人资料

微博

加好友发纸条

写留言加关注

博客等级：
博客积分：

博客访问：
关注人气：
获赠金笔：0支
赠出金笔：0支
荣誉徽章：

正文字体大小：大中小

蚂蚁和木杆的问题<2>其中的简单排列问题

(2009-07-09 16:32:25)

标签：

it

分类：小程序

有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。
木杆很细，不能同时通过一只蚂蚁。开始时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，但不会后退。
当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。
假设蚂蚁们每秒钟可以走一厘米的距离。编写程序，求所有蚂蚁都离开木杆的最小时间和最大时间。

这个问题我解决出来才突然发现，这道题本身并不用编程，它实际是个思维转换的题。题中的蚂蚁速度都一样，而且相遇后又都反向移动，那么完全可以将问题简化为所有蚂蚁相互穿过，并行不悖。但是，再一细想，我的这个程序可以解决在蚂蚁速度大小不同的情况下，求所有蚂蚁离开木杆的最大时间和最小时间的问题。

解题思路：获得由速度方向组成的五位排列(例如 1,-1,-1,1,1)的集合，迭代这个集合，每个排列代表一种情况，求出每种排列情况下，所有蚂蚁离开木杆所需的时间，时间值放置于一个数组中，然后用数组排序找出最大值和最小值。

因为多行注释的符号在博文中无法显示，所以只好以单行注释替代各个方法前的注释。此篇文章中包括main 方法，集合的拷贝方法copy(), 最重要的是排列组合的获得方法，分为两个方法，其中第二个方法为递归方法。

受博文内容大小的限制，将此程序分布在三篇博文中，此篇文章包含了问题解决的核心方法--排列组合的获得方法，其他的配合方法在蚂蚁和木杆的问题<1>这篇文章中，而核心类 Ant 则在蚂蚁和木杆的问题<3> 文章中。

//-------------------------------------

public class AntWalker {
    // 杆长
    private static double lengthOfStick = 27;
    // 在木杆上的所有蚂蚁
    private static List<Ant> ants = new ArrayList<Ant>();
    // 记录距离此刻最近一次相遇的相遇时间, 以及相遇的右侧的蚂蚁在集合中的位置
    private static double min = 0;
    private static int rightIndex = 0;

    // main
    public static void main(String[] args) {

        // 蚂蚁数量，位置
        Ant[] allAnts = new Ant[5];
        double[] positions = new double[]{3,7,11,17,23};

        // 找出由所有的蚂蚁的速度方向组成的排列组合

        // 1.准备排列的元素
        List<Integer> directions = new ArrayList<Integer>();
       directions.add(1);
       directions.add(-1);

       // 获得所有蚂蚁方向的所有排列方式
        int arrangeSize = 5; // 排列的长度
        List<List<Integer>> arrangements = getArrangements(directions, arrangeSize);

        // 求出所有速度方向排列情况下蚂蚁全部离开木杆的时间
        double[] times = getAllTime(allAnts, positions, arrangements);
        for (int i = 0; i < times.length; i++) {
           System.out.println(times[i]);
          // 数组排序，找最值
            Arrays.sort(times);
            System.out.println("最短时间：" + times[0]);
            System.out.println("最长时间：" + times[times.length-1]);
       }

    }

    // 拷贝(克隆)一个当前的蚂蚁集合
    private static List<Ant> copy(){
        List<Ant> clone = new ArrayList<Ant>();
        for(Ant ant : ants){
            clone.add(ant);
        }
        return clone;
    }

// 获得所有排列(可重复元素的集合)，再将这些排列放进一个总集合中，返回这个集合
private static List<List<Integer>> getArrangements(List<Integer> directions,

                                                       int arrangeSize) {
        // 所有排列的集合
        List<List<Integer>> arrangements = new ArrayList<List<Integer>>();
        recursion(arrangements, directions, arrangeSize); // 调用递归，向集合中填充所有排列

return arrangements;
}

// 递归方法，在集合中添加所有长度为 arrangeSize 的排列,directions 为组成排列的元素
private static void recursion(List<List<Integer>> arrangements,

List<Integer> directions,

int arrangeSize) {
// 遍历组成排列的所有元素(两种方向-1和1)，使元素添加到集合中满足条件的排列的末尾

        for (int i = 0; i < directions.size(); i++) {
            if (arrangeSize == 1) { // 排列长度参数为 1 时，新建集合作为新排列，并添加到总集合
                  List<Integer> arrangement = new ArrayList<Integer>();
                arrangements.add(arrangement);
           } else                 // 排列长度不为 1，递归调用
                  recursion(arrangements, directions, arrangeSize-1); // 递归调用
            // 递归会在集合中产生出所有长度为 arrangeSize-1 的排列
            for (List<Integer> arrangement : arrangements) {// 遍历排列总集合
                if (arrangement.size() == arrangeSize-1) { // 挑选排列的长度为当前即将生成的排列的长度减 1
                    arrangement.add(directions.get(i));     // 将排列加长
                }
            }
        }
    }
}

阅读┊ 收藏 ┊ 喜欢 ▼ ┊打印┊举报/Report

前一篇：排列组合问题(不出现重复元素)(修改7月7日代码)

后一篇：蚂蚁和木杆的问题<3>蚂蚁类

新浪BLOG意见反馈留言板　欢迎批评指正