多米诺骨牌 - 每天一道算法题 - SegmentFault
100张多米诺骨牌整齐地排成一列，按顺序编号为1、2、3、4……99、100。第一次拿走所有的奇数位置上的骨牌，第二次再从剩余的骨牌中拿走所有奇数位置上的骨牌，依次类推，请问最后剩下的一张骨牌的编号是多少（）
A.48
B.50
C.52
D.64
正确答案:D.
答对了吗？答对了吗？答对了吗？
来一波解析给大家吧：
第一次拿走多米诺骨牌我们剩下：2,4,6,8,10...均为2的倍数。
第二次拿走多米诺骨牌我们剩下4,8,12,16....均为4的倍数。
第三次拿走多米诺骨牌我们剩下，8,16,24...均为8的倍数。
那么聪明的我们发现了规律：每次剩下的都是2的n次方的倍数。2的n次方小于100的最大值是什么？
2的6次方，也就是64，所以选择答案D。
换种直观的方法：
我们不考虑什么剩下的数究竟是多少，我们只知道剩下的数是偶数，而且个数我们是清楚的，所以就有：
第一次后剩下50个偶数
将它们除以2得到1～50的一列
第二次后剩下25个偶数 2 4 6...50
将他们除以2得到1～25的一列
第三次后剩下12个偶数 2 4 5...24
将他们除以2得到1～12的一列
同理,第四次除后到6 第五次除后到3 第六次除后剩下最后一张1
所以,它的编号是1×2^6=64
Read full article from 多米诺骨牌 - 每天一道算法题 - SegmentFault
No comments:
Post a Comment