麥穗理論

　　有一天，柏拉圖問老師蘇個(gè)拉底什么是愛情?老師就讓他先到麥田里去，摘一顆全麥田里最大最金黃的麥穗來。期間只能摘一次，并且期間只能向前走，不能回頭。

　　柏拉圖于是按照老師說的去做了，結(jié)果他兩手空空的走出了田地。老師問他為什么摘不到？

　　他說：“因?yàn)橹荒苷淮危植荒茏呋仡^路，期間即使見到最大最金黃的，因?yàn)椴恢懊媸欠裼懈玫?，所以沒有摘。走到前面時(shí)，又發(fā)覺總不及之前見到的好，原來最大最金黃的麥穗早已錯(cuò)過了。于是我什么也沒有摘！”

　　老師說：這就是“愛情”。

　　之后有一天柏拉圖問他的老師什么是婚姻？老師就叫他先到樹林里，砍下一顆全樹林里最大最茂盛的，最適合放在家做圣誕樹的樹。期間同樣只能砍一次，以及同樣只能向前走，不能回頭。

　　于是柏拉圖又照著老師的話去做。今次，他帶了一顆普普通通，不是很茂盛，也不算太差的樹回來。老師問他：怎么帶這顆這么普通的樹回來？他說：“有了上一次的經(jīng)驗(yàn)，當(dāng)我走到大半路程還兩手空空時(shí)，看到這顆樹也不太差，便砍了下來，免得錯(cuò)過了后，最后有什么也帶不回來。”

　　老師說：“這就是婚姻！”

數(shù)學(xué)解答

　　現(xiàn)在我們用數(shù)學(xué)的角度來討論這個(gè)問題。

　　假設(shè)我們碰到的麥穗有n個(gè)，我們用這樣的策略來選麥穗，前k個(gè)，記住一個(gè)最大的麥穗記為d（可能是重量，也可能是體積），然后k+1個(gè)開始，只要大于d的，就選擇，否則就不選擇。

　　對(duì)于某個(gè)固定的k，如果最大的麥穗出現(xiàn)在了第i個(gè)位置（k<i≤n），要想讓他有幸正好被選中，就必須得滿足前i-1個(gè)麥穗中的最好的麥穗在前k個(gè)麥穗里，這有k/(i-1)的可能。考慮所有可能的i，我們便得到了前k個(gè)麥穗作為參考，能選中最大麥穗的總概率P(k)：

　　設(shè)k/n=x，并且假設(shè)n充分大，則上述公式可以改為：

　　對(duì)-x·lnx求導(dǎo)，并令這個(gè)導(dǎo)數(shù)為0，可以解出x的最優(yōu)值，它就是歐拉研究的神秘常數(shù)的倒數(shù)——1/e。

　　所以k=n/e.

　　如果你想摘取最大的麥穗，假設(shè)有n個(gè)麥穗，你應(yīng)該先將前n/e個(gè)麥穗作為參考，然后再k+1個(gè)麥穗開始選擇比前面k個(gè)最大的麥穗即可。

e = 2.718281828459，1/e = 0.36787944117144。

其他例子：

一、一樓到十樓的每層電梯門口都放著一顆鉆石，鉆石大小不一。你乘坐電梯從一樓到十樓，每層樓電梯門都會(huì)打開一次，只能拿一次鉆石，問怎樣才能拿到最大的一顆。

答案：首先，這個(gè)題目說的，并不能完全拿到最大的鉆石。但可以保證拿到最大鉆石的概率最大。10/e = 3.67，向上取整，得4。則：前四層皆不取，只記下最大的。后面遇到的，只要比前面最大的還大，取之。即可。

二、秘書問題。在機(jī)率及博弈論上，秘書問題（類似名稱有相親問題、止步問題、見好就收問題、蘇丹的嫁妝問題、挑剔的求婚者問題等)內(nèi)容是這樣的：要聘請(qǐng)一名秘書，有n人來面試。每次面試一人，面試過后便要即時(shí)決定聘不聘他，如果當(dāng)時(shí)決定不聘他，他便不會(huì)回來。面試時(shí)總能清楚了解求職者的適合程度，并能和之前的每個(gè)人作比較。問憑什么策略，才使選得到最適合擔(dān)任秘書的人的機(jī)率最大？

實(shí)驗(yàn)證明

基本思路

數(shù)組里存放 1-100，數(shù)字越大代表男生的質(zhì)量越高，將數(shù)組隨機(jī)打亂。從樣本容量為 1 開始到 99，在每一個(gè)樣本容量里，循環(huán)執(zhí)行 10000 次算法，用計(jì)數(shù)器來計(jì)數(shù)選到最大數(shù)字的次數(shù)。

核心算法: 記錄隨機(jī)數(shù)組中最大的數(shù)和指定樣本容量中最大的數(shù)，將備選區(qū)間里的數(shù)字和樣本 容量最大的數(shù)字比較(備選區(qū)間按照順序比較)。如果備選區(qū)間內(nèi)的數(shù)字比樣本容量中最大的數(shù)字大，則選擇該數(shù)字。如果一直比樣本容量中最大的數(shù)字小，則往后順延。用計(jì)數(shù)器記錄成功選到最 優(yōu)秀數(shù)字的個(gè)數(shù)。

實(shí)驗(yàn)代碼

clear
clc
close all
num = 100;
rng default
loop = 100000;
result = zeros(1,num);
for i = 1:num-1
    for k = 1:loop
        a=randperm(num);
        [max_a,index] = max(a);
        max_1 = max(a(1:i));
        for j = i+1:num
            if max_1<a(j) 
                if j==index
                    result(i) = result(i) + 1;
                end
                break
            end
        end
    end
end
figure
plot(result)
[max_result,index_result] = max(result)

結(jié)果符合預(yù)期，100/e=36.7，四舍五入等于37，