Magic Index；及雞蛋挺住體分析
今日面試題：
給定一個(gè)數(shù)組A，其中有一個(gè)位置被稱為Magic Index，含義是：如果i是Magic Index，則A[i] = i。假設(shè)A中的元素遞增有序、且不重復(fù)，請給出方法，找到這個(gè)Magic Index。更進(jìn)一步，當(dāng)A中允許有重復(fù)的元素，該怎么辦呢？
雞蛋挺住體分析：
原題描述
兩個(gè)軟硬程度一樣但未知的雞蛋，它們有可能都在一樓就摔碎，也可能從一百層樓摔下來沒事。有座100層的建筑，要你用這兩個(gè)雞蛋通過最少的次數(shù)確定哪一層是雞蛋可以安全落下的***位置?？梢运に閮蓚€(gè)雞蛋
方法分析
看到這個(gè)題目，最保險(xiǎn)的方法就是一層一層試驗(yàn)，但這樣只需要一個(gè)雞蛋就可以了。我們現(xiàn)在有兩個(gè)雞蛋，完全可以用有更快的方法。
進(jìn)一步呢？可能試驗(yàn)的方法是二分查找，例如，***個(gè)雞蛋再50層扔下，如果碎了，第二個(gè)雞蛋從1-49逐層試驗(yàn)；如果沒碎，***個(gè)雞蛋在75層扔 下，如果碎了，第二個(gè)雞蛋從51-74逐層試驗(yàn)…但是，這個(gè)方法，很容易悲劇，例如，當(dāng)正好49層是可以安全落下的，需要嘗試50次。比只有一個(gè)雞蛋的情 況，效果還要差。
上面的分析都是從雞蛋的角度出發(fā)的，想要得到最少的嘗試次數(shù)，似乎比較難。那如果我們換個(gè)角度，從每個(gè)高度的樓層來看呢？如果，某個(gè)樓層是可以安全落下的，那么最少需要多少次嘗試呢？看下面的分析
在我們編程解決問題的過程中，如果遇到***問題的時(shí)候，往往可以先嘗試一下動(dòng)態(tài)規(guī)劃的方法。而動(dòng)態(tài)規(guī)劃的方法，首要的我們要找到構(gòu)成這個(gè)***問題的 ***子問題。所以，下面的分析，我們首先嘗試動(dòng)態(tài)規(guī)劃的方法，如何解決這個(gè)問題，這也是典型的程序員的思路；其次，在眾多的問題當(dāng)中，有不少可以直接歸結(jié) 為數(shù)學(xué)方程式，如果我們能夠?qū)懗鰯?shù)學(xué)方程式，那么，答案將是更加的簡潔、美妙。所以，第二個(gè)方法，將嘗試如果總結(jié)出數(shù)學(xué)方程式。
基于動(dòng)態(tài)規(guī)劃的方法
前面提到，若要采用動(dòng)態(tài)規(guī)劃的方法，最重要的是要找到子問題。做如下的分析，假設(shè)f{n}表示從第n層樓扔下雞蛋，沒有摔碎的最少嘗試次數(shù)。***個(gè)雞蛋，可能的落下位置(1,n),***個(gè)雞蛋從第i層扔下，有兩個(gè)情況：
-
碎了，第二個(gè)雞蛋，需要從***層開始試驗(yàn)，有i-1次機(jī)會(huì)
-
沒碎，兩個(gè)雞蛋，還有n-i層。這個(gè)就是子問題了f{n-i} 所以，當(dāng)***個(gè)雞蛋，由第i個(gè)位置落下的時(shí)候，要嘗試的次數(shù)為1 + max(i - 1, f{n - i})，那么對于每一個(gè)i，嘗試次數(shù)最少的，就是f{n}的值。狀態(tài)轉(zhuǎn)移方程如下： f{n} = min(1 + max(i - 1, f{n - 1}) ) 其中: i的范圍為(1, n), f{1} = 1 完畢。
推廣
動(dòng)態(tài)規(guī)劃的方法，可以推廣為n層樓，m個(gè)雞蛋。如下分析： 假設(shè)f{n,m}表示n層樓、m個(gè)雞蛋時(shí)找到***樓層的最少嘗試次數(shù)。當(dāng)***個(gè)雞蛋從第i層扔下，如果碎了，還剩m-1個(gè)雞蛋，為確定下面樓層中的安全樓 層，還需要f{i-1,m-1}次，找到子問題；不碎的話，上面還有n-i層，還需要f[n-i,m]次，又一個(gè)子問題。 狀態(tài)轉(zhuǎn)移方程如下： f{n, m} = min(1 + max(f{n - 1, m - 1}, f{n - i, m}) ) 其中： i為(1, n), f{i, 1} = 1
基于數(shù)學(xué)方程的方法
假設(shè)最少嘗試次數(shù)為x，那么，***個(gè)雞蛋必須要從第x層扔下，因?yàn)椋喝绻榱耍懊孢€有x - 1層樓可以嘗試，如果沒碎，后面還有x-1次機(jī)會(huì)。如果沒碎，***個(gè)雞蛋，第二次就可以從x +（x - 1）層進(jìn)行嘗試，為什么是加上x - 1，因?yàn)?，?dāng)此時(shí)，***個(gè)雞蛋碎了，第二個(gè)雞蛋還有可以從x+1 到 x + (x - 1) - 1層進(jìn)行嘗試，有x - 2次。如果還沒碎，那***個(gè)雞蛋，第三次從 x + (x - 1) + (x - 2)層嘗試。碎或者沒碎，都有x - 3次嘗試機(jī)會(huì)，依次類推。那么，x次的最少嘗試，可以確定的***的樓層是多少呢？ x + (x - 1) + (x - 2) + … + 1 = x(x+1) / 2 那反過來問，當(dāng)***樓層是100層，最少需要多少次呢？x(x+1)/2 >= 100, 得到x>=14，最少要嘗試14次。
