2252: Pick Balls
Sherry is an excellent student of Jilin University. Today her teacher gives her a bag which is filled with M balls. She wants to pick all of them out. To make it interesting, she makes a rule as following:
Assume that the number of balls she picks last time is N,then she can only pick N, N/2 or N*2 balls this time. She can pick only one ball at the beginning. Of course, when N is equal to 1, she can not pick 0 ball this time.
Certainly she can always do that successfully no matter what value M is.But, to make it more difficult, she wants to use the fewest times to finish the task.
Could you help her? Thank you.:)
Input
There are T (T < 50000)lines in the input file.Each line there is a positive integer M (1 <= M <= 2
31-1) which indicates the total number of balls.
The end of the input will be indicated by an integer value of zero.
Output
For each integer in the input, you should print a integer in a single line which is the minimum times Sherry needs to pick these exactly M balls out.
Sample Input
2
3
8
0
Sample Output
2
2
4
hints:
2: 1 1
3: 1 2
8: 1 1 2 4
题目大意是说，给你M个球，第一次取1个，以后每次可取N,N/2,N*2个，其中N是上次取得个数。当上一次取得是1个的时候，本次不得不取，除非取球已完成。问最少多少次可取完。
首先检测最多一次能拿多少个。按等比数列增序累计。在考虑余下来的数要怎样拆分，才能达到最小。注意“以后每次可取N,N/2,N*2个，其中N是上次取得个数”，这意味着，按照我们设计得出来的数的序列，并非实际取得的顺序。我们只是把要取哪些数列出来了。