数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究在C++中，求从零点出发到达数轴上X点所需的最小跳跃次数
假设我们有一个整数X。我们必须找到从0出发到达X所需的最小跳跃次数。第一次跳跃的长度可以是一个单位，每次后续跳跃的长度都比前一次跳跃的长度恰好长一个单位。允许在每次跳跃中向左或向右跳跃。因此，如果X = 8，则输出为4。0 → -1 → 1→ 4 → 8 是可能的步骤。
如果我们仔细观察，我们可以说
- 如果你总是向右跳跃，那么跳跃n次后，你将到达点p = 1 + 2 + 3 + … + n
- 如果我们也可以向左跳跃，在第k次跳跃时，你将到达点p – 2k。
- 如果我们仔细选择哪些跳跃向左，哪些跳跃向右，跳跃n次后，你可以到达n(n+1)/2和–(n*(n+1) / 2)之间的点，并且与n(n+1)/2具有相同的奇偶性。
示例
#include<iostream>
#include<cmath>
using namespace std;
inline int sumOneToN(int n) {
return (n * (n + 1)) / 2;
}
int jumps(int n) {
n = abs(n);
int ans = 0;
while (sumOneToN(ans) < n or (sumOneToN(ans) - n) & 1)
ans++;
return ans;
}
int main() {
int n = 9;
cout << "Number of jumps: " << jumps(n);
}输出
Number of jumps: 5
更新于: 2019年12月19日
209 次浏览
广告