阿裡巴巴2014校園招聘筆試最後一道題目
題目:在黑板上寫下50個數字:1至50,在接下來的49輪操作中,每次做如下動作:選取兩個黑板上的數字a和b,擦去,在黑板上寫|b-a|。請問最後一次動作之後剩下的數字可能是什麼?為什麼?(不用寫代碼,不寫原因不得分)。
答案:1-49之間的奇數。
原因:由於這50個數當中有25個奇數,相減的過程中,奇數可能兩兩消失,也可能不消失,因此最後剩的數一定是奇數。那麼如何得到一個特定的奇數呢,以37和39為例子。
37: 以38為中樞,分成兩塊,橫線連接的兩個數兩兩相減 1 2_3 4_5 6_7 ... 36_37 38 39_40 41_42 ...49_50,得到一個序列:1,1,1……1, 38,1,1.……1,其中38前面有19個1,後面有10個1,再將相鄰的1兩兩相減,最後得到1,38,然後這兩個數相減得到37.
39:也是一樣的道理,以40為中樞,分成兩塊,前面兩兩相減可以得到20個1,後面可以得到5個1,最後得到40, 1,這兩個數相減,得到39.
對於特定的奇數X,只需要以X+1為中樞,分成兩塊,然後相鄰的數兩兩相減,全化為1,再兩兩相減,最後得到X+1和1,相減就可以得到X