1樓：100innovate
第二題我感覺需要用到線段樹的知識，猜測每乙個數的成本與數的大小成正比其實是乙個不合理的假設……事實上需要採取一些方法將複雜度轉化。
2樓：supersarah
沒有數學驗證，全憑感覺，最近懶得動腦......
版本一：對樣本等概率分布，對分查詢
版本二：我們把橫軸由「樣本」換成「猜測成本」，那麼，對樣本（1-n）等概率的分布，對成本不等概率了：0-1 是每單位成本比較高的，依次反比例下降....
然後我們再求解這個分布區線下的最優搜尋策略。如果無腦猜，我先看看能不能「等面積劃分」，要不行，看看是不是能變分
版本三：超出了我的知識範圍...... 但就按「等概率分布」，乙對分查詢，甲要知道對分查詢可以盡可能增加乙的策略，而乙貌似可以更換查詢的策略.....
我無腦猜情況會很複雜.....
3樓：
對於這個問題的目標，有兩個不同的解讀方法，乙個要用DP，乙個不要用DP。
#### 用DP的情況 ####
考慮1-N的情況，如果N這個數字事實上不大，但是現實中N對應的每單位事情事實上有很大的時間成本（例如只有100行程式，但是每跑一行需要十分鐘），這個時候就要另外單獨寫乙個程式算具體的策略，但是不需要考慮這個算策略的方法的複雜度。
寫了個程式，用樓下的DP公式把N在1500以內的情況算出來了：
對於大多數的N，最優起始查詢位置和N的關係畫出來是個分形函式
該函式在N/3到N/2之間搖擺。
橫軸：問題規模Ｎ 縱軸：最優起始查詢位置Ｋ
DP解出來的最優成本還是很低的，參見下圖這個線，幾乎是O(N)級別的。事實上這個問題直接用二叉樹查詢就已經有O(NlogN)了，DP給出乙個近乎O(N)的解還是很正常的。
橫軸：問題規模Ｎ 縱軸：最優期望成本
DP演算法本身的複雜度是O(N^3)，這增長也太大了，N稍微大一點的時候就不可解了（我拿matlab跑N=2000就非常慢了）
（首先是N*N的狀態格仔，然後每乙個格點內部要走n-m步迭代找最優子解法，這個加起來就有N^3的複雜度）
#### 不用DP的情況 ####
N如果大於2000的時候，DP解就顯然太慢了。
考慮scalability的話，直接改一下原本的二分演算法，或者另立更簡單的演算法，顯然比DP窮舉要更合適。
直接從1出發一直試到N，期望複雜度是 ，O(N^2)，比DP低。
從 出發二分查詢，期望複雜度是O(NlogN)
證法如下：從開始找到找到預期需要花的步驟數是 （也就是搜尋樹的高度），每一步的預期成本都是N/2（因為搜尋樹是對稱的）所以總成本在O(NlogN)
從 出發，每一步取左三分之一處的點。期望複雜度是O(NlogN)
這個也是乙個搜尋樹的結構，但是和樓上不一樣的是每一步的預期成本略低於N/2，總共花的步數略高於 ，乘起來就不知道了。。（根據DP給出的結果，這個應該會比直接二分快一點）
這兩個到底哪個快也可以蒙特卡羅程式設計算出來的。然而懶得編了＝ ＝
附算DP的Matlab函式：
N = 100;
c = zeros(N,N); %% cost function
k = zeros(N,N); %% optimal position
for i = 1:N
k(i,i) = i;
endfor n = 2:N
m = 1;
while n <= N
min_cost = inf;
min_position = m;
for t = m:n
current_cost = t;
if t > m
current_cost = current_cost + c(m,t-1)*(t-m)/(n-m+1);
endif t < n
current_cost = current_cost + c(t+1,n)*(n-t)/(n-m+1);
endif current_cost < min_cost
min_cost = current_cost;
min_position = t;
endend
c(m,n) = min_cost;
k(m,n) = min_position;
n = n+1;
m = m+1;
endend
4樓：高鴻瞻
這個是我們那邊經常喝酒時候的玩法。如果對於比較熟的同學來說，一般要結合其情況來猜，避免進坑。比如，他的手機尾號，生日，球衣號碼，寢室號等等。
文科生也只能用這種方法了不知道理科大神們有什麼好的方法。
5樓：Zero
回答一下第二個問題。
典型的Discrete Stochastic Dynamic Programming, 用Markov決策過程框架求解即可。
本來懶得打字，看見樓上匿名使用者已經把Bellman optimality equation打出來了，就再補充幾句：
設我們要求區間 [m,n] 中的最優初始猜測, i.e. optimal policy f(m,n), 以及此最優策略下得到最終結果而要付出的獎勵函式之和的期望 c(m,n), 也就是value function.
定義：狀態空間 S =
動作空間 A =
狀態轉移概率矩陣 P: (p(s'|s,a)), s∈S, s'∈S, a∈A
獎勵函式 r(a,s) = k·a(s) (因為我們要最小化此處的獎勵函式之和，獎勵函式正比於此時的guess; k為給定常數，此處不妨設 k=1)
Discount factor γ= 1, 即我們考慮的是 E[total reward function]
那麼四元組 構成了乙個Markov決策過程(MDP)。我們要求的就是c(1,100),以及最優策略 f(m,n), 1<=m假如可以證明 f(m,n) 是線性函式的話，難度會降低不少，我們可以直接待定係數求出；如果是一般情況要精確求解的話backward induction即可，其中要用到的Bellman equation樓上匿名使用者已經寫出來了，也很直白；如果複雜度太高就是各種強化學習近似演算法了。
//忙裡偷閒寫的答案，給昊神捧個場。如有錯誤請指正！
6樓：劉天任
定義 c(m,n) 為：
有乙個隨機整數 m<=x<=n。乙個演算法不知道 x。對任意整數 y，演算法可以詢問 x 是否滿足 xy，詢問的代價為 y。
在最優策略下，演算法為了得知 x 所付出的期望代價是 c(m,n)。
當 m>n 時，c(m,n) 已經沒有定義了。為了方便，當 m>n 時，令 c(m,n)=0。
於是問題大抵就是問 c(1,100) 等於多少。
對簡單的情況，當 m>n 時，c(m,n)=0；當 m=n 時，c(m,n)=0。
對稍複雜的情況，當 m
然後打個表算算吧。
已知 m<=x<=n 時，應該詢問那個元素？
如果 m=n，顯然不用詢問了。
如果 m
幾周之後會取匿的
7樓：日了個天
第二問自己給乙個答案，遞迴，存乙個向量，表示如果搜尋範圍是1-n，其預期成本是多少。然後一點點拉長這個向量。用這種方式找到最優演算法的時間複雜度是n方，因為每次向量長度加一，需時間正比於當前長度。
（但這是找到最優演算法的複雜度，不是最優演算法本身的預期成本）期待大神們給出更直接的演算法。
複雜度貌似不是n方，要維護的是乙個矩陣，從k1到k2的子列，複雜度應該是三次方…… gg思密達
一千個人在1 50中任選乙個數字。獲勝條件是 被選次數最少且數字最小。請問那個數字獲勝的機率最大。？
鄭晉明 如果1000個人都是理智的，1000個人都只能選1，然後一起獲勝。如果出現乙個其他選擇，那麼無人獲勝。即使1000個人都理智是小概率，理智的選擇也只能是1，因為1000個人都不理智且都由於某種原因選了同乙個數的概率更小。這裡的不理智也包括自己修改題目的字面意思。 遠遠近近近 被選次數最少且數...
為什麼乙個人在集體中很外向而乙個人卻很孤獨？
彩虹de曉島菌 我是這麼看這個情況的，在集體中很外向並不代表不會感覺到孤獨，這裡提到的可能是兩件事。其實不論說外向還是內向，都可能在某些場合某些時刻感覺到孤獨，更別說乙個人的時候會感到孤獨了。孤獨感似乎也是一種生命的本能，促使我們去與他人交往互動，尋求互相理解。我會想，如果在乙個人的時候感覺孤獨，不...
乙個人在寢室應該幹嘛？
小黃雞暴發戶 啊哈，我現在正在吃著石榴看著知乎回答問題，花了一早上的時間把所有作業寫完了，可以自由自在了。我有很多想做的事情，打掃衛生，整理衣物，洗衣洗鞋，看劇聽歌錄歌畫畫，讀書唱歌，做有氧運動啊，尬舞啊，睡覺。能做的事情多了去了。我就想乙個人在宿舍待著，沒有人吵我煩我，很自由。但是，我吃得有多撐，...