和吴昊一起玩推理 Round 2 —— 蚂蚁爬杆问题
Problem:有一根27厘米長的細木桿，在第3厘米，7厘米，11厘米，17厘米，23厘米,這五個位置上各有一只螞 蟻，木桿很細，不能同時通過兩只螞蟻，開始時，螞蟻的頭朝向左還是右是任意的，他們只會朝前走或掉頭，但不會后退,當兩只螞蟻相遇后，螞蟻會同時掉頭朝反 方向走，假設螞蟻們每秒鐘可以走1厘米的距離。求所有螞蟻都離開木桿的最小時間和最大時間。
?
一刻推理：首 先可以想到的一個方法，就是模擬算法，沒有錯，由于這些螞蟻都有其相似的地方，故可以歸為一個類，而有多少個螞蟻，就有多少個對象。問題是，這樣做，確實 是可以詳細描述出這些螞蟻活動的全過程，但是，問題要去的是，我們只需要求出所有螞蟻離開木桿的最小時間（MinTime）和最大時間(MaxTime) 即可，我們當然可以嘗試左右情況，但是，問題是，假設所有的螞蟻的數量為n，則需要嘗試的總次數為O（2^n），這樣是NP難的，有木有更神奇的方法？
二刻推理：通過聯(lián)想，很容易想到那位老外給蘇步青的一個難題，也就是說，一只狗在兩個人之間來回以相同的速度跑，我們是否需要詳細地模擬全過程？當極限的概念未知的情況下，此問題甚至是無解的！想到這里，我們應該可以得到，必須要跳開這種純粹模擬的思維，尋找更玄妙的途徑。
三刻推理：如 果題目條件沒有那么“強”，比如，桿子沒有細到不能同時通過兩只螞蟻，如果可以通過兩只螞蟻，甚至是更多的螞蟻，無非就是一個純粹的O（n）可以解決的問 題了，但是，有些問題，適當地放寬條件，問題還是成立的！本題在比較弱的條件下可以成立，那么，能不能在加強版的條件下仍然成立呢？
四刻推理：由于螞蟻都是完全相同的，我們可以悟到一點，也就是說，兩個螞蟻如果碰撞的話，其中一只螞蟻可以“穿過”另外一只螞蟻的身體，想到了這一點，問題迎刃而解了。NP難問題化為了一個時間復雜度為O（n）的問題！這就是推理帶來的效果。
?2?#include?"stdafx.h"
?3?#include?<iostream>
?4?using?namespace?std;
?5?
?6?*/
?7?根據題意：兩只螞蟻相遇后，各自掉頭朝相反方向走。但是，我們可以“看著”
?8?兩只螞蟻相遇后，擦肩而過，即，認為螞蟻是相互獨立的，是否碰頭沒什么關
?9?系。
10?所有螞蟻都離開木桿的最小時間為
11? max(min(3,27-3),min(7,27-7),?min(11,27-11),?min(17,27-17),min(23,27-23))=11
12?所有螞蟻都離開木桿的最大時間為
13? max(max(3,27-3),max(7,27-7),?max(11,27-11),?max(17,27-17),max(23,27-23))=24
14?*/
15?
16?void?antCrawlTime(double?length,???????//length?of?stick
17?????????????????????????????????double?*xPos,???????//position?of?an?ant,<=length
18?????????????????????????????????int?antNum,??????????????//number?of?ant
19?????????????????????????????????double?speed,??????//speed?of?crawl
20?????????????????????????????????double?&min,????????//min?of?leave?time
21?????????????????????????????????double?&max)???????//max?of?leave?time
22?{
23?????double?totalTime=length/speed;
24?????min=0;
25?????max=0;
26?????for(int?i=0;i<antNum;i++)
27?????{
28?????????double?tmpMin=0;
29?????????double?tmpMax=0;
30?????????if(xPos[i]<length/2)
31?????????{
32?????????????tmpMax=(length?-?xPos[i])/speed;
33?????????}
34?????????else
35?????????{
36?????????????tmpMax=xPos[i]/speed;
37?????????}
38?????????tmpMin=totalTime-tmpMax;
39?
40?????????if(max<tmpMax)
41?????????{
42?????????????max=tmpMax;
43?????????}
44?????????if(min<tmpMin)
45?????????{
46?????????????min=tmpMin;
47?????????}
48?????}
49?}
50?
51?int?_tmain(int?argc,?_TCHAR*?argv[])
52?{
53?????double?xPos[]={3,7,11,17,23};
54?????double?min,max;
55?????antCrawlTime(27,xPos,5,1,min,max);
56?????cout<<"min:"<<min<<"***max:"<<max<<endl;
57?????return?0;
58?}
拓展推理：博客上有網友更進一步地提出了如下五個問題，這里給出博客上的詳細信息以及解答，其中，[Math Processing Error]為一個數字，可能是相關的編碼錯誤吧！
擴展1的解答
現 在來解決擴展1。這個解答甚是精妙，通俗點來說，我們假設每只螞蟻都背著一袋糧食，任意兩只螞蟻碰頭時交換各自的糧食然后調頭。這種情況下，每次 有一只螞蟻離開木桿都意味著一袋糧食離開木桿（雖然可能已經不是它剛開始時背的那一袋了）。于是，我們可以求出每袋糧食離開木桿的時間（因為糧食是不會調 頭的）。又由于每袋糧食離開木桿的時間都對應某只螞蟻離開木桿的時間，這是一種一一映射關系。現在我們要找到對應于第[Math Processing Error]只螞蟻的那個映射。在此之前需要證明一個命題：
若一開始時有[Math Processing Error]只螞蟻向左走，[Math Processing Error]只螞蟻向右走，則最終會有[Math Processing Error]只螞蟻從木桿左邊落下，[Math Processing Error]只螞蟻從木桿右邊落下。
這個命題很容易證明：每次碰撞 均不改變向左和向右的螞蟻數量。于是，由于每次碰撞螞蟻都會調頭而不是穿過，最后必定是前[Math Processing Error]只螞蟻從左邊落下，后[Math Processing Error]只螞蟻從木桿右邊落下。由于我們知道每袋糧食是從哪邊落下的，故左邊落下的[Math Processing Error]袋糧食的離開木桿的時間就對應于前[Math Processing Error]只螞蟻離開木桿的時間，右邊的類似。因此，我們只需判斷[Math Processing Error]和[Math Processing Error]的關系，便知道第[Math Processing Error]只螞蟻是從左邊還是右邊落下。不妨假設是從左邊落下，因此該螞蟻落下的時間就等于從左邊落下的第[Math Processing Error]袋糧食的落下時間。時間復雜度[Math Processing Error]，一遍掃描搞定。
擴展2的解答
對 于擴展2，我們只需求得每個螞蟻的碰撞次數，然后累加即可。在這里我們換一種思路，把碰撞調頭看成不調頭而繼續(xù)向前（穿過），則容易看出原問題 （碰撞次數）就變?yōu)榍蟠┻^的次數（因為速度大小不變，原來的每次碰撞都對應于現在的一次穿過）。則對于每只向左的螞蟻，它只會“穿過”那些在它左邊的向右 走的螞蟻。因此，每只螞蟻“穿過”的螞蟻次數等于剛開始時在它前進方向上與它前進方向相反的螞蟻個數。時間復雜度也是[Math Processing Error]。改為用糧食的觀點來理解也是可以的。
擴展3的解答
第3個擴展問 題有點復雜。首先我們假設[Math Processing Error]為0.5個單位長度每秒，每個螞蟻剛開始時都處于整點處，這樣每次碰撞都發(fā)生在整秒處。這個假設有個好處，就是我們可以二分第[Math Processing Error]次 碰撞的時刻。如果碰撞時刻是浮點數，這個二分有可能永遠不會終止。我們還是看成每個螞蟻馱著一袋糧食，那么每袋糧食易主（即從一個螞蟻身上交換到另一個螞 蟻身上）時，就發(fā)生了一次碰撞。由于糧食的方向是固定不變的，我們可以很容易求出每一袋糧食在它的“前進”方向上的所有易主時刻（它易主的次數等于擴展2 中的“穿過”次數）。這樣，我們的問題就等價于：
找到最小的時間[Math Processing Error]，使得易主時刻小于或等于[Math Processing Error]的易主次數大于或等于[Math Processing Error]。
由 于現在所有碰撞（易主）的時刻都是整點，故我們可以二分[Math Processing Error]，然后用線性復雜度找出易主時刻小于或等于[Math Processing Error]的易主次數。整個復雜度為[Math Processing Error]，其中maxt和mint分別表示第一次和最后一次碰撞的時刻，均可在[Math Processing Error]時間內求出。
在上一段中，要想使用線性時間復雜度求出易主時刻小于或等于[Math Processing Error]的易主次數還需要一點技巧。可以這樣：用一個數組[Math Processing Error]表示第[Math Processing Error]個向右走的螞蟻的初始位置，當掃描到第[Math Processing Error]個向左走的螞蟻時，假設得到的中值點為[Math Processing Error]（即[Math Processing Error]到第[Math Processing Error]個位置上對應的糧食和該袋糧食的易主時刻均大于[Math Processing Error]）。由于該袋糧食向左易主的時刻是遞增的，而下一個向左走的螞蟻的初始位置又大于當前（第[Math Processing Error]個向左走的）螞蟻，故對于下一個螞蟻ant來說，[Math Processing Error]到第[Math Processing Error]個位置上對應的糧食和ant所馱糧食的易主時刻也一定大于[Math Processing Error]。即中值點的位置是單調的。因此可以在均攤[Math Processing Error]的時間內算出所求個數。
求出時刻的 同時我們也求出了位置，故第二小問也解決。接下來要求哪兩個螞蟻發(fā)生了這次碰撞（如果同時存在多個碰撞求出任意一個即可）。其實，我們只需要求出每袋糧食 在[Math Processing Error]時刻的位置即可。因為每袋糧食必然對應于一個馱著它的螞蟻，故我們只需對這些糧食的位置排序，找出位置相同的糧食以及其下標（即從左到右第幾 個），也就找出了那對螞蟻了。
擴展4的解答
對于第4個擴展，只要求出每只螞蟻的 碰撞次數即可。這也解決了擴展2的解答中原始思路。首先由擴展1的解答我們可以知道每只螞蟻最終是往左還是右掉下去，然后假設第[Math Processing Error]只螞蟻最終往左掉下，而開始時刻其左邊有[Math Processing Error]只向右走的螞蟻，則它至少要朝左邊碰撞[Math Processing Error]次才能把左邊的螞蟻全撞成向左的狀態(tài)。倘若它一開始就是向左的，則共要碰撞[Math Processing Error]次，否則為[Math Processing Error]次。這樣利用一個數組和幾個計數器仍能在[Math Processing Error]時間內求出每個螞蟻的碰撞次數，取最大那個即可。
擴展5的解答
這個 問題看起來挺復雜，其實很簡單。假設環(huán)長為[Math Processing Error]，則一個螞蟻走完一圈需要[Math Processing Error]的時間。首先，還是像上面的討論那樣假設每個螞蟻都馱著一袋糧食。那么，經過[Math Processing Error]時間后所有糧食都回到了原來的位置。由于每袋糧食都對應一個螞蟻，而螞蟻每次碰撞都會調頭，因此螞蟻的相對位置是不變的，這就說明經過 [Math Processing Error]時間后螞蟻循環(huán)移動了。假設移動了[Math Processing Error]個位置，即每個螞蟻都到達它往右第[Math Processing Error]個螞蟻的初始位置，那么，類似地，再經過[Math Processing Error]時間，當前狀態(tài)仍會循環(huán)移動[Math Processing Error]個位置。容易看出這是一個最小公倍數問題：循環(huán)移動多少個[Math Processing Error]次之后每個螞蟻回到自己位置？答案為[Math Processing Error]，于是最多經過[Math Processing Error]時間，每個螞蟻都至少回到原地一次。
除了以上幾個擴展，還有一些個人認為比較變態(tài)的擴展，有的沒空仔細想，有的暫時沒想到解法，也列出如下，歡迎拍磚：
另外，趙牛同學又提出了一些更bt的擴展，如下：
?
轉載于:https://www.cnblogs.com/tuanzang/archive/2013/02/27/2935886.html
總結
以上是生活随笔為你收集整理的和吴昊一起玩推理 Round 2 —— 蚂蚁爬杆问题的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Visual studio 2012
- 下一篇： 转：c#委托事件实现窗体传值通信