這篇文章主要講解了“Magic Index舉例分析”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“Magic Index舉例分析”吧！

目前成都創(chuàng)新互聯(lián)公司已為近1000家的企業(yè)提供了網(wǎng)站建設(shè)、域名、網(wǎng)絡(luò)空間、網(wǎng)站托管運(yùn)營(yíng)、企業(yè)網(wǎng)站設(shè)計(jì)、阿克蘇網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長(zhǎng)，共同發(fā)展。

面試題：

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

雞蛋挺住體分析：

原題描述

兩個(gè)軟硬程度一樣但未知的雞蛋，它們有可能都在一樓就摔碎，也可能從一百層樓摔下來(lái)沒(méi)事。有座100層的建筑，要你用這兩個(gè)雞蛋通過(guò)最少的次數(shù)確定哪一層是雞蛋可以安全落下的***位置?？梢运に閮蓚€(gè)雞蛋

方法分析

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

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

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

在我們編程解決問(wèn)題的過(guò)程中，如果遇到***問(wèn)題的時(shí)候，往往可以先嘗試一下動(dòng)態(tài)規(guī)劃的方法。而動(dòng)態(tài)規(guī)劃的方法，首要的我們要找到構(gòu)成這個(gè)***問(wèn)題的 ***子問(wèn)題。所以，下面的分析，我們首先嘗試動(dòng)態(tài)規(guī)劃的方法，如何解決這個(gè)問(wèn)題，這也是典型的程序員的思路；其次，在眾多的問(wèn)題當(dāng)中，有不少可以直接歸結(jié) 為數(shù)學(xué)方程式，如果我們能夠?qū)懗鰯?shù)學(xué)方程式，那么，答案將是更加的簡(jiǎn)潔、美妙。所以，第二個(gè)方法，將嘗試如果總結(jié)出數(shù)學(xué)方程式。

基于動(dòng)態(tài)規(guī)劃的方法

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

1. 碎了，第二個(gè)雞蛋，需要從***層開(kāi)始試驗(yàn)，有i-1次機(jī)會(huì)

2. 沒(méi)碎，兩個(gè)雞蛋，還有n-i層。這個(gè)就是子問(wèn)題了f{n-i} 所以，當(dāng)***個(gè)雞蛋，由第i個(gè)位置落下的時(shí)候，要嘗試的次數(shù)為1 +  max(i - 1, f{n - i})，那么對(duì)于每一個(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}次，找到子問(wèn)題；不碎的話，上面還有n-i層，還需要f[n-i,m]次，又一個(gè)子問(wèn)題。 狀態(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層樓可以嘗試，如果沒(méi)碎，后面還有x-1次機(jī)會(huì)。如果沒(méi)碎，***個(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次。如果還沒(méi)碎，那***個(gè)雞蛋，第三次從 x + (x - 1) + (x - 2)層嘗試。碎或者沒(méi)碎，都有x -  3次嘗試機(jī)會(huì)，依次類推。那么，x次的最少嘗試，可以確定的***的樓層是多少呢？ x + (x - 1) + (x - 2) + … + 1 =  x(x+1) / 2 那反過(guò)來(lái)問(wèn)，當(dāng)***樓層是100層，最少需要多少次呢？x(x+1)/2 >= 100,  得到x>=14，最少要嘗試14次。

感謝各位的閱讀，以上就是“Magic Index舉例分析”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)Magic Index舉例分析這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！