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

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

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

　　然后再來(lái)個(gè)結(jié)論2：操作1..n所有可能剩下的數(shù)字必定都小于等于n。這個(gè)顯然成立，因?yàn)閷?duì)任意非負(fù)數(shù)a,b，|b-a|<=max(a,b)必定成立。

　　開(kāi)始解題。

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

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

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

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

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

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

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

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

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

　　請(qǐng)?jiān)O(shè)計(jì)一個(gè)求最小三元組距離的最優(yōu)算法，并分析時(shí)間復(fù)雜度。

　　解：這道題目有兩個(gè)關(guān)鍵點(diǎn)：

　　第一個(gè)關(guān)鍵點(diǎn)： max{|x1-x2|,|y1-y2|} =(|x1+y1-x2-y2|+|x1-y1-(x2-y2)|)/2 --公式(1)

　　我們假設(shè)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|分離出來(lái)

　　=1/2 * max( |2x1 – (x2 + x3)| , |x2 – x3| ) + 1/2*|x2 – x3| //把(x2 + x3)看成一個(gè)整體，使用公式(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|) //求出來(lái)了等價(jià)公式，完畢!

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