  1public class BrigeAcross
  2{
  3    private int[] passed, waiting;
  4    private int sum = 0, size = 0;
  5
  6    /// 
  7    /// 过桥
  8    /// 
  9    /// 数组地址
 10    /// 数组地址
 11    /// 类型,1:过桥,2:回来
 12    private void SetCross(int index1, int index2,int type)
 13    {
 14        if (type == 1)
 15        {
 16            Console.Write("过去:"+waiting[index1].ToString()+","+waiting[index2].ToString());
 17            if (waiting[index1] < waiting[index2]) sum += waiting[index2]; else sum += waiting[index1];
 18            passed[index1] = waiting[index1]; passed[index2] = waiting[index2];
 19            waiting[index1] = 0; waiting[index2] = 0;
 20        }
 21        else
 22        {
 23            Console.Write("回来"+passed[index1].ToString() + "," + passed[index2].ToString());
 24            if (passed[index1] < passed[index2]) sum += passed[index2]; else sum += passed[index1];
 25            waiting[index1] = passed[index1]; waiting[index2] = passed[index2];
 26            passed[index1] = 0; passed[index2] = 0;
 27        }
 28    }
 29    /// 
 30    /// 过桥
 31    /// 
 32    /// 数组地址
 33    /// 类型,1:过桥,2:回来
 34    private void SetCross(int index1, int type)
 35    {
 36        if (type == 1)
 37        {
 38            Console.Write("回来" + waiting[index1].ToString());
 39            sum += waiting[index1];
 40            passed[index1] = waiting[index1];
 41            waiting[index1] = 0;
 42        }
 43        else
 44        {
 45            Console.Write("回来" + passed[index1].ToString());
 46            sum += passed[index1];
 47            waiting[index1] = passed[index1];
 48            passed[index1] = 0;
 49        }
 50    }
 51
 52    /// 
 53    /// 获得实际长度
 54    /// 
 55    /// 类型,1:过桥,2:回来
 56    private int GetLength(int type)
 57    {
 58        int len = 0;
 59        if (type == 1) { for (int i = 0; i < size; i++) if (waiting[i] != 0) len++; }
 60        else { for (int i = 0; i < size; i++) if (passed[i] != 0) len++; }
 61        return len;
 62    }
 63
 64    /// 
 65    /// 获得最小值
 66    /// 
 67    /// 类型,1:过桥,2:回来
 68    private int GetMin(int type)
 69    {
 70        if (type == 1) { for (int i = 0; i < size; i++) if (waiting[i] != 0) return i; }
 71        else { for (int i = 0; i < size; i++) if (passed[i] != 0) return i; }
 72        return 0;
 73    }
 74
 75    /// 
 76    /// 获取数组中第N大值
 77    /// 
 78    /// 类型,1:过桥,2:回来
 79    /// 数组中第N大值
 80    /// 
 81    private int GetMax(int type,int num)
 82    {
 83        int j = 1;
 84        if (type == 1) { for (int i = size-1; i > 0; i--) if (waiting[i] != 0) { if (j == num)return i; else j++; } }
 85        else { for (int i = size-1; i > 0; i--) if (passed[i] != 0) { if (j == num)return i; else j++; } }
 86        return 0;
 87    }
 88
 89    public void StartPass()
 90    {
 91        Console.Write("第1轮");
 92        SetCross(0, 1, 1);//过桥
 93        SetCross(0, 2);//回来
 94        Console.WriteLine();
 95        //第一轮结束
 96        for (int i = 0; i < size - 2; i++)
 97        {
 98            Console.Write("第"+(i+2).ToString()+"轮");
 99            if (GetLength(1) > 3)
100            {
101                SetCross(GetMax(1, 1), GetMax(1, 2), 1);//过桥
102                SetCross(GetMin(2), 2);//回来
103            }
104            else
105            {
106                SetCross(GetMin(1),GetMax(1,1),1);
107                if (i < size - 3)
108                    SetCross(GetMin(2), 2);//回来
109            }
110            Console.WriteLine();
111        }
112        Console.WriteLine("总计时间为：" + sum.ToString());
113    }
114
115    public void Go()
116    {
117        size = int.Parse(Console.ReadLine());
118        waiting = new int[size]; passed = new int[size];
119        Random rd = new Random();
120
121        for (int i = 0; i < size; i++)
122        {
123            waiting[i] = rd.Next(i, size + 10);
124            Console.WriteLine("第" + (i + 1).ToString() + "个人的过桥时间为：" + waiting[i].ToString());
125        }
126        Console.WriteLine("");
127
128        int sortTmp = 0;
129        for (int i = 0; i < size; i++)
130        {
131            for (int j = i + 1; j < size; j++)
132            {
133                if (waiting[i] > waiting[j])
134                {
135                    sortTmp = waiting[i];
136                    waiting[i] = waiting[j];
137                    waiting[j] = sortTmp;
138                }
139            }
140        }
141
142        for (int i = 0; i < size; i++)
143        {
144            Console.WriteLine("第" + (i + 1).ToString() + "个人的过桥时间为：" + waiting[i].ToString());
145        }
146        Console.WriteLine("");
147        StartPass();//开始过桥
148        Console.Read();
149    }
150}

new BrigeAcross().Go();

题目是一个FLASH中的启发:
晚上天黑,有一坐桥,有五个人A.B.C.D.E要此过桥,现在有一盏灯只能亮30秒.A过此桥要1秒,B需要3秒,C需要6秒,而D需要8秒,E则需要12秒.现在只能两两一组过此桥.过桥时间最大值.比如,E和B一起过桥.则需要12秒.C和D一起过桥则需要8秒.然后还要有一个回来送灯的人.问30秒内怎么让这5个人都过桥?
接着说下核心算法:
N个人过桥消耗时间计算步骤如下:

1.开始从等待队伍中选取最小过桥消耗时间的两个过桥进入已过桥队伍中
2.从已过桥队伍中选取最短过桥消耗时间的人回去到等待队伍中.
3.从这里开始有1个分支:
当人数大于三人时:选取等待队伍中最大和第二大过桥时间的人到已过桥队伍中回来时按2回来
当人数不大于三人时:选取队伍中最小和最大过桥时间的人到已过桥队伍中回来时按2回来
4.循环2~3可得出结果.

结果:

ITPub博客

算法N人过桥,不知是否是最短了!

最新文章