Giả sử chúng ta có một vị trí số trong dòng số vô hạn. (-inf to + inf). Bắt đầu từ con số 0, chúng ta phải đạt được mục tiêu bằng cách di chuyển như mô tả. Trong lần di chuyển thứ i, chúng ta có thể bước sang trái hoặc phải. Chúng tôi phải tìm số lượng nước đi tối thiểu được yêu cầu. Giả sử mục tiêu là 2, vì vậy các bước tối thiểu sẽ là 3. Từ 0 đến 1, từ 1 đến -1 và từ -1 đến 2.
Để giải quyết vấn đề này, chúng ta có một số điểm quan trọng cần nhớ. Nếu mục tiêu là số âm, thì chỉ cần lấy giá trị này là số dương, vì dãy số giống hệt nhau. Để giải quyết, ý tưởng được di chuyển theo một hướng càng lâu càng tốt. Vì vậy, từ 0 chuyển thành 1, từ 1 chuyển thành 3 (1 + 2), từ 3 chuyển thành 6 (1 + 2 + 3), v.v. Vì vậy, nếu sau lần di chuyển thứ n mà mục tiêu được tìm thấy, thì chỉ cần trả lại số lần di chuyển. Nhưng nếu điểm thành lập lớn hơn mục tiêu, thì chúng ta phải tìm ra sự khác biệt giữa chúng ta đang dẫn trước bao nhiêu. Bây giờ chúng ta có thể thấy, nếu chúng ta lùi lại bước thứ i, thì tổng sẽ là (sum - 2i). Bây giờ nếu sum-2i là mục tiêu, thì chúng ta đã có kết quả. Nhưng sự khác biệt có thể là chẵn hoặc lẻ. Đối với số chẵn, trả về n là kết quả, nếu không, chúng ta thực hiện thêm một bước nữa. Vì vậy, thêm n + 1 vào tổng và bây giờ một lần nữa lấy sự khác biệt. Nếu n + 1 là đích thì quay lại, nếu không thì thực hiện thêm một bước nữa với n + 2.
Ví dụ
#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);
} Đầu ra
Minimum step to reach the target is: 5