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