这篇文章主要讲解了“如何用面向对象解决夜过吊桥问题”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“如何用面向对象解决夜过吊桥问题”吧!
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(分钟)。
感谢各位的阅读,以上就是“如何用面向对象解决夜过吊桥问题”的内容了,经过本文的学习后,相信大家对如何用面向对象解决夜过吊桥问题这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是亿速云,小编将为大家推送更多相关知识点的文章,欢迎关注!
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。
原文链接:https://my.oschina.net/u/4499317/blog/5028582