问题描述
1.五我的打算过一座吊桥,开始时他们都位于该桥的一侧。算法
2.天很黑,五我的手里只有一个手电筒。app
3.该桥一次最多只能同时过两我的,不管是一我的仍是两我的过桥,都须要携带手电筒看路。并且手电筒只能经过人携带过桥的方式传递。ide
4.第一我的过桥须要1分钟时间,第二我的过桥须要2分钟,第三我的须要5分钟,第四个须要7分钟,第五个须要10分钟。因为速度不一样,两我的一块儿过桥的话,速度以慢的人为准。spa
问题:求最快过桥时间。要求写出求解的算法。
分析题目
1.从左边到右边,须要有一我的拿着手电筒,到达右边后,须要有一我的折返回到左边,那么怎么才能最大化的减小返回时间?.net
答:那么这个送回手电筒的人必定是右边最快的。日志
2.两人同时过桥,取最大时间,那怎么才能保证最大化的利用最长时间呢?code
答:在左边选最长时间的两我的一块儿过桥。xml
3.怎么保证右边折返回来回左边的人所花的时间最短?对象
答:左边选择最快的两我的一块儿到右边,而后最快的折返回左边,次快的等待最慢的两我的过来后,再折返回左边。重复这个步骤便可保证折返回左边的人所花的时间最短。blog
咱们来试着算一下,最短须要多长时间。
(1)选择左边最快的两我的先过去,1分钟和2分钟的先过去,总共花费2分钟。如今左边5,7,10。右边1,2。
(2)选择右边最快的一我的折返回来,1分钟的回来,总共花费2分钟+1分钟=3分钟。如今左边5,7,10。右边2。
(3)选择左边最慢的两我的过去,7分钟的和10分钟的过去,总共花费3分钟+10分钟=13分钟。如今左边5,1。右边2,7,10。
(4)选择右边最快的一我的折返回来,2分钟的回来,总共花费13分钟+2分钟=15分钟。如今左边5,1,2。右边7,10。
(5)选择左边最快的两我的先过去,1分钟和2分钟的先过去,总共花费15分钟+2分钟。如今左边5。右边7,10,1,2。
(6)选择右边最快的一我的折返回来,1分钟的回来,总共花费17分钟+1分钟=18分钟。如今左边5,1。右边7,10,2。
(5)选择左边最慢的两我的过去,5分钟的1分钟的过去,总共花费18分钟+5分钟=23分钟。如今左边没有。右边7,10,2,5,1。
总共花费23分钟。
总结一下上面的规律:
最快的两我的过去,最快一我的回来,最慢的两我的过去,最快的一我的回来。循环这个步骤。
怎么实现上面的算法?
这里咱们能够用面向对象的方法。
定义一个Person类。
包含的属性:
(1)过桥速度Speed。(1分钟/2分钟/5分钟/7分钟/10分钟)
(2)当前在桥的哪一边Side(左边/右边)
包含的方法:从左边走到右边的方法,或者从右边折返回左边的方法,命名为Pass(Side side);
定义一个接口IPassAction,包含一个方法void Pass(Side side);
定义一个枚举类型Side,包含Left、Right
定义一个方法,在某一边找过桥速度最慢的两我的
List<Person> FindTwoFastSpeedPersons(List<Person> persons, Side side)
定义一个方法,在某一边找过桥速度最快的两我的
List<Person> FindTwoLowestSpeedPersons(List<Person> persons, Side side)
定义一个方法,在某一边找过桥速度最慢的两我的
Person FindFastSpeedPerson(List<Person> persons, Side side)
定义一个方法,检测是否指定的person到达了指定的一边
CheckPersonsPassedToTargetSide(List<Person> persons, Side targetSide)
代码
Person类
namespace PassRiver2._0 { public class Person : IPassAction { private int _speed; private Side _side; public Person(int speed, Side side) { _speed = speed; _side = side; } public int Speed { get { return _speed; } set { _speed = value; } } public Side Side { get { return _side; } set { _side = value; } } public void Pass(Side side) { _side = side; } } }
Side枚举类
namespace PassRiver2._0 { public enum Side { Left = 0, Right = 1 } }
IPassAction接口
namespace PassRiver2._0 { public interface IPassAction { void Pass(Side side); } }
公共方法
List<Person> FindTwoFastSpeedPersons(List<Person> persons, Side side)
List<Person> FindTwoLowestSpeedPersons(List<Person> persons, Side side)
Person FindFastSpeedPerson(List<Person> persons, Side side)
CheckPersonsPassedToTargetSide(List<Person> persons, Side targetSide)
private static List<Person> FindTwoLowestSpeedPersons(List<Person> persons, Side side) { List<Person> sortedPersons = persons.Where(s=> s.Side == side).OrderByDescending(s => s.Speed).ToList(); List<Person> passedPersons = new List<Person>(); if (persons.Count > 1) { passedPersons = new List<Person>(); passedPersons.Add(sortedPersons[0]); passedPersons.Add(sortedPersons[1]); } else if (persons.Count == 1) { passedPersons.Add(sortedPersons[0]); } else { } return passedPersons; } private static List<Person> FindTwoFastSpeedPersons(List<Person> persons, Side side) { List<Person> sortedPersons = persons.Where(s=> s.Side == side).OrderBy(s => s.Speed).ToList(); List<Person> passedPersons = new List<Person>(); if (persons.Count > 1) { passedPersons = new List<Person>(); passedPersons.Add(sortedPersons[0]); passedPersons.Add(sortedPersons[1]); } else if (persons.Count == 1) { passedPersons.Add(sortedPersons[0]); } else { return null; } return passedPersons; } private static Person FindFastSpeedPerson(List<Person> persons, Side side) { if (persons.Count > 0) { List<Person> sortedPersons = persons.Where(s => s.Side == side).OrderBy(s => s.Speed).ToList(); return sortedPersons[0]; } else { return null; } } private static bool CheckPersonsPassedToTargetSide(List<Person> persons, Side targetSide) { bool isPassed = false; foreach (Person person in persons) { if (person.Side != targetSide) { isPassed = false; return isPassed; } } isPassed = true; return isPassed; }
Main方法
static void Main(string[] args) { Type type = MethodBase.GetCurrentMethod().DeclaringType; //建立日志记录组件实例 ILog log = log4net.LogManager.GetLogger(type); //记录错误日志 log.Info("Start"); List<Person> persons = new List<Person>(); persons.Add(new Person(1, Side.Left)); persons.Add(new Person(2, Side.Left)); persons.Add(new Person(5, Side.Left)); persons.Add(new Person(7, Side.Left)); persons.Add(new Person(10, Side.Left)); int totalTime = 0; while (!CheckPersonsPassedToTargetSide(persons, Side.Right)) { List<Person> twoFastSpeedPersons = FindTwoFastSpeedPersons(persons, Side.Left); foreach (Person person in twoFastSpeedPersons) { person.Pass(Side.Right); } if (twoFastSpeedPersons.Count > 1) { totalTime += twoFastSpeedPersons[1].Speed; } else if (twoFastSpeedPersons.Count == 1) { totalTime += twoFastSpeedPersons[0].Speed; } else { } //------------- log.Info("---Go To Right---------->"); foreach (Person person in twoFastSpeedPersons) { log.Info(person.Speed); } log.Info("Total Time:" + totalTime); //------------- if (CheckPersonsPassedToTargetSide(persons, Side.Right)) { break; } Person fastSpeedPerson = FindFastSpeedPerson(persons, Side.Right); fastSpeedPerson.Pass(Side.Left); totalTime += fastSpeedPerson.Speed; //------------- log.Info("<----------Go Back Left---"); log.Info(fastSpeedPerson.Speed); log.Info("Total Time:" + totalTime); //------------- if (CheckPersonsPassedToTargetSide(persons, Side.Right)) { break; } List<Person> twoLowestSpeedPersons = FindTwoLowestSpeedPersons(persons, Side.Left); foreach (Person person in twoLowestSpeedPersons) { person.Pass(Side.Right); } totalTime += twoLowestSpeedPersons[0].Speed; //------------- log.Info("---Go To Right---------->"); foreach (Person person in twoLowestSpeedPersons) { log.Info(person.Speed); } log.Info("Total Time:" + totalTime); //------------- if (CheckPersonsPassedToTargetSide(persons, Side.Right)) { break; } fastSpeedPerson = FindFastSpeedPerson(persons, Side.Right); fastSpeedPerson.Pass(Side.Left); totalTime += fastSpeedPerson.Speed; //------------- log.Info("<----------Go Back Left---"); log.Info(fastSpeedPerson.Speed); log.Info("totalTime:" + totalTime); //------------- if (CheckPersonsPassedToTargetSide(persons, Side.Right)) { break; } } log.Info("------------Total Time-------------"); log.Info(totalTime); Console.ReadKey(); }
Log4Net配置:
<?xml version="1.0"?> <configuration> <configSections> <section name="log4net" type="log4net.Config.Log4NetConfigurationSectionHandler,log4net"/> </configSections> <!--站点日志配置部分--> <log4net> <root> <!--控制级别,由低到高: ALL|DEBUG|INFO|WARN|ERROR|FATAL|OFF--> <!--好比定义级别为INFO,则INFO级别向下的级别,好比DEBUG日志将不会被记录--> <!--若是没有定义LEVEL的值,则缺省为DEBUG--> <level value="DEBUG"/> <appender-ref ref="PassRiverLogger2"/> </root> <appender name="PassRiverLogger2" type="log4net.Appender.ConsoleAppender"> <layout type="log4net.Layout.PatternLayout"> <conversionPattern value="%date [%thread] %-5level %logger - %message%newline" /> </layout> </appender> </log4net> </configuration>
结果:
注意:
这种算法只适合部分状况。好比5我的的过桥速度是1分钟、10分钟、11分钟、12分钟、13分钟,则用这种算法算出来的56分钟。可是若是1分钟和其余四我的分别过桥,每次都是1分钟的回来,则总时间是10+11+12+13+1*3=49(分钟)。
本文同步分享在 博客“7年一线互联网经验,超爱图解底层原理,全栈一枚”(CNBlog)。
若有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一块儿分享。