強盜時演算法

① 10個智力題

1、一個人在林中散步時，無意中聽到了幾個強盜在商量如何分贓。強盜們說，如果每人分6匹布，則剩餘5匹；如果每人分7匹布，則少8匹。請問：共有幾個強盜，幾匹布。

解析：這類問題就是我國數學史上有名的盈虧問題。它有一個固定的公式：(盈+虧)/分差=人數(單位數)。所以，這道題的演算法就是：

強盜人數=(8+5)/(7—6)=13

布匹數=13×6+5=83

2、有四數，取其每三個而相加，則其和分別為22、24、27 和20。求這四個數各是多少。

解析：如果設其中某個數為X，則其他三個數很難用X的式子表示出來。設四個數之和為X，則這四個數分別為X-22、X-24、X-27和X-20。

列方程：(X-22)+(X-24)+(X-27)+(X-20)=X

解得： X=31

31-22=9，31-24=7，31-27=4，31-20=11

即這四個數分別為9、7、4、11。

3、小王用600元買了一匹馬，700元賣出，又用800元買回此馬，900元賣出。小王一共賺了多少錢？還是虧了多少錢？

解析：整體收入是，第一次賣700元，第二次賣900元，整體收入即700+900＝1600元。整體支出是，第一次買馬花600元，第二次買馬花800元，整體支出是600+800＝1400元。小王的這次純收入是：1600-1400＝200元，也就是說，小王這次買賣共賺了200元錢。

4、一人花8元買一隻雞，又以9元賣出，又花10元買回，再次以11元賣出，這個人是虧了還是賺了？

解析：把買進看作負，賣出看作正，可以用以下的方式來記錄：

花8元買只雞：記作-8；

以9元賣出去：記作+9；

再花10元買回來：記作-10；

再以11元在賣出去：記作+11；

把以上的數相加能得出答案為2元。

5、甲、乙、丙，一位是山東人，一位是河南人，一位是湖北人，現在只知道：丙比湖北人年齡大，甲和河南人不同歲，河南人比乙年齡小，由此可以推知（）：

A：甲不是湖北人 B：河南人比甲年齡大 C：湖北人年齡最小 D：河南人比山東人年齡小

解析：甲跟河南人不同歲，證明甲不是河南人。河南人比乙小，證明乙不是河南人。所以丙是河南人。丙比湖北人大，丙是河南人，而乙比河南人大，所以乙不是湖北人，甲是湖北人，而且最小。所以答案是C。

② 5個強盜分500塊金子

我看到過一個相同的問題：
有5個海盜分100金幣,寫了5張紙條,分別寫了1~5五個數,然後抓鬮,抓到1就先提出分錢方案,如果有超過一半的人不同意,那麼他就會被殺掉,然後抓到2的人提出...請問最後分的結果和他們的方案?
而這個問題應該跟你的這個問題答案一樣,答案如下：
很古老的數學問題啊，其實也算一個邏輯問題，如果你 搜索下「強盜分金」就可以找到很多網頁，現將一份答案提供如下 （其實 是擴展命題的推理，有興趣自己試試？）：
10名海盜搶得了窖藏的100塊金子，並打算瓜分這些戰利品。這是一些講民主的海盜（當然是他們自己特有的民主），他們的習慣是按下面的方式進行分配：最厲害的一名海盜提出分配方案，然後所有的海盜（包括提出方案者本人）就此方案進行表決。如果50%或更多的海盜贊同此方案，此方案就獲得通過並據此分配戰利品。否則提出方案的海盜將被扔到海里，然後下一提名最厲害的海盜又重復上述過程。
所有的海盜都樂於看到他們的一位同夥被扔進海里，不過，如果讓他們選擇的話，他們還是寧可得一筆現金。他們當然也不願意自己被扔到海里。所有的海盜都是有理性的，而且知道其他的海盜也是有理性的。此外，沒有兩名海盜是同等厲害的——這些海盜按照完全由上到下的等級排好了座次，並且每個人都清楚自己和其他所有人的等級。這些金塊不能再分，也不允許幾名海盜共有金塊，因為任何海盜都不相信他的同夥會遵守關於共享金塊的安排。這是一夥每人都只為自己打算的海盜。
最凶的一名海盜應當提出什麼樣的分配方案才能使他獲得最多的金子呢？
為方便起見，我們按照這些海盜的怯懦程度來給他們編號。最怯懦的海盜為1號海盜，次怯懦的海盜為2號海盜，如此類推。這樣最厲害的海盜就應當得到最大的編號，而方案的提出就將倒過來從上至下地進行。
分析所有這類策略游戲的奧妙就在於應當從結尾出發倒推回去。游戲結束時，你容易知道何種決策有利而何種決策不利。確定了這一點後，你就可以把它用到倒數第2次決策上，如此類推。如果從游戲的開頭出發進行分析，那是走不了多遠的。其原因在於，所有的戰略決策都是要確定：「如果我這樣做，那麼下一個人會怎樣做？」因此在你以下海盜所做的決定對你來說是重要的，而在你之前的海盜所做的決定並不重要，因為你反正對這些決定也無能為力了。
記住了這一點，就可以知道我們的出發點應當是游戲進行到只剩兩名海盜——即1號和2號——的時候。這時最厲害的海盜是2號，而他的最佳分配方案是一目瞭然的：100塊金子全歸他一人所有，1號海盜什麼也得不到。由於他自己肯定為這個方案投贊成票，這樣就佔了總數的50%，因此方案獲得通過。
現在加上3號海盜。1號海盜知道，如果3號的方案被否決，那麼最後將只剩2個海盜，而1號將肯定一無所獲——此外，3號也明白1號了解這一形勢。因此，只要3號的分配方案給1號一點甜頭使他不至於空手而歸，那麼不論3號提出什麼樣的分配方案，1號都將投贊成票。因此3號需要分出盡可能少的一點金子來賄賂1號海盜，這樣就有了下面的分配方案：3號海盜分得99塊金子，2號海盜一無所獲，1號海盜得1塊金子。
4號海盜的策略也差不多。他需要有50%的支持票，因此同3號一樣也需再找一人做同黨。他可以給同黨的最低賄賂是1塊金子，而他可以用這塊金子來收買2號海盜。因為如果4號被否決而3號得以通過，則2號將一文不名。因此，4號的分配方案應是：99塊金子歸自己，3號一塊也得不到，2號得1塊金子，1號也是一塊也得不到。

5號海盜的策略稍有不同。他需要收買另兩名海盜，因此至少得用2塊金子來賄賂，才能使自己的方案得到採納。他的分配方案應該是：98塊金子歸自己，1塊金子給3號，1塊金子給1號。
這一分析過程可以照著上述思路繼續進行下去。每個分配方案都是唯一確定的，它可以使提出該方案的海盜獲得盡可能多的金子，同時又保證該方案肯定能通過。照這一模式進行下去，10號海盜提出的方案將是96塊金子歸他所有，其他編號為偶數的海盜各得1塊金子，而編號為奇數的海盜則什麼也得不到。這就解決了10名海盜的分配難題。

Omohundro的貢獻是他把這一問題擴大到有500名海盜的情形，即500名海盜瓜分100塊金子。顯然，類似的規律依然成立——至少是在一定范圍內成立。事實上，前面所述的規律直到第200號海盜都成立。200號海盜的方案將是：從1到199號的所有奇數號的海盜都將一無所獲，而從2到198號的所有偶數號海盜將各得1塊金子，剩下的1塊金子歸200號海盜自己所有。
乍看起來，這一論證方法到200號之後將不再適用了，因為201號拿不出更多的金子來收買其他海盜。但是即使分不到金子，201號至少還希望自己不會被扔進海里，因此他可以這樣分配：給1到199號的所有奇數號海盜每人1塊金子，自己一塊也不要。
202號海盜同樣別無選擇，只能一塊金子都不要了——他必須把這100塊金子全部用來收買100名海盜，而且這100名海盜還必須是那些按照201號方案將一無所獲的人。由於這樣的海盜有101名，因此202號的方案將不再是唯一的——賄賂方案有101種。
203號海盜必須獲得102張贊成票，但他顯然沒有足夠的金子去收買101名同夥。因此，無論提出什麼樣的分配方案，他都註定會被扔到海里去喂魚。不過，盡管203號命中註定死路一條，但並不是說他在游戲進程中不起任何作用。相反，204號現在知道，203號為了能保住性命，就必須避免由他自己來提出分配方案這么一種局面，所以無論204號海盜提出什麼樣的方案，203號都一定會投贊成票。這樣204號海盜總算僥幸揀到一條命：他可以得到他自己的1票、203號的1票、以及另外100名收買的海盜的贊成票，剛好達到保命所需的50%。獲得金子的海盜，必屬於根據202號方案肯定將一無所獲的那101名海盜之列。
205號海盜的命運又如何呢？他可沒有這樣走運了。他不能指望203號和204號支持他的方案，因為如果他們投票反對205號方案，就可以幸災樂禍地看到205號被扔到海里去喂魚，而他們自己的性命卻仍然能夠保全。這樣，無論205號海盜提出什麼方案都必死無疑。206號海盜也是如此——他肯定可以得到205號的支持，但這不足以救他一命。類似地，207號海盜需要104張贊成票——除了他收買的100張贊成票以及他自己的1張贊成票之外，他還需3張贊成票才能免於一死。他可以獲得205號和206號的支持，但還差一張票卻是無論如何也弄不到了，因此207號海盜的命運也是下海喂魚。
208號又時來運轉了。他需要104張贊成票，而205、206、207號都會支持他，加上他自己一票及收買的100票，他得以過關保命。獲得他賄賂的必屬於那些根據204號方案肯定將一無所獲的人（候選人包括2到200號中所有偶數號的海盜、以及201、203、204號）。
現在可以看出一條新的、此後將一直有效的規律：那些方案能過關的海盜（他們的分配方案全都是把金子用來收買100名同夥而自己一點都得不到）相隔的距離越來越遠，而在他們之間的海盜則無論提什麼樣的方案都會被扔進海里——因此為了保命，他們必會投票支持比他們厲害的海盜提出的任何分配方案。得以避免葬身魚腹的海盜包括201、202、204、208、216、232、264、328、456號，即其號碼等於200加2的某一方冪的海盜。
現在我們來看看哪些海盜是獲得賄賂的幸運兒。分配賄賂的方法是不唯一的，其中一種方法是讓201號海盜把賄賂分給1到199號的所有奇數編號的海盜，讓202號分給2到200號的所有偶數編號的海盜，然後是讓204號賄賂奇數編號的海盜，208號賄賂偶數編號的海盜，如此類推，也就是輪流賄賂奇數編號和偶數編號的海盜。

結論是：當500名海盜運用最優策略來瓜分金子時，頭44名海盜必死無疑，而456號海盜則給從1到199號中所有奇數編號的海盜每人分1塊金子，問題就解決了。由於這些海盜所實行的那種民主制度，他們的事情就搞成了最厲害的一批海盜多半都是下海喂魚，不過有時他們也會覺得自己很幸運——雖然分不到搶來的金子，但總可以免於一死。只有最怯懦的200名海盜有可能分得一份贓物，而他們之中又只有一半的人能真正得到一塊金子，的確是怯懦者繼承財富。

出處：<強盜分金演算法及分析 >

③ 三個強盜三個商人過河 簡單的入門級別演算法

3個商人和3個強盜要過一條河,如果在河的任意一邊商人數目比強盜少,商人就會被搶劫,如何過河?

河邊有一隻小船，小船上原本無人，小船最多能坐2人，他們都不會去游泳，要保證商人不會被搶劫。

先簡化一下商人和強盜：

商人為0 強盜為X 河為-

初始情況：商人和強盜都在河的一邊，即000xxx-

操作步驟：

1商人1強盜過去 一商人回000xx-x

2強盜過去 1強盜回 000x-xx

2商人過去 1商人1強盜回 00xx-x0

2商人過去 1強盜回 xxx-000

2強盜過去 1強盜回 xx-000x

2強盜過去 完畢 -xxx000