• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 100,  comments - 15,  trackbacks - 0

            結論一:?哪去了?

            結論二:
            一定有這樣一種最佳方案,在這個方案里,所有從彼岸到此岸的移動只需一個人?! ∪绻罴逊桨钢杏幸徊街行枰獌蓚€人從彼岸移動到此岸,那么我們可以把這一步改為只移動比較快的那個人。

            結論三:
            一定有這樣一種符合結論二的最佳方案,在這個方案里,所有從彼岸到此岸的移動中,回來的這個人一定是當時在彼岸所有人中速度最快的。 

            結論四:
            一定有這樣一種符合結論二—三的最佳方案,在這個方案里,每當出現手電筒在此岸的局面時,速度最快的那個人總是在此岸。


            結論五:
            一定有這樣一種符合結論二—四的最佳方案,在這個方案里,所有從此岸到彼岸的移動都需兩個人。


            結論六:
            一定有這樣一種符合結論二—五的最佳方案,在這個方案里,每次從此岸到彼岸移動兩人,要么這兩人里有一個是所有人中最快的那個,要么這兩人到達彼岸后都再也不回來?!  ?/p>


            結論七:
            一定有這樣一種符合結論二—六的最佳方案,在這個方案里,所有從彼岸到此岸的移動中,回來的這個人一定是當時在彼岸所有人中速度最快的,而且他只能是所有人中最快的或者次快的。 
            換句話說,所有返回此岸的任務都可以只由跑得最快和跑得次快的人來擔當,所有其他人一旦到達彼岸,就留在那里,再也不回來。

            結論八:
            一定有這樣一種符合結論二—七的最佳方案,在這個方案里,所有除了最快和次快的旅行者都以上面兩個模式過橋,并且再不回來。


            假設A為最快,B為次快,而Z是任意一個其他旅行者。
            模式一:由A護送到Z對岸,A返回
            模式二:AB->,A<-,YZ->,B<-

            結論九:所有符合結論八的最佳方案中,最慢兩人過橋的模式必須相同,而且如果使用的都是模式二,那么他們一定在一起過河。

            結論 
             如果給定N個(速度不同)的旅行者,根據結論九我們知道有一個最佳方案,在最初的4步里用模式一或模式二把最慢的兩個旅行者移動到彼岸,于是問題被約化成N-2個旅行者的形式。問題在于應該選擇哪一種模式。繼續假設A、B為走得最快和次快的旅行者,過橋所需時間分別為a、b;而Z、Y為走得最慢和次慢的旅行者,過橋所需時間分別為z、y?! ?br>在第六節中我們發現
            使用模式一移動Z和Y到彼岸所需的時間為:z + a + y + a
            使用模式二移動Z和Y到彼岸所需的時間為:b + a + z + b
            所以,   
            當2b>a+y時,應該使用模式一;
            當2b<a+y時,應該使用模式二 
            當2b=a+y時,使用模式一或二都可以。  
            上面的討論都是在N≥4時進行的,那時最快、次快、最慢和次慢是四個不同的人。所以我們還要稍微討論一下N=1、2、3的情況。  N=1、2是不用動腦子的,直接通通過橋就是了?!?br>N=3也很簡單,用窮舉法可以發現由最快的人往返一次把其他兩人送過河是最快的方法。  
            于是我們得到了最終結論:最佳方案構造法:
            以下是構造N個人(N≥1)過橋最佳方案的方法:  
            1) 如果N=1、2,所有人直接過橋?! ?br>2) 如果N=3,由最快的人往返一次把其他兩人送過河?!?br>3) 如果N≥4,設A、B為走得最快和次快的旅行者,過橋所需時間分別為a、b;而Z、Y為走得最慢和次慢的旅行者,過橋所需時間分別為z、y。
            那么  
            當2b>a+y時,使用模式一將Z和Y移動過橋;    
            當2b<a+y時,使用模式二將Z和Y移動過橋;   
            當2b=a+y時,使用模式一將Z和Y移動過橋。
            這樣就使問題轉變為N-2個旅行者的情形,從而遞歸解決之。
             
             最后當然我們要舉一個具體的例子:七個旅行者,所需過橋時間分別是1、4、5、5、5、8、9分鐘?! ?br>我們假設他們順次為A、B、C、D、E、F、G,我們注意到C、D、E的速度一樣,用第二節的方法太正規也太麻煩,我們可以人為規定C速度稍稍大于D,D速度又稍稍大于E。
            采用結論十的方法,最快和次快的是A、B,時間為1和4;最慢和次慢的是G和F,時間為9和8。
            現在2*4<1+9,所以用模式二:
            第1步:      A B →  4
            第2步:       A ←  1
            第3步:      F G →  9
            第4步:       B ←  4
            現在剩下A、B、C、D、E在此岸,最快和次快的是A、B,時間為1和4;最慢和次慢的是E和D,時間為5和5。
            現在2*4>1+5,所以用模式一:
            第5步:      A E →  5
            第6步:       A ←  1
            第7步:      A D →  5
            第8步:       A ←  1
            現在剩下A、B、C在此岸,用N=3的辦法結束:
            第9步:      A C →  5
            第10步:       A ←  1
            第11步:      A B →  4
            總的時間為    4+1+9+4+5+1+5+1+5+1+4 = 40分鐘
            雖然我一個其他的方案都沒列舉,我知道這個40分鐘的方案必定是最佳的。

            posted on 2009-07-08 22:38 wyiu 閱讀(719) 評論(0)  編輯 收藏 引用
            久久精品国产一区二区三区不卡| 久久午夜福利电影| 国产欧美久久久精品影院| 久久久免费精品re6| 久久国语露脸国产精品电影| 婷婷久久综合九色综合九七| 久久99久久成人免费播放| 精品多毛少妇人妻AV免费久久| 久久精品午夜一区二区福利| 一本色道久久88综合日韩精品 | 亚洲国产精品成人久久| 久久大香萑太香蕉av| 久久久久免费精品国产| 亚洲狠狠婷婷综合久久蜜芽| 久久久久亚洲AV无码专区首JN| 久久天天躁狠狠躁夜夜躁2014| 久久精品国产精品亚洲精品| 精品久久久久久久久免费影院| 亚洲av成人无码久久精品| 国内精品久久久久久99蜜桃 | 久久精品国产一区二区三区| 久久精品国产精品亚洲| 7777精品伊人久久久大香线蕉| 久久天天躁夜夜躁狠狠躁2022| 欧美亚洲国产精品久久| 久久精品卫校国产小美女| 久久99精品国产自在现线小黄鸭| 久久国产福利免费| 久久伊人精品青青草原日本| 久久久久久免费视频| 国产精品一区二区久久| 国内精品久久久久久久coent | 色妞色综合久久夜夜| 97久久精品人人做人人爽| 亚洲精品国精品久久99热| 久久精品人人槡人妻人人玩AV | 香蕉aa三级久久毛片| 日韩精品无码久久久久久| 精品久久国产一区二区三区香蕉| 欧美伊人久久大香线蕉综合| 久久99精品国产|