用面向对象解决「夜过吊桥」问题～
问题描述
1.五个人打算过一座吊桥，开始时他们都位于该桥的一侧。
2.天很黑，五个人手里只有一个手电筒。
3.该桥一次最多只能同时过两个人，无论是一个人还是两个人过桥，都需要携带手电筒看路。而且手电筒只能通过人携带过桥的方式传递。
4.第一个人过桥需要1分钟时间，第二个人过桥需要2分钟，第三个人需要5分钟，第四个需要7分钟，第五个需要10分钟。由于速度不同，两个人一起过桥的话，速度以慢的人为准。
问题：求最快过桥时间。要求写出求解的算法。
分析题目
1.从左边到右边，需要有一个人拿着手电筒，到达右边后，需要有一个人折返回到左边，那么怎么才能最大化的减少返回时间？
答：那么这个送回手电筒的人一定是右边最快的。
2.两人同时过桥，取最大时间，那怎么才能保证最大化的利用最长时间呢？
答：在左边选最长时间的两个人一起过桥。
3.怎么保证右边折返回来回左边的人所花的时间最短？
答：左边选择最快的两个人一起到右边，然后最快的折返回左边，次快的等待最慢的两个人过来后，再折返回左边。重复这个步骤即可保证折返回左边的人所花的时间最短。
我们来试着算一下，最短需要多长时间。
（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源创计划”，欢迎正在阅读的你也加入，一起分享。
- 上一篇
![优秀的自媒体个人博客,低调大师,许军]()
Pulsar：下一代消息引擎真的这么强吗？
背景 我们最近在做新业务的技术选型，其中涉及到了对消息中间件的选择；结合我们的实际情况希望它能满足以下几个要求： 友好的云原生支持：因为现在的主力语言是 Go，同时在运维上能够足够简单。 官方支持多种语言的 SDK：还有一些 Python、Java 相关的代码需要维护。 最好是有一些方便好用的特性，比如：延时消息、死信队列、多租户等。 当然还有一些水平扩容、吞吐量、低延迟这些特性就不用多说了，几乎所有成熟的消息中间件都能满足这些要求。 基于以上的筛选条件，Pulsar 进入了我们的视野。 作为 Apache 下的顶级项目，以上特性都能很好的支持。 下面我们来它有什么过人之处。 架构 从官方的架构图中可以看出 Pulsar 主要有以下组件组成： Broker 无状态组件，可以水平扩展，主要用于生产者、消费者连接；与 Kafka 的 broker 类似，但没有数据存储功能，因此扩展更加轻松。 BookKeeper 集群：主要用于数据的持久化存储。 Zookeeper 用于存储 broker 与 BookKeeper 的元数据。 整体一看似乎比 Kafka 所依赖的组件还多，这样确实会提供系...
- 下一篇
![优秀的自媒体个人博客,低调大师,许军]()
鸿蒙内核源码分析(编译环境篇) | 编译鸿蒙看这篇或许真的够了 | 百篇博客分析HarmonyOS源码 | v50.02
百万汉字注解 >> 精读鸿蒙源码,中文注解分析, 深挖地基工程,大脑永久记忆,四大码仓每日同步更新< gitee | github | csdn | coding > 百篇博客分析 >> 故事说内核,问答式导读,生活式比喻,表格化说明,图形化展示,主流站点定期更新中< oschina | 51cto | csdn | harmony > 编译鸿蒙 本篇记录编译鸿蒙的过程,以备后续不用再去一大堆无效的误导式软文中搜寻芝麻大点有用的信息,那样真挺费时的. 编译环境 先安装 Docker Desktop 下载windows版本一直下一步. 在windows下拉取openharmony-docker官方镜像,Docker方式获取编译环境 强烈推荐这么做. docker pull swr.cn-south-1.myhuaweicloud.com/openharmony-docker/openharmony-docker:0.0.3 2.36G, 拉取看网速, 大概10分钟后成功了,有了镜像 PS E:\harmony\kernel_liteos_a...
微信收款码
支付宝收款码