说明:一千个苹果放到10个框内,如果放置才能查出1~1000内任意数量的苹果。
解题:
现在第一个篮子里放1个苹果。
此时我们已经可以表达1了,但是表达不了2,所以在第二个篮子里放2个苹果
此时我们可以表达1,2,3,但是表达不了4,所以在第三个篮子里放4个苹果
此时我们可以表达1,2,3,4,5,6,7 但是表达不了8,所以在第四个篮子放8个苹果
。。。
可以看出规律,分别是1,2,4,8,16,32.......
细想一下原因,为什么会这样。其实和2进制转10进制原理相同。举个例子,假如按照上面的规则摆放完毕,怎么可以取出419个苹果?
首先将419转为2进制,结果为110100011,答案就是取出第1,2,6,8,9个篮子的苹果加到一起(值为1的位)。
但是如果想把10个篮子摆满要1023个,我们的苹果不够。如果只有9个篮子我们可以表示的范围是1~511。
1 <?php 2 $r = 0; 3 for ($i=0; $i<9; $i++) { 4 $r += pow(2, $i); 5 } 6 echo $r; //511 7 echo ($r + pow(2, $i)); //1023
所以第十个篮子要摆放1000 - 511 = 489个苹果。如果要表示1~511,直接从前9个篮子取就可以了;如果想要表示511~1000,需要前9个篮子取一部分再加上第10个篮子。大致区间划分:
前9个篮子:[1, 511]
全部篮子:[1, 511] ∪ [489+1, 489+511] = [1, 1000]
题外:我刚开始还以为要分别表示个位,十位,和百位 ,发现行不通