3.在黑板上寫下50個數(shù)字：1至50。在接下來的49輪操作中，每次做如下操作：選取兩個黑板上的數(shù)字a和b，擦去，在黑板上寫|b-a|。請問最后一次動作之后剩下的數(shù)字可能是什么?為什么?(不用寫代碼，不寫原因不得分)(阿里巴巴筆試題)

　　將題目通用化，即變成給定1..n這n個數(shù)字，操作到最后剩下的數(shù)字可能是什么。則原題即是n=50的特例。

　　首先我們有結(jié)論1：假設操作1..n，最后剩下的可能數(shù)字的個數(shù)為k，則操作1..(n+1)時，剩下數(shù)字的個數(shù)將大于等于k。這個結(jié)論簡單的用反證法證明下——假設存在n，使得操作1..n時，剩下的數(shù)字個數(shù)k，操作1..(n+1)剩下可能數(shù)字的個數(shù)為p，且k>p。則令1..n時的k個數(shù)為a[1],a[2]…a[k]，顯然它們互不相等。則1..n+1時，如果最后使用數(shù)字n+1與a[1]…a[k]做操作，得到|a[1]-(n+1)| … |a[k]-(n+1)|，此時k=p，不滿足假設，則假設不成立，原命題成立。

　　然后再來個結(jié)論2：操作1..n所有可能剩下的數(shù)字必定都小于等于n。這個顯然成立，因為對任意非負數(shù)a,b，|b-a|<=max(a,b)必定成立。

　　開始解題。

　　對于操作1..n這n個數(shù)，若只觀察它們的奇偶性，則會發(fā)現(xiàn)，當選取任意兩個數(shù)a,b做操作時，若兩個均為偶數(shù)，則結(jié)果也為偶;兩個奇數(shù)，結(jié)果為偶;一奇一偶，結(jié)果為奇。而這點跟異或完全相同，即令0代表偶數(shù)，1代表奇數(shù)，則0^0=1^1=0，0^1=1^0=1。因此，當操作1..n時，其剩下數(shù)字的奇偶性就等于1^0^1^0…^1(n為奇)/0(n為偶)，是個確定值，即剩下的數(shù)必定都為奇數(shù)或都為偶數(shù)(異或與順序無關)。進一步發(fā)現(xiàn)，當1^0^1^0…式子中1的個數(shù)為奇數(shù)時，結(jié)果為1，即剩下的數(shù)必定都為奇數(shù);1的個數(shù)為偶，結(jié)果為0，剩下的數(shù)字必定都為偶數(shù)。

　　因此我們有如下假設的結(jié)論：對于1..n，當┌n/2┐為奇數(shù)(┌n┐表示不小于n的整數(shù))時，剩下的數(shù)字為1,3,5… 2i+1(其中2*i+1為小于等于n的最大奇數(shù));當┌n/2┐為偶數(shù)時，剩下的數(shù)字為0,2,4…2*i(2*i為小于等于n的最大偶數(shù))。

　　下面用數(shù)學歸納法證明該假設。

　　1).當n=3時，可能剩下的數(shù)字為0,2，假設成立;n=4時，剩下的數(shù)字為0,2,4，假設成立;n=5時，為1,3,5，假設成立。

　　2).假設當n=k時，假設成立。即1..k時，若┌k/2┐為奇，則為1,3,5…2*i+1;┌n/2┐為偶，則為0,2,4…2*i。則現(xiàn)在需證明n=k+1時，假設仍成立。

　　3).當n=k+1時，若此時┌k/2┐為奇時，則再分為兩種情況：k為奇數(shù)，或k為偶數(shù)。當k為奇數(shù)時，1^0^1…^1=1，再異或偶數(shù)k+1，1^0=1，則此時操作1…k+1剩下的數(shù)字仍然均為奇數(shù)，再根據(jù)結(jié)論1和結(jié)論2可知，剩下數(shù)字的個數(shù)應大于等于n=k，且最大奇數(shù)不能大于偶數(shù)k+1，則唯一的可能就是1..k+1剩下的數(shù)字與1..k剩下的數(shù)字相同，此情況符合假設。當k為偶數(shù)時，1^0^…^0=1，再異或奇數(shù)k+1，1^1=0，則此時操作1..k+1剩下的數(shù)字均為偶數(shù)，但結(jié)論1,2要求其個數(shù)應該大于等于n=k時的個數(shù)，且最大數(shù)不能大于k+1，則唯一的可能就是0,2…k，此情況仍符合假設。最后┌k/2┐為偶的情況，也可根據(jù)該奇偶性和結(jié)論1,2易證得該假設成立。故n=k+1時，假設仍然成立。

　　4).最后回到題目上來，令n=50，則根據(jù)結(jié)論可知，可能剩下的數(shù)字為1,3,5…49。

　　4、已知三個升序整數(shù)數(shù)組a[l], b[m]和c[n]。請在三個數(shù)組中各找一個元素，是的組成的三元組距離最小。三元組的距離定義是：假設a[i]、b[j]和c[k]是一個三元組，那么距離為:

　　Distance = max(|a[ I ] – b[ j ]|, |a[ I ] – c[ k ]|, |b[ j ] – c[ k ]|)

　　請設計一個求最小三元組距離的最優(yōu)算法，并分析時間復雜度。

　　解：這道題目有兩個關鍵點：

　　第一個關鍵點： max{|x1-x2|,|y1-y2|} =(|x1+y1-x2-y2|+|x1-y1-(x2-y2)|)/2 --公式(1)

　　我們假設x1=a[ i ]，x2=b[ j ]，x3=c[ k ]，則

　　Distance = max(|x1 – x2|, |x1 – x3|, |x2 – x3|) = max( max(|x1 – x2|, |x1 – x3|) , |x2 – x3|) --公式(2)

　　根據(jù)公式(1)，max(|x1 – x2|, |x1 – x3|) = 1/2 ( |2x1 – x2– x3| + |x2 – x3|)，帶入公式(2)，得到

　　Distance = max( 1/2 ( |2x1 – x2– x3| + |x2 – x3|) , |x2 – x3| )

　　=1/2 * max( |2x1 – x2– x3| , |x2 – x3| ) + 1/2*|x2 – x3| //把相同部分1/2*|x2 – x3|分離出來

　　=1/2 * max( |2x1 – (x2 + x3)| , |x2 – x3| ) + 1/2*|x2 – x3| //把(x2 + x3)看成一個整體，使用公式(1)

　　=1/2 * 1/2 *((|2x1 – 2x2| + |2x1 – 2x3|) + 1/2*|x2 – x3|

　　=1/2 *|x1 – x2| + 1/2 * |x1 – x3| + 1/2*|x2 – x3|

　　=1/2 *(|x1 – x2| + |x1 – x3| + |x2 – x3|) //求出來了等價公式，完畢!

　　第二個關鍵點：如何找到(|x1 – x2| + |x1 – x3| + |x2 – x3|) 的最小值，x1，x2，x3，分別是三個數(shù)組中的任意一個數(shù)。