阿里的一道笔试题

5、在黑板上写下50个数字:1至50.在接下来的49轮操作中,每次做如下动作:选取两个黑板上的数字a和b,擦去,在黑板上写|b - a|。请问最后一次动作之后剩下数字可能是什么?为什么?

我的解答:

  结果显然是[0, 50]内的整数,不再详述

  

  第一步:奇偶分析,证明结果不可能为偶数

    有以下三种操作:

    1. | 奇 - 偶 | = 奇

    2. | 偶 - 偶 | = 偶

    3. | 奇 - 奇 | = 偶

    也就是说每次操作减少0个或者2个奇数。

    而原有 1,3,5,…,49 共25个奇数

    所以以上操作知道剩余一个数时,此数必为奇数

  第二步:构造所有奇数的解

    首先注意到对于 a, a+1, b, b+1 四个数,在操作

    | (a+1) - a | = 1

    | (b+1) - b | = 1

    | 1 - 1 | = 0

    后,化为了0

    而0与任意数k执行以上操作 | k - 0 | = k,无影响。

    总结为自然语言就是“两个连续整数对,可以直接忽略”。

    更进一步总结为“偶数个连续整数对,可以直接忽略”。

    然后开始构造了:

      需要得到结果2k-1,其中k=1,…,25

      我们就先把1和2k拿出来,

      则余下了 2,3,4,…,2k-1, 2k+1,…50

      一共24个连续整数对,

      根据我们刚才的结论,这是可以直接忽略的。

      所以,得到了 | 2k - 1 | = 2k-1

原文地址:https://www.cnblogs.com/ksedz/p/3346294.html