หาจำนวนการกระโดดเพื่อไปถึง X บนเส้นจำนวนจากศูนย์ใน C++

สมมติว่ามีจำนวนเต็ม X เราต้องหาจำนวนการกระโดดขั้นต่ำที่จำเป็นเพื่อไปถึง X จาก 0 การกระโดดครั้งแรกสามารถเป็นความยาว 1 หน่วย และการกระโดดต่อไปแต่ละครั้งจะยาวกว่าการกระโดดก่อนหน้าอย่างแน่นอน 1 หน่วย สามารถไปทางซ้ายหรือขวาได้ในแต่ละครั้ง ดังนั้นถ้า 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) โดยมีความเท่าเทียม (Parity) เหมือนกับ 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 || (sumOneToN(ans) - n) & 1)
        ans++;
    return ans;
}

int main() {
    int n = 9;
    cout << "Number of jumps: " << jumps(n);
}

ผลลัพธ์

Number of jumps: 5