题目:标题:猜字母
把abcd...s共19个字母组成的序列重复拼接106次,得到长度为2014的串。
接下来删除第1个字母(即开头的字母a),以及第3个,第5个等所有奇数位置的字母。
得到的新串再进行删除奇数位置字母的动作。如此下去,最后只剩下一个字母,请写出该字母。
/-----------------------------------
从百度知道查看但是不懂 1024 和他的思维
求大神解惑
/-----------------------------------
就是第1024位置的字母"q"
第一次留下的是2的倍数,第二次留下的是4的倍数,第三次就是8的倍数。
代码的话,只要一句话。
return ('a' + 1024%19-1);
你是对1024的那个解释不理解吗?
我们考虑第i个元素,设: i = k * 2 ^ m (k乘以2的m次方,k是奇数,也就是把i分解成奇数乘以2的幂)。
假设m大于等于1,则i是偶数。因此,在第一次筛选中,它没有被删去。
第1次筛选后,i所在的位置应该是变成了原来的一半,即k * 2 ^ (m - 1)
如果m - 1仍然大于等于1,则i所在的位置仍然是偶数,不会被删去,筛选后,其位置为k * 2 ^ (m - 2)
以此类推,直到第m次筛选后,i所在的位置变成了k,而k是奇数。因此在第m+1次筛选时,i会被删去。
这样就很清楚了,一个数什么时候被删去,取决于它的因子里有多少个2,有最多2的,最后被删去。
而1024 = 2 ^ 10,这是含2最多的。