Tìm số lần nhảy để đến X trong dòng số từ 0 trong C ++

Giả sử chúng ta có một số nguyên X. Chúng ta phải tìm số lần nhảy tối thiểu cần thiết để đạt được X từ 0. Bước nhảy đầu tiên được thực hiện có thể dài một đơn vị và mỗi bước nhảy kế tiếp sẽ dài hơn bước nhảy trước đó một đơn vị. Nó được phép đi sang trái hoặc phải trong mỗi lần nhảy. Vì vậy, nếu X =8, thì sản lượng là 4. 0 → -1 → 1 → 4 → 8 là các giai đoạn có thể xảy ra.

Nếu quan sát kỹ, chúng ta có thể nói rằng

• Nếu bạn luôn nhảy đúng hướng, thì sau n lần nhảy, bạn sẽ ở điểm p =1 + 2 + 3 +… + n
• Nếu chúng ta cũng có thể nhảy sang trái thì ở lần nhảy thứ k, bạn sẽ ở điểm p - 2k.
• Nếu chúng ta chọn cẩn thận bước nhảy nào sang trái và bước nhảy nào sang phải, sau n lần nhảy, bạn có thể ở giữa n (n + 1) / 2 và - (n * (n + 1) / 2 ), với cùng độ chẵn lẻ là n (n + 1) / 2.

Ví dụ

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

Đầu ra

Number of jumps: 5