这是之前遇到过的一个面试题,说实话,当时想到了开头,但没能进行下去,毕竟循环的条件和结束循环的条件并不容易找。而且要求在纸上手写代码,有点紧张,错误连篇。当他说完的那一刻,我已经在心里默默算出了答案,但似乎跟他的要求不相符,就一直没能说出来。
题目是这样的:有一根绳子,奇数长度时从一端减去1米长的一段,偶数长度时从中间剪断,你写一个程序,把这根绳子全部剪成1米长的小段,需要几刀?
刀数是显而易见的,就是绳子的长度减1,但是无法表达出如何实现这一过程,我写了开头,就没能在写下去。今天刚好在家没事,突然想起这个问题,觉得肯定能用代码描述这个过程。想了整整一个下午,都没有解决这个问题,后来我还画了这个图
想是不是将一根绳子拆分成类似一棵树会简单一些,即统计树的最底下一层的1个数就可以知道最终剪了几刀。但是用PHP实现这样一棵树,显然是把这个问题想复杂了,不应该有这么复杂的,但是递归一时半会又不知道怎么实现。