หาการเคลื่อนที่น้อยที่สุดเพื่อไปถึงเป้าหมายบนเส้นอนันต์ใน C++

สมมติว่ามีตำแหน่งตัวเลขบนเส้นจำนวนอนันต์ (-inf ถึง +inf) เริ่มจาก 0 เราต้องไปถึงเป้าหมายโดยเคลื่อนที่ตามที่อธิบาย ในการเคลื่อนที่ครั้งที่ i เราสามารถไป i ขั้น ทางซ้ายหรือขวา เราต้องหาจำนวนการเคลื่อนที่น้อยที่สุดที่จำเป็น สมมติว่าเป้าหมายคือ 2 ขั้นตอนขั้นต่ำจะเป็น 3 จาก 0 ถึง 1 จาก 1 ถึง -1 และจาก -1 ถึง 2

เพื่อแก้ปัญหานี้ เรามีจุดสำคัญบางประการที่ต้องจำ หากเป้าหมายเป็นลบ ให้取เป็นบวก เพราะเส้นจำนวนเหมือนกัน สำหรับการแก้ แนวคิดคือเคลื่อนที่ในทิศทางเดียวยาวที่สุดเท่าที่จะเป็นไปได้ ดังนั้นจาก 0 ไป 1 จาก 1 ไป 3 (1 + 2) จาก 3 ไป 6 (1 + 2 + 3) และต่อไป ดังนั้นถ้าหลังการเคลื่อนที่ครั้งที่ n พบเป้าหมาย ให้คืนจำนวนการเคลื่อนที่ แต่ถ้าจุดที่พบมากกว่าเป้าหมาย เราต้องหาความต่างว่ามากกว่าเท่าไร ตอนนี้เราเห็น ถ้าเราเคลื่อนที่ขั้นที่ i ถอยหลัง ผลรวมจะเป็น (sum – 2i) ตอนนี้ถ้า sum-2i เป็นเป้าหมาย เราได้ผลลัพธ์แล้ว แต่ความต่างอาจเป็นคู่หรือคี่ สำหรับคู่ ให้คืน n เป็นผลลัพธ์ มิฉะนั้น เราไปอีกหนึ่งขั้น ดังนั้นบวก n + 1 เข้ากับ sum และตอนนี้หาความต่างอีกครั้ง หาก n + 1 เป็นเป้าหมาย ให้คืนค่า มิฉะนั้นทำอีกขั้นกับ n + 2

ตัวอย่าง

#include <iostream> 
#include <cmath> 
using namespace std; 

int minStepToTarget(int target) {
    target = abs(target);
    int sum = 0, min_step = 0;
    while (sum < target || (sum - target) % 2 != 0) {
        min_step++;
        sum += min_step;
    }
    return min_step;
}

int main() {
    int target = 11;
    cout << "Minimum step to reach the target is: " << minStepToTarget(target);
}

ผลลัพธ์

Minimum step to reach the target is: 5