這篇文章主要講解了“如何用面向?qū)ο蠼鉀Q夜過吊橋問題”,文中的講解內(nèi)容簡單清晰,易于學習與理解,下面請大家跟著小編的思路慢慢深入,一起來研究和學習“如何用面向?qū)ο蠼鉀Q夜過吊橋問題”吧!
創(chuàng)新互聯(lián)建站服務項目包括旺蒼網(wǎng)站建設(shè)、旺蒼網(wǎng)站制作、旺蒼網(wǎng)頁制作以及旺蒼網(wǎng)絡營銷策劃等。多年來,我們專注于互聯(lián)網(wǎng)行業(yè),利用自身積累的技術(shù)優(yōu)勢、行業(yè)經(jīng)驗、深度合作伙伴關(guān)系等,向廣大中小型企業(yè)、政府機構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案,旺蒼網(wǎng)站推廣取得了明顯的社會效益與經(jīng)濟效益。目前,我們服務的客戶以成都為中心已經(jīng)輻射到旺蒼省份的部分城市,未來相信會繼續(xù)擴大服務區(qū)域并繼續(xù)獲得客戶的支持與信任!
1.五個人打算過一座吊橋,開始時他們都位于該橋的一側(cè)。
2.天很黑,五個人手里只有一個手電筒。
3.該橋一次最多只能同時過兩個人,無論是一個人還是兩個人過橋,都需要攜帶手電筒看路。而且手電筒只能通過人攜帶過橋的方式傳遞。
4.第一個人過橋需要1分鐘時間,第二個人過橋需要2分鐘,第三個人需要5分鐘,第四個需要7分鐘,第五個需要10分鐘。由于速度不同,兩個人一起過橋的話,速度以慢的人為準。
1.從左邊到右邊,需要有一個人拿著手電筒,到達右邊后,需要有一個人折返回到左邊,那么怎么才能最大化的減少返回時間?
答:那么這個送回手電筒的人一定是右邊最快的。
2.兩人同時過橋,取最大時間,那怎么才能保證最大化的利用最長時間呢?
答:在左邊選最長時間的兩個人一起過橋。
3.怎么保證右邊折返回來回左邊的人所花的時間最短?
答:左邊選擇最快的兩個人一起到右邊,然后最快的折返回左邊,次快的等待最慢的兩個人過來后,再折返回左邊。重復這個步驟即可保證折返回左邊的人所花的時間最短。
我們來試著算一下,最短需要多長時間。
(1)選擇左邊最快的兩個人先過去,1分鐘和2分鐘的先過去,總共花費2分鐘。現(xiàn)在左邊5,7,10。右邊1,2。
(2)選擇右邊最快的一個人折返回來,1分鐘的回來,總共花費2分鐘+1分鐘=3分鐘?,F(xiàn)在左邊5,7,10。右邊2。
(3)選擇左邊最慢的兩個人過去,7分鐘的和10分鐘的過去,總共花費3分鐘+10分鐘=13分鐘。現(xiàn)在左邊5,1。右邊2,7,10。
(4)選擇右邊最快的一個人折返回來,2分鐘的回來,總共花費13分鐘+2分鐘=15分鐘。現(xiàn)在左邊5,1,2。右邊7,10。
(5)選擇左邊最快的兩個人先過去,1分鐘和2分鐘的先過去,總共花費15分鐘+2分鐘?,F(xiàn)在左邊5。右邊7,10,1,2。
(6)選擇右邊最快的一個人折返回來,1分鐘的回來,總共花費17分鐘+1分鐘=18分鐘?,F(xiàn)在左邊5,1。右邊7,10,2。
(5)選擇左邊最慢的兩個人過去,5分鐘的1分鐘的過去,總共花費18分鐘+5分鐘=23分鐘?,F(xiàn)在左邊沒有。右邊7,10,2,5,1。
總共花費23分鐘。
總結(jié)一下上面的規(guī)律:
最快的兩個人過去,最快一個人回來,最慢的兩個人過去,最快的一個人回來。循環(huán)這個步驟。
這里我們可以用面向?qū)ο蟮姆椒ā?/p>
定義一個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; //創(chuàng)建日志記錄組件實例 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>
結(jié)果:
注意:
這種算法只適合部分情況。比如5個人的過橋速度是1分鐘、10分鐘、11分鐘、12分鐘、13分鐘,則用這種算法算出來的56分鐘。但是如果1分鐘和其他四個人分別過橋,每次都是1分鐘的回來,則總時間是10+11+12+13+1*3=49(分鐘)。
感謝各位的閱讀,以上就是“如何用面向?qū)ο蠼鉀Q夜過吊橋問題”的內(nèi)容了,經(jīng)過本文的學習后,相信大家對如何用面向?qū)ο蠼鉀Q夜過吊橋問題這一問題有了更深刻的體會,具體使用情況還需要大家實踐驗證。這里是創(chuàng)新互聯(lián),小編將為大家推送更多相關(guān)知識點的文章,歡迎關(guān)注!
文章名稱:如何用面向?qū)ο蠼鉀Q夜過吊橋問題
網(wǎng)站鏈接:http://bm7419.com/article36/igeosg.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供商城網(wǎng)站、網(wǎng)站收錄、ChatGPT、微信公眾號、網(wǎng)站維護、品牌網(wǎng)站制作
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請盡快告知,我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時需注明來源: 創(chuàng)新互聯(lián)