問(wèn)題： 有n個(gè)數(shù)字，要求你在線(xiàn)的選擇其中一個(gè)最大的，在選擇第i個(gè)之前，你知道前i-1次的數(shù)字是什么，但是無(wú)法知道你將要選擇的數(shù)字和以后待選的數(shù)字的大小。
一個(gè)很自然的策略是選定一個(gè)K，先看一下前k個(gè)的大小，不做任何選擇，然后繼續(xù)看，知道遇到一個(gè)比這之前的k個(gè)人還好。可以證明k= n/e 的時(shí)候，能夠獲得最好的選擇，能夠選擇到最大的那個(gè)。證明其實(shí)是比較簡(jiǎn)單的。假設(shè)在我們的某次選擇中，選擇第i個(gè)是最優(yōu)選擇，那么很顯然第i個(gè)必須是這n個(gè)數(shù)中最大的，那么此時(shí)的概率是1/n,第二個(gè)要求是前k個(gè)數(shù)中存在這i個(gè)數(shù)中次大的數(shù)，否則是不會(huì)選擇第i個(gè)的。此時(shí)的概率是k/i-1，所以把第k個(gè)到第n個(gè)累加起來(lái)就OK了，然后取得次數(shù)的最大數(shù),可以計(jì)算獲得k=n/e。
很顯然這個(gè)問(wèn)題是一個(gè)在線(xiàn)算法的問(wèn)題，無(wú)法預(yù)知之后的情況，邊輸入邊進(jìn)行處理。而離線(xiàn)算法是要求當(dāng)輸入完成之后，然后進(jìn)行輸出。 在線(xiàn)算法的目的就是能夠達(dá)到離線(xiàn)算法的一樣好的效果。
題目來(lái)源：
http://zhiqiang.org/blog/science/tcs-classroom-notes-the-best-dating-strategy.html
http://www.cnblogs.com/fll/archive/2008/06/01/1211569.html