版权声明:本文为博主原创文章未经博主允许不得转载。 /qq_/article/details/
在漆黑的夜里N位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话大家是无论如何也不敢过桥去的。不幸的是N个人一共只带了一只手电筒,而桥窄得只够让两个人同时过如果各自单独过桥的话,N人所需要的时间已知;而洳果两人同时过桥所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是如何设计一个方案,让这N人尽快过桥
这个問题的解决方案,充分体现了能者多劳(用时短的人必须多跑几次以便传递手电筒)也就是需要用到贪心算法。要么是最快的带最慢的然后回来带第二慢的,依次带完要么是最快的两个先过去,然后最快的把手电筒送回来让最慢的两个过去,然后让第二快的把手电筒送过来即将过河的人按其过河时间长短从大到小排序,设为对于时间排序得到S(1) <= S(2) .... S(n-1) <=
一个人过河时间肯定是S(1)
时间则为 S(1)+S(2)+S(3)
1.第一短的带最长的再回来带第二短的,依次带完
时间为:(N-2)S(1)+S(2)+······S(n);
2.第一短带第二短第一短回来,把手电给最长和第二長再让第二短回来,依次类推
由分析可知首先把每个人的过河时间存储到数组中再排序,然后通过集合让人和时间一一对应起来然後统计过桥时间及输出详细的过桥步骤,最后输出总时间java过桥问题程序分析框架如以下代码所示:
在原有框架上进行补充就可得到完整的java过桥问题程序分析
版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。