0062 玻璃珠從樓層上丢下找破碎臨界樓層（騰訊筆試題）

最近做的一道騰訊筆試題，大意是：

騰訊深圳總部大廈有39層。你手裡有兩顆一模一樣的玻璃珠。當你拿着玻璃珠在某一層往下扔的時候，一定會有兩個結果，玻璃珠碎了或者沒碎。這幢大樓有個臨界樓層。低于它的樓層，往下扔玻璃珠，玻璃珠不會碎，等于或高于它的樓層，扔下玻璃珠，玻璃珠一定會碎。玻璃珠碎了就不能再扔。現在讓你設計一種方式，使得在該方式下，最壞的情況扔的次數比其他任何方式最壞的次數都少。也就是設計一種最有效的方式。

思路：

動态規劃。設樓層N

把問題轉換為在39-N裡找臨界樓層。

假如結果都儲存在F[40]這個數組裡面，那麼：

F[N]=40-N，

F[40]=min（max（1，1+F[N-1]），max（2，1+F[N-2]），……，max（N-1，1+F[1]））;

已知狀态轉移方程，代碼就簡單了：

#include <iostream>  
using namespace std;
//gendlee 2016-9-17

#define N 40
int F[N]={0};

void Test()
{
	     int temp;
	    for (int loop1=2; loop1<N; ++loop1)
	   {
			F[loop1]=loop1;
			for (int loop2=1; loop2<N;++loop2)
		   	{
				temp= (loop2>=(1+F[loop1-loop2]))?loop2:(1+F[loop1-loop2]);
			
			if (F[loop1]>temp)
				F[loop1]=temp;
			 }

	 }
}
int main()
{
	    F[0]=0;
	    F[1]=1;
	     Test();
	     cout<<F[N-1]<<endl;
	   return 0;
}
           

結果： 9  次

那麼實際是怎樣操作這9次呢：

先從9樓開始抛第一次；如果沒碎，再從17（9+8）樓抛第二次；如果還沒碎，再從24（9+8+7）樓抛第三次；如果還沒碎，再從30（9+8+7+6）樓抛第四次；如此，每次間隔的樓層少一層。這樣，任何一次抛棋子碎時，都能確定最多抛9次可以找出臨界樓層。 

證明如下： 

1、第一次抛棋子的樓層：最優的選擇必然是間隔最大的樓層。比如，第一次如果在m層抛下棋子，以後再抛棋子時兩次樓層的間隔必然不大于m層（大家可以自己用反證法簡單證明） 

2、從第二次抛棋子的間隔樓層最優的選擇必然比第一次間隔少一層，第三次的樓層間隔比第二次間隔少一層，如此，以後每次抛棋子樓層間隔比上一次間隔少一層。（大家不妨自己證明一下） 

3、是以，設n是第一次抛棋子的最佳樓層，則n即為滿足下列不等式的最小自然數： 

  不等式如下：  1+2+3+...+(n-1)+n  >=   39 

由上式可得出  n = 9

即最優的政策是先從第9層抛下，最多抛9次肯定能找出臨界樓層。