« 前一篇:PHP项目外包
后一篇:HTTP客户端协议分析 »

求过河最短时间 @ 6/22/2007

Dev.做技术几年后只剩下算法
N个人一起潜水过河,只有一个氧气瓶,只能2个人同时用,每个人得游泳速度不一样,必须同步游泳(按速度慢得人游)所有人一起过河最少需要得时间 ?


发布于 6/22/2007 21:29:23 | 评论:6
流... @ 6/22/2007 21:31:19
java实现
不知道是否正确...


import java.util.Arrays;


public class PassRiver {

    private int[] a = new int[]
                             {45,10,7,6,6,4,3,2,2};
                             //{400,500,501,502,5005,5008};
                                 //{1,2,100,45,10,7,6,6,4};
    //private int[] b = new int[a.length];
   
    public void pass(){
       
        if(a.length==1){
            System.out.println("->速度为"+a[0]+"的人过河,时间为:"+a[0]);
            return;
        }
        if(a.length==2){
            System.out.println("->速度为"+a[0]+"、"+a[1]+"的人过河,时间为:"+(a[0]>a[1]?a[1]:a[1]));
            return;
        }   
        Arrays.sort(this.a);
        int total =0;
        int n = a.length-1;
        System.out.println("->速度为"+a[0]+"、"+a[1]+"的人过河,时间为:"+a[1]);
        total+=a[1];
        System.out.println("<-速度为"+a[0]+"的人回来,时间为:"+a[0]);
        total+=a[0];
       
        for(int j=n;j>=2;j--){
            if(j==2 ){
                total=print(a[0],a[j],total);
            }else if(a[j-1]<=(a[0]+a[1])){
                total=print(a[0],a[j],total);
                total=print(a[0],total);
            }
            else if(a[j-1]==a[1] ){
                total=print(a[0],a[1],total);//b[j]=1;
                total=print(a[0],total);
            }
            else{
                total=print(a[j],a[j-1],total);//b[j]=1;b[j-1]=1;
                total=print(a[1],total);
                total=print(a[0],a[1],total);
                total=print(a[0],total);
                j--;
                if(j==2){
                    total=print(a[0],a[1],total);
                    break;
                }
            }
           
        }
        System.out.println("total time:"+total);
       
    }
    private int print(int a,int total){
        System.out.println("<-速度为"+a+"的人回来,时间为:"+a);
        return total+a;
    }
    private int print(int a,int b,int total){
        System.out.println("->速度为"+a+"、"+b+"的人过河,时间为:"+(a>b?a:b));
        return total+(a>b?a:b);
    }
    public static void main(String[] args) {
        PassRiver p =  new PassRiver();
        p.pass();

    }
}

hjk @ 6/23/2007 11:57:21
这样做不知道对不对:

假设按速度从大到小排序,其速度为 v[0]...v[n-1]
那么最快的方法应该是由 速度为 v[0] 的人 ( 称其为 p[0] ) 与 p[1]一起过河,然后 p[0] 将氧气瓶送回,再与 p[2] 一起过河...最后 p0 与 p[n-1] 一起过河
设河宽为 L ,那么 p[0] 往回游的时间为 (n-1)*L/v[0] ,而过河时间分别为 L/v[1], L/v[2], ..., L/v[n-1]
故总时间 (n-1)*L/v[0] + L/v[1] + L/v[2] + ... + L/v[n-1]
流... @ 6/23/2007 17:50:15
上面的JAVA程序中 速度为x的人过河,写错了,实为过河时间为X的人过河...


楼上的想法不对,如{45,10,7,6,6,4,3,2,2}

第一趟为:2,2过河,2回来
第二趟为:45,10过河,2回来(另一个2)

这样时间才是比较短的...




流... @ 6/23/2007 18:19:15
改了下程序



import java.util.Arrays;


public class PassRiver {

    private int[] a = new int[]
                             //{1,2,4,5};
                             {45,10,7,6,6,4,3,2,2};
                             //{400,500,501,502,5005,5008};
                                 //{1,2,100,45,10,7,6,6,4};
    //private int[] b = new int[a.length];
   
    public void pass(){
       
        if(a.length==1){
            System.out.println("->速度为"+a[0]+"的人过河,时间为:"+a[0]);
            return;
        }
        if(a.length==2){
            System.out.println("->速度为"+a[0]+"、"+a[1]+"的人过河,时间为:"+(a[0]>a[1]?a[1]:a[1]));
            return;
        }   
        Arrays.sort(this.a);
        int total =0;
        int n = a.length-1;

        total = print(a[0],a[1],total);
        total=print(a[0],total);
        for(int j=n;j>=2;j--){
            if(j==2 ){
                total=print(a[0],a[j],total);
            }else if(a[j-1]+2*a[0]<=a[1]){
                total=print(a[0],a[j],total);
                total=print(a[0],total);
            }
            else if(a[j-1]==a[1] ){
                total=print(a[0],a[1],total);//b[j]=1;
                total=print(a[0],total);
            }
            else{
                total=print(a[j],a[j-1],total);//b[j]=1;b[j-1]=1;
                total=print(a[1],total);
                total=print(a[0],a[1],total);
                total=print(a[0],total);
                j--;
                if(j==2){
                    total=print(a[0],a[1],total);
                    break;
                }
            }
           
        }
        System.out.println("total time:"+total);
       
    }
    private int print(int a,int total){
        System.out.println("<-过河时间为"+a+"的人回来,时间为:"+a);
        return total+a;
    }
    private int print(int a,int b,int total){
        System.out.println("->过河时间为"+a+"、"+b+"的人过河,时间为:"+(a>b?a:b));
        return total+(a>b?a:b);
    }
    public static void main(String[] args) {
        PassRiver p =  new PassRiver();
        p.pass();

    }
}



{45,10,7,6,6,4,3,2,2}输出的结果是:


->过河时间为2、2的人过河,时间为:2
<-过河时间为2的人回来,时间为:2
->过河时间为45、10的人过河,时间为:45
<-过河时间为2的人回来,时间为:2
->过河时间为2、2的人过河,时间为:2
<-过河时间为2的人回来,时间为:2
->过河时间为7、6的人过河,时间为:7
<-过河时间为2的人回来,时间为:2
->过河时间为2、2的人过河,时间为:2
<-过河时间为2的人回来,时间为:2
->过河时间为6、4的人过河,时间为:6
<-过河时间为2的人回来,时间为:2
->过河时间为2、2的人过河,时间为:2
<-过河时间为2的人回来,时间为:2
->过河时间为2、3的人过河,时间为:3
total time:83
n @ 6/24/2007 16:22:39
以前听过类似的题,好像是尽量让速度差不多的人一起过去。
Nothing @ 7/23/2012 16:50:23
  要是不算最短时间呢?而是展示所有的情况

看帖要回帖...

Loading...


撩乱的城市...
midnight...

Free HTML Hit Counters

Dict.CN 在线词典, 英语学习, 在线翻译
categories
archives
links
statistics
  • 网志数:484
  • 评论数:648