题目
输入描述:
第一行,有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
。
分治算法:
- 分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题
- 解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题
- 合并:将各个子问题的解合并为原问题的解
我们在这里已经得到了子问题的解决方法,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; }