今日面試題：

給定一個數組A，其中有一個位置被稱為Magic Index，含義是：如果i是Magic Index，則A[i] = i。假設A中的元素遞增有序、且不重復，請給出方法，找到這個Magic Index。更進一步，當A中允許有重復的元素，該怎么辦呢？

雞蛋挺住體分析：

原題描述

兩個軟硬程度一樣但未知的雞蛋，它們有可能都在一樓就摔碎，也可能從一百層樓摔下來沒事。有座100層的建筑，要你用這兩個雞蛋通過最少的次數確定哪一層是雞蛋可以安全落下的***位置。可以摔碎兩個雞蛋

方法分析

看到這個題目，最保險的方法就是一層一層試驗，但這樣只需要一個雞蛋就可以了。我們現在有兩個雞蛋，完全可以用有更快的方法。

進一步呢？可能試驗的方法是二分查找，例如，***個雞蛋再50層扔下，如果碎了，第二個雞蛋從1-49逐層試驗；如果沒碎，***個雞蛋在75層扔 下，如果碎了，第二個雞蛋從51-74逐層試驗…但是，這個方法，很容易悲劇，例如，當正好49層是可以安全落下的，需要嘗試50次。比只有一個雞蛋的情 況，效果還要差。

上面的分析都是從雞蛋的角度出發的，想要得到最少的嘗試次數，似乎比較難。那如果我們換個角度，從每個高度的樓層來看呢？如果，某個樓層是可以安全落下的，那么最少需要多少次嘗試呢？看下面的分析

在我們編程解決問題的過程中，如果遇到***問題的時候，往往可以先嘗試一下動態規劃的方法。而動態規劃的方法，首要的我們要找到構成這個***問題的 ***子問題。所以，下面的分析，我們首先嘗試動態規劃的方法，如何解決這個問題，這也是典型的程序員的思路；其次，在眾多的問題當中，有不少可以直接歸結 為數學方程式，如果我們能夠寫出數學方程式，那么，答案將是更加的簡潔、美妙。所以，第二個方法，將嘗試如果總結出數學方程式。

基于動態規劃的方法

前面提到，若要采用動態規劃的方法，最重要的是要找到子問題。做如下的分析，假設f{n}表示從第n層樓扔下雞蛋，沒有摔碎的最少嘗試次數。***個雞蛋，可能的落下位置(1,n),***個雞蛋從第i層扔下，有兩個情況：

1. 碎了，第二個雞蛋，需要從***層開始試驗，有i-1次機會

2. 沒碎，兩個雞蛋，還有n-i層。這個就是子問題了f{n-i} 所以，當***個雞蛋，由第i個位置落下的時候，要嘗試的次數為1 + max(i - 1, f{n - i})，那么對于每一個i，嘗試次數最少的，就是f{n}的值。狀態轉移方程如下： f{n} = min(1 + max(i - 1, f{n - 1}) ) 其中: i的范圍為(1, n), f{1} = 1 完畢。

推廣

動態規劃的方法，可以推廣為n層樓，m個雞蛋。如下分析： 假設f{n,m}表示n層樓、m個雞蛋時找到***樓層的最少嘗試次數。當***個雞蛋從第i層扔下，如果碎了，還剩m-1個雞蛋，為確定下面樓層中的安全樓 層，還需要f{i-1,m-1}次，找到子問題；不碎的話，上面還有n-i層，還需要f[n-i,m]次，又一個子問題。 狀態轉移方程如下： f{n, m} = min(1 + max(f{n - 1, m - 1}, f{n - i, m}) ) 其中： i為(1, n), f{i, 1} = 1

基于數學方程的方法

假設最少嘗試次數為x，那么，***個雞蛋必須要從第x層扔下，因為：如果碎了，前面還有x - 1層樓可以嘗試，如果沒碎，后面還有x-1次機會。如果沒碎，***個雞蛋，第二次就可以從x +（x - 1）層進行嘗試，為什么是加上x - 1，因為，當此時，***個雞蛋碎了，第二個雞蛋還有可以從x+1 到 x + (x - 1) - 1層進行嘗試，有x - 2次。如果還沒碎，那***個雞蛋，第三次從 x + (x - 1) + (x - 2)層嘗試。碎或者沒碎，都有x - 3次嘗試機會，依次類推。那么，x次的最少嘗試，可以確定的***的樓層是多少呢？ x + (x - 1) + (x - 2) + … + 1 = x(x+1) / 2 那反過來問，當***樓層是100層，最少需要多少次呢？x(x+1)/2 >= 100, 得到x>=14，最少要嘗試14次。

原文鏈接：http://www.ituring.com.cn/article/49818