Chúng ta được cho một chuỗi nhị phân gồm 0 và 1. Cũng giả sử một người ngồi tại một vị trí hoặc điểm lưu trong current_pos. Bây giờ bắt đầu từ current_pos, nếu chuỗi nhị phân có 0 thì anh ta di chuyển một bước sang trái (current_pos - 1). Nếu là 1 thì di chuyển một bước sang phải (current_pos + 1). Mục tiêu là tìm các vị trí hoặc điểm riêng biệt anh ta đã truy cập sau khi chuỗi nhị phân hoàn thành.
Chúng ta sẽ giải quyết bằng cách sử dụng số lần một điểm được truy cập. Nếu tần suất khác 0, tăng số điểm riêng biệt.
Ví dụ
Đầu vào
Path[] = "001100" current_pos = 3
Đầu ra
Điểm riêng biệt được truy cập trên đường số: 3
Giải thích − Bắt đầu từ path[0] và vị trí 3.
Path[0]: 0 → di chuyển trái ...currpos=2 Path[1]: 0 → di chuyển trái ...currpos=1 Path[2]: 1 → di chuyển phải ...currpos=2 Path[3]: 1 → di chuyển trái ...currpos=3 Path[4]: 0 → di chuyển trái ...currpos=2 Path[5]: 0 → di chuyển trái ...currpos=1
Tổng vị trí riêng biệt là 3, là 1, 2, 3.
Đầu vào
Path[] = "010101" current_pos = 5
Đầu ra
Điểm riêng biệt được truy cập trên đường số: 2
Giải thích − Bắt đầu từ path[0] và vị trí 5.
Path[0]: 0 → di chuyển trái ...currpos=4 Path[1]: 1 → di chuyển phải ...currpos=5 Path[2]: 0 → di chuyển trái ...currpos=4 Path[3]: 1 → di chuyển phải ...currpos=5 Path[4]: 0 → di chuyển trái ...currpos=4 Path[5]: 1 → di chuyển phải ...currpos=5
Tổng vị trí riêng biệt là 2, là 4 và 5.
Phương pháp sử dụng trong chương trình dưới đây
- Chuỗi 0 và 1 được lưu trong path.
- Current_pos lưu điểm bắt đầu.
- Hàm getDistinctPoints(int current_pos, string path) nhận vị trí hiện tại và path, trả về số lượng vị trí/điểm riêng biệt.
- Biến len lưu độ dài path.
- Mảng frequency[21] lưu tần suất truy cập mỗi điểm. Chỉ số đại diện cho điểm. Tổng cộng 0-20.
- Duyệt chuỗi path.
- Nếu giá trị hiện tại là 0, di chuyển trái (current_pos - 1). Cập nhật tần suất điểm này frequency[current_pos]++.
- Ngược lại giá trị hiện tại là 1, di chuyển phải (current_pos + 1). Cập nhật tần suất điểm này frequency[current_pos]++.
- Duyệt mảng frequency và với mỗi giá trị khác 0. Tăng count.
- Count chứa số điểm truy cập riêng biệt.
- Trả về count là kết quả mong muốn.
Ví dụ mã nguồn
#include <bits/stdc++.h>
using namespace std;
// Điểm riêng biệt được truy cập giữa 0 đến 20
int getDistinctPoints(int current_pos, string path) {
// Độ dài path
int len = path.length();
int count = 0;
// Mảng lưu số lần điểm được truy cập
int frequency[21] = {0};
// Với tất cả hướng trong path
for (int i = 0; i < len; i++) {
// Hướng trái
if (path[i] == '0') {
current_pos--;
frequency[current_pos]++; // tăng số lần truy cập
}
// Hướng phải
else {
current_pos++;
frequency[current_pos]++; // tăng số lần truy cập
}
}
for (int i = 0; i < 21; i++)
if (frequency[i] != 0) // nếu đã truy cập thì frequency[i] khác 0
count++;
return count;
}
int main() {
int current_pos = 3;
string path = "011101100";
cout << "Số điểm riêng biệt được truy cập trên đường số: "
<< getDistinctPoints(current_pos, path);
return 0;
}
Kết quả
Số điểm riêng biệt được truy cập trên đường số: 5