如何用面向?qū)ο蠼鉀Q夜過吊橋問題

這篇文章主要講解了“如何用面向?qū)ο蠼鉀Q夜過吊橋問題”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“如何用面向?qū)ο蠼鉀Q夜過吊橋問題”吧！

創(chuàng)新互聯(lián)建站服務(wù)項(xiàng)目包括旺蒼網(wǎng)站建設(shè)、旺蒼網(wǎng)站制作、旺蒼網(wǎng)頁制作以及旺蒼網(wǎng)絡(luò)營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢(shì)、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，旺蒼網(wǎng)站推廣取得了明顯的社會(huì)效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到旺蒼省份的部分城市，未來相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

問題描述

1.五個(gè)人打算過一座吊橋，開始時(shí)他們都位于該橋的一側(cè)。

2.天很黑，五個(gè)人手里只有一個(gè)手電筒。

3.該橋一次最多只能同時(shí)過兩個(gè)人，無論是一個(gè)人還是兩個(gè)人過橋，都需要攜帶手電筒看路。而且手電筒只能通過人攜帶過橋的方式傳遞。

4.第一個(gè)人過橋需要1分鐘時(shí)間，第二個(gè)人過橋需要2分鐘，第三個(gè)人需要5分鐘，第四個(gè)需要7分鐘，第五個(gè)需要10分鐘。由于速度不同，兩個(gè)人一起過橋的話，速度以慢的人為準(zhǔn)。

問題：求最快過橋時(shí)間。要求寫出求解的算法。

如何用面向?qū)ο蠼鉀Q夜過吊橋問題

分析題目

1.從左邊到右邊，需要有一個(gè)人拿著手電筒，到達(dá)右邊后，需要有一個(gè)人折返回到左邊，那么怎么才能最大化的減少返回時(shí)間？

答：那么這個(gè)送回手電筒的人一定是右邊最快的。

2.兩人同時(shí)過橋，取最大時(shí)間，那怎么才能保證最大化的利用最長時(shí)間呢？

答：在左邊選最長時(shí)間的兩個(gè)人一起過橋。

3.怎么保證右邊折返回來回左邊的人所花的時(shí)間最短？

答：左邊選擇最快的兩個(gè)人一起到右邊，然后最快的折返回左邊，次快的等待最慢的兩個(gè)人過來后，再折返回左邊。重復(fù)這個(gè)步驟即可保證折返回左邊的人所花的時(shí)間最短。

我們來試著算一下，最短需要多長時(shí)間。

（1）選擇左邊最快的兩個(gè)人先過去，1分鐘和2分鐘的先過去，總共花費(fèi)2分鐘?，F(xiàn)在左邊5，7，10。右邊1，2。

（2）選擇右邊最快的一個(gè)人折返回來，1分鐘的回來，總共花費(fèi)2分鐘+1分鐘=3分鐘?，F(xiàn)在左邊5，7，10。右邊2。

（3）選擇左邊最慢的兩個(gè)人過去，7分鐘的和10分鐘的過去，總共花費(fèi)3分鐘+10分鐘=13分鐘?，F(xiàn)在左邊5，1。右邊2，7，10。

（4）選擇右邊最快的一個(gè)人折返回來，2分鐘的回來，總共花費(fèi)13分鐘+2分鐘=15分鐘?，F(xiàn)在左邊5，1，2。右邊7，10。

（5）選擇左邊最快的兩個(gè)人先過去，1分鐘和2分鐘的先過去，總共花費(fèi)15分鐘+2分鐘。現(xiàn)在左邊5。右邊7，10，1，2。

（6）選擇右邊最快的一個(gè)人折返回來，1分鐘的回來，總共花費(fèi)17分鐘+1分鐘=18分鐘?，F(xiàn)在左邊5，1。右邊7，10，2。

（5）選擇左邊最慢的兩個(gè)人過去，5分鐘的1分鐘的過去，總共花費(fèi)18分鐘+5分鐘=23分鐘。現(xiàn)在左邊沒有。右邊7，10，2，5，1。

總共花費(fèi)23分鐘。

總結(jié)一下上面的規(guī)律：

最快的兩個(gè)人過去，最快一個(gè)人回來，最慢的兩個(gè)人過去，最快的一個(gè)人回來。循環(huán)這個(gè)步驟。

怎么實(shí)現(xiàn)上面的算法？

這里我們可以用面向?qū)ο蟮姆椒ā?/p>

定義一個(gè)Person類。

包含的屬性：

（1）過橋速度Speed。（1分鐘/2分鐘/5分鐘/7分鐘/10分鐘）

（2）當(dāng)前在橋的哪一邊Side（左邊/右邊）

包含的方法：從左邊走到右邊的方法，或者從右邊折返回左邊的方法，命名為Pass(Side side);

定義一個(gè)接口IPassAction，包含一個(gè)方法void Pass(Side side);

定義一個(gè)枚舉類型Side，包含Left、Right

定義一個(gè)方法，在某一邊找過橋速度最慢的兩個(gè)人

List<Person> FindTwoFastSpeedPersons(List<Person> persons, Side side)

定義一個(gè)方法，在某一邊找過橋速度最快的兩個(gè)人

List<Person> FindTwoLowestSpeedPersons(List<Person> persons, Side side)

定義一個(gè)方法，在某一邊找過橋速度最慢的兩個(gè)人

Person FindFastSpeedPerson(List<Person> persons, Side side)

定義一個(gè)方法，檢測(cè)是否指定的person到達(dá)了指定的一邊

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)建日志記錄組件實(shí)例
            ILog log = log4net.LogManager.GetLogger(type);
            //記錄錯(cuò)誤日志

            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>
  <!--站點(diǎn)日志配置部分-->
  <log4net>
    <root>
      <!--控制級(jí)別，由低到高: ALL|DEBUG|INFO|WARN|ERROR|FATAL|OFF-->
      <!--比如定義級(jí)別為INFO，則INFO級(jí)別向下的級(jí)別，比如DEBUG日志將不會(huì)被記錄-->
      <!--如果沒有定義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é)果：

如何用面向?qū)ο蠼鉀Q夜過吊橋問題

注意：

這種算法只適合部分情況。比如5個(gè)人的過橋速度是1分鐘、10分鐘、11分鐘、12分鐘、13分鐘，則用這種算法算出來的56分鐘。但是如果1分鐘和其他四個(gè)人分別過橋，每次都是1分鐘的回來，則總時(shí)間是10+11+12+13+1*3=49（分鐘）。

感謝各位的閱讀，以上就是“如何用面向?qū)ο蠼鉀Q夜過吊橋問題”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對(duì)如何用面向?qū)ο蠼鉀Q夜過吊橋問題這一問題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！

文章名稱：如何用面向?qū)ο蠼鉀Q夜過吊橋問題
網(wǎng)站鏈接：http://muchs.cn/article36/igeosg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供商城網(wǎng)站、網(wǎng)站收錄、ChatGPT、微信公眾號(hào)、網(wǎng)站維護(hù)、品牌網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)

h5響應(yīng)式網(wǎng)站建設(shè)