[C++][分治算法]多多的魔术盒子

题目

多多的魔术盒子

输入描述:

第一行，有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 = 1和N = 2时候，此处为1和2，根据此处，可以得到代码。

代码

#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;
}