c++代码题目描述 数轴上有一个人,设他所在的位置为 x,初始时 x=0。第 i 秒中他可以选择往左或往右跳 2^(i−1) 单位长度,即将 x 增大或减小 2^(i−1)。问他至少需要多少秒才能到达 n,即在某一秒结束的时刻使得 x=n。如果永远都不可能到达 n,那么输出 −1。 本题每个测试点中有多组数据。 输入描述 第一行,一个整数,表示数据组数 T(1<=1e3<=T)。 接下来 T 行,每行一个整数,表示一组测试数据中的 n(1<=n<=1e9)。 输出描述 共 T 行,每行一个数,依次表示每组数据的答案。 样例 输入 复制 10 1 2 7 8 9 10 11 935 101 2023 输出 复制 1 -1 3 -1 4 -1 4 10 7 11 提示 n=1 时只需要在第一秒中往右跳即可。 2n=2 时可以证明永远都不可能到达 n。
时间: 2024-04-09 18:27:33 浏览: 173
可以使用循环来逐步计算人所在的位置。首先,我们需要找到一个值 k,使得 2^(k-1) <= n < 2^k。然后,我们可以将 n 与 2^(k-1) 相减,得到剩余的距离。这个剩余的距离可以通过对剩余的距离不断除以 2,来判断在每一秒中是往左还是往右跳。如果剩余的距离为奇数,则需要额外的一秒钟往左或往右跳。
以下是使用 C++ 编写的解法:
```cpp
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
int k = log2(n) + 1;
if (n == pow(2, k - 1)) {
cout << -1 << endl; // 永远无法到达
} else {
int seconds = k - 1;
int remainingDistance = n - pow(2, k - 1);
while (remainingDistance > 0) {
if (remainingDistance % 2 == 0) {
remainingDistance /= 2;
} else {
remainingDistance = (remainingDistance - 1) / 2;
seconds++;
}
}
cout << seconds << endl;
}
}
return 0;
}
```
希望能够帮助到你!如果还有其他问题,请随时提问。