資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告