题目

多多的魔术盒子

输入描述:

第一行,有1个整数T,表示测试用例的组数。
(1 <= T <= 100)
接下来T行,每行1个整数N,表示有N个魔术盒子。
(1 <= N <= 1,000,000,000)

输出描述:

共T行,每行1个整数,表示要将所有盒子的球变没,最少需要进行多少次操作。

示例1

输入

3
1
2
5

输出

1
2
3

思路

由例子可以推导部分规律:

/**
   1 2
1  1 0
2  0 0


   1 2 3
1  1 0 1
2  0 0 0

   1 2 3 4
1  1 2 0 1
2  1 0 0 1
3  0 0 0 0


   1 2 3 4 5 6
1  1 2 3 0 1 2
2  1 0 1 0 1 0
3  0 0 0 0 0 0

   1 2 3 4 5 6 7 8
1  1 2 3 4 0 1 2 3
2  1 2 0 1 0 1 2 0
3  1 0 0 1 0 1 0 0
4  0 0 0 0 0 0 0 0
*/

第一次的X必然是中间数字,本例中N/2 + 1

分治算法:

  1. 分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题
  2. 解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题
  3. 合并:将各个子问题的解合并为原问题的解

我们在这里已经得到了子问题的解决方法,N/2 + 1,而分解到N = 1N = 2时候,此处为12,根据此处,可以得到代码。

代码

#include <iostream>
#include <vector>

using std::vector;
using std::cout;
using std::cin;
using std::endl;

/**
   1 2
1  1 0
2  0 0


   1 2 3
1  1 0 1
2  0 0 0

   1 2 3 4
1  1 2 0 1
2  1 0 0 1
3  0 0 0 0


   1 2 3 4 5 6
1  1 2 3 0 1 2
2  1 0 1 0 1 0
3  0 0 0 0 0 0

   1 2 3 4 5 6 7 8
1  1 2 3 4 0 1 2 3
2  1 2 0 1 0 1 2 0
3  1 0 0 1 0 1 0 0
4  0 0 0 0 0 0 0 0
*/

int cal(const int n) {
    if (n == 1 || n == 2) {
        return n;
    }
    return 1 + cal(n/2);
}


int main(int argc, char *argv[])
{
    int T{0}, N{0};
    vector<int> Nvec;           // 结果存储

    cin >> T;

    while(T-- != 0 && cin >> N) {
        cout << cal(N) << endl;
    }


    return 0;
}