lq_kevin
lq_kevin
2009-02-22 23:22

一道关于程序设计的题,请各位帮忙(急)

已采纳

有一根长27厘米的小木棍儿,在木棍儿的3厘米,7厘米,11厘米,17厘米,23厘米的地方各有一只蚂蚁。这5只蚂蚁的走向是不知道的,假设小木棍儿很细只能通过一只蚂蚁。蚂蚁只能往前走或者掉头,不能后退(也就是不能倒着走)!当任意两只蚂蚁碰头的时候会同时掉头朝反方向走。假设蚂蚁一秒钟能走一厘米,求蚂蚁全部离开木棍儿的最小和最大时间。用程序设计出来,可以只写思路!

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

4条回答

  • FengShen_Xia ChocooM 12年前

    [code="java"]
    public class Test {

    static int[] state = new int[5]; // -1:left; 1:right
    static int ss = 0; // 结果
    
    static int[] pos = { 3, 7, 11, 17, 23 };
    
    static int start = 0;
    static int end = 27;
    
    static void go() {
        while (true) {
            ss++;
            for (int i = 0; i < pos.length; i++) {
                if (pos[i] > 0 && pos[i] < 27) {
                    pos[i] += state[i];
                    if (i < pos.length - 1 && state[i] == 1
                            && state[i + 1] == -1) {
                        // 碰头情况
                        if (pos[i] + 1 > pos[i + 1]) {
                            state[i] = -1;
                            state[i + 1] = 1;
                        }
                    }
                    if (i > 0 && state[i] == -1 && state[i - 1] == 1) {
                        // 碰头情况
                        if (pos[i] - 1 < pos[i - 1]) {
                            state[i] = 1;
                            state[i - 1] = -1;
                        }
                    }
                }
            }
            if (proof()) {
                print();
                break;
            }
        }
    }
    
    private static void print() {
        System.out.println(ss);
    }
    
    private static boolean proof() {
        boolean isOk = true;
        for (int i = 0; i < state.length; i++) {
            if (pos[i] > 0 && pos[i] < 27) {
                isOk = false;
            }
        }
        return isOk;
    }
    
    static void init() {
        ss = 0;
        pos[0] = 3;
        pos[1] = 7;
        pos[2] = 11;
        pos[3] = 17;
        pos[4] = 23;
    }
    
    public static void main(String[] args) {
    
        state[0] = -1;
        state[1] = -1;
        state[2] = -1;
        state[3] = 1;
        state[4] = 1;
        // 共32种情况
        for (int i = 0; i < 32; i++) {
            String s = Long.toBinaryString(i);
            int n = 5 - s.length();
            for (int j = 0; j < n; j++) {
                s = "0" + s;
            }
            for (int j = 0; j < s.length(); j++) {
                char a = s.charAt(j);
                if (a == '1')
                    state[j] = 1;
                else
                    state[j] = -1;
            }
            init();
            go();
        }
    }
    

    }

    [/code]

    点赞 评论 复制链接分享
  • FengShen_Xia ChocooM 12年前

    蚂蚁碰头同时掉头朝反方向走,可以理解成只要把2只蚂蚁位子置换一下就可以了,这样就可以理解为什么最大是24s了,因为3cm的蚂蚁离另一头是最远的。

    点赞 评论 复制链接分享
  • FengShen_Xia ChocooM 12年前

    每个蚂蚁对象维护自己的几个属性:

    time 在木头上走的时间

    pos 在木头上的坐标

    orientation 方向(-1 or 1)

    recursion:

    1.所有蚂蚁走一步,矢量pos加1,time加1

    2.检查是否有蚂蚁在同一坐标上,如果有,将它们掉头

    3.检查是否有蚂蚁的坐标在[0,27]以外的外围,如果有,记下它的time值,然后这个蚂蚁出局

    4.反复1-3步,直到所有蚂蚁出局。它们time的最大值就是一个解(一共有32个情况,32种解).

    其实你只要考虑最中间和最外面的那2个蚂蚁就可以了,因为最中间那个也就是11cm的那个蚂蚁用时是最少的,为11s,而用时最大的就是那个3cm的蚂蚁,用时24s,只要把这2个判断好就可以了,其他的可以忽视。

    点赞 评论 复制链接分享
  • xenocide xenocide 12年前

    答案很简单,不管方向怎么走,结果都是24秒……

    硬要写个程序的话...

    a = [3,7,11,17,23]
    b = 27 - a
    max(a.max, b.max)

    点赞 评论 复制链接分享

相关推荐